# 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.

#### Contents

## \(\ \ \)4. Compactness

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

satisfiableif there exists (is) a truth assessment \(v\) satisfying each wff of \(\sum\). It is saidfinitely satisfiableif any finite subset of \(\sum\) is satisfiable.

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

Definition 1.4.2.A set \(\Delta\) of wffs is said

completeif 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.5Let \(\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....

## \(\ \ \)5. Deductive systems

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

**-Russell's paradox-** Russell's paradox

Let \(A = \{X \text { / } X \notin X\}\), then \(A \in A \iff A \notin 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

metalanguagethat 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?...

Definition 1.5.1.Let \(W\) be the set of wffs.

An

inference ruleis an application \(f : D \subseteq W^{n} \longrightarrow W\) (i.e, a partial internal n-ary operation), such that the image \(f(\alpha_1, ..., \alpha_n)\) doesn't depend on the order of \(\alpha_{i}\) but only on the set \(\{\alpha_1, ..., \alpha_{n}\}\).If \(\alpha = f(\alpha_1, ..., \alpha_n)\), it's said that \(\alpha\) is a

directe consequenceof the well-formed formulas \(\alpha_1, ..., \alpha_n\) by(throught) the rule \(f\).

\(f(\alpha, \alpha \Rightarrow \beta) = \beta\), \(\space \space \space \space\) \(f( \alpha \Rightarrow \beta, \alpha) = \beta\) \(\space \space \space \space\) is a binary inference rule.

Definition 1.5.2.Let \(R\) be a set of inference rules and \(\Delta\) a set of wffs (well-formed formulas). It is called a

deduction from\(\Delta\)by\(R\) to a finite sequence \(\langle \alpha_1, \alpha_2, ... , \alpha_n \rangle\) of well-formed formulas such that each \(\alpha_i\) fulfills one of two:

\(\alpha_i\) is a well formed formula of \(\Delta\).

\(\alpha_i\) is a directe consequence of the wffs \(\alpha_{{j}_{1}}, ..., \alpha_{{j}_{r}}\) prior(previous) to \(\alpha_i\) in the sequence, by a rule of \(R\).

And it is said that a wff \(\psi\) is

deductible from\(\Delta\)by\(R\), if it is the last term of a deduction from \(\Delta\) by \(R\).

Defintion 1.5.3.A

deductive (language) system\(\mathfrak{D}\) language is formed by 2 sets:

A set \(\Lambda\) of wffs, called

axiomsof \(\mathfrak{D}\) (\(\Lambda\) can be empty).A set \(R\) of inference rules, not empty.

Given \(\Gamma\) a set of well-formed formulas, we'll call

theorem from\(\Gamma\)in\(\mathfrak{D}\),to each \(\alpha\) wff that is deductible from \(\Gamma \cup \Lambda\) by \(R\). It's written: \(\Gamma \vdash_{(\mathfrak{D})} \alpha\), or simply, \(\Gamma \vdash \alpha\) when \(\mathfrak{D}\) is known. The wffs of \(\Gamma\) are calledpremisesof the theorem.

\(\underline{\text{Notable particular case}}\)

If \(\Gamma \subseteq \Lambda\), \(\Gamma \vdash \alpha\) is the same as \(\emptyset \vdash \alpha\), and frequently
it's written \(\vdash \alpha\). Such \(\alpha\) is said to be a **logical theorem** (in the system).

Theorem 1.5.4.The set \(T\) of all the theorems of a \(\Gamma\) set of wffs fulfills:

a) It contains \(\Gamma \cup \Lambda\).

b) It is closed for each one of the inference rules.

c) It is the intersection of all sets \(T_i\) of wffs that fulfill a) and b).

Proof.-Analogous to proof of the theorem 1.2.3., substituting \(B\) for \(\Gamma \cup \Lambda\), and the operations\(f\), \(g\) for the inference rules. \(\square\).

1.5.5. Induction principle for theorems of\(\Gamma\)Let \(C\) be a subset of \(T\) that satisfies a) and b) of theorem 1.5.4. Then, we have \(C = T\).

1.5.6. Consequences of the definition of theorem from\(\Gamma\).

a) Let \(\Delta\) be a set of wffs and \(\Gamma \subseteq \Delta\). Then, \(\Gamma \vdash \alpha \Rightarrow \Delta \vdash \alpha\).

b) \(\Gamma \vdash \alpha \iff\) there exists a finite subset \(\Gamma_1 \subseteq \Gamma\) such that \(\Gamma_1 \vdash \alpha\).

c)

