Mathematical Logic and Computability II (continuation)

This wiki page is a continuation of another wiki: Mathematical Logic and Computability. At the end of this chapter, I'll review both of them.

This section is not only of interest for the study of mathematical logic, but also for the ordinary one. In this chapter we will see, among other things, that Four-Color Problem (already solved,it's already a theorem) has an affirmative solution for any infinite map, if it has a solution for any finite map, which is true (we'll prove it).

Definition 1.4.1.

A set \(\sum\) of well-formed formulas is said satisfiable if there exists (is) a truth assessment \(v\) satisfying each wff of \(\sum\). It is said finitely satisfiable if any finite subset of \(\sum\) is satisfiable.

\(\sum\) satisfiable \(\Rightarrow\) \(\sum\) finitely satisfiable.

Definition 1.4.2.

A set \(\Delta\) of wffs is said complete if for each wff \(lpha\) we have: \(lpha \in \Delta\) or \( eg lpha \in \Delta\).

Lemma 1.4.3.

If a set \(\sum\) is finitely satisfiable, then there exists a set \(\Delta\) finitely satisfiable and complete, containing \(\sum\).

---

Proof.- We'll make two proofs, the second one uses Zorn's Lema.

\(oxed{1}\) The set formed by the assertion symbols is countable, that is, it is finite or there exists a bijection from the set formed by the assertion symbols to \(\mathbb{N}\), \(\Rightarrow\) \( ext{W = set of the well-formed formulas (wffs)}\) formed by finite sequences of elements of a countable set is countable.

Let \(\{lpha_1, lpha_2, ... \}\) be an enumeration of \(W\), that is, a bijective application from \(\mathbb{Z}^{+}\) to \(W\).

Let's define a sequence \(\Delta_ {0}, \Delta_{1}, \Delta_{2}, ... ,\) of sets of wffs by recursion in \(\mathbb{N}\) such that :

• \(\Delta_ {0} = \sum\).

• Known \(\Delta_{n}\), let's define \(\Delta_{n + 1} = \Delta_{n} \cup lpha_{n + 1}\), if \(\Delta_{n} \cup lpha_{n + 1}\) is finitely satisfiable. If the set \( \Delta_{n} \cup lpha_{n + 1}\) is not finitely satisfiable, it's defined \(\Delta_{n + 1} = \Delta_{n} \cup eg lpha_{n + 1}\).

By induction in \(\mathbb{N}\), \(\Delta_ {0} = \sum\) is finitely satisfiable. Let's suppose that \(\Delta_{n}\) is finitely satisfiable, then if \(\Delta_{n} \cup lpha_{n + 1}\) is finitely satisfiable, by definition it is also \(\Delta_{n + 1}\) finitely satisfiable.

if \(\Delta_{n} \cup lpha_{n + 1}\) is not finitely satisfiable, there exists a finite subset \(J_1 \subseteq \Delta_{n}\) such that \(J_1 \cup lpha_{n + 1}\) is not finitely satisfiable, but now \(\Delta_{n + 1} = \Delta_{n} \cup eg lpha_{n + 1}\), and let \(J_2\) be any finite subset of \(\Delta_{n} \cup eg lpha_{n + 1}\). If \(J_2 \subseteq \Delta_n\), \(J_2\) is satisfiable by induction hypothesis. If \(J_2 ot\subseteq \Delta_n\), then \(J_2 = J_3 \cup eg lpha_{n + 1}\), with \(J_3 \subseteq \Delta_n\). Since \(J_1 \cup J_3 \subseteq \Delta_n\) is a finite subset , it's satisfiable or finitely satisfiable , \(\Rightarrow\) there exists a truth assesssment \(v\) that satisfies \(J_1\) and \(J_3\), this implies that \(\overline{v} (lpha_{n + 1}) = ext{F}\) due to \(J_1 \cup lpha_{n + 1}\) is not finitely satisfiable, therefore \(\overline{v} ( eg lpha_{n + 1}) = ext{T}\) and hence \(v\) satisfies \(J_3 \cup eg lpha_{n + 1} = J_2\). It is thus proven that \(\Delta_{n + 1} = \Delta_{n} \cup eg lpha_{n + 1}\) is finitely satisfiable.

