Editing Mathematical induction (section)

== Relationship to the well-ordering principle{{anchor|Proof of mathematical induction}} ==
The principle of mathematical induction is usually stated as an [[axiom]] of the natural numbers; see [[Peano axioms]]. It is strictly stronger than the [[well-ordering principle]] in the context of the other Peano axioms. Suppose the following:
* The [[trichotomy (mathematics)|trichotomy]] axiom: For any natural numbers {{mvar|n}} and {{mvar|m}}, {{mvar|n}} is less than or equal to {{mvar|m}} if and only if {{mvar|m}} is not less than {{mvar|n}}.
* For any natural number {{mvar|n}}, {{math|''n'' +&thinsp;1}} is greater {{nowrap|than ''n''}}.
* For any natural number {{mvar|n}}, no natural number is {{nowrap|between ''n''}} and {{math|''n'' +&thinsp;1}}.
* No natural number is less than zero.

It can then be proved that induction, given the above-listed axioms, implies the well-ordering principle. The following proof uses complete induction and the first and fourth axioms.

'''Proof.''' Suppose there exists a [[empty set|non-empty]] set, {{mvar|S}}, of natural numbers that has no least element. Let {{math|''P''(''n'')}} be the assertion that {{mvar|n}} is not in {{mvar|S}}. Then {{math|''P''(0)}} is true, for if it were false then 0 is the least element of {{mvar|S}}. Furthermore, let {{mvar|n}} be a natural number, and suppose {{math|''P''(''m'')}} is true for all natural numbers {{mvar|m}} less than {{math|''n'' +&thinsp;1}}. Then if {{math|''P''(''n'' +&thinsp;1)}} is false {{math|''n'' +&thinsp;1}} is in {{mvar|S}}, thus being a minimal element in {{mvar|S}}, a contradiction. Thus {{math|''P''(''n'' +&thinsp;1)}} is true. Therefore, by the complete induction principle, {{math|''P''(''n'')}} holds for all natural numbers {{mvar|n}}; so {{mvar|S}} is empty, a contradiction. Q.E.D.

[[File:OmegaPlusOmega_svg.svg|thumb|600px|"[[Number line]]" for the set {{math|1={{color|#800000|{(0, ''n''): ''n'' ∈ '''N'''}<nowiki/>}} ∪ {{color|#000080|{(1, ''n''): ''n'' ∈ '''N'''}<nowiki/>}}}}. Numbers refer to the second component of pairs; the first can be obtained from color or location.]]
On the other hand, the set <math>\{(0, n) : n \in \mathbb{N}\} \cup \{(1, n) : n \in \mathbb{N}\}</math>, shown in the picture, is well-ordered<ref name=Ohman2019 />{{rp|35lf}} by the [[lexicographic order]].
Moreover, except for the induction axiom, it satisfies all Peano axioms, where Peano's constant 0 is interpreted as the pair (0,&thinsp;0), and Peano's ''successor'' function is defined on pairs by {{math|1=succ(''x'', ''n'') = (''x'', ''n'' +&thinsp;1)}} for all <math>x \in \{0,1\}</math> and <math>n \in \mathbb{N}</math>.
As an example for the violation of the induction axiom, define the predicate {{math|''P''(''x'', ''n'')}} as {{math|1=(''x'', ''n'') = (0, 0)}} or {{math|1=(''x'', ''n'') = succ(''y'', ''m'')}} for some <math>y \in \{0,1\}</math> and <math>m \in \mathbb{N}</math>. Then the base case {{math|''P''(0,&thinsp;0)}} is trivially true, and so is the induction step: if {{math|''P''(''x'', ''n'')}}, then {{math|''P''(succ(''x'', ''n''))}}. However, {{math|''P''}} is not true for all pairs in the set, since {{math|''P''(1,0)}} is false.

Peano's axioms with the induction principle uniquely model the natural numbers. Replacing the induction principle with the well-ordering principle allows for more exotic models that fulfill all the axioms.<ref name=Ohman2019>{{cite journal |last1=Öhman |first1=Lars–Daniel |title=Are Induction and Well-Ordering Equivalent? |journal=The Mathematical Intelligencer |date=6 May 2019 |volume=41 |issue=3 |pages=33–40 |doi=10.1007/s00283-019-09898-4|doi-access=free}}</ref>

It is mistakenly printed in several books<ref name=Ohman2019 /> and sources that the well-ordering principle is equivalent to the induction axiom. In the context of the other Peano axioms, this is not the case, but in the context of other axioms, they are equivalent;<ref name=Ohman2019 /> specifically, the well-ordering principle implies the induction axiom in the context of the first two above listed axioms and
* Every natural number is either 0 or {{math|''n'' +&thinsp;1}} for some natural number {{mvar|n}}.

A common mistake in many erroneous proofs is to assume that {{math|''n'' −&thinsp;1}} is a unique and well-defined natural number, a property which is not implied by the other Peano axioms.<ref name=Ohman2019 />