# Cardinality of infinity

Dick
Homework Helper
Yes, by definition a constructiblle point in the xy-plane is a point such that both components are constructible numbers and I am wondering how I can find a bijection between {constructible numbers} and {constructible points in the xy-plane}.
The constructible numbers in R have cardinality N. So the constructible points have cardinality NxN. Doesn't this remind you of the previous problem?

The constructible numbers in R have cardinality N. So the constructible points have cardinality NxN. Doesn't this remind you of the previous problem?
Let C={constructible numbers}
|C|=|N| is true
But does this imply |CxC|=|NxN|? How to justify? (sorry if this is obvious to you, I am a beginner in this topic, and I am just trying to be careful...)

And here we can't really find an explicit 1-1, onto function between {constructible numbers} and {constructible points in the xy-plane}, right?

Dick
Homework Helper
The points in the plane are pairs of constructible numbers, (x,y) where x and y are constructible. I don't see why you don't think this is the same thing as CxC where C is the constructibles. Yes, you would be hard put to find an explicit 1-1 function. But proving it exists is a different matter from actually writing it down in detail. And the proof it exists is all you need.

Hurkyl
Staff Emeritus
Gold Member
kingwinner: Are you aware that, for any sets S and T, $|S \times T| = |S| \cdot |T|$?

kingwinner: Are you aware that, for any sets S and T, $|S \times T| = |S| \cdot |T|$?
No, I am not aware of this...there is very few that I know about this topic so far... :(

The points in the plane are pairs of constructible numbers, (x,y) where x and y are constructible. I don't see why you don't think this is the same thing as CxC where C is the constructibles. Yes, you would be hard put to find an explicit 1-1 function. But proving it exists is a different matter from actually writing it down in detail. And the proof it exists is all you need.
I can see that it's the same thing as CxC, but you said that:
"The constructible numbers in R have cardinality N. So the constructible points have cardinality NxN"

C={constructible numbers}
N={natural numbers}

|C|=|N| => |CxC|=|NxN| ? <----I can't follow this step...

Dick
Homework Helper
If |C|=|N| then there is a bijective map f:C->N. Use it to construct a bijective map from CxC to NxN.

2) Find the cardinality of the set of all finite subsets of Q.

Attempt:
Let S={all finite subsets of Q}
For every k E N, let Ak = {all subsets of Q having EXACTLY k elements}

S is equal to

U Ak U {empty set}
k=1
...
=======================
Something is funny here, S is set of all finite subsets of Q, but in the union of Ak, we are summing fom 1 up to infinity (so S may have infinitely many elements???) How can they be totally inconsistent (one is finite and the other is infinite)? Is there a mistake somewhere?

I am puzzled...could someone please explain?

HallsofIvy
Homework Helper
2) Find the cardinality of the set of all finite subsets of Q.

Attempt:
Let S={all finite subsets of Q}
For every k E N, let Ak = {all subsets of Q having EXACTLY k elements}

S is equal to

U Ak U {empty set}
k=1
...
=======================
Something is funny here, S is set of all finite subsets of Q, but in the union of Ak, we are summing fom 1 up to infinity (so S may have infinitely many elements???) How can they be totally inconsistent (one is finite and the other is infinite)? Is there a mistake somewhere?

I am puzzled...could someone please explain?
Why are you puzzled? Q is infinite itself so if S is set of all finite subsets of Q, there must be an infinite number of such sets! One can be finite and the other infinite, because they are different things: each set in S is finite but S itself is infinite because the number of sets in S is infinite.

Try the same thing for the natural numbers. Let S be the collection of all "singleton" sets: S= {{1}, {2}, {3}, ...}. Every set in S is finite but S itself is infinite.

Why are you puzzled? Q is infinite itself so if S is set of all finite subsets of Q, there must be an infinite number of such sets! One can be finite and the other infinite, because they are different things: each set in S is finite but S itself is infinite because the number of sets in S is infinite.

Try the same thing for the natural numbers. Let S be the collection of all "singleton" sets: S= {{1}, {2}, {3}, ...}. Every set in S is finite but S itself is infinite.

OK, I can now see that S has infintely many elements.

But if I define the S = union of Ak (k summing fom 1 up to infinity), will S contain all subsets of Q with infinitely many elements? k is supposed to be finite, but from the union, k can be all the way from 1 to infinity. How come?

Dick
Homework Helper
OK, I can now see that S has infintely many elements.

But if I define the S = union of Ak (k summing fom 1 up to infinity), will S contain all subsets of Q with infinitely many elements? k is supposed to be finite, but from the union, k can be all the way from 1 to infinity. How come?
I don't think you are giving these questions much thought before you post them. Answer this one yourself. WHY doesn't S contain an infinite subset? Try answering it instead of asking it.

Last edited:
I don't think you are giving these questions much thought before you post them. Answer this one yourself. WHY doesn't S contain an infinite subset? Try answering it instead of asking it.
S certainly doesn't contain an infinite subset by definition, or by the statement of the problem.

But when I try to write this as S = union of Ak (k summing fom 1 up to infinity) U {empty set}
Then the right side would contain the infinite subset since k is summing from 1 to infinity.

On the other hand, if I write it as S = union of Ak (k summing fom 1 up to n) U {empty set}, then the right side would not contain An+1, An+2, etc...

So either of them seem to be an incorrect description of S, but what else can I do? Dick
Homework Helper
The notation S = union of Ak (k from 1 up to infinity) does not mean that you include A_infinity, you just union over all finite k. That fits with your notion of what S should be as you described in the first sentence, right?

Last edited:
The notation S = union of Ak (k from 1 up to infinity) does not mean that you include A_infinity, you just union over all finite k. That fits with your notion of what S should be as you described in the first sentence, right?
Is this simply a matter of notation/convention? Although it is an infinite union, it can still never go up to infinity?

However, I think the following is true:
union of Ak (k from 1 up to ∞) = A1 U A2 U...UA
And by definition, Ak = {all subsets of Q having k elements}
Now put k=∞, UA contains infinite subsets of Q

I think I am missing something...

Dick