Results 1 to 13 of 13

Math Help - Cardinality of Algebraic Numbers

  1. #1
    Senior Member
    Joined
    Jan 2009
    Posts
    404

    Arrow Cardinality of Algebraic Numbers

    Prove that the set of algebraic numbers is countable.

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

    U A_n = A
    n=1

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

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

    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, | A_n|, 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!


    [note: also under discussion in math links forum]
    Last edited by kingwinner; March 14th 2010 at 12:38 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Prove that the set of algebraic numbers is countable.

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

    U A_n = A
    n=1

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

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

    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" to these polynomials, | A_n|, 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!


    [note: also under discussion in math links forum]
    You would agree that S_n(a_0,\cdots,a_n)=\left\{x\in\mathbb{R}:a_0+a_1x  +\cdots+a_n x^n=0,\text{ }a_k\in\mathbb{Z}\right\} is finite, right? And obviously each a\in\mathbb{A} belongs to some S_n(a_0,\cdots,a_n) right? Thus, \mathbb{A}\subseteq\bigcup_{n=1}^{\infty}\bigcup_{  (a_0,\cdots,a_n)\in\mathbb{Z}^n}S_n(a_0,\cdots,a_n  ). But the right hand side is the countable union of the countable union of finite sets and thus countable. The conclusion follows.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Thanks!

    A related problem:

    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.

    Attempt:
    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|, i.e. the cardinality of the set of transcendental numbers is exactly equal to the cardinality of the real numbers. How to prove this??

    Any help is appreciated!
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by kingwinner View Post
    Thanks!

    A related problem:

    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.

    Attempt:
    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|, i.e. the cardinality of the set of transcendental numbers is exactly equal to the cardinality of the real numbers. How to prove this??

    Any help is appreciated!
    Well, it depends on what you have to go on or what you can use. Presumably you know that |\mathbb R - C | = |\mathbb R| ? where C is a countable subset of \mathbb R (If not, you can use the Schroeder-Bernstein theorem to show this). Then just note that |T| = |\mathbb R - A| = |\mathbb R|.

    If you assume the continuum hypothesis, which you probably shouldn't to be safe, you can note that |T| \le |\mathbb R|, and since T is uncountable (which you proved above), it must mean |T| = |\mathbb R| by the hypothesis.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Jhevon View Post
    Well, it depends on what you have to go on or what you can use. Presumably you know that |\mathbb R - C | = |\mathbb R| ? where C is a countable subset of \mathbb R (If not, you can use the Schroeder-Bernstein theorem to show this). Then just note that |T| = |\mathbb R - A| = |\mathbb R|.

    If you assume the continuum hypothesis, which you probably shouldn't to be safe, you can note that |T| \le |\mathbb R|, and since T is uncountable (which you proved above), it must mean |T| = |\mathbb R| by the hypothesis.
    OK, but how to prove that if C is a countable, then|R \ C| =|R|? I haven't seen this result before...

    thanks!
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Aug 2006
    Posts
    18,390
    Thanks
    1476
    Awards
    1
    Quote Originally Posted by kingwinner View Post
    OK, but how to prove that if C is a countable, then|R \ C| =|R|? I haven't seen this result before...
    You know that \mathbb{R}=C\cup (\mathbb{R}\setminus C). Right?
    What would it imply if \mathbb{R}\setminus C were also countable?
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Plato View Post
    You know that \mathbb{R}=C\cup (\mathbb{R}\setminus C). Right?
    What would it imply if \mathbb{R}\setminus C were also countable?
    That would be a contradiction, so we can say that |R\C| is uncountable. But this ends up having the exact same trouble as in my attempt above.

    What we need to prove is that |R\C| is EXACTLY equal to |R|. How?
    Follow Math Help Forum on Facebook and Google+

  8. #8
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by kingwinner View Post
    That would be a contradiction, so we can say that |R\C| is uncountable. But this ends up having the exact same trouble as in my attempt above.

    What we need to prove is that |R\C| is EXACTLY equal to |R|. How?
    Recall the Schroeder-Bernstein Theorem: If A and B are sets such that |A| \le |B| and |B| \le |A|, then |A| = |B|.

    Also recall that |(0,1)| = |\mathbb R| ( 0,1) \mapsto \mathbb R" alt="f0,1) \mapsto \mathbb R" /> defined by f(x) = \frac {1 - 2x}{x^2 - x} is a bijective function that maps the open interval (0,1) onto \mathbb R)

    Now, clearly, if C is a countable subset of \mathbb R, we have

    (1) |\mathbb R| \ge |\mathbb R - C| and

    (2) |\mathbb R - C| \ge |(0,1)| (The reals minus a countable set should be at least as big as the reals minus an uncountable one)

    But since |(0,1)| = |\mathbb R|, (1) tells us that |\mathbb R| = |(0,1)| \ge |\mathbb R - C|. But then we have |\mathbb R - C| \le |(0,1)| and |(0,1)| \le |\mathbb R - C|, which implies |\mathbb R - C| = |(0,1)| = |\mathbb R| by the Schroeder-Bernstein Theorem.

    Taking C = A in your problem yields that |T| = |\mathbb R|
    Follow Math Help Forum on Facebook and Google+

  9. #9
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Thanks, I like your proof.

    Quote Originally Posted by Jhevon View Post
    (2) |\mathbb R - C| \ge |(0,1)| (The reals minus a countable set should be at least as big as the reals minus an uncountable one)
    This is the only point I'm having trouble now. I understand this intuitively; nobody should doubt why this is true.
    But the precise definition says |A|≤|B| iff there is a one-to-one map f:A->B. How can we rigorously prove, i.e. define a one-to-one map from (0,1) into R \ C?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

  10. #10
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    Thanks, I like your proof.


    This is the only point I'm having trouble now. I understand this intuitively; nobody should doubt why this is true.
    But the precise definition says |A|≤|B| iff there is a one-to-one map f:A->B. How can we rigorously prove, i.e. define a one-to-one map from (0,1) into R \ C?

    Thanks!
    Since C\simeq\mathbb{N} there exists some w:\mathbb{R}-\mathbb{N}\to \mathbb{R}-C which is bijective. So, define 0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" alt="\varphi0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" /> by the inclusion mapping x\mapsto x. This is clearly both well-defined (since (0,1)\cap\mathbb{N}=\varnothing) and injective. So, then 0,1)\to\mathbb{R}-C" alt="w\circ \varphi0,1)\to\mathbb{R}-C" /> is the composition of two injective functions and thus injective.
    Follow Math Help Forum on Facebook and Google+

  11. #11
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    Since C\simeq\mathbb{N} there exists some w:\mathbb{R}-\mathbb{N}\to \mathbb{R}-C which is bijective. So, define 0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" alt="\varphi0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" /> by the inclusion mapping x\mapsto x. This is clearly both well-defined (since (0,1)\cap\mathbb{N}=\varnothing) and injective. So, then 0,1)\to\mathbb{R}-C" alt="w\circ \varphi0,1)\to\mathbb{R}-C" /> is the composition of two injective functions and thus injective.
    By definition, since |N|=|C|, there exists a bijection between N and C, but how to find the explicit bijection between R\N and R\C?
    (C is countable)
    Follow Math Help Forum on Facebook and Google+

  12. #12
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by kingwinner View Post
    By definition, since |N|=|C|, there exists a bijection between N and C, but how to find the explicit bijection between R\N and R\C??
    (where C is countable)
    Have you tried to find one or make a convincing argument for why you don't need to construct an EXACT bijection?
    Follow Math Help Forum on Facebook and Google+

  13. #13
    Senior Member
    Joined
    Jan 2009
    Posts
    404
    Quote Originally Posted by Drexel28 View Post
    Have you tried to find one or make a convincing argument for why you don't need to construct an EXACT bijection?
    Hi,
    I understand that |N|=|C|, so there exists a bijection bewteen N and C, but there is some gap in my understanding as to why |R\N| = |R\C|. It is intutively believable, but I don't see how it rigorously follows.

    Is it provable in general that
    If |A|=|C| and |B|=|D|,
    then |A\B| = |C\D| ?

    If so, what is the way to do a formal proof on statements like this?

    Thanks!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algebraic numbers
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: October 13th 2010, 03:56 AM
  2. Proof: All rational numbers are algebraic numbers
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 5th 2010, 10:26 AM
  3. cardinality of the set of all Liouville numbers
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: September 2nd 2010, 02:51 AM
  4. Algebraic Numbers
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: April 1st 2010, 09:21 AM
  5. The cardinality of the set of complex numbers
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: December 4th 2009, 08:27 PM

Search Tags


/mathhelpforum @mathhelpforum