• Support PF! Buy your school textbooks, materials and every day products Here!

Spivak Chapter 2 problem 10

  • Thread starter Jef123
  • Start date
  • #1
29
0
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.
 

Answers and Replies

  • #2
22,097
3,282
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.
 
  • #3
29
0
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
22,097
3,282
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

[tex]A = \{n\in \mathbb{N}~\vert~ P(n)~\text{is true}\}[/tex]

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
29
0
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
22,097
3,282
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?
 
  • #7
29
0
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
22,097
3,282
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.
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.
 
  • Like
Likes 1 person

Related Threads on Spivak Chapter 2 problem 10

  • Last Post
Replies
5
Views
2K
Replies
3
Views
2K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
3
Views
5K
Replies
12
Views
5K
Replies
2
Views
927
  • Last Post
Replies
5
Views
1K
  • Last Post
Replies
15
Views
2K
Replies
3
Views
4K
Top