1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Cardinality of infinity

  1. Apr 3, 2008 #1
    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:
     
  2. jcsd
  3. Apr 3, 2008 #2

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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.
     
  4. Apr 3, 2008 #3

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  5. Apr 3, 2008 #4
    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?
     
  6. Apr 3, 2008 #5

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    Isn't it easy to show all integers are 'constructible'?
     
  7. Apr 3, 2008 #6
    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
  8. Apr 3, 2008 #7
    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?
     
  9. Apr 3, 2008 #8

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  10. Apr 3, 2008 #9
    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:
    [​IMG]

    But for Q2, how can I arrange the array in the right way?
     
    Last edited: Apr 4, 2008
  11. Apr 3, 2008 #10

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  12. Apr 3, 2008 #11
    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...
     
  13. Apr 3, 2008 #12

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  14. Apr 3, 2008 #13
    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?
     
  15. Apr 3, 2008 #14

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  16. Apr 4, 2008 #15
    (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
  17. Apr 4, 2008 #16
    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?
     
  18. Apr 4, 2008 #17

    HallsofIvy

    User Avatar
    Staff Emeritus
    Science Advisor

    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?
     
  19. Apr 4, 2008 #18

    Dick

    User Avatar
    Science Advisor
    Homework Helper

    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.
     
  20. Apr 5, 2008 #19
    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?
     
  21. Apr 5, 2008 #20
    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?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Cardinality of infinity
  1. Bijection Cardinality (Replies: 2)

  2. Cardinal arithmetic (Replies: 39)

Loading...