ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 14
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.2. Model Theory for Sentential Logic (cont.)
|
| We say that p is a 'consequence' of !S!,
| in symbols,
|
| !S! |= p,
|
| iff every model of !S! is a model of p.
|
| The reader is asked to prove Exercises 1.2.3-1.2.6 as well as the following:
|
| 1.2.13. Corollary. [Truth & Consequences].
|
| 1. !S! |- p if and only if !S! |= p.
|
| 2. If !S! |= p,
| then there is a finite subset !S!_0 of !S! such that !S!_0 |= p.
|
| We shall conclude our model theory for sentential logic with a few applications of
| the compactness theorem. In these applications, the true spirit of model theory
| will appear, but at a very rudimentary level. Since we shall often wish to
| combine a finite set of sentences into a single sentence, we shall use
| expressions like:
|
| p_1 & p_2 & ... & p_n
|
| and
|
| p_1 v p_2 v ... v p_n.
|
| In these expressions the parentheses are assumed,
| for the sake of definiteness, to be associated
| to the right; for instance:
|
| p_1 & p_2 & p_3 = p_1 & (p_2 & p_3).
|
| First we introduce a bit more terminology.
|
| A set !C! of sentences is called a 'theory'.
|
| A theory !C! is said to be 'closed' iff
| every consequence of !C! belongs to !C!.
|
| A set !D! of sentences is said to
| be a 'set of axioms' for a theory !C!
| iff !C! and !D! have the same consequences.
|
| A theory is called 'finitely axiomatizable'
| iff it has a finite set of axioms.
|
| Since we may form the conjunction of a finite
| set of axioms, a finitely axiomatizable theory
| actually always has a single axiom.
|
| The set !C!^c of all consequences of !C!
| is the unique closed theory which has !C!
| as a set of axioms.
|
| 1.2.14. Proposition.
|
| !D! is a set of axioms for a theory !C!
|
| if and only if
|
| !D! has exactly the same models as !C!.
|
| 1.2.15. Corollary.
|
| Let !C!_1 and !C!_2 be two theories such that:
|
| The set of all models of !C!_2
|
| is the complement of
|
| the set of all models of !C!_1.
|
| Then !C!_1 and !C!_2 are both finitely axiomatizable.
|
| Proof. The set !C!_1 |_| !C!_2 is not satisfiable,
| so it is not finitely satisfiable. Thus,
| we may chose finite sets:
|
| !D!_1 c !C!_1 and !D!_2 c !C!_2
|
| such that !D!_1 |_| !D!_2 is not satisfiable.
|
| If A |= !D!_1 then A is not a model of !C!_2,
|
| and consequently A |= !C!_1.
|
| It follows by Proposition 1.2.14 that
|
| !D!_1 is a finite set of axioms for !C!_1.
|
| Similarly,
|
| !D!_2 is a fimite set of axioms for !C!_2. -|
|
| Chang & Keisler, 'Model Theory', pages 11-12.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