How Can the Well-Ordering Principle Prove Mathematical Induction?

[Jef123]

1. Prove the principle of mathematical induction from the well ordering principle.

I didn't get very far, but here's my attempt at it...

Let A be a set that contains 1 and contains n whenever it contains n+1. Now, let there be a non empty set B that contains all natural numbers not in A. By the well-ordering theorem, B must contain a least element m. m≠1...

Aside from hints to head me in the right direction, any tips on how to improve at proofs or just the way to go about thinking about questions to prove would be helpful.

 

[micromass]

1. Prove the principle of mathematical induction from the well ordering principle.

I didn't get very far, but here's my attempt at it...

Let A be a set that contains 1 and contains n whenever it contains n+1. Now, let there be a non empty set B that contains all natural numbers not in A. By the well-ordering theorem, B must contain a least element m. m≠1...

Good. You're almost there. So $m\neq 1$. This means that $m-1$ is also a natural number. Is $m-1$ in $A$ or in $B$. What can you conclude?

Aside from hints to head me in the right direction, any tips on how to improve at proofs or just the way to go about thinking about questions to prove would be helpful.

This would be more suited in the academic guidance forum. But there is no easy answer. The best answer is to do a lot of proofs, you'll get the hang of it eventually. There are proof books, but they won't help constructing specific proofs.

 

[Jef123]

Okay, so I think m−1 is in A? Is it because m is the least element in B, thus m-1 must be in A? If that be the case, then A = (m-1) +1 = m. This is a contradiction because m is in B.

I'm not sure if the proof is done yet. If it is done, how does this prove induction? And thank you for your help!

 

[micromass]

Okay, so I think m−1 is in A? Is it because m is the least element in B, thus m-1 must be in A? If that be the case, then A = (m-1) +1 = m.

What do you mean with $A = m$? How can a set $A$ equal a natural number $m$?

If it is done, how does this prove induction?

That's still left to prove of course. The theorem of induction says that if $P(m)$ is a property about the natural number $m$ and if

• $P(1)$ is true.
• If $P(n)$ is true, then $P(n+1)$ is true.

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

So we need to start by assuming that $P(m)$ is a property that satisfies the two points above. We then need to prove that $P(n)$ is true for all $n\in \mathbb{N}$. To do this, set

$$A = \{n\in \mathbb{N}~\vert~ P(n)~\text{is true}\}$$

So $A$ is the set of all numbers $n$ such that $P(n)$ is true. Now show that $1\in A$ and that if $n\in A$ then $n+1\in A$.

 

[Jef123]

Sorry, i meant that since m-1 is an element of A and since n+1 is an element, then (m-1)+1 is an element of A as well, but this a contradiction because (m-1)+1 = m which is already an element of B.

 

[micromass]

Sorry, i meant that since m-1 is an element of A and since n+1 is an element, then (m-1)+1 is an element of A as well, but this a contradiction because (m-1)+1 = m which is already an element of B.

Then that is exactly right! So you have now correctly proven that if $A$ is a set that contains $1$ and such that $n+1\in A$ whenever $n\in A$, then $A=\mathbb{N}$.

Can you now see the link to the theorem of induction?

 

[Jef123]

I think I am not seeing something here. So the contradiction is stating that m is in A or B? If its in A then I understand... If not, then i am confused.

 

[micromass]

I think I am not seeing something here. So the contradiction is stating that m is in A or B? If its in A then I understand... If not, then i am confused.

You took $m$ by definition to be the least element of $B$. So $m$ is by definition in $B$.

But then you have proven that since $m-1$ is in $A$, that by the definition of $A$, we must have $m=(m-1)+1$ to be in $A$. So we have proven that $m$ is in $A$.

So it follows that $m$ is in both $A$ and $B$, which is a contradiction.
The resolution to this contradiction is that we assumed $B$ to be nonempty. So we have proven that if $B$ is nonempty, then there is a contradiction. So $B$ must be empty.