Transitive rule:If \(\Gamma \vdash \beta_i\) for each wff of a set \(\{\beta_i\}\), and \(\{\beta_i\} \vdash \alpha\), then \(\Gamma \vdash \alpha\).

Proof.-a) and b) are trivial (obvious). For proving c), Let's indicate \(\langle \Gamma, \Lambda, R, \psi \rangle\) a deduction of \(\psi\) (any wff) from \(\Gamma \cup \Lambda\) by \(R\). Since \(\{\beta_i\} \vdash \alpha\), there exists a deduction \(\langle \beta_1, ... , \beta_{r}, \Lambda, R, \alpha \rangle\) and since \(\Gamma \vdash \beta_i\) there exist deductions \(\langle \Gamma, \Lambda, R, \beta_1 \rangle\), ... , \(\langle \Gamma, \Lambda, R, \beta_{r} \rangle\). Therefore, \(\langle \Gamma, \Lambda, R, \beta_1, ... , \Gamma, \Lambda, R, \beta_{r}, \Lambda, R, \alpha \rangle\) is a deduction of \(\alpha\) from \(\Gamma \cup \Lambda\) by \(R\). \(\square\)

## \(\ \ \)6. A basic deductive system

We know \(\{\neg, \Rightarrow\}\) is a complete system of conectives. For convenience, the set of well- formed formulas is now generated by assertion symbols( \(S\)) by(through) the operations \(E_{\neg}\) and \(E_{\Rightarrow}\). The main advantage of this language is that it shortens demostrations by induction on wffs. To justify this a bit, we are going to propose the following exercise:

Exercise: Equivalence TheoremLet \(\psi\) be a wff, \(\beta\) a subformula of \(\psi\), and \(\psi^{'}\) the wff that results from replacing in \(\psi\), \(\beta\) by \(\beta^{'}\) (a wff) . Show that if \(\beta\) and \(\beta^{'}\) are tautologically equivalent, so are \(\psi\) and \(\psi^{'}\).

Solution.-By induction on wffs twice... Let \(T\) be the set of wffs which satisfy the above property, let's see it is an inductive set.

\(\underline{\text{step Assetion symbols )}}\) If \(\psi\) is an assetion symbol, then WLOG \(\psi = A = \beta\), replacing in \(\psi\), \(\beta\) by \(\beta^{'}\) (a wff), we get \(\psi^{'} = \beta^{'}\) which is a wff. Furthemore, if \(\beta\) and \(\beta^{'}\) are tautologically equivalent, then \(\psi = \beta\) and \(\psi^{'} = \beta^{'}\) are tautologically equivalent.

\(\underline{\text{step } \neg \text{ )}}\) Suppose that \(\psi\) is a wff, \(\beta\) a subformula of \(\psi\), and \(\psi^{'}\) the expression that results from replacing in \(\psi\), \(\beta\) by a wff \(\beta^{'}\) , then \(\psi^{'}\) is a wff, and if \(\beta\) and \(\beta^{'}\) are tautologically equivalent, so are \(\psi\) and \(\psi^{'}\). What happens to \(\neg \psi\)? We have two possibilities: \[\begin{cases} \text{ a)} \neg \psi = \beta \\ \text{ b)} \neg \psi \neq \beta \end{cases}\] Case a) is obvious, i.e, replacing \(\beta = \neg \psi\) by \(\beta^{'} = \psi^{'}\), \(\psi^{'}\) is a wff, and furthemore, if \(\beta\) and \(\beta^{'}\) are tautologically equivalent, then \(\neg \psi\) and \(\psi^{'}\) are also tautologically equivalent.

In case b) \(\beta\) is a subformula of \(\psi\) and hence if \( \psi^{'}\) is a wff, then \(\neg \psi^{'}\) is also a wff, and of course,\(\psi\) and \(\psi^{'}\) are tautologically equivalent \(\iff\) \(\neg \psi\) and \(\neg \psi^{'}\) are tautologically equivalent.

\(\underline{\text{step } \alpha \text{ & } \beta \text{ )}}\) (Exercise for the reader).

If \(\alpha\) and \(\beta\) are wffs, it is established that:

- The expression \(\alpha \wedge \beta\) represents \(\neg (\alpha \Rightarrow \neg \beta).\) (They are tautologically equivalent.) See, now, exercise 1.3.1. after corollary 1.3.6.

