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 \(\alpha\) we have: \(\alpha \in \Delta\) or \(\neg \alpha \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.

\(\boxed{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\) \(\text{W = set of the well-formed formulas (wffs)}\) formed by finite sequences of elements of a countable set is countable.

Let \(\{\alpha_1, \alpha_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 \alpha_{n + 1}\), if \(\Delta_{n} \cup \alpha_{n + 1}\) is finitely satisfiable. If the set \( \Delta_{n} \cup \alpha_{n + 1}\) is not finitely satisfiable, it's defined \(\Delta_{n + 1} = \Delta_{n} \cup \neg \alpha_{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 \alpha_{n + 1}\) is finitely satisfiable, by definition it is also \(\Delta_{n + 1}\) finitely satisfiable.

If \(\Delta_{n} \cup \alpha_{n + 1}\) is not finitely satisfiable, there exists a finite subset \(J_1 \subseteq \Delta_{n}\) such that \(J_1 \cup \alpha_{n + 1}\) is not finitely satisfiable, but now \(\Delta_{n + 1} = \Delta_{n} \cup \neg \alpha_{n + 1}\), and let \(J_2\) be any finite subset of \(\Delta_{n} \cup \neg \alpha_{n + 1}\). If \(J_2 \subseteq \Delta_n\), \(J_2\) is satisfiable by induction hypothesis. If \(J_2 \not\subseteq \Delta_n\), then \(J_2 = J_3 \cup \neg \alpha_{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} (\alpha_{n + 1}) = \text{F}\) due to \(J_1 \cup \alpha_{n + 1}\) is not finitely satisfiable, therefore \(\overline{v} (\neg \alpha_{n + 1}) = \text{T}\) and hence \(v\) satisfies \(J_3 \cup \neg \alpha_{n + 1} = J_2\). It is thus proven that \(\Delta_{n + 1} = \Delta_{n} \cup \neg \alpha_{n + 1}\) is finitely satisfiable.

Let \(\displaystyle \Delta = \bigcup_{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 \(\alpha_n\), and by construction, \(\alpha_n \in \Delta\) or \(\neg \alpha_n \in \Delta\). \(\square\)

\(\boxed{2}\) Let \(C = \{ H \text{ / } \sum \subseteq H \text{ and } H \textrm{ 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 = \bigcup_{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 \(\alpha\) (wff) , we have one of two:

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

• \(\Delta \cup \{\alpha\}\) is not finitely satisfiable. Then, proceeding as in demonstration 1, it follows that \(\Delta \cup \{\neg \alpha\}\) is finitely satisfiable, and being \(\Delta \) a maximal element in \(C\), it is concluded that \( \neg \alpha \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. \(\forall \psi\) wff, we have: \(\boxed{\psi \notin \Delta \iff \neg \psi \in \Delta}\), because if \(\psi \notin \Delta\), \( \neg \psi \in \Delta\) since \(\Delta\) is complete. And, due to \(\{\psi, \neg \psi\}\) is not satisfiable, if \(\neg \psi \in \Delta\) then \(\psi \notin \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: \(\boxed{\overline{v} (\psi) = T \iff \psi \in \Delta}\), which is equivalent to \(\boxed{\overline{v} (\psi) = F \iff \psi \notin \Delta}\).

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

\(\underline{\text{ Step } \neg \text{ ) }}\) Let \(\psi = \neg \alpha\), with \(\alpha\) fulfilling the framed thesis. Then: \(\overline{v} (\neg \alpha) = T \iff \overline{v} (\alpha) = F \iff \alpha \notin \Delta \iff \neg \alpha \in \Delta\).

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

\(\Rightarrow\)) If this were not true, \(\{\alpha , \beta , \neg(\alpha \wedge \beta)\} \subseteq \Delta\) \(\Rightarrow\) \(\Delta\) is not finitely satisfiable because \(\{\alpha , \beta , \neg(\alpha \wedge \beta)\}\) is not satisfiable.

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

\(\underline{\text{ Step } \vee \text{ ) }}\) Let \(\psi = \alpha \vee \beta\), with \(\alpha\) and \(\beta\) fulfilling the framed thesis. It is easy to see that: \(\vDash \alpha \vee \beta \iff \neg(\neg \alpha \wedge \neg \beta)\). Due to the steps \(\neg\) and \(\wedge\), \(\neg \alpha\) and \(\neg \beta\) fulfill the thesis \(\Rightarrow\) \(\neg \alpha \wedge \neg \beta\) fulfill also the thesis, and therefore \(\neg(\neg \alpha \wedge \neg \beta)\) fulfill also the thesis. To abreviate \(\neg(\neg \alpha \wedge \neg \beta) = \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, \(\{\neg \gamma, \psi\} \subseteq \Delta\) or \(\{\neg \psi, \gamma\} \subseteq \Delta\),and because of \(\vDash \psi \iff \gamma\), \(\Delta\) would contain a finite subset not satisfible (Contradiction).

\(\underline{\text{ steps } \Rightarrow,\space \iff \text{ ) }}\) is tested as step \(\vee)\) taking into account that:\[\vDash (\alpha \Rightarrow \beta) \iff \neg(\alpha \wedge \neg \beta), \text{ and } \vDash (\alpha \iff \beta) \iff \neg(\alpha \wedge \neg \beta) \wedge \neg(\beta \wedge \neg \alpha)\] Therefore, the truth assessment \(v\) satisfies \(\Delta\) and \(\sum \subseteq \Delta\). \(\square\).

Corollary 1.4.5

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

---

Proof.- \( \sum \vDash \tau\) means each truth assesment satisfying \(\sum\) also satisfies \(\tau\), that is, \( \sum \vDash \tau\) \(\iff\) \(\{\sum, \neg \tau\}\) is a not satisfiable set. Applying compactness theorem, there exists a finite subset \(J \subseteq \{\sum, \neg \tau\}\) which is not satisfiable. Hence, \( J = \sum_{0} \cup \{\neg \tau\}\) or \(J = \sum_{0}\) where \(\sum_{0} \subseteq \sum\) is a finite set and therefore \(\sum_{0} \vDash \tau\). \(\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.