Need help to prove N is not infinite by induction

[jiao_fly]

Homework Statement

Use induction to prove N is not finite.

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

The Attempt at a Solution

 

[Mark44]

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

 

[jiao_fly]

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

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

 

[VeeEight]

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

 

[jiao_fly]

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

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

 

[Office_Shredder]

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

 

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

 

[Office_Shredder]

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

 

[HallsofIvy]

What is your definition of "finite"?

 

[jiao_fly]

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

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.

: (

 

[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

 

[emyt]

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.

: (

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