With these conventions, any wff of the "major" language represents (and is represented by) a wff of the "minor" language, and in addition, both wffs are tautologically equivalent in the Major Language Logic. For this reason, the Logic of the minor language serves to represent the ordinary Logic, in equal measure that of the major language. \[\underline{\text{ Ordinary Logic - Formal Logic}}\] In ordinary Logic, if the premises of a deductive chain are true, the conclusion must also be true.

Translation: If \(\alpha\) is a theorem of a deduction from a set \(\Gamma \cup \Lambda\) and the premises are true for a truth asessment \(v\), then \(\overline{v} (\alpha) = T\), i. e., \(\Gamma \vdash \alpha \Rightarrow \Gamma \vDash \alpha\). This is the following Theorem 1.6.1. (Theorem of Righteousness). In addition, we are also going to see the theorem of completeness: \(\Gamma \vDash \alpha \Rightarrow \Gamma \vdash \alpha\) to explain why in Ordinary Logic, when we want to prove a theorem: \(\Gamma \vDash \alpha\), what we do is to show (demonstrate) \(\Gamma \vdash \alpha\) .

Within the attempt that the formal Logic represent the Ordinary to a certain degree, the deductive systems that are said to be

basicare defined so that the following 2 conditions are met:

a) \(\Gamma \vdash \alpha \Rightarrow \Gamma \vDash \alpha\).

b) \(\Gamma \vDash \alpha \Rightarrow \Gamma \vdash \alpha\).

A deductive system, plus \(\Gamma\) a set of wffs being not axioms,is said to be **a formal theory**... And theorems from \(\Gamma\) are said to be **theorems of the theory**.

\(\underline{\text{ A basic deductive system } \mathfrak{B}}\)

**Axioms of** \(\mathfrak{B}\), \(\quad \quad\) (\(\Lambda\))

1) \(\alpha \Rightarrow (\beta \Rightarrow \alpha)\)

2) \((\alpha \Rightarrow (\beta \Rightarrow \gamma)) \Rightarrow ((\alpha \Rightarrow \beta) \Rightarrow (\alpha \Rightarrow \gamma))\)

3) \((\neg \beta \Rightarrow \neg \alpha) \Rightarrow ((\neg \beta \Rightarrow \alpha) \Rightarrow \beta)\)

being \(\alpha\), \(\beta\) and \(\gamma\) any wffs. All these axioms are tautologies. We'll call \(\Lambda = \{\text{ axioms of } \mathfrak{B}\}\) .

**Inference rules of** \(\mathfrak{B}\)

Just only one, called "Modus Ponens" (**MP**) given by \(\langle \alpha, \alpha \Rightarrow \beta \rangle \to \beta\), being \(\alpha\), \(\beta\) any wffs.

Theorem 1.6.1.\(\underline{\text{ (Theorem of Righteousness) }}\)

Let \(\Gamma\) be a set of wffs and \(\alpha\) be a wff. Then, \(\Gamma \vdash \alpha \Rightarrow \Gamma \vDash \alpha\). In particular, if \(\alpha\) is a logical theorem, then \(\alpha\) is a tautology.

Proof.-\(\Gamma \vdash \alpha \Rightarrow\) there exists a deduction \(\langle \alpha_1, \alpha_2, ... , \alpha_{n} = \alpha \rangle \) from \(\Gamma \cup \Lambda\) byMP, such that each \(\alpha_{i}, i = 1, ... , n\) is an axiom, a premise or a directe consequence of \( \alpha_{j}, \alpha_{k}\) by (through)MPwith \(j , k < i\). Let \(v\) be a truth assessment which satisfies each premise, we have to prove that \(\overline{v} (\alpha) = T \). By induction hypothesis:

\(\overline{v} (\alpha_1) = T \) because \(\alpha_1\) is a premise or an axiom. In the first case, \(\overline{v} (\alpha_1) = T \) by hypothesis and in the second case, \(\overline{v} (\alpha_1) = T \) because \(\alpha_1\) is an axiom an all axioms are tautologies.

Let's suppose by induction hypothesis that \(\overline{v} (\alpha_i) = T \) with \(i =1, ... , r\). Now, if \(\alpha_{r + 1}\) is an axiom or a premise, we have \(\overline{v} (\alpha_{r + 1}) = T \) as in the previous step. If \(\alpha_{r + 1}\) is obtained by

MPfrom \( \alpha_{j}, \alpha_{k}\) with \(j , k \leq r \) and such that \(\alpha_k = \alpha_j \Rightarrow \alpha_{r + 1}\) since \(\overline{v} (\alpha_j) = T \) and \(\overline{v} (\alpha_k) = T \) we get \(\overline{v} (\alpha_{r + 1}) = T \). Therefore, \(\overline{v} (\alpha) = T \). \[\square\]

