1. Not finding help here? Sign up for a free 30min 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!

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) [​IMG]

    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
    Staff Emeritus
    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: 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
    Staff Emeritus
    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
    Staff Emeritus
    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
    Staff Emeritus
    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
    Staff Emeritus
    Science Advisor

    What kind of answer do you want? If S and T are empty, then |S||T| is 00 and that is undefined.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?