Results 1 to 9 of 9

Math Help - Proof By Induction help!

  1. #1
    Newbie
    Joined
    Feb 2008
    Posts
    14

    Proof By Induction help!

    I don't know where to start or how to do this proof. Can someone please help me?

    Prove by induction on n that if r < n and f:N(r)--> N(n), then f is not onto N(n). (Where N is the natural numbers)

    Thank you for your help!
    Last edited by calcprincess88; April 27th 2008 at 03:52 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by calcprincess88 View Post
    I don't know where to start or how to do this proof. Can someone please help me?

    Prove by induction on n that if r < n and f:N(r)--> N(n), then F is not onto N(n). (Where N is the natural numbers)

    Thank you for your help!
    The inductive step is true trivially by the falsity of the conditional. (you take the natural numbers to be 1,2,3,... or do you include 0? I have to ask these days. It doesn't make a difference in the inductive step though)

    to continue, i need to know how you define something like N(n)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2008
    Posts
    14
    I don't understand what you mean.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by calcprincess88 View Post
    I don't understand what you mean.
    you have an if-then statement here. that is, an implication.

    so you want to prove P \implies Q for all n \in \mathbb{N}

    where P is the statement " r < n and f : \mathbb{N}(r) \mapsto \mathbb{N}(n)" where r \in \mathbb{N}

    and the statement Q is " f is not onto \mathbb{N}(n)"

    Now, if the statement P is false, then the implication P \implies Q is always true.

    The thing is, P is false for the inductive step. since if we take n = 1 (which i am assuming is the first natural number by your definition), then there is no r \in \mathbb{N} such that r < n. Thus the r < n part of the first statement is false, which ends up making the whole statement true. thus, the inductive step holds.

    Now i need to know how you define \mathbb{N}(n) for some n \in \mathbb{N}
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Feb 2008
    Posts
    14
    Ok. So i get what you are saying about the first part. But I still dont get what you are asking when you say to "define for some ." I think n is either a natural number or an integer. I'm not sure.


    Thank you for your help so far!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by calcprincess88 View Post
    Ok. So i get what you are saying about the first part. But I still dont get what you are asking when you say to "define for some ." I think n is either a natural number or an integer. I'm not sure.


    Thank you for your help so far!
    I'm just asking what do you mean when you write N(n). I am unfamiliar with the notation. i want to know what it implies. so that i can know how to continue
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by calcprincess88 View Post
    I don't know where to start or how to do this proof. Can someone please help me?

    Prove by induction on n that if r < n and f:N(r)--> N(n), then f is not onto N(n). (Where N is the natural numbers)

    Thank you for your help!
    Induction Hypothesis: P(n):=" if r < n and f:N(r)--> N(n), then f is not onto N(n)"

    Claim: P(n+1):=" if r < n+1 and f:N(r)--> N(n+1), then f is not onto N(n+1)"

    There are two cases to consider:
    1) \forall i \in N(r), f(i) \neq n+1

    2) \exists i \in N(r), f(i) = n+1

    Case 1:
    \forall i \in N(r), f(i) \neq n+1
    Trivially not onto.

    Case 2:
    \exists i \in N(r), f(i) = n+1
    Define a function g:N(r) --> N(n), such that
    \forall i \in N(r)[\text{ with }f(i)\neq n+1],  g(i)=f(i) .
    \forall i \in N(r)[\text{ with }f(i)=n+1],  g(i)=n .
    By Induction Hypothesis on g, there exists a m \in N(n), such that \forall i \in N(r), g(i) \neq m. But then g(i) = f(i). So the conclusion follows.

    Afterthought: I think this proof is not completely right. You can proceed in a similar manner. You have to take care of a small detail in case 2. Anyway can you spot the mistake?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    Lord of certain Rings
    Isomorphism's Avatar
    Joined
    Dec 2007
    From
    IISc, Bangalore
    Posts
    1,465
    Thanks
    6
    Quote Originally Posted by Jhevon View Post
    I'm just asking what do you mean when you write N(n). I am unfamiliar with the notation. i want to know what it implies. so that i can know how to continue
    I think she means:
    N(n) = \{i \in \mathbb{N}: i \leq n\}
    Follow Math Help Forum on Facebook and Google+

  9. #9
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by Isomorphism View Post
    I think she means:
    N(n) = \{i \in \mathbb{N}: i \leq n\}
    I thought so (though i probably would have used <, i don't know why, it's probably stupid), but I wasn't sure. I didn't want to go ahead and do something and make a fool out of myself...again...i've already done it a dozen times this week. People are going to start to wonder why i'm a helper.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 4
    Last Post: October 11th 2011, 08:22 AM
  2. Proof by Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 16th 2010, 01:09 PM
  3. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  4. Proof by Induction??
    Posted in the Algebra Forum
    Replies: 1
    Last Post: October 6th 2008, 04:55 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 02:20 PM

Search Tags


/mathhelpforum @mathhelpforum