Lemma 1.6.2.\(\quad \vdash \alpha \Rightarrow \alpha\) being \(\alpha\) any wff.

Proof.-Let's build a deduction \(\langle \alpha_1, \alpha_2, ... , \alpha_5 \rangle\) from \(\Lambda\) by MP.

\(\alpha_1\)) \(\alpha \Rightarrow (\beta \Rightarrow \alpha)\) Axiom 1.

\(\alpha_2\)) \((\alpha \Rightarrow (\beta \Rightarrow \alpha)) \Rightarrow ((\alpha \Rightarrow \beta) \Rightarrow (\alpha \Rightarrow \alpha))\) Axiom 2.

\(\alpha_3\)) \((\alpha \Rightarrow (\gamma \Rightarrow \alpha)) \Rightarrow (\alpha \Rightarrow \alpha)\),

MP(\(\alpha_1, \alpha_2\)), and replacing \(\beta\) by \((\gamma \Rightarrow \alpha\)).\(\alpha_4\)) \(\alpha \Rightarrow (\gamma \Rightarrow \alpha)\) Axiom 1.

\(\alpha_5\)) \(\alpha \Rightarrow \alpha\),

MP(\(\alpha_3, \alpha_4\)).\[\square\]

Theorem 1.6.3.\(\underline{\text{Deduction Theorem (DT)}}\)

If \(\{\Gamma, \alpha\} \vdash \beta\), then \(\Gamma \vdash \alpha \Rightarrow \beta\)

Proof.-We'll use theorem 1.5.5.(Induction principle for theorems of \(\{\Gamma, \alpha\}\)). Let's call \(D = \{\beta \text{ / } \beta \text{ is a theorem of } \{\Gamma, \alpha\} \text{ fulfilling } \Gamma \vdash \alpha \Rightarrow \beta\}\). It suffices to prove that \(D\) contains \(\{\Gamma, \alpha\} \cup \Lambda\) and is closed (or stable) forMP.

\(\underline{\text{ step } \Gamma})\) If \(\beta \in \Gamma\), then \(\Gamma \vdash \beta\). Furthemore, \(\langle \beta, \beta \Rightarrow (\alpha \Rightarrow \beta), \alpha \Rightarrow \beta \rangle\) is a deduction of \(\alpha \Rightarrow \beta\) from \(\beta \cup \Lambda\) by

MP. Applying transitive rule (1.5.6. c)), \(\Gamma \vdash \alpha \Rightarrow \beta\)... And therefore \(\beta \in D\).\(\underline{\text{ step } \alpha})\) \(\quad \vdash \alpha \Rightarrow \alpha\) (1.6.2.) \(\Rightarrow \Gamma \vdash \alpha \Rightarrow \alpha\)... And hence \(\alpha \in D\).

\(\underline{\text{ step } \Lambda})\) . Let \(\gamma \in \Lambda\). It's clear that if \(\vdash \alpha \Rightarrow \gamma\), then \(\Gamma \vdash \alpha \Rightarrow \gamma\), but \(\langle \gamma, \gamma \Rightarrow (\alpha \Rightarrow \gamma), \alpha \Rightarrow \gamma \rangle\) is a deduction from \(\Lambda\)...

\(\underline{\text{ step MP) }}\) Suppose that \(\beta \in D\) and \(\beta \Rightarrow \gamma \in D\), then \(\{\Gamma, \alpha\} \vdash \beta\) and \(\{\Gamma, \alpha\} \vdash \beta \Rightarrow \gamma\) and since \(\{\beta, \beta \Rightarrow \gamma\} \vdash \gamma\) applying tansitive rule we have \(\{\Gamma, \alpha\} \vdash \gamma\).

On the other hand, \(\beta \in D\) and \(\beta \Rightarrow \gamma \in D\) say us \(\Gamma \vdash \alpha \Rightarrow \beta\) and \(\Gamma \vdash \alpha \Rightarrow (\beta \Rightarrow \gamma)\), but \((\alpha \Rightarrow (\beta \Rightarrow \gamma)) \Rightarrow ((\alpha \Rightarrow \beta) \Rightarrow (\alpha \Rightarrow \gamma))\) (Axiom 2) imply \(\{\alpha \Rightarrow (\beta \Rightarrow \gamma), \alpha \Rightarrow \beta \} \vdash \alpha \Rightarrow \gamma\), and applying transitive rule again we get \(\Gamma \vdash \alpha \Rightarrow \gamma\), i.e, \(\gamma \in D\) \[\square\]

