Cardinality of Algebraic Numbers

**kingwinner** · March 13th 2010, 11:38 PM

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]

**Drexel28** · March 13th 2010, 11:54 PM

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.

**kingwinner** · March 14th 2010, 01:00 PM

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!

**Jhevon** · March 14th 2010, 01:49 PM

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.

**kingwinner** · March 14th 2010, 02:31 PM

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!

**Plato** · March 14th 2010, 02:36 PM

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?

**kingwinner** · March 14th 2010, 02:46 PM

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?

**Jhevon** · March 14th 2010, 03:07 PM

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|$ ( $f<img src=$ 0,1) \mapsto \mathbb R" alt="f

0,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|$

**kingwinner** · March 14th 2010, 03:50 PM

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!

**Drexel28** · March 14th 2010, 04:21 PM

Originally Posted by kingwinner

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 $\varphi<img src=$ 0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" alt="\varphi

0,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 \varphi<img src=$ 0,1)\to\mathbb{R}-C" alt="w\circ \varphi

0,1)\to\mathbb{R}-C" /> is the composition of two injective functions and thus injective.

**kingwinner** · March 14th 2010, 07:15 PM

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 $\varphi<img src=$ 0,1)\hookrightarrow\mathbb{R}-\mathbb{N}" alt="\varphi

0,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 \varphi<img src=$ 0,1)\to\mathbb{R}-C" alt="w\circ \varphi

0,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)

**Drexel28** · March 14th 2010, 07:21 PM

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?

**kingwinner** · March 14th 2010, 07:30 PM

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!

Thread: Cardinality of Algebraic Numbers

LinkBack

Thread Tools

Display

Cardinality of Algebraic Numbers

Similar Math Help Forum Discussions

Algebraic numbers

Proof: All rational numbers are algebraic numbers

cardinality of the set of all Liouville numbers

Algebraic Numbers

The cardinality of the set of complex numbers

Search Tags