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

Cardinality of infinity

  • Thread starter kingwinner
  • Start date
  • #26
Dick
Science Advisor
Homework Helper
26,258
618
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?
 
  • #27
1,270
0
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?
 
  • #28
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
  • #29
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,916
19
kingwinner: Are you aware that, for any sets S and T, [itex]|S \times T| = |S| \cdot |T|[/itex]?
 
  • #30
1,270
0
kingwinner: Are you aware that, for any sets S and T, [itex]|S \times T| = |S| \cdot |T|[/itex]?
No, I am not aware of this...there is very few that I know about this topic so far... :(
 
  • #31
1,270
0
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...
 
  • #32
Dick
Science Advisor
Homework Helper
26,258
618
If |C|=|N| then there is a bijective map f:C->N. Use it to construct a bijective map from CxC to NxN.
 
  • #33
1,270
0
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?
 
  • #34
HallsofIvy
Science Advisor
Homework Helper
41,833
955
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.
 
  • #35
1,270
0
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?
 
  • #36
Dick
Science Advisor
Homework Helper
26,258
618
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:
  • #37
1,270
0
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?:confused:
 
  • #38
Dick
Science Advisor
Homework Helper
26,258
618
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:
  • #39
1,270
0
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...
 
  • #40
Dick
Science Advisor
Homework Helper
26,258
618
I already told you that most people wouldn't include A_infinity. If you insist on reading it that way, then you'll have to find a different way of expressing the union you want.
 

Related Threads on Cardinality of infinity

  • Last Post
Replies
11
Views
5K
  • Last Post
Replies
17
Views
3K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
2
Views
4K
  • Last Post
Replies
6
Views
1K
Replies
5
Views
1K
  • Last Post
Replies
4
Views
1K
  • Last Post
Replies
3
Views
2K
  • Last Post
Replies
6
Views
2K
  • Last Post
Replies
4
Views
1K
Top