Theorem 1.6.4. Reciprocal of deduction theoremIf \(\Gamma \vdash \alpha \Rightarrow \beta\), then \(\{\Gamma, \alpha\} \vdash \beta\).

Proof.-\(\Gamma \vdash \alpha \Rightarrow \beta\) imply \(\{\Gamma , \alpha\} \vdash \alpha \Rightarrow \beta\), and of course, \(\{\Gamma , \alpha\} \vdash \alpha \). On the other hand, \(\{\alpha, \alpha \Rightarrow \beta\} \vdash \beta\), and applying transitive rule again we get \(\{\Gamma, \alpha\} \vdash \beta\). \[\square\]

Corollary 1.6.5.\(\quad \forall \space \alpha, \beta, \gamma\) wffs, we have:

DT1) \(\{\alpha \Rightarrow \beta, \beta \Rightarrow \gamma\} \vdash \alpha \Rightarrow \gamma\).

DT2) \(\{\alpha \Rightarrow (\beta \Rightarrow \gamma), \beta \} \vdash \alpha \Rightarrow \gamma\).

Proof.-

DT1) Due to DT (1.6.3.), it suffices to prove that: \(\{\alpha \Rightarrow \beta, \beta \Rightarrow \gamma, \alpha\} \vdash \gamma\). (\(\langle \alpha, \alpha \Rightarrow \beta, \beta, \beta \Rightarrow \gamma, \gamma \rangle\)).

DT2) Due to DT (1.6.3.), it suffices to prove that: \(\{\alpha \Rightarrow (\beta \Rightarrow \gamma), \beta,\alpha \} \vdash \gamma\). (\(\langle \alpha, \alpha \Rightarrow (\beta \Rightarrow \gamma), \beta \Rightarrow \gamma, \beta, \gamma \rangle\)). \[\square\]

Lemma 1.6.6.\(\quad \forall \space \alpha, \beta\) wffs, we have: \(\vdash (\neg \beta \Rightarrow \neg \alpha) \Rightarrow (\alpha \Rightarrow \beta)\).

Observation.-This lemma is often used in mathematical demonstrations in all branches of mathematics.

Proof.-Due to DT, it suffices to prove that: \(\{\neg \beta \Rightarrow \neg \alpha, \alpha \} \vdash \beta\).

1.- \((\neg \beta \Rightarrow \neg \alpha) \Rightarrow ((\neg \beta \Rightarrow \alpha) \Rightarrow \beta)\) (Axiom 3).

2.- \(\neg \beta \Rightarrow \neg \alpha\) (Premise).

3.- \((\neg \beta \Rightarrow \alpha) \Rightarrow \beta\) (

MP(1, 2)).4.- \(\alpha \Rightarrow (\neg \beta \Rightarrow \alpha)\) (Axiom 1).

5.- \(\alpha\) (Premise).

6.- \(\neg \beta \Rightarrow \alpha\) (

MP(4, 5)).7.- \(\beta\) (

MP(3, 6)).\(\square\).

Definition 1.6.7.We'll call an

abbreviated deduction from\(\Gamma\) to a finite sequence \(\langle \alpha_1, ... , \alpha_n \rangle\), such that each \(\alpha_i\) satisfies one of the following 4 conditions:

\(\alpha_i\) is an axiom.

\(\alpha_i\) is a logical theorem.

\(\alpha_i\) is a wff of \(\Gamma\).

\(\alpha_i =\)

MP\((\alpha_j, \alpha_k)\) being \(j, k < i\).

Lemma 1.6.8.If \(\alpha\) is the last term of an abbreviated deduction from \(\Gamma\), \(\alpha\) is a theorem of \(\Gamma\).

Proof.-Let \(\langle \alpha_1, ... , \alpha_n = \alpha \rangle\) be such an abbreviated deduction from \(\Gamma\), and let \(\alpha_j = \psi\) a logical theorem.\( \vdash \psi\) means there exists a deduction \(\langle \ldots, \psi \rangle\) from \(\Lambda\) by

MP, then \(\langle \alpha_1, ... , \alpha_{j - 1}, ... , \psi, \alpha_{j + 1}, \alpha_n \rangle\) is an abbreviated deduction from \(\Gamma\). By doing the same with all the logical theorems of this abbreviated deduction from \(\Gamma\), we obtain a deduction of \(\alpha\) from \(\Gamma \cup \Lambda\) byMP, and therefore \(\alpha\) is a theorem of \(\Gamma\). \[\square\]

