ONT Re: Model Theory
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
Note 37
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤
| 1. Introduction
|
| 1.4. Theories and Examples of Theories (cont.)
|
| 1.4.11. Example. [Peano Arithmetic].
|
| Let $L$ = {+, ·, S, 0},
|
| where + and · are 2-placed function symbols,
| where S is a 1-placed function symbol,
| called the 'successor' function,
| and 0 is a constant symbol.
|
| 'Number theory' (or 'Peano arithmetic')
| has the following list of axioms:
|
| 1. 0 =/= Sx (0 has no predecessor)
|
| 2. Sx = Sy => x = y (S is a one-to-one map)
|
| 3. x + 0 = x
|
| 4. x + Sy = S(x + y)
|
| 5. x · 0 = 0
|
| 6. x · Sy = (x · y) + x
|
| and, finally, for each formula
| !p!(v_0, v_1, ..., v_n) of $L$,
| where v_0 does not occur bound
| in !p!, the axiom:
|
| 7_!p!. !p!(0, v_1, ..., v_n)
|
| &
|
| (`A`v_0) (!p!(v_0, v_1, ..., v_n) => !p!(Sv_0, v_1, ..., v_n))
|
| =>
|
| (`A`v_0) !p!(v_0, v_1, ..., v_n)
|
| Axioms (3) and (4) are the usual recursive definition of + in terms of 0 and S,
| while axioms (5) and (6) are the recursive definition of · in terms of 0, S, +.
| The whole list of axioms (7_!p!), one for each !p!, is called the 'axiom schema
| of induction'.
|
| The 'standard model' of number theory is <!w!, +, ·, S, 0>, where
| S is the successor function and +, ·, 0 have their usual meaning.
| All other (non-isomorphic) models are called 'nonstandard'.
|'Complete number theory' is the set of all sentences !p!
| of $L$ that hold in the standard model.
|
| There are several deep results about number theory:
|
| Gödel's (1931) incompleteness theorem states that number theory
| is not complete; therefore, complete number theory is a proper
| extension of number theory.
|
| No finite extension (that is, by adding a finite number of new axioms)
| of number theory is complete; therefore complete number theory is not
| finitely axiomatizable over number theory, whence it is certainly not
| finitely axiomatizable.
|
| Number theory itself is not finitely axiomatizable. This was proved by
| Ryll-Nardzewski (1952) by the use of nonstandard models. The existence of
| nonstandard models of complete number theory was first shown by Skolem (1934).
|
| We mention a number of interesting subtheories of number theory.
| For instance, if the induction schema (7_!p!) is replaced by
| the single axiom:
|
| 8. (`A`x) (x =/= 0 => (`E`y) (x = Sy))
|
| we obtain a finitely axiomatizable subtheory of number theory (the theory Q
| of Tarski, Mostowski, and Robinson, 1953) which is incomplete, and no finite
| extension of it is complete.
|
| In the language $L$’ = {S, 0} obtained by leaving out
| the symbols + and ·, the subtheory of number theory
| given by axioms (1), (2), and the schema (7_!p!),
| restricted of course to formulas of $L$’, is
| complete. However, it is still not finitely
| axiomatizable, as can be shown by using the
| compactness theorem.
|
| In the language $L$” = {+, S, 0}, the axioms (1, 2, 3, 4) and
| the schema (7_!p!), again restricted to formulas of $L$”, give the
|'additive number theory'. This theory is not finitely axiomatizable,
| but it is complete (Presburger, 1929); the completeness of the theory
| $L$’ in the previous paragraph follows from the proof given by Presburger.
|
| Chang & Keisler, 'Model Theory', pages 42-43.
|
| C.C. Chang and H.J. Keisler, 'Model Theory',
| North-Holland, Amsterdam, Netherlands, 1973.
¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤~~~~~~~~~¤