# Equivalence Induction and Well-Ordering

I need some help please. I am trying to get to grips with proving the equivalence between mathematical induction (MI) and well-ordering principle (WOP). As a theorem, I have

Principle of mathematical induction. Let $$P(n)$$ be a statement about the natural numbers, if it is established that both

1. $$P(1)$$ is true
2. For every natural number $$k$$, if $$P(k)$$ is true, then $$P(k+1)$$ is also true.

Then $$P(n)$$ is true for all $$n \in \mathbb{N}$$.

From my understanding of the theorem, it means that if both conditions 1 and 2 hold, then $$P(n)$$ is true for all natural numbers, or $$1$$ AND $$2$$ $$\implies$$ $$P(n)$$ for all $$n \in \mathbb{N}$$. So, to prove MI, I need to assume 1 and 2 to be true, and demonstrate that $$P(n)$$ is true for all natural numbers. By using the well-ordering principle and assuming there exists some n such that $$P(n)$$ is false I arrive at a contradiction - that is fine.

However, proving that WOP $$\implies$$ MI, I find confusing. In my mind it looks a bit like

WOP $$\implies$$ $$\Big($$($$1$$ AND $$2$$) $$\implies$$ $$P(n)$$ for all $$n \in \mathbb{N})\Big)$$.

Must I assume that the WOP is true, assume both 1 and 2 are true, and demonstrate that $$P(n)$$ is true for all n? Or must I assume that WOP is true, and first demonstrate that both 1 and 2 hold before showing that it holds for all natural numbers?

• Note that the argument you already have (in the paragraph starting "From my understanding ...") proves the direction WOP${}\Rightarrow{}$MI. (Perhaps the source of your confusion is that you find yourself doing exactly the thing you've already done -- because you have not actually switched direction?) What remains is the direction MI${}\Rightarrow{}$WOP. There you need to assume that induction works and prove that every nonempty set of naturals has a least element. – Henning Makholm Sep 26 '18 at 19:38
• To be pendantic, Well Ordering is only equivalent to Induction if you assume every nonzero value has a predecessor. – DanielV Sep 27 '18 at 4:41

## 1 Answer

Must I assume that the WOP is true, assume both 1 and 2 are true, and demonstrate that P(n) is true for all n? Or must I assume that WOP is true, and first demonstrate that both 1 and 2 hold before showing that it holds for all natural numbers?

Your first guess is the right one. Remember that when we want to prove a statement of the form $$X\implies Y$$, we assume $$X$$ and try to prove $$Y$$ (in the context of having assumed $$X$$). So to prove a statement of the form $$A\implies (B\implies C),$$ we "iterate" this process:

• Assume $$A$$, and try to prove $$B\implies C$$.

• But to prove $$B\implies C$$ (within the context of having assumed $$A$$) we assume $$B$$ and try to prove $$C$$.

So really this simplifies to

• Assume $$A$$ and $$B$$ and try to prove $$C$$.

One way to think about this on a symbolic logic level is to show that $$A\implies (B\implies C)$$ is equivalent to $$(A\mbox{ and }B)\implies C$$ (incidentally, this has a set theory/computer science analogue).

• In his case, WOP is an axiom and it is assumed to be true. he just need to prove that 1 and 2 are true . – hamam_Abdallah Sep 26 '18 at 19:59
• @Salahamam_Fatima No, he needs to assume that 1 and 2 are true and then prove the conclusion (that $P$ holds of all natural numbers). (Also, I don't think you're right about WOP being an axiom in his context - I think he's talking about proving "WOP implies MI" over a weak theory of arithmetic, namely one without either WOP or MI, but that's a side issue.) – Noah Schweber Sep 26 '18 at 20:08
• He has not to prove the conclusion ! – hamam_Abdallah Sep 26 '18 at 20:10
• @Salahamam_Fatima I don't understand what you're saying. To prove "WO implies (if 1 and 2 hold, then P holds for all n)" you have to assume WO (maybe you have this as an axiom already, in which case it's already been assumed) and 1 and 2 and then prove "P holds for all n." – Noah Schweber Sep 26 '18 at 20:15
• He has not to prove that P hold for all $n$. If he proves 1 and 2 then automatically P holds for all n. – hamam_Abdallah Sep 26 '18 at 20:17