Lemma 1.6.9.\(\quad \forall \space \alpha, \beta\) wffs, \(\vdash \neg \alpha \Rightarrow (\alpha \Rightarrow \beta)\).

Proof.-Due to DT, it suffices to prove that: \(\{\neg \alpha\} \vdash \alpha \Rightarrow \beta \). Let's build an abbreviated deduction from \(\{\neg \alpha\} \)

1) \(\neg \alpha\) (Premise).

2) \(\neg \alpha \Rightarrow (\neg \beta \Rightarrow \neg \alpha)\) (Axiom 1).

3) \(\neg \beta \Rightarrow \neg \alpha\) (

MP(1, 2)).4) \((\neg \beta \Rightarrow \neg \alpha) \Rightarrow (\alpha \Rightarrow \beta)\) (logical theorem, Lemma 1.6.6.).

5) \(\alpha \Rightarrow \beta \). (

MP(3, 4)). \[\square\]

Lemma 1.6.10.\(\quad \vdash (\neg \alpha \Rightarrow \alpha) \Rightarrow \alpha, \space \forall \space \alpha\) wff.

Proof.-An abbreviated deduction:

1.- \((\neg \alpha \Rightarrow \neg \alpha) \Rightarrow ((\neg \alpha \Rightarrow \alpha) \Rightarrow \alpha)\) (Axiom 3).

2.- \(\neg \alpha \Rightarrow \neg \alpha\) (logical theorem, Lemma 1.6.2.)

3.- \((\neg \alpha \Rightarrow \alpha) \Rightarrow \alpha)\) (

MP(1, 2)) \[\square\]

Definition 1.6.11.A deductive system is said to be

inconsistentif there exists a logical theorem \(\psi\) such that \(\neg \psi\) is also a logical theorem. It is said to beconsistentif it is not inconsistent.It's said that a set of wffs \(\Delta\) is

inconsistent(in a deductive system) if there is a wff \(\alpha\) such that \(\Delta \vdash \alpha\) and \(\Delta \vdash \neg \alpha\). It is said to beconsistentif it is not inconsistent.

ExerciseOur deductive system \(\mathfrak{B}\) is consistent.

Solution.-(By contradiction = By reductio ad absurdum (next proposition 1.6.13.)).Let's suppose that there exists a wff \(\psi\) in our deductive system \(\mathfrak{B}\), such that \(\vdash \psi\) and \( \vdash \neg \psi\), then applying Theorem of of Righteousness (1.6.1.) we get \(\vDash \psi\) and \( \vDash \neg \psi\) (Contradiction). \(\square\)

Lemma 1.6.12.A set of wffs \(\Delta\) is inconsistent \(\iff\) \(\Delta \vdash \beta, \space \forall \space \beta\) wff.

Proof.-\(\Leftarrow\)) If \(\beta\) is a wff, then \(\neg \beta\) is also other wff, and hence \(\Delta\) is inconsistent.\(\Rightarrow\)) If \(\Delta\) is inconsistent (in a deductive system) there is a wff \(\alpha\) such that \(\Delta \vdash \alpha\) and \(\Delta \vdash \neg \alpha\). Furthemore, \( \neg \alpha \Rightarrow (\alpha \Rightarrow \beta)\) (1.6.9) is a logical theorem, and applying the reciprocal of deduction theorem (1.6:4.) \(\{\neg \alpha, \alpha\} \vdash \beta\) and transitive rule, we get \(\Delta \vdash \beta, \space \forall \space \beta\) wff. \(\square\)

1.6.13. Reductio ad absurdum (RAA)\(\{\Delta, \neg \alpha\}\) is inconsistent \(\iff\) \(\Delta \vdash \alpha\).

Proof.-\(\Leftarrow\)) \(\{\Delta, \neg \alpha\} \vdash \neg \alpha\),and \(\{\Delta, \neg \alpha\} \vdash \alpha\), so \(\{\Delta, \neg \alpha\}\) is inconsistent.\(\Rightarrow\)) Due to previous lemma , \(\{\Delta, \neg \alpha\} \vdash \alpha\) and because of DT \(\Delta \vdash \neg \alpha \Rightarrow \alpha\). Furthemore, 1.6.10. and reciprocal of DT says us \( \neg \alpha \Rightarrow \alpha \vdash \alpha\) and applying transitive rule, we get \(\Delta \vdash \alpha\)., \(\square\)

Lemma 1.6.14.If a set of wffs \(\sum\) is consistent, then there exists a set \(\Delta\) containing \(\sum\) and such that \(\Delta\) is consistent and complete.