Let \(\displaystyle \Delta = igcup_{n \ge 0} \Delta_n\). It's clear that \(\sum = \Delta_0 \subseteq \Delta\), (\(\Delta_0 \subseteq \Delta_1 \subseteq \Delta_2, ...\)). Furthemore, \(\Delta\) is finitely satisfiable since any finite subset of \(\Delta\) is contained in some \(\Delta_n\). Finally, \(\Delta\) is complete because given a wff \(\psi\), \(\psi\) is a certain \(lpha_n\), and by construction, \(lpha_n \in \Delta\) or \( eg lpha_n \in \Delta\). \(\square\)

\(oxed{2}\) Let \(C = \{ H ext{ / } \sum \subseteq H ext{ and } H extrm{ is finitely satisfiable} \}\). This set isn't empty because \(\sum \in C\), and is partially ordered by the inclusion relation \(\subseteq\). In this ordering, each chain \( \{ H_0 \subseteq H_1 \subset , ... \}\) has an upper bound \(\displaystyle H = igcup_{j \ge 0} H_j\); effectively, \( \sum \subseteq H \) and \(H\) is finitely satisfiable because of each finite subset contained in \(H\) is contained in some \(H_n\).

Applying Zorn's lemma, there exists a maximal element \(\Delta \in C\), that is, if \(K \in C\) and \(\Delta \subseteq K \Rightarrow K = \Delta\). \(\Delta \) is a set of wffs contained in \(C\) such that \(\sum \subseteq \Delta\) and \(\Delta \) is finitely satisfiable. Furthemore, \(\Delta \) is complete, because given any \(lpha\) (wff) , we have one of two:

• \(\Delta \cup \{lpha\}\) is finitely satisfiable, then this set belongs to \(C\), and being \(\Delta \) a maximal element in \(C\), it is concluded that \(lpha \in \Delta\).

• \(\Delta \cup \{lpha\}\) is not finitely satisfiable. Then, proceeding as in demonstration 1, it follows that \(\Delta \cup \{ eg lpha\}\) is finitely satisfiable, and being \(\Delta \) a maximal element in \(C\), it is concluded that \( eg lpha \in \Delta\).

Note that this demonstration 2 is valid even if \(W\) is not a countable set. \(\square\)

Compactness Theorem 1.4.4.

If a set of wffs \(\sum\) is finitely satisfiable, then \(\sum\) is satisfiable.

---

Proof.- Due to 1.4.3., there exists \(\Delta\) (a set of wffs), such that \(\sum \subseteq \Delta\), \(\Delta\) being finitely satisfiable and complete. \(orall \psi\) wff, we have: \(oxed{\psi otin \Delta \iff eg \psi \in \Delta}\),because if \(\psi otin \Delta\), \( eg \psi \in \Delta\) since \(\Delta\) is complete. And, due to \(\{\psi, eg \psi\}\) is not satisfiable, if \( eg \psi \in \Delta\) then \(\psi otin \Delta\) because \(\Delta\) is finitely satisfiable.

Let \(v\) be a truth assessment given by, for each assertion symbol \(A\), \(v(A) = T \iff A \in \Delta\).

We are going to show, by induction on well-formed formulas, that for each \(\psi\) well-formed formula we have: \(oxed{\overline{v} (\psi) = T \iff \psi \in \Delta}\), which is equivalent to \(oxed{\overline{v} (\psi) = F \iff \psi otin \Delta}\).

\(\underline{ ext{ Step assertion symbols) }}\) It is met(fulfilled) by definition of \(v\).

\(\underline{ ext{ Step } eg ext{ ) }}\) Let \(\psi = eg lpha\), with \(lpha\) fulfilling the framed thesis. Then: \(\overline{v} ( eg lpha) = T \iff \overline{v} (lpha) = F \iff lpha otin \Delta \iff eg lpha \in \Delta\).

\(\underline{ ext{ Step } \wedge ext{ ) }}\) Let \(\psi = lpha \wedge eta\), with \(lpha\) and \(eta\) fulfilling the framed thesis. Then \(\overline{v} ( lpha \wedge eta) = T\) \(\iff\) (\(\overline{v} ( lpha) = T\) and \(\overline{v} (eta) = T\)) \(\iff\) (\(lpha \in \Delta\) and \(eta \in \Delta\)). Let's prove that: (\(lpha \in \Delta\) and \(eta \in \Delta\)) \(\iff\) \( lpha \wedge eta \in \Delta\).

