I saw the following theorem (in Computational Complexity book by Papadimitriou, p. 111) :
Theorem :
If $\Delta$ is a set of first-order sentences such that $N$ $\vDash \Delta$, then there is a model $N'$ such that $N' \vDash$ $\Delta$, and the universe of $N'$ is a proper superset of the universe of $N$.
Proof :
Consider the sentences $\phi_i$ = $\exists x ((x!=0) \wedge$ $(x!=1)\ \wedge ... (x!=i))$, and the set $\Delta \cup \{\phi_i:$ $i>=0\}$. The set is consistent, because if it were not, if would have a finite subset that is inconsistent. This finite subset contains only finitely many of the $\phi_i$ sentences. But $N$ obviously satisfies both $\Delta$ and any finite subset of these sentences. So, there is a model of $\Delta \cup \{\phi_i: i>=0\}$, and the universe of this model must be a strict superset of the universe of $N$.
My first question is about the last (italicized) statement of the proof above : Why must the universe of the model be a superset of $N$? Any individual sentence $\phi_i$ can be satisfied by $N$ itself (just choose x=i+1, for example), and so $N$ simultaneously satisfies all $\phi_i$, and therefore $N$ is a model for $\Delta \cup \{\phi_i: i>=0\}$.
Second, the book claims that this theorem "shows that the nonstandard model $N'$ of number theory (the natural numbers plus a disjoint copy of the integers) cannot be differentiated from $N$ by first-order sentences." But all this theorem claims to show is that for any set of first orders sentences $\Delta$ there is some strict superset of $N$ that statisfies $\Delta$. How do we know that the nonstandard model $N'$ (with the disjoint copy of the integers) is one such superset?
You're right, the proof doesn't work in the form you have quoted it. What the proof tries to be is known as the usual compactness argument for nonstandard models of arithmetic, but it botches the details.
How it is supposed to go is something like this:
First we extend the language of arithmetic with a new constant symbol $c$.
Then consider the theory whose axioms are (a) the sentences $\Delta$, (b) the infinitely many new axioms $c\ne 0, c\ne 1, c\ne 2, \ldots$, (c) if necessary, sufficiently many axioms to guarantee that $0, 1, 2,\ldots$ are all distinct and arithmetic on them gives the correct results.
Any finite subset of the new theory has a model, namely $\mathbb N$ with $c$ assigned to some number whose new axiom is not in the finite subset.
Therefore, by compactness, there is a model for the entire new theory. If we forget the part of the model that interprets the new constant $c$ we get a model for $\Delta$. However, because the new model has to contain an interpretation of $c$, it needs to contain at least one element that is not one of $0, 1, 2, \ldots$. Thus, its domain can be identified with a superset of $\mathbb N$.
If the $N$ in your quote is not necessarily $\mathbb N$, but simply some model of $\Delta$, then a few technical changes to this scheme are necessary -- the new theory must contain new constants for each element of the domain of $N$, and axioms that say these elements are distinct and behave like they do in $N$. This will make sure that the new model contains an isomorphic copy of $N$.
Where the quoted proof goes wrong is that it attempts to replace the new constant $c$ with a separately quantified variable for each new axiom. But that doesn't work; it will not force the new model to have the same witness for each of the new axioms, and therefore its new theory may just be $\mathbb N$ itself.
Finally, it is simply wrong that the nonstandard model consists of "the natural numbers plus a disjoint copy of the integers". That is one possible nonstandard model of just zero and the successor function, but as soon as one wants to handle addition and multiplication too, nonstandard models will necessarily have an extremely complex structure -- in fact, one that cannot even be described in a computable way.