4
$\begingroup$

Let P be some proposition. If we have that $P(0)$ is true and that if $P(n)$ is true, then $P(S(n))$ is true, where $S(n)$ is the successor of natural number $n$. Then we have that $P(n)$ is true for all natural numbers.

To my understanding, we need this axiom to eliminate formulations like $\{0, 0.5, 1, 1.5, 2, \ldots\}$ which otherwise fulfill the peano axioms. That is, the induction axiom forces the natural numbers to all 'stem' from zero. So why don't we just edit the axiom that says 'no element has $0$ as its successor' to be '$0$ is the only element that isn't a successor to another element'.

Are these two formulation equivalent or am I confused? I'm not sure whether this works for $\mathbb{R} \setminus \mathbb{N}^+$, which also otherwise fulfills peano axioms, but I haven't gotten to real numbers yet.

  • 0
    @Asaf: Good point.2012-04-26

2 Answers 2

10

Imagine for example the following structure. It consists of the natural numbers, coloured blue, together with the integers, coloured red. The successor operation is the natural one.

If you want a more formal description, our structure $S$ is the union of the set of all ordered pairs $(a,0)$, where $a$ ranges over the natural numbers, and the set of all ordered pairs $(b,1)$, where $b$ ranges over the integers. If $x=(a,0)$, define $S(x)$ by $S(x)=(a+1,0)$, and if $x=(b,1)$, define $S(x)$ by $S(x)=(b+1,1)$.

This structure $S$ satisfies your axiom, but is quite different from the natural numbers.

There are much worse possibilities. In the above description of $S$, instead of using all pairs $(b,1)$ where $b$ ranges over the integers, we can use all pairs $(b,1)$, where $b$ ranges over the reals.

Remark: Because of the wording of the question, we addressed only the issue of order type, which is settled by the second-order version of the induction axiom, and is indeed equivalent to it. Order types of models provide only weak information about the structure of models of first-order Peano arithmetic.

  • 0
    @Praslow D.: I read in Goldsern and Judah, The Incompleteness Phenomenon, that you still can't force everything to come from from $0$. You wind up needing $\mathbb {Q \times Z}$. You would like a postulate $\forall n n\in \mathbb N$ but that is second order logic.2012-04-26
2

One way to think about it is that the induction axiom guarantees that you can 'reach' every natural number, starting from $0$, in finitely many successor steps. This is a bit stronger than just "everything stems from $0$", which, in principle, might allow for transfinite processes (such as we have with ordinals).

In the presence of the induction axiom, the single axiom

The successor function is a bijection from $\mathbb{N}$ to $\mathbb{N}-\{0\}$.

is equivalent to the first four Peano postulates, (that is, this axiom plus Induction is equivalent to the five Peano postulates); but this latter axiom is, by itself, stronger than the first four Peano axioms (which do not suffice to show that everything except $0$ is a successor, whereas it follows easily from the statement above).

Your set, $\{0,0.5,1,1.5,\ldots\}$ is a model for the Peano Axioms, if you define $S(n) = n+\frac{1}{2}$. (As Asaf points out in comments, with this definition, the "addition" in the set coincides with that of these numbers as reals, $n+0 = n$, and $n+S(m) = S(n+m)$; but multiplication does not coincide with multiplication of the numbers in $\mathbb{R}$). What you "really" want to eliminate are models such as the ones that André Nicolas mentions (which satisfies the single axiom I list above, hence the first four Peano Axioms, but not induction). Note that in that model, the set of elements you can 'reach' from $0$ in finitely many successor steps does not exhaust the set.

  • 0
    @PraslowD.: "The set you can reach in infinitely many steps" is not necessarily a well-defined concept; the common "transfinite induction" is to show that if you can do it for "everything strictly smaller", then you can do it for the element in question. But in any case, the point is to exclude sets in which not every element can be reached from zero via successor in *finitely* many steps, whether they are well-ordered or not.2012-04-27