2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Henning Makholm Sep 26 '18 at 19:38
  • $\begingroup$ To be pendantic, Well Ordering is only equivalent to Induction if you assume every nonzero value has a predecessor. $\endgroup$ – DanielV Sep 27 '18 at 4:41
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ 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 . $\endgroup$ – hamam_Abdallah Sep 26 '18 at 19:59
  • $\begingroup$ @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.) $\endgroup$ – Noah Schweber Sep 26 '18 at 20:08
  • $\begingroup$ He has not to prove the conclusion ! $\endgroup$ – hamam_Abdallah Sep 26 '18 at 20:10
  • $\begingroup$ @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." $\endgroup$ – Noah Schweber Sep 26 '18 at 20:15
  • $\begingroup$ He has not to prove that P hold for all $n$. If he proves 1 and 2 then automatically P holds for all n. $\endgroup$ – hamam_Abdallah Sep 26 '18 at 20:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.