I've had the idea of nonstandard Peano arithmetic introduced to me in the comments of this question. The concept that we could write down the axioms which produce the natural numbers and also produce something else from them is totally crazy to me! I did not expect this.
I've been doing some reading here, to try and understand what these non-standard models of the Peano axioms are. It's difficult for me to follow the details of this paper, but I've understood that the most simple non-standard model of the Peano axioms is
$$
M = \{\mathbb{N}, +, ×, ≤, 0, 1, c\}
$$
I understand this to be the natural numbers along with an additional constant $c$, is that correct?
So from this understanding, it makes sense to me to ask the questions,
- What is $n+c$ for $n$ a natural number?
- What is $n\cdot c$ for $n$ a natural number?
- What is $c+c$?
- What is $c\cdot c$?
- Is $c≤n$ for $n$ a natural number?
Are these sensible questions? If not, is there some similar concrete way to understand this model?
Best Answer
Delving into the proof of completeness theorem, as Noah suggests, is one good way to gain intuition about nonstandard models of PA. Here's another approach.
First, we should see why there are nonstandard models of PA. It's not hard to find proofs that "Peano's Axioms" have a unique model, up to isomorphism. (Peano's predecessor Dedekind may have given the first such proof, in his paper "Was sind und was sollen die Zahlen" ("The nature and meaning of numbers")). This doesn't contradict the existence of nonstandard models of PA, because "PA" nowadays doesn't mean Peano's Axioms, but the first-order theory of arithmetic. Peano's induction axiom says that an arbitrary subset of $\mathbb{N}$ is $\mathbb{N}$ if it contains 0 and is closed under succession. This is a second-order axiom, meaning it talks about arbitrary sets of natural numbers.
The induction axioms of PA talk only about subsets of the system that can be defined by a first-order formula: a formula built up with +, $\times$, etc., and the basic constructs of logic ($\forall$, $\neg$, $\wedge$, etc.) A nonstandard model, call it $N$, will have subset that is isomorphic to $\mathbb{N}$; we might as well call it $\mathbb{N}$. This subset violates the second-order version of induction in $N$, since it's a subset closed under succession and containing 0 but not all of $N$. But it's "invisible" to first-order logic: it can't be defined by a first-order formula.
There is a weaker set of first-order axioms known as PA$^-$. (See here for a list of its axioms.) Basically this includes all the "algebraic" and "ordering" properties of PA, but omits all the induction axioms. So for example we have $x+y=y+x$ and $x<y\rightarrow x+z<y+z$ as axioms. Here it's much easier to construct a nonstandard model. Start with $\mathbb{N}$, and add a constant $c$; you may think of $c$ as a kind of "infinite number". Because you have $c$, you also must have $c\pm n$ for all $n\in\mathbb{N}$, $c^2$, $2c^2$, etc. In fact, it's not hard to see that the model must contain elements corresponding to all polynomials of the form $$a_nc^n+\cdots+a_0,\qquad a_n,\cdots,a_0\in\mathbb{Z},\;a_n>0$$ And that's enough! The set of such polynomials, together with 0, with the natural definitions for $+,\times,<$, is a model of PA$^-$ (call it $M$).
The induction axioms do not hold in $M$. For example, you can prove by induction that $$\forall x\exists y(y+y=x\vee y+y+1=x)$$ in other words, every number is even or odd. But there is no such $y$ in $M$ when $x=c$.
What to do, if we want a nonstandard model of PA? One idea: extend $M$ to a model $N$ of PA. Say we add a new constant $d$ and stipulate that $d+d+1=c$. (Or $d+d=c$, but not both!) Just as adjoining $c$ forced us to add lots of other elements, adjoining $d$ will force us to add a lot more. And that's just for one instance of one induction axiom! Still, the basic idea is to keep adjoining new elements whenever PA proves that something should exist, and it doesn't yet.
It is kind of remarkable that this approach can be made to work. With the model $M$, each polynomial defined a unique element, and different polynomials defined different elements. Also it was not hard to decide on the meaning of $+,\times,<$ for the elements of $M$. This becomes much more problematic with the wholesale introduction of constants designed to satisfy the induction axioms.
That it does work is the beauty of Henkin's construction, that Noah sketched. But we have to sacrifice something. The model $M$ of PA$^-$ is recursive, i.e., you could write a computer program to implement it. Tennenbaum's theorem says that no recursive nonstandard model of PA exists. In fact, you can't even make a model where the + operation is computable, not to say $\times$. (And vice versa.)
Plug: I've been blogging about nonstandard models of PA with a couple of other people (John Baez and Bruce Smith).