Results 1 to 2 of 2

Math Help - induction help please

  1. #1
    Newbie
    Joined
    Nov 2005
    Posts
    4

    induction help please

    Let Nk= {1,2,,k} be a finite set with k elements. This problems shows that if n, r elements of N with n > r, then there is no one-to-one function from Nn to Nr. We prove this by induction on n ≥ 2 for the following statement.
    (Pn): For all r with 1 ≤ r < n, there is no one-to-one function from Nn to Nr.
    a. The first step covers the general case when r=1 and any n>r.
    Prove that if n > r=1, then there is no one-to-one function from Nn to Nr.
    b. Show that the base case (P2) is true.
    c. Assume the induction hypothesis (Pn) is true and prove that (Pn+1) is true.
    Hint: If r ≥ 2 and f: Nn+1 to Nr were one-to-one, then the restriction of f to Nn into Nr \ {f(n+1)} would be one-to-one. You may also use the fact that there is a bijection from Nr \{f(n+1)} to Nr-1.
    d. Conclude that (Pn) is true for all n≥ 2.
    e. Prove that if n,r is an element of N with n not = r, then Nn does not have the same cardinality as Nr.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Grand Panjandrum
    Joined
    Nov 2005
    From
    someplace
    Posts
    14,972
    Thanks
    4
    This is fairly easy, as you are lead by the hand through the proof:

    (Pn): For all r with 1 ≤ r < n, there is no one-to-one function from Nn to Nr.

    Let Nk= {1,2,,k} be a finite set with k elements. This problems shows that if n, r elements of N with n > r, then there is no one-to-one function from Nn to Nr. We prove this by induction on n = 2 for the following statement.
    (Pn): For all r with 1 = r < n, there is no one-to-one function from Nn to Nr.


    a. The first step covers the general case when r=1 and any n>r.
    Prove that if n > r=1, then there is no one-to-one function from Nn to Nr.
    We will take:

    (Pn): For all n and r in \mathbb{N} with 1 \leq r < n, there is no one-to-one function
    from N_n to N_r.

    Suppose there is a one-to-one function f_{n,r} from N_n to N_r where r=1 and n>r.
    Then 1 belongs to N_n as does 2. Then by definition of a one-to-one function f_{n,r}(1) \neq f_{n,r}(2),
    but f_{n,r}(1) = 1, as does f_{n,r}(2) as this is the only element in N_r, a contradiction, so there can be no
    such function.

    b. Show that the base case (P2) is true.
    Part a shows that for all n>1, there is no one-to-one function between
    N_n and N_1. Let n=2 and this is a proof that P(2) is true.

    c. Assume the induction hypothesis (Pn) is true and prove that (Pn+1) is true.
    Hint: If r = 2 and f: Nn+1 to Nr were one-to-one, then the restriction of f to Nn into Nr \ {f(n+1)} would be one-to-one. You may also use the fact that there is a bijection from Nr \{f(n+1)} to Nr-1.
    Suppose that for some n \geq 2 P(n) is true and that P(n+1) is false.
    Let f_{n+1,r} be a one-to-one function between N_{n+1} and N_r, r<n, which
    exists by supposition. Then the restriction of f_{n+1,r} to N_n is a one-to-one
    function from N_n to N_r, but this contradict the supposition that P(n) is true.
    Hence if P(n) is true so is P(n+1).

    d. Conclude that (Pn) is true for all n= 2.
    By b P(2) is true, by c if P(n) is true so is P(n+1), hence
    by the principle of induction P(n) is true for all n \geq 2.

    e. Prove that if n,r is an element of N with n not = r, then Nn does not have the same cardinality as Nr.
    Two sets A and B have the same cardinality if there exits a one-to-one
    function from A to B and a one-to-one function from B to A.

    If n \neq r without loss of generality we may assume n>r,
    and so there is no one-to-one function from N_n to N_r
    and so they do not have the same cardinality.

    (We may assume n>r because either n>r or
    r>n, and in the latter case the same argument goes through
    but with n and r interchanged.)

    RonL
    Last edited by CaptainBlack; December 5th 2005 at 11:04 AM.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Strong induction vs. structural induction?
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: April 21st 2011, 01:36 AM
  2. Replies: 10
    Last Post: June 29th 2010, 01:10 PM
  3. induction help
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: April 19th 2010, 06:39 AM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 10:33 PM
  5. Induction!
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: March 7th 2008, 05:10 PM

Search Tags


/mathhelpforum @mathhelpforum