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.
All chapters are connected. This wiki will be continued in another page when it be necessary.
Contents
Preface
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.
Introduction
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."
Chapter 0: Preliminaries
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.
1. 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
- means is an element of , i.e. belongs to .
- means isn't an element of , i.e. doesn't belong to .
- means that and are the same thing.
For us,
2. Propositional Symbols and Quantifiers
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 is true, another is also true, then it is said that implies In this case, is a sufficient condition for , and is necessary if
When not only implies , but also implies , it is said that propositions and are logically equivalent. Then the event of occurs if and only if the event of occurs:
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, and , called quantifiers that are used with the following meanings:
"" means there exists an element belonging to the set such that satisfies the property .
"" means every (each) element belonging to the set satisfies the property .
3. Subsets: Intersection and Union
Set is a subset of set if each element of belongs to . It's written .
According to this, but in this case the inclusion is not strict. When , but contains an element such that , i. e, , the inclusion is strict and is a proper subset of . It's written . Note that
For the following, you need to read Subsets, Power Set, Unions, Intersections and Complements.
A partition of a set is a collection of subsets of , none empty, such that each element of belongs to one and only one of the members of . Each non-empty element of is a class of the partition of , i.e, is the disjoint union of non-empty subsets of , where each one of these non-empty subsets is an element of .
Equivalence relation Partition. We'll see this in section 5 of this chapter
4. Product Set
Let and be two sets, then the product set of these 2 sets is
Note that, in general, , i.e. the order of these 2-couplings is important.
In the same way, we define the product set of sets as
Notation: If , the product set is
5. Relations and Order
Let be a set, then a -ary relation in is a subset of
The case , a binary relation, is especially important.
Let be a binary relation in , then if , we'll write .
. Then is a binary relation in . With this relation, nevertheless, is not true, i.e.
- A binary relation in is said to be a reflexive relation if for each element is satisfied .
- It is said that is a symmetric relation when .
- It is said that is a transitive relation when .
- It is said that is an anti-symmetric relation when .
A binary relation in is said to be a equivalence relation if it owns reflexive, symmetric and transitive relations. Given an equivalence relation in , and an element in , is called the class of equivalence of
Note that . The set of classes of equivalence is denoted by and it's called quotient set made by the classes of equivalence of If there is no doubt about the equivalence relation of which one is speaking, the equivalence class of , , is sometimes denoted by .
Let be the set of integer numbers and a fixed integer number, then is a equivalence relation in . In this case,
See Quotient Groups:
Every equivalence relation in a set gives rise to a partition of the set , and conversely, every partition of a set gives rise to an equivalence relation in the set .
A partition of a set gives rise to an equivalence relation in the set , where each class of the partition of is a class of equivalence of . On the other hand, an equivalence relation in a set gives rise to a partition of the set , because each element satisfies , and given two classes of equivalence in , we have two possibilities:
or
and .
and .
In the same way, . Therefore, .
A binary relation in is said to be a partial order relation if it owns reflexive, anti-symmetric and transitive relations. In this case, is said to be partially ordered by .
A partially ordered subset of is a chain, if every two elements of satisfy or , that is, any two elements of are comparable and, in this case, is totally ordered with .
An element (a partially ordered set) is said to be maximal if for each element it satisfies this:
See Partially Ordered Sets and Fundamentals in Combinatorial Sets.
The power set of a set is a partially ordered set with the binary relation , i.e. is a partial order relation in
Zorn's Lemma
Let be a partially ordered set with the property that every chain in has an upper bound in Then 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.