\(\Rightarrow\)) If this were not true, \(\{lpha , eta , eg(lpha \wedge eta)\} \subseteq \Delta\) \(\Rightarrow\) \(\Delta\) is not finitely satisfiable because \(\{lpha , eta , eg(lpha \wedge eta)\}\) is not satisfiable.

\(\Leftarrow\)) If this were not true, \(\{ eg lpha , lpha \wedge eta\} \subseteq \Delta\) or \(\{ eg eta , lpha \wedge eta\} \subseteq \Delta\), but this is a contradiction because the two previous subsets are not satisfiable.

\(\underline{ ext{ Step } ee ext{ ) }}\) Let \(\psi = lpha ee eta\), with \(lpha\) and \(eta\) fulfilling the framed thesis. It is easy to see that: \(Dash lpha ee eta \iff eg( eg lpha \wedge eg eta)\). Due to the steps \( eg\) and \(\wedge\), \( eg lpha\) and \( eg eta\) fulfill the thesis \(\Rightarrow\) \( eg lpha \wedge eg eta\) fulfill also the thesis, and therefore \( eg( eg lpha \wedge eg eta)\) fulfill also the thesis. To abreviate \( eg( eg lpha \wedge eg eta) = \gamma\). Hence \(\overline{v} (\psi) = T \iff \overline{v} (\gamma) = T \iff \gamma \in \Delta\). Then \(\gamma \in \Delta \iff \psi \in \Delta\), on the contrary, \(\{ eg \gamma, \psi\} \subseteq \Delta\) or \(\{ eg \psi, \gamma\} \subseteq \Delta\),and because of \(Dash \psi \iff \gamma\), \(\Delta\) would contain a finite subset not satisfible (Contradiction).

\(\underline{ ext{ steps } \Rightarrow,\space \iff ext{ ) }}\) is tested as step \(ee)\) taking into account that:\[Dash (lpha \Rightarrow eta) \iff eg(lpha \wedge eg eta), ext{ and } Dash (lpha \iff eta) \iff eg(lpha \wedge eg eta) \wedge
eg(eta \wedge eg lpha)\] Therefore, the truth assessment \(v\) satisfies \(\Delta\) and \(\sum \subseteq \Delta\). \(\square\).

Corollary 1.4.5

Let \(\sum\) be a set of wffs and \( au\) a wff such that \( \sum Dash au\). Then, there exists a finite subset \(\sum_{0} \subseteq \sum\) fulfilling \(\sum_{0} Dash au\).

---

Proof.- \( \sum Dash au\) means each truth assesment satisfying \(\sum\) also satisfies \( au\), that is, \( \sum Dash au\) \(\iff\) \(\{\sum, eg au\}\) is a not satisfiable set. Applying compactness theorem, there exists a finite subset \(J \subseteq \{\sum, eg au\}\) which is not satisfiable. Hence, \( J = \sum_{0} \cup \{ eg au\}\) or \(J = \sum_{0}\) where \(\sum_{0} \subseteq \sum\) is a finite set and therefore \(\sum_{0} Dash au\). \(\square\)

We'll conclude this section with an application of the compactness theorem to the Four-Color Problem. To be continued....

Before starting (first of all), it's interesting see Bertrand Russell's Paradox and

-Russell's paradox- Russell's paradox

Let \(A = \{X ext { / } X otin X\}\), then \(A \in A \iff A otin A\).

"Semantic paradoxes" (These are not paradoxes from a certain mathematic point of view, I mean we can't use language for talking about language ).

The language of propositional logic uses metalanguage that is a mathematical language that uses ordinary language

• Epiménides states that all Cretans lie. Epimenides is a Cretan. Then Epimenides lies if and only if (\(\iff\)) Epiménides tells the truth.
• In a certain city, there is a barber who shaves all the people who do not shave themselves. Who shaves the barber?...

Note: This wiki has been truncated due to temporary limitations, the full text will be available soon.