Cardinality of infinity (2)

[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} <-> R².
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!

 

[slider142]

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} <-> R².
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?

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.

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...

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?

 

[kingwinner]

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.

Let f: R²->{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?)

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?

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 R² countable?
The justification that I get in the solutions is that "Countable squares of unit sides covers R², and |[0,1]x[0,1]|=c, so |R²|=c", but I don't get it, how do you know that the number of squares to cover R² 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...

 

[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.

 

[kingwinner]

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 vertcal line x= a so the set of all vertical lines is of cardinality "only" c so that does not affect the answer.

Say A={y=ax+b, a,b E R}
Let f: R²->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 R² has cardnality c. How does it follow from the theorem: a countable union of sets of cardinality c has cardnality c?

 

[HallsofIvy]

Say A={y=ax+b, a,b E R}
Let f: R²->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...

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

Now I am struggling to understand why R² has cardnality c. How does it follow from the theorem: a countable union of sets of cardinality c has cardnality c?

There is another theorem that says that the Cartesian product of a two sets with cardinality c has cardinality c.

 

[kingwinner]

Let A={y=ax+b, a,b E R}, B={x=c, c E R}

Let f: R²->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| = |R²| = 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, |R²| = 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 R² is countable? How can a countable number of unit squares cover R²?

Thanks for any help!

 

[HallsofIvy]

Let A={y=ax+b, a,b E R}, B={x=c, c E R}

Let f: R²->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| = |R²| = 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, |R²| = 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] is countable, along with theorem (*), imply that R² is countable? How can a countable number of unit squares cover R²?

Thanks for any help!

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

But you certainly can cover R² 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 R²

 

[kingwinner]

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

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

But you certainly can cover R² 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 R²

Is it because Z x Z is countable?

 

[HallsofIvy]

Yes, exactly.

 

[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.

 

[HallsofIvy]

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