• Support PF! Buy your school textbooks, materials and every day products Here!

Cardinality of infinity (2)

  • Thread starter kingwinner
  • Start date
1,270
0
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:
 

Answers and Replies

1,005
65
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?
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?
 
Last edited:
1,270
0
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: 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?)


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 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:
HallsofIvy
Science Advisor
Homework Helper
41,734
893
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:
1,270
0
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: 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?
 
HallsofIvy
Science Advisor
Homework Helper
41,734
893
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...
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.

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?
There is another theorem that says that the Cartesian product of a two sets with cardinality c has cardinality c.
 
1,270
0
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:
HallsofIvy
Science Advisor
Homework Helper
41,734
893
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] is countable, along with theorem (*), imply that R2 is countable? How can a countable number of unit squares cover R2?

Thanks for any help!
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
 
1,270
0
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 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
Is it because Z x Z is countable?
 
HallsofIvy
Science Advisor
Homework Helper
41,734
893
Yes, exactly.
 
1,270
0
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
Science Advisor
Homework Helper
41,734
893
What kind of answer do you want? If S and T are empty, then |S||T| is 00 and that is undefined.
 

Related Threads for: Cardinality of infinity (2)

  • Last Post
2
Replies
39
Views
9K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
7
Views
5K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
6
Views
1K
Replies
5
Views
1K
  • Last Post
Replies
6
Views
2K
Top