# Math Help - Cardinality of Algebraic Numbers

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

2. Originally Posted by kingwinner
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.

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

4. Originally Posted by kingwinner
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.

5. Originally Posted by Jhevon
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!

6. Originally Posted by kingwinner
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?

7. Originally Posted by Plato
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?

8. Originally Posted by kingwinner
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|$ ( $f0,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|$

9. Thanks, I like your proof.

Originally Posted by Jhevon
(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!

10. Originally Posted by kingwinner

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 $\varphi0,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 $w\circ \varphi0,1)\to\mathbb{R}-C" alt="w\circ \varphi0,1)\to\mathbb{R}-C" /> is the composition of two injective functions and thus injective.

11. Originally Posted by Drexel28
Since $C\simeq\mathbb{N}$ there exists some $w:\mathbb{R}-\mathbb{N}\to \mathbb{R}-C$ which is bijective. So, define $\varphi0,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 $w\circ \varphi0,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)

12. Originally Posted by kingwinner
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?

13. Originally Posted by Drexel28
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!