Mathematical Logic and Computability

First of all, I want to apologize for my English and the names I'm going to use on this wiki, because many of them probably have different names when written in books (Guillermo Templado). The purpose of this wiki is to study ordinary logic or natural logic, using mathematical methods or a "mathematical logic." This wiki has 3 chapters and a chapter 0:

• Chapter 0: Preliminaries (9 sections)
• Chapter 1: Logic or Calculus of Propositional Logic (6 sections)
• Chapter 2: First-order Logic (11 sections)
• Chapter 3: Computability (10 sections)

This wiki is a summary of the book by J. Sancho San Román: Lógica matemática y computabilidad. In Chapter 3, we will discuss Turing machines, Church's thesis, and Kurt Gödel's incompleteness theorem (using lambda calculus), and of course, we'll prove them. It's important to tell that we'll assume axiom of choice which is equivalent to Zorn's lemma (Chapter 0.5), though; nevertheless there exists logic without assuming this axiom in set theory. It is not necessary, but knowledge of a first course in abstract algebra or group theory would be very useful.

\(\space \space\) All chapters are connected. This wiki will be continued in another page when it be necessary.

Mathematical logic is a fundamental instrument in the construction of computers and the formation of programming languages. This wiki is going to be written thinking about people who want to know the precise concepts and fundamental rules of logic, or the reasons behind these rules. In particular, these concepts and rules will be of interest for all people working in logical programming, such as PROLOG, LISP, or expert systems of artificial intelligence.

For getting to understand this wiki, you will need a lot of time, review chapters over and over, constantly memorize, and use a lot of ordinary logic.

Mathematical logic or symbolic logic is a science whose primary task is the study of ordinary logic or natural logic with mathematical methods.   The ordinary logic or natural logic, basically, is composed of an ordinary language and sequences of sentences of said language that are called deductions. Language and deductions constitute the fundamental instrument of human mind, with which it has built all the sciences known today.

The study of anything from real life is done by creating a model of that thing. For this, some elements of the thing are taken, and some properties are chosen. Each element is represented by an ideal entity that resembles it, and the model is defined by these ideal entities that are the elements of the model, and by the chosen properties.

Can you study ordinary logic with mathematical methods? To answer this question, I will transcribe a few paragraphs of LUKASIEWICZ:

"Philosophical logic includes epistemological problems: What is the truth? Is there any criterion of truth? However, these issues do not belong to logic... If we remove from philosophical logic everything that belongs to epistemology, psychology and philosophy in general, what we have is the so-called formal logic, whose content is properly logical... There are no two logics, mathematical and philosophical, there is a single logic, founded by Aristotle, completed by the old school of the Stoics and continued, often with great subtlety, by medieval logicians, and this is the logic that develops mathematical logic."

There are 9 sections in this chapter, and there will be some theorems and examples without proof. This doesn't mean you shouldn't prove it. You always have to prove all, for a total knowledge and understanding of this wiki. This chapter has many "known" concepts of a first course in abstract algebra and the notion of cardinality and countable sets.

Any explanation of the meaning of the word "set" would use more complicated concepts than the one we are trying to define; however, we have a more or less clear notion, or sufficient coincidence, about the meaning that each person gives to this word in question. For us, a set is a well-defined collection of different objects (elements).

Relevant link: Set

• \(a \in A\) means \(a\) is an element of \(A\), i.e. \(a\) belongs to \(A\).
• \(a \notin A\) means \(a\) isn't an element of \(A\), i.e. \(a\) doesn't belong to \(A\).
• \(a = b\) means that \(a\) and \(b\) are the same thing.

For us,

• \(\mathbb{N} = \{0, 1, 2, 3, \ldots \}\)
• \(\mathbb{N}^{+} = \mathbb{Z}^{+} = \{1, 2, 3, \ldots \}\)
• \(\mathbb{Z} = \text{set of } \)integer numbers
• \(\mathbb{Q} = \text{set of } \)rational numbers
• \(\mathbb{R} = \text{set of } \) real numbers.

