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).
A set of well-formed formulas is said satisfiable if there exists (is) a truth assessment satisfying each wff of . It is said finitely satisfiable if any finite subset of is satisfiable.
satisfiable finitely satisfiable.
A set of wffs is said complete if for each wff we have: or .
If a set is finitely satisfiable, then there exists a set finitely satisfiable and complete, containing .
Proof.- We'll make two proofs, the second one uses Zorn's Lema.
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 , formed by finite sequences of elements of a countable set is countable.
Let be an enumeration of , that is, a bijective application from to .
Let's define a sequence of sets of wffs by recursion in such that :
Known , let's define , if is finitely satisfiable. If the set is not finitely satisfiable, it's defined .
By induction in , is finitely satisfiable. Let's suppose that is finitely satisfiable, then if is finitely satisfiable, by definition it is also finitely satisfiable.
If is not finitely satisfiable, there exists a finite subset such that is not finitely satisfiable, but now , and let be any finite subset of . If , is satisfiable by induction hypothesis. If , then , with . Since is a finite subset , it's satisfiable or finitely satisfiable , there exists a truth assesssment that satisfies and , this implies that due to is not finitely satisfiable, therefore and hence satisfies . It is thus proven that is finitely satisfiable.
Let . It's clear that , (). Furthemore, is finitely satisfiable since any finite subset of is contained in some . Finally, is complete because given a wff , is a certain , and by construction, or .
Let . This set isn't empty because , and is partially ordered by the inclusion relation . In this ordering, each chain has an upper bound ; effectively, and is finitely satisfiable because of each finite subset contained in is contained in some .
Applying Zorn's lemma, there exists a maximal element , that is, if and . is a set of wffs contained in such that and is finitely satisfiable. Furthemore, is complete, because given any (wff) , we have one of two:
is finitely satisfiable, then this set belongs to , and being a maximal element in , it is concluded that .
is not finitely satisfiable. Then, proceeding as in demonstration 1, it follows that is finitely satisfiable, and being a maximal element in , it is concluded that .
Note that this demonstration 2 is valid even if is not a countable set.
Compactness Theorem 1.4.4.
If a set of wffs is finitely satisfiable, then is satisfiable.
Proof.- Due to 1.4.3., there exists (a set of wffs), such that , being finitely satisfiable and complete. wff, we have: , because if , since is complete. And, due to is not satisfiable, if then because is finitely satisfiable.
Let be a truth assessment given by, for each assertion symbol , .
We are going to show, by induction on well-formed formulas, that for each well-formed formula we have: , which is equivalent to .
It is met(fulfilled) by definition of .
Let , with fulfilling the framed thesis. Then: .
Let , with and fulfilling the framed thesis. Then ( and ) ( and ). Let's prove that: ( and ) .
) If this were not true, is not finitely satisfiable because is not satisfiable.
) If this were not true, or , but this is a contradiction because the two previous subsets are not satisfiable.
Let , with and fulfilling the framed thesis. It is easy to see that: . Due to the steps and , and fulfill the thesis fulfill also the thesis, and therefore fulfill also the thesis. To abreviate . Hence . Then , on the contrary, or ,and because of , would contain a finite subset not satisfible (Contradiction).
is tested as step taking into account that: Therefore, the truth assessment satisfies and . .
Let be a set of wffs and a wff such that . Then, there exists a finite subset fulfilling .
Proof.- means each truth assesment satisfying also satisfies , that is, is a not satisfiable set. Applying compactness theorem, there exists a finite subset which is not satisfiable. Hence, or where is a finite set and therefore .
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 , then .
"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 () 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.