ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 13
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.2. Model Theory for Sentential Logic (cont.)
|
| 1.2.10. Lemma. Suppose !C! is a maximal
| consistent set of sentences in $S$.
|
| Then:
|
| 1. For each sentence p, exactly one of
| the sentences p, ~p belongs to !C!.
|
| 2. For each pair of sentences {p, q},
| we have that p & q belongs to !C!
| if and only if both p and q
| belong to !C!.
|
| We leave the proof as an exercise.
|
| Now consider a set !S! of sentences of $S$.
|
| We shall say that A is a 'model' of !S!,
| in symbols,
|
| A |= !S!,
|
| iff every sentence p in !S! is true in A.
|
| !S! is said to be 'satisfiable' iff it has at least one model.
|
| We now prove the most important theorem of sentential logic,
| which is a criterion for a set !S! to be satisfiable.
|
| 1.2.11. Theorem. (Extended Completeness Theorem).
|
| A set !S! of sentences of $S$ is consistent
| if and only if !S! is satisfiable.
|
| Proof. Assume first that !S! is satisfiable, and let A |= !S!.
|
| We show that every sentence deducible from !S! holds in A.
|
| Let q_0, q_1, ..., q_n be a deduction of q_n from !S!.
|
| Let m =< n.
|
| If q_m is in !S! or
| if q_m is a tautology,
| then q_m holds in A.
|
| If q_m is inferred from two sentences
| q_k and q_k => q_m which hold in A,
| then q_m must clearly hold in A.
|
| It follows by induction on m that each of
| the sentences q_0, q_1, ..., q_n holds in A.
| Since S & ~S does not hold in A, it is not
| deducible from !S!, so !S! is consistent.
|
| Now assume that !S! is consistent.
|
| By Lindenbaum's theorem we enlarge !S!
| to a maximal consistent set !C!.
|
| We now construct a model of !S!.
|
| Let A be the set of all sentence symbols S in $S$
| such that S is in !C!. We show by induction that,
| for each sentence p, we have:
|
| 1. p in !C! if and only if A |= p.
|
| By definition, (1) holds when p is a sentence symbol S_n.
|
| Lemma 1.2.10.1 guarantees that,
| if (1) holds when p = q,
| then (1) holds when p = ~q.
|
| Lemma 1.2.10.2 guarantees that,
| if (1) holds when p = q and when p = r,
| then (1) holds when p = q & r.
|
| From (1), it follows that A |= !C!,
| and since !S! c !C!, that A |= !S!. -|
|
| We can obtain a purely semantical corollary.
|
| !S! is said to be 'finitely satisfiable' iff
| every finite subset of !S! is satisfiable.
|
| 1.2.12. Corollary. (Compactness Theorem).
|
| If !S! is finitely satisfiable,
| then !S! is satisfiable.
|
| Proof. Suppose !S! is not satisfiable.
|
| Then by the extended completeness theorem !S! is inconsistent.
|
| Hence, !S! |- S & ~S.
|
| In the deduction of the sentence S & ~S from !S!
| only a finite set !S!_0 of sentences of !S! is used.
|
| It follows that !S!_0 |- S & ~S, so !S!_0 is inconsistent.
|
| Then !S!_0 is not satisfiable, so !S! is not finitely satisfiable. -|
|
| Notice that the converse of the compactness theorem is trivially true,
| that is, every satisfiable set of sentences is finitely satisfiable.
|
| Chang & Keisler, 'Model Theory', pages 10-11.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