Homework Help: Cardnality of Infinite Sets (3)

1) Prove that |NxR|=|R|

I know how to prove that |R|<|NxR|. But I am stuck at proving that |NxR|<|R|. To prove this, I need a one-to-one function f: NxR ->R, but how can I find one?




2) Prove that the cardinality of the set of all finite subsets of the xy-plane is c.

Let S={all finite subsets of the xy-plane}
Let S_k={all finite subsets of the xy-plane with exactly k elements}

But I have some trouble understanding what S actually consists of. What I understand is that S contains points, lines, parabloas, etc.
S={ {(0,1), (5,8), (20,51)}, {y=2x+1 or y=x^2}, {y=2x^3}, ...}
How many elements are in {y=2x+1 or y=x^2}? 1 or 2?


Thank you for any help!

 

1) What theorems can I use? There are very few theorems on this topic that were taught in my class...

 

Unfortunately, no! (it seems that I have to derive everything from scratch:uhh:)

So I think I need to construct a one-to-one function f: NxR ->R or f: NxR ->[0,1]
(note: |[0,1]|=|R|=c, this is something I can take it for granted)
Or is there any other method?

 

If we can prove this theorem, then I think we're done with question 1.

What does the proof look like?

 

1) Yes, I know that |RxR|=|R| (I'm glad).

f:NxR->RxR
f(n,r)=(n,r), nEN, rER
f is one-to-one => |NxR|<|RxR|=|R|

g: R->NxR
g(r)=(1,r), rER
g is one-to-one => |R|<|NxR|

Thus, |NxR|=|R|.

I think this is correct. Thanks for your great idea!

 

2) Let S={all finite subsets of the xy-plane}
Let S_k={all finite subsets of the xy-plane with exactly k elements}

S=U S_K U {empty set}
k>1

Countable union of sets of cardnality c has cardnality c, so if we can prove that |S_k|=c, then we're done, but how can we prove this?

Thanks for any help!

 

2) I think we need R^(2k), right?

f: S_k -> R^(2k)
f({(r11,r12),...,(rk1,rk2)})=(r11,r12,...,rk1,rk2)
But no repeated elements can be in the set, how can I make sure this is satisifed while not missing any elements in the domain S_k?

If f is one-to-one, then |S_k|<|R^(2k)|=|R|=c

 

But I can't miss any elements in the domain space S_k.

f: S_k -> R^(2k)
f({(r11,r12),...,(rk1,rk2)})=(r11,r12,...,rk1,rk2)

If I put the restriction r11<r21<...<rk1 and r12<r22<rk2, then this would ensure that there are no repeated elements in the set, but this would miss out some elements in S_k, e.g. r11<r21, but r12>r22 is an element in S_2, but does not satisfy the restriction.

 

2) I can't believe it's going to get this complicated when nothing similar is done in my lectures and notes (there is no textbook in this course) and it appeared as a past exam question with very limited time to think. It's understandable when you actually see how to do it, but very hard to come up on my own.

All we've proven so far is |S_k|<|R^(2k)|=|R|=c.

How to prove the other direction: |S_k|>c ?

 

Yes, |R^2|={all points in xy-plane} is uncountable, but S_k={all finite subsets of the xy-plane with exactly k elements}, S_k is "smaller than" R^2.

 

I think I am concentrating too much of my attention on the difference between a set and ordered tuple. For a set, {(1,1),(2,2)} and {(2,2),(1,1)} are the same, and also {(1,1),(1,1)} is not allowed, this leads me to the wrong conclusion that S_k is "smaller than" R^2. Sorry about that.

But I think I've found another reason:
Define f: R->S_k by
f(r)={(r,r),(r+1,r+1),...,(r+k-1,r+k-1)}, r E R
Then f is one-to-one.
=> c=|R|<|S_k|