3
$\begingroup$

I have a question about the following proof of existence of a model of non-standard arithmetic (taken from wikipedia):

The existence of non-standard models of arithmetic can be demonstrated by an application of the compactness theorem. To do this, a set of axioms $P^*$ is defined in a language including the language of Peano arithmetic together with a new constant symbol $x$. The axioms consist of the axioms of Peano arithmetic $P$ together with another infinite set of axioms: for each numeral $n$, the axiom $x > n$ is included. Any finite subset of these axioms is satisfied by a model that is the standard model of arithmetic plus the constant $x$ interpreted as some number larger than any numeral mentioned in the finite subset of $P^*$. Thus by the compactness theorem there is a model satisfying all the axioms $P^*$.

Since any model of $P^*$ is a model of $P$ (since a model of a set of axioms is obviously also a model of any subset of that set of axioms), we have that our extended model is also a model of the Peano axioms. The element of this model corresponding to $x$ cannot be a standard number, because as indicated it is larger than any standard number.

Why is it acceptable to augment the structure by a new constant symbol $x$?

$\endgroup$
  • 4
    $\begingroup$ Any model for the extended language will still be a model for the orginal language of PA. $\endgroup$ – Lord Shark the Unknown Jan 28 '18 at 13:11
  • $\begingroup$ @LordSharktheUnknown Can you offer a proof? $\endgroup$ – Dole Jan 28 '18 at 13:12
  • 4
    $\begingroup$ After forgetting the interpretation for the constant $x$, an $L_{PA}\cup\{x\}$-structure becomes a structure in the language $L_{PA}$ $\endgroup$ – Alessandro Codenotti Jan 28 '18 at 13:19
  • 2
    $\begingroup$ What could possibly be unacceptable about it? $\endgroup$ – Henning Makholm Jan 28 '18 at 14:08
  • 4
    $\begingroup$ Another brief way of putting it: because if a model satisfies every sentence of a theory, how could it fail to satisfy a subset of that theory? $\endgroup$ – Malice Vidrine Jan 28 '18 at 16:01
6
$\begingroup$

There's nothing mysterious or underhand going on here. Though there is an important point in the background, which is simply this:

In a standard formal language (like the language of Peano Arithmetic, but this same applies to any first-order language, or indeed to any sensible formal language) the truth-value of a sentence $A$ will depend only on the interpretation of the vocabulary in the sentence $A$, plus the domain of the quantifiers. What interpretation we give to any additional vocabulary not in $A$ can't affect its truth-value.

Formally, only stuff on the construction tree of a closed wff feeds into determining the semantic evaluation of the wff.

Now, why is this observation relevant to the compactness argument you are worrying about?

  1. First, generalize: Suppose we have a set of sentences $S$ drawn from a given language $L$. Then the truth-values of those sentences will depend only on the interpretation of the vocabulary in $L$ (plus fixing the domain of the quantifiers).
  2. Suppose now that we have a set of sentences $S$ drawn from the language $L$, and $S \subset S^+$ where the set of sentences $S^+$ is drawn from the richer language $L^+$ which contains all the vocabulary of $L$ plus some more (maybe extra names, for a start). And suppose we have a model, an interpretation of $L^+$, which makes all the sentences $S^+$ true. Consider the cut-down part of this model that interprets just the vocabulary in $L$ (keeping domains of quantification the same). Then this cut-down model makes all the sentences in $S$ true. Why?
  3. By hypothesis, the original model, that interpretation of $L^+$, makes all the sentences in $S^+$ true, and since $S \subset S^+$ it in particular makes the sentences in $S$ true. But the interpretation of the bits of vocabulary not in the $S$-sentences, i.e. the bits of vocabulary not in the original language $L$ don't matter by point (2). So the cut-down model interpreting just $L$ will have the same effect, i.e. make the sentences in $S$ true. QED

So now to apply this general observation. If there is a model for the axioms of Peano Arithmetic Plus Some Extra Sentences in Whatever Vocabulary You Fancy then the same model cut down to deal with just the original language of PA will also be a model for the axioms of Peano Arithmetic. That's why is perfectly legitimate tactic to establish that there are non-standard models of Peano Arithmetic by cutting down models of Peano Arithmetic Plus ... (Though as @Mikhail Katz points out in his answer, this route to non-standard models perhaps doesn't give you a "feel" for what the models are like.)

$\endgroup$
2
$\begingroup$

You are quite right to think that this type of application of the compactness theorem looks like a small miracle. To get motivation for this type of result, it is useful to think of some concrete extensions. Once one believes that such a thing is possible it becomes a little easier to accept the power of the compactness theorem. One good example to think of is Skolem's construction of a nonstandard extension of the natural numbers.

Skolem essentially used definable sequences modulo a suitable equivalence relation which basically measures their asymptotic rate of growth. In fact, the more sophisticated ultrapower construction of nonstandard models is essentially a refinement of Skolem's construction with a more powerful result but of a flavor that's less of a hands-on construction.

Once you get a feel for this type of construction it will be easier to relate to the application of the compactness theorem to get the "same" result.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.