# Need help to prove N is not infinite by induction

1. Oct 20, 2009

### jiao_fly

1. The problem statement, all variables and given/known data
Use induction to prove N is not finite.

2. Relevant equations
I think we just need to prove for all K in N, there is no bijection f:N-{1, 2, .....k}
However, couldn't figure out. If there is anyone can help with, thanks a loooooot.

3. The attempt at a solution

Last edited: Oct 21, 2009
2. Oct 20, 2009

### Staff: Mentor

What does N represent here? I'm guessing that it represents the natural numbers, of which there are an infinite number.

3. Oct 20, 2009

### jiao_fly

That's right. N is natural numbers here. It is an infinite number. We need to prove that it is. Weird question, right? :(

4. Oct 20, 2009

### VeeEight

I'm guessing you misunderstood the question. Do you have the question as it is exactly stated in front of you?

5. Oct 21, 2009

### jiao_fly

Re: Need help to prove N is not finite by induction

I am sorry, I made a typo here. I mean N is not finite, use induction to prove that. Sorry.

6. Oct 21, 2009

### Office_Shredder

Staff Emeritus
Can you prove there is no bijection from N to {1}?

7. Oct 21, 2009

### jiao_fly

I sure can.

Since f(1)=f(2)=f(3)=......=1, then f:N-{1} is not a one-to-one.
So it is not a bijection.

8. Oct 21, 2009

### Office_Shredder

Staff Emeritus
The inductive hypothesis will result in a similar argument. What have you tried so far?

9. Oct 21, 2009

### HallsofIvy

Staff Emeritus
What is your definition of "finite"?

10. Oct 21, 2009

### jiao_fly

When n=1, {1} it is easy to show that there is no bijection f:N-{1}

suppose when n=K, there is no bijection f: N-{1, 2, .....k}, then I think I need to show that here is also no bijection f:N-{1, 2, 3, .....K , K+1}

However, I couldn't figure out how to do that. I think I need to use contradtion to prove that. I tryed, however failed.

: (

11. Oct 21, 2009

### emyt

I think this might be something:

let S be a set

let |N, the set of all natural numbers, be S U |N\S

U = union symbol

|N\S = the set of natural numbers excluding S

for any n that is a natural number, n+1 is also a natural number, then n+1 is also an element of the natural numbers.

for n = k, n+1= k+1
If S: {1,......,k}, then |N\S is non empty, since there exists a K+1 which is also a natural number.
so by the well ordering principle, |N\S has a least element, which is K+1.
you can continue with this pattern for n = K+1 and n+1 = K+2 indefinitely to show that |N\S is never an empty set, so there are no finite sets S that can span all of |N

Last edited: Oct 21, 2009
12. Oct 21, 2009

### emyt

I'm not sure if this will work. are you trying to show that for K there is no bijection implies K+1 has no bijection? if you prove this, then it will be true for all n that is a natural number.. which continues indefinitely into all natural numbers.. I don't know if you can get anywhere with this

I think your focus should be using the idea that any set is finite and the natural numbers will always have more than any finite set - this makes it a non-finite set. I think the proof I posted above should work.. it's rough but I think that is the idea