# Prove that transcendental numbers exist: Are there less paniful ways of doing it?

I've found this exercise on Boolos' Logic and Computability:

A real number $x$ is called algebraic if it is a solution to some equation of the form:

$$c_{\small d}x^{\small d}+c_{\small d-1}x^{\small d-1}+c_{\small d-2}x^{\small d-2}+\text{ }...\text{ }+c_{\small 2}x^{\small 2}+c_{\small 1}x+c_{\small 0}=0$$

Where the $c_i$ are rational numbers and $c_d\neq 0$. For instance, for any rational number $r$, the number $r$ itself is algebraic, since it is the solution to $x-r=0$; and the square root $\sqrt{r}$ or $r$ is algebraic, since it is a solution to $x^2-r=0$.

(b) A real number that is not algebraic is called transcendental. Prove that transcendental numbers exist.

This exercise is nice, but I don't know if I know enough to do it. I thought it was simple to do because it's located on an early chapter of the mentioned book, but searching for it on Wikipedia I've seen that it seems to be difficult to do it - So, the fact that it's located on an early chapter of Boolos' book could indicate that perhaps there is a simple way that is show in the book and I'm unaware of such way, is that it?

I'll use the tags logic and computability because of the title of the book.

Edit: Oh, I forgot one thing, I don't know if it's a good idea or if it's possible, but is there a way of proving it pretending I don't know that such numbers do exist with antecedence? I guess it's easier if you know they exist beforehand although I don't know if it's possible to do that way.

-
Existence as opposed to finding a transcendental number is key here. – Git Gud Sep 15 '13 at 0:21
You use the phrase "less painful" in the title but you never provide the example you're thinking of that you want proofs to be "less painful" than... – anon Sep 15 '13 at 0:32
@anon Well, Perhaps trying to find $\pi$ or $e$ - and using the fail to do so to conclude such thing. But the answer below seems to be way easier. – Voyska Sep 15 '13 at 0:35
This problem also appeared in Rudin's Principles of Mathematical Analysis. (1) Rudin defined algebraic numbers as solutions of integer polynomials (I think this is equivalent to the definition above), and (2) Rudin gave the following hint: how many integer polynomials $c_0 + c_1 x + \ldots + c_d x^d$ are there such that $|c_0| + |c_1| + \ldots + |c_d| = n$, for each positive integer $n$? – Elliott Sep 4 '14 at 23:53

You presumably know the real numbers are uncountable. It is not hard to show the algebraic numbers are countable. This immediately implies your desired result.

-
This seems like the right answer if and only if un/countability has been referred to in Boolos's text. Can anyone confirm or deny that this is the case? – Pete L. Clark Sep 15 '13 at 0:24
Note that this proof is constructive. You can - explicitly - cook up a transcendental number going through this proof (unions of countable sets, diagonal argument, etc.). – Martin Brandenburg Sep 15 '13 at 0:24
@GustavoBandeira Can you prove that the set of roots of linear polynomials is countable? The set of roots of quadratics? The set of roots of $n$th degree polynomials? Since any algebraic number must be a root of a polynomial with some degree $k$th, what do you know about countable unions of countable sets? – Potato Sep 15 '13 at 0:30
@Gustavo By "such a proposition" do you mean the claim that algebraic numbers are countable, or the claim that this fact immediately implies the desired result, or what exactly? – anon Sep 15 '13 at 0:30
If no transcendental real numbers exist, then all real numbers are algebraic, so the set of reals is countable, contradicting the fact that reals are uncountable. – anon Sep 15 '13 at 0:33

Sketch:

-Show that $\mathbb Q$ is countable.

-Show that $\mathbb R$ is uncountable.

-Show that there is a bijection between $\mathbb Q[x]$ and the set of all finite sequences of rationals. The set of all finite sequences of a countable set is countable, therefore $\mathbb Q[x]$ is countable.

Hint: Inject $\mathbb Q$ into $\mathbb Q[x]$ and $\mathbb Q[x]$ into the set described above. Use that this set and $\mathbb Q$ have the same cardinal number and Cantor-Bernstein Theorem.

-Show that every non zero polynomial as at most a finite number of roots. Therefore the set of all algebraic complex numbers over $\mathbb Q$ is a countable union of finite sets, therefore it's at most countable.

-Conclude that non algebraic numbers exists, since $|\mathbb Q|<|\mathbb R|$

-

In view of the "computability" tag, it might be worth pointing out that every algebraic real number is computable. So once you know that there are non-computable reals (one of the basic facts of computability theory), you also know that there are transcendental reals.

-