Clarifications on the Incompleteness Theorems

Question

I wanted to clarify my understanding of the big picture of the first Incompleteness Theorem and a question about the second.

1. The big picture of the first Incompleteness Theorem is that PA (or any other axiomatization of arithmetic) fails to define a unique model up to isomorphism. The axioms allow for the existence of models that are different in some important way (not elementarily equivalent). For some statement(s), one model thinks it's true and the other doesn't think it's true leading to the "true, but unprovable statements". Additionally, that a sentence is not provable from the axioms because two models disagree on the truth of the sentence is a consequence of the Completeness Theorem.

Is this a correct understanding of the first Incompleteness Theorem?

Side Note: If my understanding of the first Incompleteness Theorem is accurate, then the "true, but unprovable" characterization seems like a terrible description of it because it seems to leave out the important fact that truth is relative to a model. I'm thinking it is better so say something like, "true in $\mathbb{N}$, but unprovable from PA".

2. And the second Incompleteness Theorem says that the consistency of PA is precisely one of those statements where two models disagree on its truth. I can't express how bizarre this is to me. How could a model of PA think PA is inconsistent? Intuitively, this makes no sense to me.

3. Is there any understanding of what kinds of properties theories that behave well (define their models up to isomorphism) have? ...I guess one thing they have is that they can't be strong enough to do arithmetic.

Answer 1

Re: (1), you're correct (and I agree with your side note). The one quibble I have is with the order of things: you seem to view the incompleteness theorem as a result about models which then gets turned into a result about proofs via Completeness, but it's actually the other way around.

Re: (2), this old question is relevant.

Re: (3), such a theory is called (fully) categorical. In first-order logic, as a consequence of the compactness theorem (which can be proved as a corollary of the completeness theorem), there are no fully categorical theories at all (barring those theories of finite structures). We can however talk about categoricity in a given cardinality. For $\kappa$ an infinite cardinal, a (complete, consistent, and with no finite models) theory $T$ is $\kappa$-categorical iff $T$ has exactly one model, up to isomorphism, of cardinality $\kappa$. There are indeed interesting things we can say about this more restrictive kind of categoricity:

• If $T$ is countable, then there are only two kinds of categoricity: $T$ is categorical in some uncountable cardinal iff $T$ is categorical in every uncountable cardinal. So we just have $\aleph_1$-categoricity and $\aleph_0$-categoricity. This is Morley's theorem. Once we look at uncountable theories things get more complicated; see e.g. this exposition of Harrington and Makkai.

• Within the context of countable theories, we can identify relevant model-theoretic properties. On the $\aleph_0$-categoricity side, see here; for some information about uncountably categorical theories, see here.

Finally, I have to mention the hilarious Vaught's Never-Two Theorem: no complete countable theory has exactly two countable models up to isomorphism. Yes, we can get every natural number except two.

Answer 2

Noah's answer is good as usual, but I'll add a few things.

1. Regarding your side note, that "true" means "true in $\mathbb N$ is a common point of confusion. This often goes unexplained, because as Noah suggests, the core of Godel's theorem really isn't about model theory per se, and many expositors simply don't want to get into model theory. (But perhaps then they should resist the urge to mention truth at all.) And I'll second Noah's remarks that everything you say is correct, but the "models first" perspective is a bit cart-before-horse.
2. It might seem bizarre, but if you think hard about it you'll see that there's really no reason a model of PA should go one way or another about some statement that is undecidable in PA. Being a model of PA just means it needs to agree with PA on the things that PA can prove. There's nothing particularly special about the consistency of PA in this regard, it's just like any other PA-undecidable statement... the fact that it's "about" PA in some sense doesn't change anything. Models of PA can be wrong about all sorts of stuff, where of course "wrong" means they disagree with $\mathbb N$. And indeed, the completeness theorem indicates that there will be models of PA that are wrong about any PA-undecidable statement. $^*$
3. Remarkably, no first order theory with infinite models has a unique model up to isomorphism. This even includes complete theories that evade the incompleteness theorem by not including enough arithmetic (e.g. Presberger and Skolem arithmetic) as well as complete theories that evade the incompleteness theorem by not being recursively axiomatizable (like the theory of $\mathbb N$, i.e. "true arithmetic"). In the complete case, all models are elementarily equivalent, but they can never all be isomorphic. This follows from compactness / Lowenheim-Skolem, which imply that models with many different cardinalities exist. To get fully categorical theories, say ones that can axiomatize $\mathbb N$ up to isomorphism, we need stronger semantics, for example the standard semantics of second order or infinitary logic. (This doesn't solve any foundational problems, or evade incompleteness in any meaningful way, though.)

$^*$ For brevity, I've omitted a lot of hedging and handwringing that might be prudent from a foundations perspective. In particular, I'm implicitly assuming PA to be sound (with respect to $\mathbb N$), which is stronger than even assuming consistency.