Just as an aside, I really enjoyed Scott Aaronson’s explanation of nonstandard models in this writeup:
...The Completeness Theorem is confusing for two reasons: on the one hand, it sounds like a tautology (“that which is consistent, is consistent”) — what could it possibly mean to prove such a thing? And on the other hand, it seems to contradict the Incompleteness Theorem.
We’re going to clear up this mess, and as a bonus, answer our question about whether all models of ZF are uncountable. The best way to understand the Completeness Theorem is to make up a consistent axiom set that you’d guess doesn’t have a model. Given a theory T, let Con(T) be the assertion that T is consistent. We know from Gödel’s Incompleteness Theorem that Con(ZF) can be expressed in ZF, and also that Con(ZF) can’t be proved in ZF, assuming ZF is consistent. It follows that assuming ZF is consistent, the “self-hating theory” ZF+¬Con(ZF), or ZF plus the assertion of its own inconsistency, must also be consistent. So by the Completeness Theorem, ZF+¬Con(ZF) has a model. What on earth could it be? We’ll answer this question via a fictional dialogue between you and the axioms of ZF+¬Con(ZF).
You: Look, you say ZF is inconsistent, from which it follows that there’s a proof in ZF that 1+1=3. May I see that proof?
Axioms of ZF+¬Con(ZF): I prefer to talk about integers that encode proofs. (Actually sets that encode integers that encode proofs. But I’ll cut you a break — you’re only human, after all.)
You: Then show me the integer.
Axioms: OK, here it is: X.
You: What the hell is X?
Axioms: It’s just X, the integer encoded by a set in the universe that I describe.
You: But what is X, as an ordinary integer?
Axioms: No, no, no! Talk to the axioms.
You: Alright, let me ask you about X. Is greater or smaller than a billion?
Axioms: Greater.
You: The 10^10^1,000,000,000th Ackermann number?
Axioms: Greater than that too.
You: What’s X^2+100?
Axioms: Hmm, let me see… Y.
You: Why can’t I just add an axiom to rule out these weird ‘nonstandard integers?’ Let me try: for all integers X, X belongs to the set obtained by starting from 0 and...
Axioms: Ha ha! This is first-order logic. You’re not allowed to talk about sets of objects — even if the objects are themselves sets.
You: Argh! I know you’re lying about this proof that 1+1=3, but I’ll never catch you.
Axioms: That right! What Gödel showed is that we can keep playing this game forever. What’s more, the infinite sequence of bizarre entities you’d force me to make up — X, Y, and so on — would then constitute a model for the preposterous theory ZF+¬Con(ZF).
You: But how do you know I’ll never trap you in an inconsistency?
Axioms: Because if you did, the Completeness Theorem says that we could convert that into an inconsistency in the original axioms, which contradicts the obvious fact that ZF is consis—no, wait! I’m not supposed to know that! Aaahh! [The axioms melt in a puddle of inconsistency.]
Just as an aside, I really enjoyed Scott Aaronson’s explanation of nonstandard models in this writeup: