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!