A "proposition" is the expression that an event occurs. If this really happens, the proposition is said to be true; if it does not, it is said to be false. If whenever a proposition \(J\) is true, another \(K\) is also true, then it is said that \(J\) implies \(K.\) In this case, \(J\) is a sufficient condition for \(K\), and \(K\) is necessary if \(J:\)

\[J \implies K. \quad ( \text{logical implication})\]

When not only \(J\) implies \(K\), but also \(K\) implies \(J\), it is said that propositions \(J\) and \(K\) are logically equivalent. Then the event of \(J\) occurs if and only if the event of \(K\) occurs:

\[ J \iff K. \quad ( \text{logical equivalence})\]

The propositions "J = Today is Tuesday" and "K = Tomorrow is Wednesday" are logically equivalent.

There exist more propositional symbols. We'll see them later. There exist 2 symbols, \(\exists\) and \(\forall\), called quantifiers that are used with the following meanings:

• "\(\exists a \in A, a \text{ satisfies } P\)" means there exists an element \(a\) belonging to the set \(A\) such that \(a\) satisfies the property \(P\).

• "\(\forall a \in A, a \text{ satisfies }P\)" means every (each) element \(a\) belonging to the set \(A\) satisfies the property \(P\).

Set \(A\) is a subset of set \(E\) if each element of \(A\) belongs to \(E\). It's written \(A \subseteq E\).

According to this, \(E \subseteq E\) but in this case the inclusion is not strict. When \(A \subseteq E\), but \(E\) contains an element \(a\) such that \(a \notin A\), i. e, \(A \neq E\), the inclusion is strict and \(A\) is a proper subset of \(E\). It's written \(A \subset E,\space A \neq E\). Note that

\[(A \subseteq E \text{ and } E \subseteq A) \iff A = E.\]

For the following, you need to read Subsets, Power Set, Unions, Intersections and Complements.

A partition of a set \(E \neq \emptyset\) is a collection \(F\) of subsets of \(E\), none empty, such that each element of \(E\) belongs to one and only one of the members of \(F\). Each non-empty element of \(F\) is a class of the partition of \(E\), i.e, \(E \neq \emptyset\) is the disjoint union of non-empty subsets of \(E\), where each one of these non-empty subsets is an element of \(F\).

Equivalence relation \(\iff\) Partition. We'll see this in section 5 of this chapter

Let \(E\) and \(G\) be two sets, then the product set of these 2 sets is

\[E \times G = \{(a,b) \text{ / } a \in E \text{ and } b \in G\}.\]

Note that, in general, \((a,b) eq (b,a)\), i.e. the order of these 2-couplings is important.

In the same way, we define the product set of \(n\, (n > 2 \in \mathbb{Z}^{+})\) sets as

\[ E_1 \times E_2 \times \ldots \times E_n = \{(a_1, a_2, \ldots, a_n) \text{ / } a_1 \in E_1, a_2 \in E_2, \ldots, a_n \in E_n\}.\]

Notation: If \(E_i = E, \space \forall i =1, ..., n\), the product set is \(\underbrace{E \times E \times \cdots \times E}_\text{ n } = E^{n}.\)

Let \(E\) be a set, then a \(n\)-ary relation in \(E\) is a subset of \(E^n.\)

The case \(n =2\), a binary relation, is especially important.

Let \(R \subseteq E^2\) be a binary relation in \(E\), then if \((a,b) \in R\), we'll write \(aRb\).

\(\mathbb{N} = E \). Then \(B =\{(a,b) \in \mathbb{N}^2 \text{ / } a < b\}\) is a binary relation in \(\mathbb{N}\). With this relation, \(1R4;\) nevertheless, \(5R4\) is not true, i.e. \((5,4) \notin B.\)

• A binary relation \(R\) in \(E\) is said to be a reflexive relation if for each element \(a \in E\) is satisfied \(aRa\).
• It is said that \(R\) is a symmetric relation when \(aRb \implies bRa\).
• It is said that \(R\) is a transitive relation when \(aRb \text{ and } bRc \implies aRc\).
• It is said that \(R\) is an anti-symmetric relation when \(aRb \text{ and } bRa \implies a = b\).

