1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Need help to prove N is not infinite by induction

  1. Oct 20, 2009 #1
    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. jcsd
  3. Oct 20, 2009 #2


    Staff: Mentor

    What does N represent here? I'm guessing that it represents the natural numbers, of which there are an infinite number.
  4. Oct 20, 2009 #3
    That's right. N is natural numbers here. It is an infinite number. We need to prove that it is. Weird question, right? :(
  5. Oct 20, 2009 #4
    I'm guessing you misunderstood the question. Do you have the question as it is exactly stated in front of you?
  6. Oct 21, 2009 #5
    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.
  7. Oct 21, 2009 #6


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Can you prove there is no bijection from N to {1}?
  8. Oct 21, 2009 #7
    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.
  9. Oct 21, 2009 #8


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    The inductive hypothesis will result in a similar argument. What have you tried so far?
  10. Oct 21, 2009 #9


    User Avatar
    Science Advisor

    What is your definition of "finite"?
  11. Oct 21, 2009 #10
    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.

    : (
  12. Oct 21, 2009 #11
    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
  13. Oct 21, 2009 #12
    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
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook