# Homework Help: Cardinality of infinity (2)

1. Apr 5, 2008

### kingwinner

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!

2. Apr 5, 2008

### slider142

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
3. Apr 5, 2008

### kingwinner

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
4. Apr 5, 2008

### HallsofIvy

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
5. Apr 6, 2008

### kingwinner

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?

6. Apr 6, 2008

### HallsofIvy

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.

7. Apr 7, 2008

### kingwinner

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
8. Apr 7, 2008

### HallsofIvy

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

9. Apr 7, 2008

### kingwinner

Yes, I mistyped, I meant it has cardnality c.

Is it because Z x Z is countable?

10. Apr 7, 2008

### HallsofIvy

Yes, exactly.

11. Apr 8, 2008

### kingwinner

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.

12. Apr 8, 2008

### HallsofIvy

What kind of answer do you want? If S and T are empty, then |S||T| is 00 and that is undefined.