Proof.-We'll make 2 proofs as lemma 1.4.3.(advice: see this lemma again, because the proof of this lemma is very similar to that one). \[\boxed{1}\] Let \(\{\alpha_1, ... , \alpha_n\}\) be an enumeration of the set of wffs. Let's define a sequence of sets of wffs \(\Delta_0, \Delta _1, ...\), by recursion on \(\mathbb{N}\), by the conditions:

i) \(\Delta_0 = \sum\).

ii) Suppose \(\Delta_n\) is consistent, if \(\Delta_n \cup \alpha_{n + 1}\) is consistent, \(\Delta_{n + 1} = \Delta_n \cup \alpha_{n + 1}\). If \(\Delta_n \cup \alpha_{n + 1}\) is inconsistent, then \(\Delta_{n + 1} = \Delta_n \cup \neg \alpha_{n + 1}\).

We are going to prove, by induction in \(\mathbb{N}\), that \(\Delta_i\) is consistent, \(\forall i \in \mathbb{N}\):

Step \(0\)) \(\Delta_0 = \sum\) is consistent.

Step \(n + 1\)) If \(\Delta_{n}\) is consistent, then if \(\Delta_{n} \cup \alpha_{n +1}\) is also consistent, \(\Delta_{n + 1} =\Delta_{n} \cup \alpha_{n +1} \) is consistent.

If \(\Delta_{n + 1} =\Delta_{n} \cup \alpha_{n +1} \) is inconsistent, then \(\Delta_{n + 1} =\Delta_{n} \cup \neg \alpha_{n +1} \) is consistent. Why? By RAA, if \(\Delta_{n + 1} =\Delta_{n} \cup \neg \alpha_{n +1} \) was inconsistent, \(\Delta_{n} \vdash \alpha_{n +1} \), but because of \(\{\Delta_{n}, \alpha_{n +1}\} \) is inconsistent, \(\{\Delta_{n}, \alpha_{n +1}\} \vdash \neg \alpha_{n +1} \). By TD: \(\Delta_{n} \vdash \alpha_{n +1} \Rightarrow \neg \alpha_{n +1} \). Applying the transitive rule together with: \( \{\alpha_{n +1}, \alpha_{n +1} \Rightarrow \neg \alpha_{n +1}\} \vdash \neg \alpha_{n + 1} \) we would get \(\Delta_{n} \vdash \neg \alpha_{n +1}\) and this would imply \(\Delta_{n}\) is inconsistent, and this is a contradiction with the supposed.

Let \(\Delta \) be \(\displaystyle \Delta = \cup_{n \ge 0} \space \Delta_{n} \). It's clear that \(\sum = \Delta_{0}\). Furthemore, \(\Delta \) is consistent, because if \(\Delta \vdash \beta\) and \(\Delta \vdash \neg \beta\) for a wff \(\beta\),we would get \(\Delta^{'} \vdash \beta\) and \(\Delta^{''} \vdash \neg \beta\) being \(\Delta^{'}\) and \(\Delta^{''}\) are finite subsets of \(\Delta\), and this implies that \(\Delta^{'} \cup \Delta^{''}\) is a finite subset of \(\Delta\) and therefore \(\Delta^{'} \cup \Delta^{''}\) is contained in a subset \(\Delta_{n}\) and then \(\Delta_{n}\) would be inconsistent (Contradiction). And it's clear that \(\Delta\) is complete. \[\boxed{2}\] Apply Zorn's Lemma to the set \( C = \{H \text{ / } \sum \subseteq H \text{ and } H \text{ is consistent }\}\) ordered by \(\subseteq\) with arguments from demonstration 1. \(\square\)

Proposition 1. 6.15.Let \(\Lambda\), \(\sum\), arbitrary sets of wffs, and \(\alpha\) any wff. Then are equivalent:

1) If \(\Lambda \models \alpha\), then \(\Lambda \vdash \alpha\).

2) If \(\sum \) is consistent, then \(\sum\) is satisfiable.

Proof.-1) \(\Rightarrow\) 2) If \(\sum\) is not satisfiable, then \(\sum \models \alpha\) and \(\sum \models \neg \alpha\) where \(\alpha\) is any wff, therefore applying 1) \(\sum \vdash \alpha\) and \(\sum \vdash \neg \alpha\), i. e., \(\sum \) is inconsistent. Contradiction.

2) \(\Rightarrow\) 1) If \(\Lambda \models \alpha\), then \(\{\Lambda, \neg \alpha\}\) is not satisfiable, and due to 2) \(\{\Lambda, \neg \alpha\}\) is inconsistent, and applying RAA, \(\Lambda \vdash \alpha\). \(\square\)

