In this entry, we prove the following assertion known as Lindenbaum’s lemma: every consistent set is a subset of a maximally consistent set. From this, we automatically conclude the existence of a maximally consistent set based on the fact that the empty set is consistent (vacuously).
(Lindenbaum’s lemma) Every consistent set can be extended to a maximally consistent set.
We give two proofs of this, one uses Zorn’s lemma, and the other does not, and is based on the countability of the set of wff’s in the logic. Both proofs require the following:
The union of a chain of consistent sets, ordered by , is consistent.
Let be a chain of consistent sets ordered by and indexed by some set . We want to show that is also consistent. Suppose not. Then . Let be a deduction of (which is ) from . Then for each , there is some such that . Since is a chain, take the largest of the ’s, say , so that for all . This implies that , or , contradicting the assumption that is consistent. As a result, is consistent. ∎
First Proof. Suppose is consistent. Let be the partially ordered set of all consistent supersets of , ordered by inclusion . If is a chain of elements in , then is consistent by the lemma above, so as each element of is a superset of . By Zorn’s lemma, has a maximal element, call it . To see that is maximally consistent, suppose is not maximal. Then there is a wff such that and , the first of which implies that , and the second of which implies that is consistent, and therefore in . The two imply that is a consistent proper superset of , contradicting the maximality of in . Therefore, is maximally consistent.
Second Proof. Let be an enumeration of all wff’s of the logic in question (this can be achieved if the set of propositional variables can be enumerated). Let be a consistent set of wff’s. Define sets of wff’s inductively as follows:
First, notice that each is consistent. This is done by induction on . By assumption, the case is true when . Now, suppose is consistent. Then its deductive closure Ded is also consistent. If , then clearly is consistent since it is a subset of Ded. Otherwise, , or by the substitution theorem, and therefore by one of the properties of consistency (see here (http://planetmath.org/PropertiesOfConsistency)). In either case, is consistent.
Next, is maximally consistent. is consistent because, by the lemma above, it is the union of a chain of consistent sets. To see that is maximal, pick any wff . Then is some in the enumerated list of all wff’s. Therefore, either or . Since , we have or , which implies that is maximal (see here (http://planetmath.org/MaximallyConsistent)). .
Given a logic , let be the set of all maximally -consistent sets. By Lindebaum’s lemma, . We record two useful corollaries:
For any consistent set , Ded.
The second statement is a corollary of the first, for . To see the first, let . Then by Lindebaum’s lemma. Also, for any , Ded since is deductively closed. On the other hand if , then , so is consistent, and therefore is contained in a maximally consistent set by Lindenbaum’s lemma. Since , , so that . ∎
|Date of creation||2013-03-22 19:35:16|
|Last modified on||2013-03-22 19:35:16|
|Last modified by||CWoo (3771)|