Results 1 to 6 of 6

Math Help - Proof of cardinality

  1. #1
    Junior Member
    Joined
    May 2009
    Posts
    57

    Proof of cardinality

    I know I must be missing something, since I've tried for the past 4 hours to understand some cardinality proofs, but they just don't make sense to me.

    I know that if two sets have the same cardinality then the function that maps one set to the other must be a bijective function. I also know that for a function to be bijective, it has to be injective and surjective. I also understand completely what injective, surjective and bijective functions are... but I still can't make sense of the cardinality proofs given to me. Here is an example:

    The set of all natural numbers including zero (call it N(o)) has the same cardinality as the set of natural numbers (call it N). To prove this, we have to find a bijective mapping from N(o) --> N.

    Define f: N(o) --> N, where n |--> n+1
    Let f be one-to-one. Let n, m be elements of N(o) such that f(n) = f(m), then n+1 = m+1, and hence n = m, so f is injective.
    Let f be onto. Let n be an element of N, then n-1 is an element of N(o) and f(n-1) = n-1+1 = n. Hence f is surjective.
    Therefore f is bijective and N(o) has the same cardinality as N.

    That all fine and well, I can regurgitate that proof for other cardinality tests, but I don't truly know how what was stated above is enough to prove that a function f is bijective.

    Take for instance this example:

    Define f: R --> R, where x |--> x^2
    This function is clearly not bijective since it is not injective or surjective, but using the same style of proof from above and regurgitating its contents I have the following:

    Let f be one-to-one. Let n, m be elements of R such that f(n)= f(m), then n^2 = m^2 which implies that n = m.
    Let f be onto. Let n be an element of R, then sqrt(n) is an element of R, such that f(sqrt(n)) = (sqrt(n))^2 = n.
    Therefore f is bijective and R has the same cardinality of R.

    I know that my proof was completely false, but how the heck can the first proof be enough to justify that f: N(o) --> N is bijective? I just don't get it!

    If anyone could help me out I would really appreciate it, I'm getting sick of reading and then re-reading the proofs and definitions a million times without understanding why the cardinality proofs are valid.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,642
    Thanks
    1594
    Awards
    1

    Re: Proof of cardinality

    Quote Originally Posted by Alexrey View Post
    I know I must be missing something, since I've tried for the past 4 hours to understand some cardinality proofs, but they just don't make sense to me.

    I know that if two sets have the same cardinality then the function that maps one set to the other must be a bijective function. I also know that for a function to be bijective, it has to be injective and surjective. I also understand completely what injective, surjective and bijective functions are... but I still can't make sense of the cardinality proofs given to me. Here is an example:

    The set of all natural numbers including zero (call it N(o)) has the same cardinality as the set of natural numbers (call it N). To prove this, we have to find a bijective mapping from N(o) --> N.

    Define f: N(o) --> N, where n |--> n+1
    Let f be one-to-one. Let n, m be elements of N(o) such that f(n) = f(m), then n+1 = m+1, and hence n = m, so f is injective.
    Let f be onto. Let n be an element of N, then n-1 is an element of N(o) and f(n-1) = n-1+1 = n. Hence f is surjective.
    Therefore f is bijective and N(o) has the same cardinality as N.

    That all fine and well, I can regurgitate that proof for other cardinality tests, but I don't truly know how what was stated above is enough to prove that a function f is bijective.

    Take for instance this example:

    Define f: R --> R, where x |--> x^2
    This function is clearly not bijective since it is not injective or surjective, but using the same style of proof from above and regurgitating its contents I have the following:

    Let f be one-to-one. Let n, m be elements of R such that f(n)= f(m), then n^2 = m^2 which implies that n = m.
    Let f be onto. Let n be an element of R, then sqrt(n) is an element of R, such that f(sqrt(n)) = (sqrt(n))^2 = n.
    Therefore f is bijective and R has the same cardinality of R.

    I know that my proof was completely false, but how the heck can the first proof be enough to justify that f: N(o) --> N is bijective? I just don't get it!

    If anyone could help me out I would really appreciate it, I'm getting sick of reading and then re-reading the proofs and definitions a million times without understanding why the cardinality proofs are valid.
    Would you kindly state very simply and concisely what are you asking?
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor Also sprach Zarathustra's Avatar
    Joined
    Dec 2009
    From
    Russia
    Posts
    1,506
    Thanks
    1

    Re: Proof of cardinality

    Quote Originally Posted by Alexrey View Post
    I know I must be missing something, since I've tried for the past 4 hours to understand some cardinality proofs, but they just don't make sense to me.

    I know that if two sets have the same cardinality then the function that maps one set to the other must be a bijective function. I also know that for a function to be bijective, it has to be injective and surjective. I also understand completely what injective, surjective and bijective functions are... but I still can't make sense of the cardinality proofs given to me. Here is an example:

    The set of all natural numbers including zero (call it N(o)) has the same cardinality as the set of natural numbers (call it N). To prove this, we have to find a bijective mapping from N(o) --> N.

    Define f: N(o) --> N, where n |--> n+1
    Let f be one-to-one. Let n, m be elements of N(o) such that f(n) = f(m), then n+1 = m+1, and hence n = m, so f is injective.
    Let f be onto. Let n be an element of N, then n-1 is an element of N(o) and f(n-1) = n-1+1 = n. Hence f is surjective.
    Therefore f is bijective and N(o) has the same cardinality as N.

    That all fine and well, I can regurgitate that proof for other cardinality tests, but I don't truly know how what was stated above is enough to prove that a function f is bijective.

    Take for instance this example:

    Define f: R --> R, where x |--> x^2
    This function is clearly not bijective since it is not injective or surjective, but using the same style of proof from above and regurgitating its contents I have the following:

    Let f be one-to-one. Let n, m be elements of R such that f(n)= f(m), then n^2 = m^2 which implies that n = m.
    Let f be onto. Let n be an element of R, then sqrt(n) is an element of R, such that f(sqrt(n)) = (sqrt(n))^2 = n.
    Therefore f is bijective and R has the same cardinality of R.

    I know that my proof was completely false, but how the heck can the first proof be enough to justify that f: N(o) --> N is bijective? I just don't get it!

    If anyone could help me out I would really appreciate it, I'm getting sick of reading and then re-reading the proofs and definitions a million times without understanding why the cardinality proofs are valid.
    I don't understand you.

    f(x)=x^2

    f(-1)=1=f(1)

    So f is clearly not injective.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Senior Member
    Joined
    Feb 2010
    Posts
    466
    Thanks
    4

    Re: Proof of cardinality

    Quote Originally Posted by Alexrey View Post
    if two sets have the same cardinality then the function that maps one set to the other must be a bijective function
    That needs to be restated:

    X and Y have the came cardinality if and only if there exists a bijection between X and Y.

    There is no "the" function that maps one to another, since there are many functions that map one to the other. And for equal cardinality, it is not required that all such functions be bijections but rather it is required only that there exists at least one bijection from one to the other.

    Quote Originally Posted by Alexrey View Post
    Define f: N(o) --> N, where n |--> n+1
    Let f be one-to-one.
    No, don't say "Let f be 1-1." Rather, say, "We need to PROVE that f is is 1-1."

    Quote Originally Posted by Alexrey View Post
    Let f be onto.
    No, don't say "Let f be onto N." Rather, say, "We need to PROVE that f is onto N".

    Quote Originally Posted by Alexrey View Post
    Define f: R --> R, where x |--> x^2

    Let f be one-to-one.
    No, don't say "Let f be 1-1".

    Quote Originally Posted by Alexrey View Post
    n^2 = m^2 which implies that n = m.
    But that's false, as you know.

    Quote Originally Posted by Alexrey View Post
    Let f be onto.
    No, don't say "Let f be onto."

    Quote Originally Posted by Alexrey View Post
    Let n be an element of R, then sqrt(n) is an element of R
    But that's false, as you know.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Nov 2010
    Posts
    193

    Re: Proof of cardinality

    These are two completely different functions. You can't just copy one proof, replace all of the N's with R's and +1's with ^2's, and expect that it should work, or that the two should have anything to do with each other at all.

    They are two different situations and should be treated as such.
    Follow Math Help Forum on Facebook and Google+

  6. #6
    Junior Member
    Joined
    May 2009
    Posts
    57

    Re: Proof of cardinality

    Maybe I need to just wrap my head around it a bit more. It just seems like the only thing that the proof is doing is restating the definitions of surjectivity and injectivity.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. cardinality proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: August 2nd 2010, 02:34 AM
  2. Proof: Cardinality Question
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 13th 2010, 12:35 AM
  3. Cardinality Inequality Proof
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 3rd 2009, 07:41 PM
  4. finite cardinality proof
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: November 25th 2008, 08:56 PM
  5. cardinality proof
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: September 19th 2008, 08:52 PM

Search Tags


/mathhelpforum @mathhelpforum