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

### Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

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?

-

Regarding your reference question: Dedekind's 1888 Was sind und was sollen die Zahlen is the original source, and Dover has an English edition Essays on the Theory of Numbers (which contains that and also Dedekind's 1872 article where Dedekind cuts are introduced). – Ed Dean Mar 11 2012 at 21:13
@EdDean: Since you knew about the reference, do you happen to know if it is available online? I checked on JSTOR and MathSciNet and couldn't find it. – Samuel Reid Mar 11 2012 at 21:15
archive.org/details/essaysintheoryof00dedeuoft – Ed Dean Mar 11 2012 at 21:18
Hehe, by the way, I just noticed that your blockquote mentions Dedekind's source; I hadn't bothered reading that part of the question ... – Ed Dean Mar 11 2012 at 21:23

## 1 Answer

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 axiomation 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 entireity 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 additiona 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.

-
{"extraction_info": {"found_math": true, "script_math_tex": 0, "script_math_asciimath": 0, "math_annotations": 0, "math_alttext": 0, "mathml": 0, "mathjax_tag": 0, "mathjax_inline_tex": 18, "mathjax_display_tex": 2, "mathjax_asciimath": 0, "img_math": 0, "codecogs_latex": 0, "wp_latex": 0, "mimetex.cgi": 0, "/images/math/codecogs": 0, "mathtex.cgi": 0}, "config": {"markdown_headings": true, "markdown_code": true, "boilerplate_config": {"ratio_threshold": 0.18, "absolute_threshold": 10, "end_threshold": 15, "enable": true}, "remove_buttons": true, "remove_image_figures": true, "remove_link_clusters": true, "table_config": {"min_rows": 2, "min_cols": 3, "format": "github"}, "remove_chinese": true, "remove_edit_buttons": true, "extract_latex": true}, "english_confidence": 0.9382692575454712, "perplexity_flag": "head"}