compactness theorem for classical propositional logic
(Compactness Theorem) is sound iff every finite subset of it is sound.
One direction is trivial. The converse is trivial too if is finite. We now prove that if every finite subset of an infinite set is sound, so is . There are two well-known proofs of this, one assumes that the set of propositional variables is countable, and the other does not. The one that does uses Konig’s lemma, and the other one uses Tychonoff’s theorem (hence the name compactness theorem).
Proof using Konig’s lemma. Let be an enumeration of all the wff’s in (this assumes that the set of all propositional variables is countable). Let be positive integers such that are the propositional variables that occur in wff’s . Since is sound, the set for each . Furthermore, . Let . In other words, each is a set of words over of length . Then is finite and non-empty (because ) for each . Since , there is a word in that is a prefix of a word in for each .
Let be the tree with root (some arbitrary symbol) such that
its vertices other than are elements of .
the children of are elements of ,
if is a vertex, then its children are elements of with prefix
It’s easy to see that is finitely branching, since each is finite. Furthermore, by induction, if , then its prefix of length , an element of , is a vertex of . So , as a child of , is a vertex . Since each for each , the has infinitely many vertices. As a result, we apply Konig’s lemma, so that has an infinite branch . It is easy to see that corresponds to an infinite word over , which in turn corresponds to an interpretation such that is the ’th letter in . It is now clear that for each , hence is sound.
Proof using Tychonoff’s theorem. For any set of wff’s, define . It is easy to see that
for is in the former set iff for all iff for all , , iff in the later set.
Next, equip with the discrete topology, and the product topology. Since is compact, so is by the Tychonoff’s theorem, and therefore the finite intersection property applies. In addition, for any wff , is closed in , since there are only a finite number of propositional variables occurring in . As a result, by equation , is closed for any set of wff’s.
Now, suppose every finite subset of is sound. In particular, every singleton subset of is sound. This means that for each , . Let . Then every member of is closed, and, by assumption and equation , the intersection of any finite family of members of is non-empty, which means that . But by equation , the result follows.
By the compactness theorem, one can show that soundness and consistency are the semantical and syntactical sides of the same idea.
Soundness and consistency are the same on finite sets.
If , then , where is , or for all , or or , or or or or for all , by induction, or for some , where , which means is not sound.
Soundness and consistency are the same on all sets.
A set of wff’s is uniquely sound if there is a unique interpretation such that for every .
A set is maximally consistent iff it is a uniquely sound theory.
If is maximally consistent, then it is a theory (see here (http://planetmath.org/MaximallyConsistent)), and sound by the last corollary. Suppose for all . If , then there is some wff such that . So one of them is , say . Then is sound, and therefore consistent by the last corollary, contradicting the maximality of .
We actually proved more: any maximally consistent is , where is the unique interpretation such that for all . One direction is obvious. The other direction comes from the fact that is consistent and is maximal.
Conversely, suppose a theory is uniquely sound. Then , where is the set of all maximally consistent sets of the logic . Suppose has at least two elements, say, . Then by the last paragraph, they are both uniquely sound. Let be the two respective unique interpretations such that for every , . Since , there is a wff such that and . In addition, for all , which forces because is uniquely sound. But this contradicts the inequality . Therefore, has exactly one element, which is . ∎
Remark. It is easy to see that is maximally consistent for any interpretation : it is sound, and therefore consistent; it is maximal, for given any wff , either or , so that either or . Coupled with the corollary above, there is a one-to-one correspondence between interpretations and maximally consistent sets of a logic.
|Title||compactness theorem for classical propositional logic|
|Date of creation||2013-03-22 19:35:21|
|Last modified on||2013-03-22 19:35:21|
|Last modified by||CWoo (3771)|