Cardinality of infinity

[kingwinner]

1) Consider the xy-plane.
Find the cardinality of the set of constructible points on the x-axis.

Attempt:
Every constructible number is algebraic (i.e. Let A=set of algebraic numbers, C=set of constructible nubmers, then C is a subset of A)
and A is countable.

=> |C|<|A|=|N|
=>|C|<|N|
=> C is either finite OR countably infinite
I believe that C should be an infinite set, but how can I prove this?
Also, is the set {constructible points on the x-axis} an infinite set? How can I prove this? I am stuck here...


=================================


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 A_k = {all subsets of Q having EXACTLY k elements}

S is equal to
∞
U A_k U {empty set}
k=1

k is a natural number, so the union is a union of a countable number of sets.

Theorem: The union of a countable number of countable sets is countable.

So by this theorem, S is countable if we can prove that A_k is countable for every k E N.

S is also infinite, so S is countably infinite, i.e. |S|=|N|
==================

Does this proof work? If so, then it remains to prove that A_k is countable for every k E N, how can we prove this?


Any help would be appreciated! Thank you!

 

[HallsofIvy]

What do you have available to use? For example, can you use the fact that all numbers, algebraic of order a power of 2, are "constructible"? Since that set is obviously infinite, that should make the problem easy.

 

[Dick]

To prove A_k is countable, you need to prove a finite cartesian product of countable sets is countable. Start with two sets, that's just a diagonal argument. Then use induction to get to the finite case.

 

[kingwinner]

What do you have available to use? For example, can you use the fact that all numbers, algebraic of order a power of 2, are "constructible"? Since that set is obviously infinite, that should make the problem easy.

I can't use that fact since it's not taught in my class...

Is there any other way to prove that the set {constructible points on the x-axis} is an infinite set?

 

[Dick]

I can't use that fact since it's not taught in my class...

Is there any other way to prove that the set {constructible points on the x-axis} is an infinite set?

Isn't it easy to show all integers are 'constructible'?

 

[kingwinner]

To prove A_k is countable, you need to prove a finite cartesian product of countable sets is countable. Start with two sets, that's just a diagonal argument. Then use induction to get to the finite case.

A_k = {all subsets of Q having exactly k elements}
Need to prove: |A_k| < |N| for every k E N

But I don't quite get your point...why do we need the Cartesian product?

For example, if k=3, how can we prove that |A_k| < |N| ?

I can't see the connection between Cartesian product and A_k...

 

[kingwinner]

Isn't it easy to show all integers are 'constructible'?

OK, since the set of integers is contained in {constructible points on the x-axis}, and the set of integers is infinite, {constructible points on the x-axis} must be infinite.


But in this question, they are talking about constructible points rather than constructbile numbers, is this going to change the proof?

 

[Dick]

A_k = {all subsets of Q having exactly k elements}
Need to prove: |A_k| < |N| for every k E N

But I don't quite get your point...why do we need the Cartesian product?

For example, if k=3, how can we prove that |A_k| < |N| ?

I can't see the connection...

Because it's easy to construct an injective mapping from A_2 to QxQ. Try it. Then if QxQ is countable, so is A_2. The extension to A_k is pretty obvious.

 

[kingwinner]

Because it's easy to construct an injective mapping from A_2 to QxQ. Try it. Then if QxQ is countable, so is A_2. The extension to A_k is pretty obvious.

Define f({r,q})=(r,q) r,q E Q, then f: A_k->Q² is one-to-one but not onto, so |A_k|<|Q²|

It suffices to prove that Q² is coutnably infinite.

For N², I know how to do:
http://pirate.shu.edu/projects/reals/infinity/graphics/combctbl.gif

But for Q², how can I arrange the array in the right way?

 

[Dick]

I'd be a little careful if I were writing this as a formal proof. I.e. you don't want to say {1,2}->(1,2) and {2,1}->(2,1) since {1,2} and {2,1} are the same set. (Take the elements of the set in sorted order to construct the ordered pair). But you already know Q is countable. So you can write Q={q1,q2,q3,q4...}. You can index all of the elements of Q by an integer. Use the index instead of the rational itself to order the grid.

 

[kingwinner]

I'd be a little careful if I were writing this as a formal proof. I.e. you don't want to say {1,2}->(1,2) and {2,1}->(2,1) since {1,2} and {2,1} are the same set. (Take the elements of the set in sorted order to construct the ordered pair). But you already know Q is countable. So you can write Q={q1,q2,q3,q4...}. You can index all of the elements of Q by an integer. Use the index instead of the rational itself to order the grid.