A binary relation \(R\) in \(E \neq \emptyset\) is said to be a equivalence relation if it owns reflexive, symmetric and transitive relations. Given an equivalence relation \(R\) in \(E \neq \emptyset\), and an element \(a\) in \(E\), \([a] = \{b \in E \text{ / } bRa\}\) is called the class of equivalence of \(a.\)

Note that \(a \in [a]\). The set of classes of equivalence is denoted by \(\frac{E}{R}\) and it's called quotient set made by the classes of equivalence of \(R.\) If there is no doubt about the equivalence relation of which one is speaking, the equivalence class of \(a\), \([a]\), is sometimes denoted by \(a\).

Let \(\mathbb{Z}\) be the set of integer numbers and \(n \in \mathbb{Z}\) a fixed integer number, then \(R = \{(a, b) \in \mathbb{Z}^2 \text{ / } \exists m \in \mathbb{Z} \text{ fulfilling } n\cdot m = a - b\}\) is a equivalence relation \(R\) in \(\mathbb{Z}\). In this case,

\[ \displaystyle \frac{E}{R}= \frac{\mathbb{Z}}{R} = \frac{\mathbb{Z}}{n\mathbb{Z}} = \mathbb{Z}_n = \big\{ [0], [1], ..., [n - 1]\big\}. \]

See Quotient Groups: \[ \mathbb{Z}_0 = \mathbb{Z}, \quad \mathbb{Z}_1 = \big\{[0]\big\}.\]

Every equivalence relation in a set \(E \neq \emptyset\) gives rise to a partition of the set \(E\), and conversely, every partition of a set \(E \neq \emptyset\) gives rise to an equivalence relation in the set \(E\).

---

A partition of a set \(E \neq \emptyset\) gives rise to an equivalence relation in the set \(E\), where each class of the partition of \(E\) is a class of equivalence of \(E\). On the other hand, an equivalence relation in a set \(E \neq \emptyset\) gives rise to a partition of the set \(E\), because each element \(a \in E\) satisfies \(a \in [a]\), and given two classes of equivalence \([a], [b]\) in \(E\), we have two possibilities:

• \([a] \cap [b] = \emptyset,\) or

• \([a] \cap [b] \neq \emptyset \implies \exists c \in [a]\) and \(c \in [b]\).

\(\big(c \in [a] \implies cRa \underbrace{\implies}_\text{symmetry} aRc\big)\) and \(\big(c \in [b] \implies cRb\big) \implies\) \(\big(aRc \text{ and } cRb\big) \underbrace{\implies}_\text{transitivity} aRb \implies a \in [b] \implies [a] \subseteq [b]\).

In the same way, \(b \in [a] \implies [b] \subseteq [a]\). Therefore, \([a] = [b]\). \(_\square\)

• A binary relation \(R\) in \(E \neq \emptyset\) is said to be a partial order relation if it owns reflexive, anti-symmetric and transitive relations. In this case, \(E\) is said to be partially ordered by \(R\).

• A partially ordered subset \(C\) of \(E\) is a chain, if every two elements of \(C\) satisfy \(aRb\) or \(bRa\), that is, any two elements of \(C\) are comparable and, in this case, \(C\) is totally ordered with \(R\).

• An element \(a \in E\) (a partially ordered set) is said to be maximal if for each element \(x \in E\) it satisfies this: \(aRx \implies x = a.\)

See Partially Ordered Sets and Fundamentals in Combinatorial Sets.

The power set \(\mathbb{P}(E)\) of a set \(E \neq \emptyset\) is a partially ordered set with the binary relation \(\subseteq\), i.e. \(I = \{(A, B) \text { / } A \subseteq E, B \subseteq E \text{ and } A \subseteq B\}\) is a partial order relation in \(E.\)

Zorn's Lemma

Let \( X\) be a partially ordered set with the property that every chain in \(X\) has an upper bound in \( X.\) Then \( X\) contains a maximal element.

See axiom of choice. This lemma can't be proved, it is a choice made by us. You can try to prove the equivalence between axiom of choice and Zorn's lemma, which needs an "advanced machinery" or, in other words, a "deep logic thought."

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