Cardinality of Transcendental Numbers

[kingwinner]

Homework Statement

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.

Homework Equations

N/A

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!

 

[kingwinner]

Cardinality of Algebraic Numbers

Homework Statement

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!

Homework Equations

The Attempt at a Solution

N/A

 

[CompuChip]

1) So, if you'd want to be very precise, you'd have to say that
$$\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|$$
(where Zⁿ means Z x Z x ... x Z - n times).

To show that this is actually $\left|\mathbb{Z}^{n + 1}\right|$ you could write down a function like
$$\phi: (a_n, a_{n - 1}, \ldots, a_1, a_0) \mapsto (f(a_n), a_{n - 1}, \ldots, a_1, a_0)$$
where
$$f(k) = \begin{cases} k & \text{ if } k < 0 \\ k - 1 & \text{ if } k > 0$$
and check that $\phi$ 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 $\mathbb{Z} \subset A$). 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 $|\mathbb{Z}^n| = |\mathbb{Z}|$, which is a rather standard result proven in every textbook.

 

[HallsofIvy]

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.

 

[rrogers]

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.

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

 

[kingwinner]

1) So, if you'd want to be very precise, you'd have to say that
$$\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|$$
(where Zⁿ means Z x Z x ... x Z - n times).

To show that this is actually $\left|\mathbb{Z}^{n + 1}\right|$ you could write down a function like
$$\phi: (a_n, a_{n - 1}, \ldots, a_1, a_0) \mapsto (f(a_n), a_{n - 1}, \ldots, a_1, a_0)$$
where
$$f(k) = \begin{cases} k & \text{ if } k < 0 \\ k - 1 & \text{ if } k > 0$$
and check that $\phi$ 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 $\mathbb{Z} \subset A$). 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 $|\mathbb{Z}^n| = |\mathbb{Z}|$, which is a rather standard result proven in every textbook.

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

 

[kingwinner]

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.

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!

 

[CompuChip]

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

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

Once you have that, you can use induction on n to prove that |Zⁿ| = |Z|

 

[kingwinner]

2) Yes, I understand that |Zⁿ|=|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!

 

[Hurkyl]

Do you understand |N| + |N| = |Z|?

 

[kingwinner]

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!

 

[Hurkyl]

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.

 

[CompuChip]

2) Yes, I understand that |Zⁿ|=|Z|.
But what I don't understand is: why |Z| = n |Z|?

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

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
$$|{1} \times \mathbb{Z}| \le |{1, 2, \ldots, n} \times \mathbb{Z}| \le |\mathbb{Z} \times \mathbb{Z}|$$
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 ({ p_i | i in Z })ⁿ <> { r_i,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 A_n 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). [/size]

 

[kingwinner]

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!

 

[rrogers]

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)

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.