# Proof of Strong Induction Using Well-Ordering Principle

Context: I keep running into circular reasoning in attempting to derive strong induction (more generally "induction" whether it be weak or strong) from the well-ordering principle. Assume:

Peano Axioms w/ Well-Order: (I realize these are presented semi-informally)

• (P1) $\ \exists x[x\!=\!1]$;

• (P2) $\$there exists an unary ("successor") function $S$ on $\mathbb{N}$ (i.e., $x\!\in\!\mathbb{N}\rightarrow S(x)\!\in\!\mathbb{N}$);

• (P3) $\ \forall x[S(x)\!\neq\!1]$;

• (P4) $\ \forall x\forall y[x\!\neq\!y\rightarrow S(x)\!\neq\!S(y)]$

• (P5') $\$Well-Ordering Principle: Every non-empty set includes a least-element: $$\forall B\Big[\emptyset\!\subset\!B\!\subseteq\!\mathbb{N}\longrightarrow\exists m\big[m\!\in\!B\wedge\forall p[p\!\in\!B\rightarrow m\!\leq\!p]\big]\Big]$$ Note: Since I am trying to show the logical equivalency between Induction and the Well-Ordering Principle, I am assuming the latter as an axiom and treating the former as a theorem (below). The relation $\leq$ used above is defined next.

Order Relation

• (O1) $\ x\!<\!y\leftrightarrow\exists z[x\!+\!z\!=\!y]$

• (O2) $\ x\!\leq\!y\leftrightarrow[x\!=\!y\vee x\!<\!y]$

Addition (since order above is defined with "$+$")

• (A1) $\forall x[S(x)=x+1]$

• (A2) $\forall x\forall y[x+S(y)=S(x\!+\!y)]$

With this as background, below is the theorem and proof I see most often (or some variation thereof) in textbooks and online forums.

Theorem: The Well-Ordering Principle (P5') implies the Strong Induction Principle.

Proof: Suppose $X\!\subset\!\mathbb{N}$ with: (1) $1\!\in\!X$, and (2) $\forall x[x\!<\!k\rightarrow x\!\in\!X]\rightarrow k\!\in\!X$. Assume $X'\!\equiv\!\mathbb{N}\setminus X$ is non-empty. From Well-Ordering Principle (P5'), $X'$ includes a least element $m$. From (1), $m\!\neq\!1$. Since $m$ is the least element of $X'$, then all $x\!<\!m$ must belong to $X$. However, property (2) implies that $m\!\in\!X$, a contradiction. Thus, $X'$ must be empty and $X\!=\!\mathbb{N}$.

My problem is with the highlighted sentence above, which appears to me to require the result that $\neg(m\!\leq\!x)\leftrightarrow x\!<\!m$, which I believe is based on the Trichotomy Property (exactly one of $x\!<\!y$, $x\!=\!y$, $x\!>\!y$ holds). However, the only proof of the Trichotomy Property (that I am aware of) based on the above axioms/definitions alone uses Induction (see Thm 4.1c). Thus, it appears the reasoning is circular (induction is used to prove an intermediate result that is then used to prove induction).

Question: Assuming my understanding above is correct, my question simply put is this: does a proof exist of the Trichotomy Property for $<$ as defined above that does not require a proof based on induction?

• If you tag this "logic" you'll probably attract someone who knows the answer. – saulspatz Mar 4 '18 at 3:32

The axioms you listed (P1-P5') are not equivalent to Peano's. Replacing the (weak) induction axiom with the well-ordering axiom gives a weaker theory. The well-ordered sets that are not order-isomorphic to the natural numbers still obey the well-ordering axiom.

Before I come back to the trichotomy question, let's recall the role of induction in Peano's axioms. Like all the other axioms, induction is chosen so that the resulting theory may describe as well as possible the natural numbers. Induction, specifically, is there to exclude certain undesirable models.

For instance, without induction, one could easily build a "non-standard" model of arithmetic that, besides the natural numbers, contained two more elements, call them $\alpha$ and $\beta$, such that $s(\alpha) = \beta$ and $s(\beta) = \alpha$. Such a model would satisfy P1-P4, but induction rules it out.

If Peano's axioms included strong induction instead of weak induction, the resulting theory would allow models whose order type is not $\omega$. For instance, $W = \{0,1\} \times \mathbb{N}$, with lexicographic ordering, satisfies P1-P5'. (In particular, it is a well-order.)

On the other hand, weak induction does not "work" on $W$, because starting from $(0,0)$, which is the least element of $W$, and working up to $(0,1), (0,2)$ and so on, one never reaches $(1,0)$. One could "prove" by weak induction that all elements of $W$ have first component equal to $0$. For $W$ one needs transfinite induction, which is essentially strong induction.

Now, for the trichotomy property. Note that Mendelson introduces $x < y$ as a "purely abbreviational definition" in terms of $+$. Therefore, $<$ must be proved a total order. For that, induction is used; specifically, to show that the trichotomy property holds.

When proving that a well-ordered set satisfies the strong induction principle, the ordering of the set is supposed to be given, and to be a strict total order. No property of strict total orders needs to be proved.

• Two comments. First, I do not see how your example $\{0,1\}\times\mathbb{N}$ is a model of the axioms (P1)-(P5') listed above. Given, for example, a non-empty set $\{(0,1),(1,1)\}\!\subset\!W$, (P5') says it must have a least element. But I do not see how definitions (O1)-(O2) allow for one of those elements to be $\leq$. In particular, what $z$ exists that allows for $(0,1)+z=(1,1)$ or $(0,1)=(1,1)+z$? Therefore, it still seems to me that (P1)-(P5') "exclude certain undersirable models" equivalent to induction. – Stephen K. Mar 4 '18 at 11:48
• btw, I wonder if you are using a different definition of "strong induction" than I am, since I've never seen anyone say that transfinite induction is the same as strong induction. Strong induction to me as properties (1) and (2) in the first line of the proof given in my original question. – Stephen K. Mar 4 '18 at 11:48
• Second, wrt to your comment on the trichotomy prop itself, perhaps my original question was not clear enough. Yes, I want to prove that $<$ is a total order. Obviously, imgur.com/a/MPOhi uses induction to do so. But that's not my question. To clarify, contrary to the label I gave it, I am not assuming that (P5') qualifies the system as well-ordered. I want to prove that (without using induction!). – Stephen K. Mar 4 '18 at 11:48
• Let's start from strong vs. transfinite. In $\mathbb{N}$, the first condition of strong induction is redundant: the antecedent of the implication step is vacuously satisfied for an element with no predecessors. That's why we can describe strong induction thus: If $P(x)$ is true whenever $P(y)$ is true for all $y < x$, then $P(x)$ is true for all $x$. And this is essentially the principle of transfinite induction. (See, for instance, Pinter, A Book of Set Theory, Theorem 4.57.) Pragmatically, one distinguishes three cases (zero, successor, and limit) but there's only one rule. – Fabio Somenzi Mar 4 '18 at 16:00
• Besides Pinter, see Smullyan and Fitting, Set Theory and the Continuum Problem, Theorem 1.8, or Dasgupta, Set Theory, Section 9.2, Mendelson, Introduction to Mathematical Logic, Proposition 4.9, and many others. The equivalence of strong and weak induction, which is covered in most elementary treatments of induction, holds for the natural numbers. Once a proof by strong induction is given for a property $P$ of $\mathbb{N}$, one can mechanically derive a proof by weak induction of the stronger property $(\forall k \leq n) P(k)$. This, however, relies on the existence of predecessors. – Fabio Somenzi Mar 4 '18 at 16:22

The well-ordering principle implies trichotomy: given $x \neq y$, the well-ordering principle implies that that the set $\{x, y\}$ has a least element. If that least element is $x$ then $x < y$. If it is $y$ then $y < x$. If moreover, it is given that $<$ is a partial order (transitive and irreflexive), then the well-ordering principle implies trichotomy in the stronger sense that for any $x$ and $y$, exactly one of $x < y$, $x = y$ or $y < x$ holds.

The existence of a well-ordering that is also an unbounded partial order does imply the existence of a successor operator $S$ such that $S(x)$ is the least element of $\{y \mid x < y\}$. However the principle of induction does not hold for this successor operator in general. The simplest counter-example is the ordered set $\omega + \omega$, comprising two copies of the natural numbers laid one after the other. More generally any limit ordinal greater than $\omega$ is a counter-example. The "proof" that the well-ordering principle is equivalent to induction assumes that the well-ordering is a sub-order of the usual order on $\Bbb{N}$.

• It seems your reasoning assumes that the least element is unique? How do you show that without using the Trichotomy property itself? – Stephen K. Mar 4 '18 at 4:09
• Because I am assuming (as I am entitled to) that "$<$ is a partial order", – Rob Arthan Mar 4 '18 at 4:27
• Why are you entitled to assume that? In what part of definitions (O1)-(O2) and (A1)-(A2) above give you that right? The auther of imgur.com/a/MPOhi apparently didn't assume that, by rigourously proving in Thm. 4.1 that $<$ is a strict partial order. But he used induction above, which is really the whole basis for my original question. – Stephen K. Mar 4 '18 at 11:32
• You haven't told us what "textbooks or online forums" you are actually talking about, so without that information, I am entitled to make any reasonable assumptions I like. – Rob Arthan Mar 4 '18 at 11:42
• See, e.g., faculty.math.illinois.edu/~lerman/347/s17/ch1.pdf (page 5, part 1.4); also, the original Thm4.1 cited by my link is from Elliott Mendelson's Number Systems and the Foundations of Analysis text by Dover. But I hope that my original question presented sufficient context and what tools I am assuming (and nothing more). – Stephen K. Mar 4 '18 at 11:57

Much thanks to @Fabio for providing the answer which (after some slow thinking on my part and patience on @Fabio's part) led to my understanding of this problem. It helped in my understanding to further write out the exemplary counterexample with the detail filled in (in particular, completing the definition of the addition operation), which I felt may be helpful to others to duplicate here.

Theorem The "Well-Ordering Principle" identified as (P5') above does not imply induction.

Proof: A counterexample satisfying (P1)-(P5') (where P5' is defined by (O1)-(O2) and (A1)-(A2)) is provided that does not satisfy the induction principle. Let $W$ be defined as the union of two systems of natural numbers $\mathbb{N}_a$ and $\mathbb{N}_b$. Next, the binary operation of "addition" can be defined on $W$ as follows: $$(A1)\ \ \forall x[x+1_a=S(x)]$$ $$(A1_b)\ \ \left\{\begin{array}{l}\forall x\!\in\!\mathbb{N}_a[x+1_b=1_b] \\ \forall x\!\in\!\mathbb{N}_b[x+1_b=x] \end{array}\right.$$ $$(A2)\ \ \forall x\forall y[x+S(y)=S(x+y)]$$ The order relations $<$ and $\leq$ are defined as above in (O1) and (O2). So, for example, $7_a<3_b$ because $\exists z[7_a+z=3_b]$; in particular, $z=3_b$: $$7_a\!+\!3_b\!=\!7_a\!+\!S(2_b)\!=\!S(7_a\!+\!2_b)\!=\!S(7_a\!+\!S(1_b))\!=\!S(S(7_a\!+\!1_b))\!=\!S(S(1_b))\!=\!S(2_b)\!=\!3_b.$$ In this sense, all $x\!\in\!\mathbb{N}_a$ are "less than" those $y\!\in\!\mathbb{N}_b$. Since $\mathbb{N}_a$ alone satisfies the induction principle, but $\mathbb{N}_a\neq W$, then (P5') does not imply induction.

Trichotomy: One further point can be made--the trichotomy property does not hold for $W$ for the order defined by (O1)-(O2). For example, $1_b=1_b$ (implicit equality axioms what are part of the logical axioms). But from ($A1_b$), it also follows that $1_b+1_b=1_b$, which means $1_b<1_b$ (from (O1)). So $<$ is not trichotomous in this example.

So in conclusion, I think careful attention needs to be paid when one sees the statement that the "Well-Ordering Principle" is logically equivalent to "Induction" (I believe seen throughout the literature; but see, e.g., here). I think a more accurate statement would be: The Well-Ordering Principle (where the order relation is trichotomous) is logically equivalent with Induction.

• Trichotomy is not enough on its own: see my updated answer. – Rob Arthan Mar 6 '18 at 11:29