3
$\begingroup$

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!

Improve this question
$\endgroup$
2
  • $\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
    Commented 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
    Commented Aug 21, 2015 at 1:16

1 Answer 1

Reset to default
6
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .