Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Cardinality of Transcendental Numbers

  1. Mar 14, 2010 #1
    1. The problem statement, all variables and given/known data
    Assuming the fact that the set of algebraic numbers is countable, prove that the set of transcendental numbers has the same cardinality R, the set of real numbers.

    2. Relevant equations
    N/A

    3. The attempt at a solution
    Let A be the set of algebraic numbers and T the set of transcendentals. Then R= A U T, so if T was countable then so would R be (because a countable union of countable sets is countable). Contradiction. Thus T is uncountable.

    But this only proves that T is uncountable, and we need to prove MORE than that, namely, |T|=|R|. How to prove this?

    Any help is appreciated!
     
  2. jcsd
  3. Mar 14, 2010 #2
    Cardinality of Algebraic Numbers

    1. The problem statement, all variables and given/known data
    Prove that the set of algebraic numbers is countable.

    Proof:
    Let A be the set of all algebraic numbers.
    Let [tex]A_n[/tex]={x E R : p(x) = 0 for some p a polynomial of degree n with integer coefficients}

    U [tex]A_n[/tex] = A
    n=1

    Consider the n-th degree polynomial
    [tex]a_nx^n+...+a_1x+a_0[/tex], [tex]a_i[/tex] E Z, [tex]a_n[/tex]≠0
    |{[tex](a_n,...,a_1,a_0)[/tex]: [tex]a_i[/tex] E Z, [tex]a_n[/tex]≠0}| = |[tex]Z^{n+1}[/tex]| = |Z| = |N|
    Each such polynomial has at most n roots.
    Therefore, [tex]A_n[/tex] is countable.
    A countable union of countable sets is countable, thus A is countable.
    ============================

    1) I don't understand why |{[tex](a_n,...,a_1,a_0)[/tex]: [tex]a_i[/tex] E Z, [tex]a_n[/tex]≠0}| = |[tex]Z^{n+1}[/tex]|. [tex]a_n[/tex] cannot be 0, so the set on the LHS is a little bit different from [tex]Z^{n+1}[/tex]. How can we formally prove that it has the same cardinality as [tex]Z^{n+1}[/tex]?

    2) Assuming the above, I understand why the set of all polynomials with integer coefficients is countable, but I don't understand why the set of all "roots" of these polynomials, |[tex]A_n[/tex]|, is also countable. I know each polynomial with degree n has at most n roots, but I don't see how it rigorously follows that the set of all "roots" are countable. How can we prove it formally?

    These are the two fine points that I don't understand in this proof.
    I hope someone can clarify these. Thanks for any help!
    2. Relevant equations

    3. The attempt at a solution
    N/A
     
    Last edited: Mar 14, 2010
  4. Mar 14, 2010 #3

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Re: Cardinality of Algebraic Numbers

    1) So, if you'd want to be very precise, you'd have to say that
    [tex]\left| \{ (a_n, \ldots, a_1, a_0): a_i \in \mathbb{Z}, a_n \neq 0 \} \right| = \left| (\mathbb{Z} \setminus \{ 0 \} \right) \times \mathbb{Z}^n \right| [/tex]
    (where Zn means Z x Z x ... x Z - n times).

    To show that this is actually [itex]\left|\mathbb{Z}^{n + 1}\right|[/itex] you could write down a function like
    [tex]\phi: (a_n, a_{n - 1}, \ldots, a_1, a_0) \mapsto (f(a_n), a_{n - 1}, \ldots, a_1, a_0)[/tex]
    where
    [tex]f(k) = \begin{cases} k & \text{ if } k < 0 \\ k - 1 & \text{ if } k > 0[/tex]
    and check that [itex]\phi[/itex] is really a bijection.

    2) Let's suppose for the moment that every polynomial has exactly n roots. That means we are overcounting the number of algebraic numbers, but if this overcounting shows that it is countable, then the real set is definitely countable (or finite, which is also countable - you can rule this out if you want by noting that [itex]\mathbb{Z} \subset A[/itex]). Then the set of algebraic numbers that follows from the set of polynomials of degree n, is exactly n times as large. Since the latter is countable, all you have to do is show that the former is as well. You can do this by showing that [itex]|\mathbb{Z}^n| = |\mathbb{Z}|[/itex], which is a rather standard result proven in every textbook.
     
  5. Mar 14, 2010 #4

    HallsofIvy

    User Avatar
    Science Advisor

    T is a subset of R and so cannot have larger cardinality. The "continuum hypothesis" says that there is no uncountable set with cardinality lower than that of R.

    I note that this was posted twice so I am going to merge the two threads.
     
  6. Mar 14, 2010 #5
    Since the "continuum hypothesis" is not necessarily true I think the problem should be restated.
    Prove that the set R-A (wikipedia says R\A I guess I am totally obsolete) is of the same cardinality as R.
    It's interesting that if Z<B<R then B-A would work as well. This seems to mean that some theorems proven using R could not be reached by generic -A reasoning; unless the continuum hypothesis is evoked or R is explicitly given.
    It's been years since I studied this so please correct me if I am wrong.

    Ray
     
  7. Mar 14, 2010 #6
    Re: Cardinality of Algebraic Numbers

    1) I like your explanation, thanks!

    2) Sorry, I don't understand this.
    I understand why the set of all polynomials with integer coefficients is countable, but I don't understand why the set of all "roots" of these polynomials, |An|, is countable.
    How to prove "rigorously" that n times the cardinality of Z is exactly equal to the carinality of Z? What is the bijection?

    Thanks!
     
  8. Mar 14, 2010 #7
    Hi,
    But the "continuum hypothesis" is not necessarily true.
    Is there any other way to prove that the cardinality of the set of transcendental numbers is exactly equal to the cardinality of the real numbers??

    Thanks!
     
  9. Mar 14, 2010 #8

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    Re: Cardinality of Algebraic Numbers

    There is a very nice proof for |Z x Z| = |Z|. Graphically, it looks like this:
    Rationals.png

    Once you have that, you can use induction on n to prove that |Zn| = |Z|
     
  10. Mar 14, 2010 #9
    2) Yes, I understand that |Zn|=|Z|.
    But what I don't understand is: why |Z| = n |Z|?
    The number of polynomials of degree n is countable, but each of them has at most n roots, so we have to multiply them by n, this would possibly give a larger set, how do we know that it will remain countable? How can we rigorously prove this?

    Thank you!!!
     
  11. Mar 14, 2010 #10

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Do you understand |N| + |N| = |Z|?
     
  12. Mar 14, 2010 #11
    No. Actually my textbook never defined "addition" of infinite cardnalities. The discussion is really basic and is defined in terms of bijections...

    So how do we prove that the set of all ROOTS of polynomials of degree n is countable?? What is the explicit bijection between "the set of all ROOTS of polynomials of degree n" and "the set of all polynomials of degree n"?

    Can someone explain this, please? Thank you!
     
  13. Mar 14, 2010 #12

    Hurkyl

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    One reason we learn cardinal numbers is that arithmetic is much, much, much more convenient than constructing explicit bijections....

    And, IMO, bijections with N are often more conveniently described via writing program that enumerates things, rather than something resembling a function.
     
  14. Mar 15, 2010 #13

    CompuChip

    User Avatar
    Science Advisor
    Homework Helper

    So the set of polynomials of degree n is countable, right? That means we can enumerate the polynomials as { pi | i in Z }.
    Suppose that every polynomial has n roots. Then we can enumerate all the roots of all the polynomials as { ri,j | i in Z; j = 1, 2, .., n }, where ri,j is the jth root of pi.

    The question is then, why is |{1, 2, ..., n} x Z| = |Z|.

    Of course you can copy the "diagonal" argument I posted earlier, changing it a bit. But an even quicker way is probably to note that, since {1} is a subset of {1, 2, ..., n} and {1, 2, .., n} is itself a subset of Z, by some inclusion theorem we must have
    [tex]|{1} \times \mathbb{Z}| \le |{1, 2, \ldots, n} \times \mathbb{Z}| \le |\mathbb{Z} \times \mathbb{Z}|[/tex]
    The less-or-equals sign denotes the ordering of the cardinal numbers here. Since on the left we have simply |Z|, and on the right |Z x Z| = |Z|, the set in the middle must also have cardinality |Z|.

    Note that if you want to be completely rigorous, you need to assume that all the roots of all the polynomials are different, and all the polynomials have precisely n of them, such that you have a bijection from ({ pi | i in Z })n <> { ri,j | i in Z; j = 1, 2, .., n } <> {1, 2, ..., n} x Z. Then when you have it all worked out, you will find that the cardinality of An is at most that of Z (you are overestimating it), and by simple construction you can show that it is not lower (i.e. it is not a finite set).
     
  15. Mar 16, 2010 #14
    Thanks!

    1) But if we have the result of
    Theorem: a countable union of countable sets is countable.

    Can we use this theorem two times and say that a countable union of a countable union of countable sets is countable?
    (The number of roots in each polynomial is countable, take the countable union of that over all polynomials of a fixed degree n with integer coefficients, it is still countable. Then take the countable union of that over all degrees, the resulting set is still countable.)
    Do I have the right idea here? But how can we properly LABEL the above mathematically?


    2) Different polynomials may have some roots that are the same, so it could (theoretically) be the case that we are taking two unions, but at the end we only getting a finite number of roots. How can we rigorously prove that the set of all such roots is actually INFINITE? (i.e. it's countably infinite, not finite)


    Thanks for helping!!!
     
  16. Mar 16, 2010 #15
    Start counting; take a given order n, start assigning the first coefficient all the integers Z, ignore the roots and multiplicities and just order the factors by magnitude throwing out multiplicities, start running through the second coefficient picking the next value from Z and rerunning the first coefficient, and so forth. You are generating a countable set of countable sets as n is increased and the process repeated. Throwing out the multiplicities reduces count a little but every n would still have every element of Z appearing as a root a countable number of times. In fact for your problem it wouldn't matter if the sets were finite.
    As has been mentioned you can't take -A as R unless you assume the "continuum hypothesis" otherwise you just prove that taking the elements of A out of something of higher order doesn't matter much. i.e. you can remove any countable set out of a higher order set and paper over the holes by rearranging the points; Hilbert's hotel.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook