Spivak Chapter 2 problem 10

1. May 21, 2014

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.

2. May 21, 2014

micromass

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?

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.

3. May 21, 2014

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!

4. May 21, 2014

micromass

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

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

5. May 21, 2014

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.

6. May 21, 2014

micromass

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?

7. May 24, 2014

Jef123

I think im 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.

8. May 24, 2014

micromass

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.