1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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$.

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

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.