How Can the Peano Postulates Be Categorical If They Have NonStandard Models?

Question

Having just read Noah Schweber's excellent answer to this question, I am reminded of something that has always mystified me. I was taught that the Peano Postulates are categorical (that is, any two models are isomorphic,) a fact which seems intuitively obvious. So, how can there be nonstandard models? In particular if I have some uncountable nonstandard model of PA, why can't I pick some element $s$, and consider the elements$$s, s+s, s+s+s, ...$$ to get a countable model inside the given model, just as I would construct the even positive integers inside the natural numbers by taking $s=2$? Surely the uncountable model and the countable model aren't isomorphic, are they?

I understand how the compactness theorem shows the existence of nonstandard models, and I have no problem with that. I just don't understand how to reconcile this with categoricity.

Answer 1

There are two different versions of "Peano arithmetic": a first-order version and a second-order version. The second-order version has as its induction axiom the statement that for any subset $S$ of the structure, if $0\in S$ and $x+1\in S$ for all $x\in S$, then $S$ is the entire structure. The first-order version has a much weaker induction axiom: it only applies to subsets $S$ which are definable in first-order logic (that is, subsets which can be described as the set of elements of the structure which make some first-order formula true). The first-order version is generally far more interesting from the perspective of logic and is what "Peano arithmetic" normally refers to, since it can be formulated as a first-order theory.

The second-order version of Peano arithmetic is categorical, but the first-order version is not. The answer you linked to is talking about the first-order version, not the second-order version.

Answer 2

The way that we obtain categoricity in the second-order Peano axioms is not only about the axioms - it's also about the way we interpret them. We need to be talking about the "second order Peano axioms", rather than first-order Peano arithmetic, for the rest of this answer.

There are two different ways to treat the semantics of second order Peano arithmetic. They are known as "standard semantics" and "Henkin semantics".

In standard semantics, each model can have its own set of "natural numbers" $\mathbb{N}$, and then we interpret quantifiers over subsets of $\mathbb{N}$ as quantifying over all subsets of the set of numbers in the model.

In Henkin semantics, we allow each model to have both a set of "numbers" $\mathbb{N}$ and a set of "sets of numbers", and we interpret a quantifier over subsets of $\mathbb{N}$ as only quantifying over the collection of "sets of numbers" that is in the model. So standard semantics is the same as Henkin semantics with the extra restriction that we only consider models where the collection of subsets of $\mathbb{N}$ is the entire powerset of the set of naturals $\mathbb{N}$ of the model.

Given any set of (possibly second-order axioms) for arithmetic, we can choose either of these semantics. Either way, the set of provable consequences of the axioms is exactly the same. The only difference is in which models we consider.

Given this setup, we can prove that second-order Peano arithmetic with standard semantics is categorical, while second-order Peano arithmetic with Henkin semantics is not.

The key point here is that it is not the theory which is categorical - it is the combination of the theory and the collection of models that we consider that combine to make the theory categorical. If we consider a smaller collection of models, it is easier for the same theory to be categorical.

When we use methods such as compactness or the completeness theorem, we generate models in sense of Henkin semantics that may not be models in standard semantics. That fact explains how the categoricity of second order PA in standard semantics can be reconciled with the compactness theorem - standard semantics can ignore many possible interpretations of a set of axioms.