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

Cardnality of Infinite Sets (3)

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

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
To prove this, I need a one-to-one function f: NxR ->R
No you don't. In order to prove this, you could, for example, invoke theorems that don't require you to explicitly construct such a function.
 
  • #3
1,270
0
No you don't. In order to prove this, you could, for example, invoke theorems that don't require you to explicitly construct such a function.
1) What theorems can I use? There are very few theorems on this topic that were taught in my class...
 
  • #4
Dick
Science Advisor
Homework Helper
26,258
618
Possibly something like if card(A)<card(B) and A and B are infinite, then card(AxB)=card(B). Do you have that?
 
  • #5
1,270
0
Possibly something like if card(A)<card(B) and A and B are infinite, then card(AxB)=card(B). Do you have that?
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?
 
  • #6
1,270
0
Possibly something like if card(A)<card(B) and A and B are infinite, then card(AxB)=card(B). Do you have that?
If we can prove this theorem, then I think we're done with question 1.

What does the proof look like?
 
  • #7
179
0
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?
Spell it out. By {y=2x+1 or y=x^2}, what you mean is {(x, y) | y=2x+1 or y=x^2}. So there are infinitely many points in this set, not only 1 or 2.

What are the strategies you use to prove that a set has cardinality c? Can you assume that the set is countably infinite and then get a contradiction?
 
  • #8
179
0
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?
So for this function you need to "separate" the elements of N and the elements of R in a way that you can get them back by just looking at elements of R. Consider

f(n, r) = n + r / 10^(the number of non-zero digits left of the decimal place in r)

What I'm doing here is putting the n stuff to the left of the decimal, and the r stuff to the right. Is this a bijection?
 
  • #9
Dick
Science Advisor
Homework Helper
26,258
618
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?
If you just want to show |NxR|<=|R|, how about using that |RxR|=|R|? You've proved that, I think. Now you just need an injection NxR->RxR.
 
  • #10
1,270
0
If you just want to show |NxR|<=|R|, how about using that |RxR|=|R|? You've proved that, I think. Now you just need an injection NxR->RxR.
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!
 
  • #11
1,270
0
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!
 
  • #12
Dick
Science Advisor
Homework Helper
26,258
618
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!
You're welcome. Actually constructing an explicit bijection in cases like this is tedious and really doesn't teach you anything. Try to avoid it.
 
  • #13
Dick
Science Advisor
Homework Helper
26,258
618
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!
How about trying to find an injection from S_k into a set like RxRxRxRxRx... How many copies of R do you need?
 
  • #14
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
17
For the record, there is a slick way to generate an injection from NxR to R. First, observe that (0, 1) is bijective with R....
 
  • #15
1,270
0
How about trying to find an injection from S_k into a set like RxRxRxRxRx... How many copies of R do you need?
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
 
  • #16
359
3
f:Nx[0,1) -> [1,infinity) given by
f(n,x)=n+x
is your desired bijection.
 
  • #17
Dick
Science Advisor
Homework Helper
26,258
618
It's ok if you miss elements in R^(2k). We don't need a bijection to conclude |S_k|<=|R^(2k)|. Just an injection.
 
  • #18
1,270
0
It's ok if you miss elements in R^(2k). We don't need a bijection to conclude |S_k|<=|R^(2k)|. Just an injection.
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.
 
  • #19
Dick
Science Advisor
Homework Helper
26,258
618
I see what you are saying. You need to order the points in an element of S_k to make the map well defined. I overlooked that. Sort them lexicographically (as in dictionary order). I.e. sort first by the first coordinate, then within cases where the first coordinate is equal by the second coordinate etc etc. That's a well defined ordering. The problem is a little deeper than I thought. But still not 'hard'. Then map them to R^(2k).
 
  • #20
1,270
0
I see what you are saying. You need to order the points in an element of S_k to make the map well defined. I overlooked that. Sort them lexicographically (as in dictionary order). I.e. sort first by the first coordinate, then within cases where the first coordinate is equal by the second coordinate etc etc. That's a well defined ordering. The problem is a little deeper than I thought. But still not 'hard'. Then map them to R^(2k).
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 ?
 
  • #21
Dick
Science Advisor
Homework Helper
26,258
618
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 ?
You REALLY shouldn't ask something that easy. It makes it harder to take you seriously. The points in the xy-plane have cardinality c.
 
Last edited:
  • #22
1,270
0
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.
 
  • #23
Dick
Science Advisor
Homework Helper
26,258
618
You are joking, right? Ha, ha! S_1 is "equal to" R^2. How can S_k be "smaller than" R^2????? Now, I'm having a hard time taking you seriously. I warned you.
 
Last edited:
  • #24
1,270
0
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|
 
  • #25
Dick
Science Advisor
Homework Helper
26,258
618
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|
That's more like it!
 

Related Threads for: Cardnality of Infinite Sets (3)

  • Last Post
Replies
7
Views
2K
  • Last Post
2
Replies
34
Views
4K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
8
Views
944
  • Last Post
Replies
11
Views
1K
  • Last Post
Replies
2
Views
1K
Top