Exercise.-Let's suppose that \(\Delta\) is consistent and complete. Then:

a) \(\Delta \vdash \psi\) \(\iff\) \(\psi \in \Delta\).

b) \(\psi \notin \Delta\) \(\iff\) \(\neg \psi \in \Delta\)

Solution.-

a) is proved in the next theorem.

b) \(\Rightarrow \) ) A is complete.

\(\Leftarrow\) ) If \(\psi \in \Delta\) then \(\Delta\) would be inconsistent (Contradiction).

Theorem 1.6.16.\( \underline{\text{ Completion theorem }}\)

If \(\sum \models \alpha\), then \(\sum \vdash \alpha\). In particular, all tautology is a logic theorem.

Proof.-It will suffice to prove that any set of consistent wffs is satisfiable. Let \(\sum\) be a set consistent. By 1.6.14. there exists a set \(\Delta\) consistent and complete containing \(\sum\).Let's see that if \(\psi\) is a wff and \(\Delta \vdash \psi\), then \(\psi \in \Delta\). Indeed, if \(\psi \notin \Delta\), then \(\neg \psi \in \Delta\) because \(\Delta\) is complete, and hence \(\Delta \vdash \neg \psi\) and this imply that \(\Delta\) is inconsistent (contradiction).Let \(v\) be the truth assesment such that if \(A\) is an assertion symbol, \(\boxed{v \text{(A) = T } \iff A \in \Delta}\). Let's prove that, by induction in wffs, for any \(\psi\) wff: \(\boxed{v \text{(}\psi \text{) = T } \iff \psi \in \Delta}\) which is equivalent to \(\boxed{v \text{(} \psi \text{) = F } \iff \psi \notin \Delta}\). Notice that \(\psi \notin \Delta \iff \neg \psi \in \Delta\) due to \(\Delta\) is complete and consistent.

\(\underline{\text{ Step assertion symbols) }}\) 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 } \Rightarrow \text{ )}}\) Let \(\psi = \alpha \Rightarrow \beta\) with \(\alpha, \beta\) fulfilling the thesis. Then , \(\overline{v} (\alpha \Rightarrow \beta) = F\) \(\iff\) \(\overline{v} (\alpha ) = T\) and \(\overline{v} (\beta)= F\) \(\iff\) \(\alpha \in \Delta\) and \(\neg \beta \in \Delta\). It will be enough to prove: \[\alpha \in \Delta \text { and } \neg \beta \in \Delta \iff \neg (\alpha \Rightarrow \beta) \in \Delta \iff (\alpha \Rightarrow \beta) \notin \Delta\] \(\Rightarrow\)) If \(\alpha \in \Delta \text {, } \neg \beta \in \Delta \text { and } \neg (\alpha \Rightarrow \beta) \notin \Delta\), we would have \(\alpha \Rightarrow \beta \in \Delta\) due to \(\Delta\) is complete, and since \(\{\alpha, \neg \beta, \alpha \Rightarrow \beta \} \subseteq \Delta\) \(\Delta\) would be inconsistent because \(\{\alpha, \alpha \Rightarrow \beta \} \vdash \beta\) and \(\{\neg \beta\} \vdash \neg \beta\).

\(\Leftarrow\) ) If \(\neg (\alpha \Rightarrow \beta) \in \Delta \) and \(\alpha \notin \Delta\) we would have \(\neg \alpha \in \Delta\) and hence \(\Delta\) would be inconsistent, since \(\neg \alpha \vdash \alpha \Rightarrow \beta\) (Lemma 1.6.9. and reciprocal of DT) and \(\neg (\alpha \Rightarrow \beta) \vdash \neg (\alpha \Rightarrow \beta)\). And if \(\neg (\alpha \Rightarrow \beta) \in \Delta \) and \(\neg \beta \notin \Delta\) we would have \(\beta \in \Delta\) and again, \(\Delta\) would be inconsistent, since \(\beta \vdash \alpha \Rightarrow \beta\) (Axiom and reciprocal of DT) and \(\neg (\alpha \Rightarrow \beta) \vdash \neg (\alpha \Rightarrow \beta)\).

In conclusion, \(v\) satisfies each wff of \(\Delta\), and therefore, of \(\sum\). \(\square\)

## References

\(\small \textrm{References: J. Sancho San Román: Lógica Matemática y computabilidad.}\)

**Cite as:**Mathematical Logic and Computability II (continuation).

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/mathemathical-logic-and-computability-ii/