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

Question

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.

Answer 1

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.

Answer 2

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

Answer 3

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.