2) I see the problem, {1,2}->(1,2) and {2,1}->(2,1), but {1,2}={2,1}, so f({r,q})=(r,q), r,q E Q is not even a function, let alone one-to-one.

But I don't get how I can fix this problem.
If we take Q={q1,q2,q3,q4...}, how is this going to change things? I don't understand your strategy of fixing the problem...

 

[Dick]

Define f({r,q})=(max(r,q),min(r,q)). That fixes it. Replace (1,1) in your picture with (q1,q1) replace (1,2) with (q1,q2) etc, etc, etc. That CxC is countable if C is isn't really about the exact nature of C. For ANY countable set C, CxC is countable, using your most excellent diagram.

 

[kingwinner]

1) Every constructible number is algebraic (i.e. Let A=set of algebraic numbers, C=set of constructible nubmers, then C is a subset of A)
and A is countable.

=> |C|<|A|=|N|
=>|C|<|N|
=> C is either finite OR countably infinite
Z is a subset of C and Z is infinite, so C must be infinite
=>|C|=|N|, i.e. C is countably infinite

So I am OK if the question is about consturctible numbers. However, in this problem we are considering constructible points

Every constructible number is algebraic
=> Every constructible point has coordinates that are algebraic numbers.

Now I have to prove that the set {points in the plane with coordinates that are algebraic numbers} is countable. But how? There is a theorem saying that the set of algebraic numbers is countable, but I am not sure how it can be applied in this situtation.

Could somebody help, please?

 

[Dick]

Your problems are not nearly so deep as you seem to think. There is a 1-1 correspondence between POINTS is the plane and pairs of COORDINATES in the plane, isn't there? If you don't believe me, ask Descartes.

 

[kingwinner]

Define f({r,q})=(max(r,q),min(r,q)). That fixes it. Replace (1,1) in your picture with (q1,q1) replace (1,2) with (q1,q2) etc, etc, etc. That CxC is countable if C is isn't really about the exact nature of C. For ANY countable set C, CxC is countable, using your most excellent diagram.

(i) OK, so f:A₂->Q² defined by f({r,q})=(max(r,q),min(r,q)) is one-to-one function, but not onto.
This implies |A₂|<|Q²|, which means A₂ is countable (which is enough for our purpose) since Q² is countable.

(ii) Regrading your Q={q1,q2,q3,q4...}, is it a sequence? Can some of them be the same (e.g.q1=q3) ? I am confused (in general) about the idea of enumeration.
A set S is countable
<=> S is infinite or has the same cardinality as the set of natural numbers
<=> the elements can be listed in a sequence (enumerated), but in sequences some of the elements can be the same, then how can this be a one-to-one mapping from N to S?

(iii) How can I extend the idea in (i) to proving Q^k countable? Yes, this looks obvious, but my instructors may get mad if I don't prove it rigorously. Mathematical induction works for the set of natural numbers which is infinite, but in our case "k" is always finite (because the question says "finite" subsets...), so I don't think induction is going to work...

 

[kingwinner]

Your problems are not nearly so deep as you seem to think. There is a 1-1 correspondence between POINTS is the plane and pairs of COORDINATES in the plane, isn't there? If you don't believe me, ask Descartes.

1) Yes, but all I've proven so far is the the set of constructible numbers is countably infinite.

How can I prove that the set of constructible points is also countably infinte?

 

[HallsofIvy]

1) Yes, but all I've proven so far is the the set of constructible numbers is countably infinite.

How can I prove that the set of constructible points is also countably infinte?

Isn't a "constructible point on the x-axis" simply a point whose x coordinate is constructible? Isn't that an obvious one-to-one correspondence?

 

[Dick]

(i) OK, so f:A₂->Q² defined by f({r,q})=(max(r,q),min(r,q)) is one-to-one function, but not onto.
This implies |A₂|<|Q²|, which means A₂ is countable (which is enough for our purpose) since Q² is countable.

(ii) Regrading your Q={q1,q2,q3,q4...}, is it a sequence? Can some of them be the same (e.g.q1=q3) ? I am confused (in general) about the idea of enumeration.
A set S is countable
<=> S is infinite or has the same cardinality as the set of natural numbers
<=> the elements can be listed in a sequence (enumerated), but in sequences some of the elements can be the same, then how can this be a one-to-one mapping from N to S?

