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: Cardinality of infinity (2)

  1. Apr 5, 2008 #1
    I am still struggling with the topic of cardinality, it would be nice if someone could help:

    1) http://www.geocities.com/asdfasdf23135/absmath2.jpg

    In the solutions , they said that{y=ax+b|a,b E R} <-> R2.
    But I am wondering...what is the actual mapping that gives one-to-one correspondence (1-1, onto)? How can we define such a map?

    Also, I don't understand the last line of the solutions at all. In particular, c+c=c? How come? I am feeling very uncomfortable about this...





    2) Show that if S and T are finite sets, then the set of all functions from S to T has |T||S| many elements.

    My idea: Fix an element of S, there are |T| possible ways to map this element of S to an element of T. S has |S| many elements, so we have |T| x |T| x ... x |T| (|S| times)=|T||S| ways to determine a function from S to T, and thus |T||S| elements in the set of all functions from S to T.

    But what if S and T are "empty sets"? How can I prove the statement in these cases?


    Thanks for any help!:smile:
     
  2. jcsd
  3. Apr 5, 2008 #2
    How do you specify the equation of a particular line? How do you identify a particular point in the plane? This should give you the mapping; he has given it to you in the curly braces.

    c is the cardinality of the set of all real numbers. He's simply saying that the union of these two sets is has the same cardinality; there is a bijection between the set of all real numbers and this set. Can you find one?
     
    Last edited: Apr 5, 2008
  4. Apr 5, 2008 #3
    Let f: R2->{y=ax+b, a,b E R} be the bijection defined by f(a,b)=ax+b, a,b E R. Is this the correct map? How can we prove that this is onto? (is there any systematic way to prove onto?)


    OK, I think I've missed a theorem: a countable union of sets of cardinality c has cardnality c. Now, I get the general idea.

    First of all, why is R2 countable?
    The justification that I get in the solutions is that "Countable squares of unit sides covers R2, and |[0,1]x[0,1]|=c, so |R2|=c", but I don't get it, how do you know that the number of squares to cover R2 is countable?

    And I am sorry, I can't figure out the bijection between {all real numbers} and {all lines in xy-plane}, I am having a pretty hard time on finding these bijections...
     
    Last edited: Apr 5, 2008
  5. Apr 5, 2008 #4

    HallsofIvy

    User Avatar
    Science Advisor

    Actually, (a,b) mapped to the line y= ax+ b is NOT onto- it misses the vertical lines. However, there is an obvious correspondence between real numbers a and the vertical line x= a so the set of all vertical lines is of cardinality "only" c so that does not affect the answer.
     
    Last edited by a moderator: Apr 6, 2008
  6. Apr 6, 2008 #5
    Say A={y=ax+b, a,b E R}
    Let f: R2->A be defined by f(a,b)=ax+b, a,b E R, then it will be onto A, or simply onto, right? In general f: U->V is onto iff (image of U)= V, that's the definition of onto, I believe...

    Now I am struggling to understand why R2 has cardnality c. How does it follow from the theorem: a countable union of sets of cardinality c has cardnality c?
     
  7. Apr 6, 2008 #6

    HallsofIvy

    User Avatar
    Science Advisor

    Yes, but my point was that the set of all "ax+ b" is NOT equivalent to the set of all lines in R2- it does not include any vertical lines which cannot be written in that form.

    There is another theorem that says that the Cartesian product of a two sets with cardinality c has cardinality c.
     
  8. Apr 7, 2008 #7
    Let A={y=ax+b, a,b E R}, B={x=c, c E R}

    Let f: R2->A be the bijection defined by f(a,b)=ax+b, a,b E R
    Let g: R->B be the bijection defined by f(c)=c, c E R

    Thus |A| = |R2| = c
    |B| = |R| = c

    Theorem (*): a countable union of sets of cardinality c has cardnality c.
    So |A U B| = c

    I think this is the general idea of the proof. However, |R2| = c needs justification.
    The theorem "Cartesian product of a two sets with cardinality c has cardinality c" unfortunately is not taught in my class so I don't think I can use it right now.

    How does the fact that the unit square [0,1]x[0,1] has cardnality c, along with theorem (*), imply that R2 is countable? How can a countable number of unit squares cover R2?

    Thanks for any help!
     
    Last edited: Apr 7, 2008
  9. Apr 7, 2008 #8

    HallsofIvy

    User Avatar
    Science Advisor

    Did you mistype? The unit square, like R, is not countable!

    But you certainly can cover R2 with a countable number of squares. Place a unit square with left lower corner on (n, m) with n and m integers. That's a countable number of squares that covers all of R2
     
  10. Apr 7, 2008 #9
    Yes, I mistyped, I meant it has cardnality c.

    Is it because Z x Z is countable?
     
  11. Apr 7, 2008 #10

    HallsofIvy

    User Avatar
    Science Advisor

    Yes, exactly.
     
  12. Apr 8, 2008 #11
    Thank you!

    Does anyone have any idea about question 2? (for the cases in which S and T are "empty sets")
    The question says "if S and T are finite sets...", and finite sets can be empty or non-empty, I have proved the statement for the non-empty cases.
     
  13. Apr 8, 2008 #12

    HallsofIvy

    User Avatar
    Science Advisor

    What kind of answer do you want? If S and T are empty, then |S||T| is 00 and that is undefined.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook