Proof for a stubborn nonstandard model

This a theory in the book Computational Complexity by Christos Papadimitriou, on Page 111, as a corollary of Godel's Completeness Theorem. It asserts:

Corollary 3: If $\Delta$ is a is a set of first-order sentences such that $\mathbf{N}\models\Delta$ , then there is a model $\mathbf{N}'$ such that $\mathbf{N}'\models\Delta$, and the universe of $\mathbf{N}'$ is a proper superset of the universe of $\mathbf{N}$.

Proof: Consider the sentences $\phi_i = \exists x((x\neq0)\wedge(x\neq1)\wedge\ldots(x\neq i))$ , and the set $\Delta\cup\{\phi_i:i\geq0\}$. We claim that this set is consistent. Because, if it were not, it would have a finite subset that is inconsistent. This finite subset contains only finitely many of the $\phi_i$ sentences. But $\mathbf{N}$ obviously satisfies both $\Delta$ and any finite subset of these sentences. So, there is a model of $\Delta\cup\{\phi_i:i\geq0\}$, and the universe of this model must be a strict superset of the universe of $\mathbf{N}$.

Here $\mathbf{N}$ denote the model of number theory, and its universe is the set of natural numbers. But I don't know why he claims that the model of $\Delta\cup\{\phi_i:i\geq0\}$ must be larger than $\mathbf{N}$. I suppose that he indicates $\mathbf{N}$ cannot satisfy it, yet I don't think so. Could anyone explain it for me? Maybe I've got something wrong with 'satisfiability', so I want to make it explicit for me. Thank you indeed for your help.

The theorem is not as precisely put as it might be. Presumably the language has a unary function symbol $S$ for "successor," and a constant symbol $0$.

However, if $\Delta$ is a very poor set of axioms, that is not enough to force a model to contain a substructure isomorphic to $\mathbb{N}$.

So we will assume that $\Delta$ is rich. For example, suppose that it contains all the axioms of first-order Peano arithmetic (much less than that is needed).

Let $M$ be a model of $\Delta$ plus certain added axioms. The axioms used in the quoted proof, as you noticed, don't work. For there are plenty enough integers in $\mathbb{N}$ to satisfy each of the $\phi_i$ without going outside $\mathbb{N}$: the "$x$" whose existence is forced by the various $\phi_i$ need not be the same.

What we need to do is to add a new constant symbol $B$ to the language, and add special axioms $B\ne 0$, $B\ne S(0)$, $B\ne S(S(0))$, and so on. Every finite subset of $\Delta$ together with these special axioms has $\mathbb{N}$ as a model.

Then the interpretations of the terms $0,S(0),S(S(0)),\dots$ are a substructure of $M$ isomorphic to $\mathbb{N}$.

By replacing the interpretations of the terms $0,S(0),S(S(0)),\dots$ in $M$ by the actual natural numbers, we obtain a structure $\mathbb{N}'$ isomorphic to $M$ that has $\mathbb{N}$ as a substructure.

Now consider the interpretation of the constant symbol $B$ in $\mathbb{N}'$. It is easy to see that this cannot be any of $0,1,2,3,\dots$.

• Thanks! Your answer does help. – Willard Zhan Sep 30 '13 at 7:19
• You are welcome. The "special axioms" were not well chosen. Congratulations for noticing. – André Nicolas Sep 30 '13 at 7:21