(iii) How can I extend the idea in (i) to proving Q^k countable? Yes, this looks obvious, but my instructors may get mad if I don't prove it rigorously. Mathematical induction works for the set of natural numbers which is infinite, but in our case "k" is always finite (because the question says "finite" subsets...), so I don't think induction is going to work...

I've said this before. I'll put it in caps this time for emphasis. YOU KNOW Q IS COUNTABLE. HENCE THERE IS A BIJECTION OF Q WITH THE INTEGERS. Call that bijection f. Then what I mean by q_k is f(k). So, no, it's not possible e.g. q1=q3. The elements of a sequence can be the same, but this is a special sequence, not ANY sequence. I said this before. FORGET ABOUT PROVING THE SPECIAL CASE Q^k COUNTABLE. PROVE CxD COUNTABLE FOR ANY C AND D THAT ARE COUNTABLE. I.e. take a bijection of C and D with N, say g and h, and define c_k=g(k) and d_k=h(k). Put c_k and d_k into your grid. Now you have CxD is countable. Now for QxQxQ, that's 1-1 with (QxQ)xQ. QxQ is countable, Q is countable, so QxQxQ is countable. Etc.

 

[kingwinner]

Isn't a "constructible point on the x-axis" simply a point whose x coordinate is constructible? Isn't that an obvious one-to-one correspondence?

OK, you're right...so I think in this case it's clear.

Let's modify the problem:
Find the cardinality of the set of constructible points on the xy-plane.

Then ,how can we prove that the set of constructible points on the xy-plane is countably infinite?

 

[kingwinner]

YOU KNOW Q IS COUNTABLE. HENCE THERE IS A BIJECTION OF Q WITH THE INTEGERS. Call that bijection f. Then what I mean by q_k is f(k). So, no, it's not possible e.g. q1=q3. The elements of a sequence can be the same, but this is a special sequence, not ANY sequence. I said this before...Now for QxQxQ, that's 1-1 with (QxQ)xQ. QxQ is countable, Q is countable, so QxQxQ is countable. Etc.

Provided Q & Q² are countable, then Q³ is countable.
Provided Q & Q³ are countable, then Q⁴ is countable.
etc...so it's clear that any Q^k is countable.

Is this rigorous enough? Is it possible to prove this using mathematical induction?

 

[HallsofIvy]

OK, you're right...so I think in this case it's clear.

Let's modify the problem:
Find the cardinality of the set of constructible points on the xy-plane.

Then ,how can we prove that the set of constructible points on the xy-plane is countably infinite?

Okay, what do you mean by "constructiblle point in the xy-plane"? Points such that both components are constructible?

 

[Dick]

Provided Q & Q² are countable, then Q³ is countable.
Provided Q & Q³ are countable, then Q⁴ is countable.
etc...so it's clear that any Q^k is countable.

Is this rigorous enough? Is it possible to prove this using mathematical induction?

Is it possible? You basically just did it. Say 'Q is countable' and show if Q^k is countable, Q^(k+1) is countable and that's the whole proof.

 

[kingwinner]

Is it possible? You basically just did it. Say 'Q is countable' and show if Q^k is countable, Q^(k+1) is countable and that's the whole proof.

So we've proven that the set of all finite subsets of Q has cardnality |N|

The set of all finite subsets of Q seems to have much more elements than Q, yet they have the same cardnality...is this kind of surprise usual?

 

[kingwinner]

Okay, what do you mean by "constructiblle point in the xy-plane"? Points such that both components are constructible?

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}.

 

[Dick]

So we've proven that the set of all finite subsets of Q has cardnality |N|

The set of all finite subsets of Q seems to have much more elements than Q, yet they have the same cardnality...is this kind of surprise usual?

Very usual. Weren't you surprised that Q had the same cardinality as N??

 

[Dick]

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?

 

[kingwinner]

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]

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]

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

 

[kingwinner]

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... :(

 

[kingwinner]

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]

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

 

[kingwinner]

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 A_k U {empty set}
k=1
...
=======================
Something is funny here, S is set of all finite subsets of Q, but in the union of A_k, 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]

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 A_k U {empty set}
k=1
...
=======================
Something is funny here, S is set of all finite subsets of Q, but in the union of A_k, 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.

 

[kingwinner]

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 infinitely many elements.

But if I define the S = union of A_k (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?