Under what conditions does $\mathcal{M} \vDash \mathsf{PA}$ and $\mathcal{K} \vDash \mathsf{PA}$ such that $\mathcal{M} \ncong \mathcal{K}$?

Question

I'm currently learning some introductory model theory from Marker's "Model Theory: An Introduction", Kaye's "Models of Peano Arithmetic", and Hodges' "Model Theory", and I am confused by the Wikipedia article on Peano Arithmetic. I am interested in the question I posed in the title and this article is really confusing me.

It states there that,

A model of the Peano axioms is a triple $(\mathbb{N}, 0, S)$, where $\mathbb{N}$ an infinite set, $0 \in \mathbb{N}$ and $S : \mathbb{N} \rightarrow \mathbb{N}$ satisfies the axioms. Dedekind proved in his 1888 book, What are numbers and what should they do (German: Was sind und was sollen die Zahlen) that any two models of the Peano axioms (including the second-order induction axiom) are isomorphic. In particular, given two models $(\mathbb{N}_A, 0_A, S_A)$ and $(\mathbb{N}_B, 0_B, S_B)$ of the Peano axioms, there is a unique homomorphism $f : \mathbb{N}_A \rightarrow \mathbb{N}_B$ satisfying, $$f(0_A)=0_B$$ and $$f(S_{A}(n))=S_{B}(f(n))$$ and it is a bijection.

Doesn't Tennenbaums theorem, and the existence of non-standard models, show that not all models of peano arithmetic are isomorphic? If this is the case, then what result did Dedekind actually prove and does anyone know where I can find a reference to the theorem he proved or a proof of it?

Answer 1

Your question is answered by the distinction between the first-order and second-order Peano axioms.

The categoricity result of Dedekind refers to the second-order Peano axioms rather the first-order axiomatization PA that gives rise to the nonstandard models and other phenomenon you mention.

The second order axiomatization includes the axiom that every subset of the model containing $0$ and closed under successor $S$ is equal to the entirety of the model. This axiom is second-order, because it refers to arbitrary subsets of the universe of the model. It is not difficult to see that any two models of the second order Peano axioms are isomorphic, since each initial segment of one maps uniquely to an initial segment of the other (proved by induction), and these maps union to an isomorphism.

Meanwhile, the first-order axioms of PA are usually stated in a larger language, with symbols for addition and multiplication, and one has the induction scheme only for subsets that are definable in this language. Meanwhile, the theorems of elementary model theory give rise to nonstandard models of this first-order version of PA. None of these nonstandard models is a model of the second-order axiomatization, since the standard cut of a nonstandard model is a subset containing $0$ and closed under successor, but is not the whole model.

There is quite an interesting interplay between first-order arithmetic, second-order arithmetic and first-order set theory here, because the second-order logic involved in the second-order Peano axioms used by Dedekind can be treated naturally in first-order set theory, such as ZFC (for the subsets of the model of arithmetic are just first order objects, sets, in set theory). In short, one may formalize Dedekind's argument as a result in ZFC. So ZFC proves that there is unique structure of arithmetic $\mathbb{N}$. But meanwhile, we know that different models of ZFC can have different non-isomorphic versions of this unique structure $\mathbb{N}$. So the situation is that there are many different models $M$ of ZFC, each insisting that its own version of arithmetic $\mathbb{N}^M$ is the one-and-only absolute concept of arithmetic, the unique structure of the second-order Peano axioms, but externally, we can see that these different $\mathbb{N}^M$'s are not all isomorphic to each other.