I am struggling to understand Corollary 3 from Section 5.6 of Papadimitriou's Complexity Theory book (Addison-Wesley, 1993). It got me completely confused... If anyone out there has read it and understood it, I would be thankful for some help.

I would first say that I don't see how this corollary implies the result alluded to in the previous paragraph, that the nonstandard model $N'$ of number theory cannot be differentiated from the standard model by any set of sentences.

In any case, I also have problems with the proof of the corollary as it is given. As I see it, the standard model $N$ satisfies all of the expressions $\phi_i$, plus the ones in $\Delta$. So why can't it be taken as the model for $\Delta \cup \{ \phi_i : i \geq 0\}$ that he claims at the end must have a universe that is a strict superset of the universe of the standard model?

Also, why can't it be the case that all the $\phi_i$ expressions be in $\Delta$ in the first place, since there is no constraint on $\Delta$ except that $N$ must satisfy it? The proof would seem pretty empty in this case.

I must be overlooking some pretty stupid thing in this; for me it just didn't parse!

  • $\begingroup$ Does each $\phi_n$ asserts something akin to $c > \bar{n}$, where $c$ is a fixed constant and $\bar{n}$ is the numeral for $n$? If so, then while the standard $N$ satisfies any finite subset of the $\phi_n$'s, it can't satisfy the entire set of them simultaneously. (I don't have access to the book, so I'm guessing at the result in question. It would be useful to state the corollary and include definitions for $\Delta$ and $\phi_n$, though ultimately this question is likely more suited to math.stackexchange.com.) $\endgroup$
    – Ed Dean
    Aug 21, 2015 at 0:20
  • $\begingroup$ Well, $\phi_i = \exists x ((x \neq 0) \wedge \cdots \wedge (x \neq i))$. That is, $\phi_i$ says that there is a number different from $0, \ldots, i$. Of course $N$ satisfies each $\phi_i$, or any finite subset of them. I don't understand what you mean when you say that $N$ cannot satisfy all of them simultaneously. Isn't the definition of satisfaction that $N$ satisfies each $\phi_i$? What would it mean for it to satisfy them all simultaneously? $\endgroup$
    – Fernando
    Aug 21, 2015 at 1:16

1 Answer 1


The proof in Papadimitriou's book has an error.

Corollary 3

To fix the proof, first add a new constant symbol, 'c', to the language of arithmetic, and then define $\phi_i$ be the sentence "$(c \neq 0) \wedge ... \wedge (c \neq i)$". The rest of the proof is correct.

  • $\begingroup$ I think you are right, this would fix the argument. Thanks! $\endgroup$
    – Fernando
    Aug 21, 2015 at 11:20

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.