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
- $P(1)$ is true
- 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?
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
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).