# Induction as Peano Axiom

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.

-

3
You need induction to exclude systems like naturals + disjoint copy of integers, where only $0$ has no predecessor. – sdcvvc Apr 26 '12 at 6:01
Your first paragraph makes no sense (nor it "compiles") you are stating that If ... and (if ... then ...), you are missing then ... is true for all the numbers. – Asaf Karagila Apr 26 '12 at 6:54

1
The formulation you give is a perfectly fine model of the Peano Axioms, where the successor of $n$ is $n+\frac{1}{2}$. – Arturo Magidin Apr 26 '12 at 15:09
@Arturo: You are correct, of course, however one should remark that while addition in this model would coincide with the usual addition of those as real numbers, multiplication will not be the same since it should be that $S(0)\times S(0)=S(0)$. – Asaf Karagila Apr 26 '12 at 16:49
@Asaf: Good point. – Arturo Magidin Apr 26 '12 at 16:53

## 2 Answers

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.

-

@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. – Ross Millikan Apr 26 '12 at 17:12

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.

-

Very good comment, thank you. – Praslow D. Apr 27 '12 at 6:10
But to be clear, in the example of André Nicolas: While the set of elements you can reach from 0 in finitely many steps does not exhaust the set, neither does the set of elements you can reach from 0 in infinitely many steps. You'd go (0,0), (1,0), (2,0), ...., (n,0), ... Right? I suppose the finite steps is needed for $\mathbb{Q} \setminus \mathbb{N}^+$ where not every element is reachable in finite steps but can be reached in infinitely many steps. – Praslow D. Apr 27 '12 at 6:20
Sorry, make the set $\mathbb{Q} \setminus \mathbb{Q}^-$ – Praslow D. Apr 27 '12 at 6:26
@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. – Arturo Magidin Apr 27 '12 at 14:13
{"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": 47, "mathjax_display_tex": 0, "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.9316917061805725, "perplexity_flag": "head"}