ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 12
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.2. Model Theory for Sentential Logic (cont.)
|
| 1.2.9. Lemma. (Lindenbaum's Theorem).
|
| Any consistent set !S! of sentences can be enlarged
| to a maximal consistent set !C! of sentences.
|
| Proof. Let us arrange all of the sentences of $S$ in a list:
|
| p_0, p_1, p_2, ..., p_!a!, ...
|
| The order in which we list them is immaterial,
| as long as the list associates in a one-one
| fashion an ordinal number with each sentence.
|
| We shall form an increasing chain
| of consistent sets of sentences:
|
| !S! = !S!_0 c !S!_1 c !S!_2 c ... c !S!_!a! c ...
|
| If !S! |_| {p_0} is consistent, define !S!_1 = !S! |_| {p_0}.
|
| Otherwise, define !S!_1 = !S!.
|
| At the !a!^th stage, we define:
|
| 1. !S!_(!a! + 1) = !S!_!a! |_| {p_!a!}
|
| if !S!_!a! |_| {p_!a!} is consistent;
|
| 2. Otherwise define:
|
| !S!_(!a! + 1) = !S!_!a!.
|
| At limit ordinals !a! take unions:
|
| !S!_!a! = |_|^(!b! < !a!) !S!_!b!.
|
| Now let !C! be the union of all the sets !S!_!a!.
|
| We claim that !C! is consistent.
|
| Suppose not.
|
| Then there is a deduction
|
| q_0, q_1, ..., q_u
|
| of the sentence S & ~S from !C!, (see Proposition 1.2.8).
|
| Let r_1, ..., r_v be all the sentences in !C! which are
| used in this deduction. We may choose !a! so that all
| of r_1, ..., f_v belong to !S!_!a!. But this means
| that !S!_!a! is inconsistent (by Proposition 1.2.8),
| which is a contradiction.
|
| Having shown that !C! is consistent, we next claim that !C! is
| maximal consistent. For suppose !D! is consistent and !C! c !D!.
| Let p_!a! be in !D!. Then !S!_!a! |_| {p_!a!} is consistent, hence:
|
| !S!_(!a! + 1) = !S!_!a! |_| {p_!a!}.
|
| Thus p_!a! is in !C!, and hence !D! = !C!. -|
|
| Chang & Keisler, 'Model Theory', page 10.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