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

Cardinality of infinity

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

Answers and Replies

HallsofIvy
Science Advisor
Homework Helper
41,734
893
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
Science Advisor
Homework Helper
26,258
618
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.
 
1,270
0
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
Science Advisor
Homework Helper
26,258
618
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'?
 
1,270
0
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.
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:
1,270
0
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
Science Advisor
Homework Helper
26,258
618
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...
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.
 
1,270
0
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: 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:
Dick
Science Advisor
Homework Helper
26,258
618
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.
 
1,270
0
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
Science Advisor
Homework Helper
26,258
618
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.
 
1,270
0
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
Science Advisor
Homework Helper
26,258
618
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,270
0
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: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:
1,270
0
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
Science Advisor
Homework Helper
41,734
893
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
Science Advisor
Homework Helper
26,258
618
(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...
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.
 
1,270
0
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?
 
1,270
0
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 & 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?
 
HallsofIvy
Science Advisor
Homework Helper
41,734
893
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
Science Advisor
Homework Helper
26,258
618
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?
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.
 
1,270
0
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 suprise usual?
 
1,270
0
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
Science Advisor
Homework Helper
26,258
618
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 suprise usual?
Very usual. Weren't you surprised that Q had the same cardinality as N??
 

Related Threads for: 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
6
Views
2K
  • Last Post
Replies
4
Views
1K
Top