# Cardinality of infinity

1. Apr 3, 2008

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

S is equal to

U Ak 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 Ak 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 Ak is countable for every k E N, how can we prove this?

Any help would be appreciated! Thank you!

2. Apr 3, 2008

### HallsofIvy

Staff Emeritus
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.

3. Apr 3, 2008

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

4. Apr 3, 2008

### kingwinner

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?

5. Apr 3, 2008

### Dick

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

6. Apr 3, 2008

### kingwinner

Ak = {all subsets of Q having exactly k elements}
Need to prove: |Ak| < |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 |Ak| < |N| ?

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

Last edited: Apr 3, 2008
7. Apr 3, 2008

### kingwinner

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?

8. Apr 3, 2008

### Dick

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.

9. Apr 3, 2008

### kingwinner

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

It suffices to prove that Q2 is coutnably infinite.

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

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

Last edited: Apr 4, 2008
10. Apr 3, 2008

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

11. Apr 3, 2008

### kingwinner

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

12. Apr 3, 2008

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

13. Apr 3, 2008

### 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?

14. Apr 3, 2008

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

15. Apr 4, 2008

### kingwinner

(i) OK, so f:A2->Q2 defined by f({r,q})=(max(r,q),min(r,q)) is one-to-one function, but not onto.
This implies |A2|<|Q2|, which means A2 is countable (which is enough for our purpose) since Q2 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 Qk 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...

Last edited: Apr 4, 2008
16. Apr 4, 2008

### kingwinner

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?

17. Apr 4, 2008

### HallsofIvy

Staff Emeritus
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?

18. Apr 4, 2008

### Dick

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.

19. Apr 5, 2008

### kingwinner

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?

20. Apr 5, 2008

### kingwinner

Provided Q & Q2 are countable, then Q3 is countable.
Provided Q & Q3 are countable, then Q4 is countable.
etc...so it's clear that any Qk is countable.

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