# countable sets help

In each item below, you may rely on the earlier items.

A real number r is called algebraic if there exists a polynomial $P(x) = a_nx_n + \cdots + a_2x_2 + a_1x + a_0$ whose coefficients $a_0, \ldots, a_n$ are integers and are not all zero, such that $P(r) = 0$. A real number is called transcendental if it is not algebraic. A root of a polynomial $P(x)$ is a number $r$ such that $P(r) = 0$. Thus, a number is algebraic if it is a root of some polynomial with integer coefficients.

"At most countable" means countable or finite. We recall that if $X_1, X_2, \ldots,$ is a countable collection of sets, and each set $X_i$ is at most countable, then the union $X_1 \cup X_2 \cup \cdots$ is at most countable.

(1) Show that every rational number is algebraic. (Hint: given a rational number, find an appropriate polynomial of degree one.) Also, show that $\sqrt{2}$ and $2^\frac{1}{3}$ are algebraic.

(2) Prove by induction on $n$ that if $C_0, \ldots , C_n$ is a finite collection of countable sets then the Cartesian product $C_0 \times \cdots \times C_n = \{f(a_0, \ldots , a_n) \mid a_i \in C_i\text{ for each }i\}$ is countable. (For $n = 1$ write $C_0 \times C_1$ as a countable union of countable sets.)

(3) Use (2) to prove that, for each $n$, the set of polynomials of degree $n$ whose coefficients are integers is countable.

(4) Fact: a polynomial $P(x)$ of degree $n$ has at most $n$ real roots. Use this fact to prove that the set of algebraic real numbers is countable.

(5) Prove that there exists a real number that is transcendental.

-
Note that a countable set may be finite, by definition. – Git Gud Feb 15 '13 at 7:16
Regarding $(1)$, you needto show that any rational number $r$ is a root of a polynomial with integer coefficients. Any rational number $r$ is such that there exist $m,n\in \Bbb Z$ such that $r=\displaystyle \frac{m}{n}$. Now note that $r=\displaystyle \frac{m}{n}\Longrightarrow nr=m\Longrightarrow \Longrightarrow nr-m=0$. Can you now find one of the polynomials you're looking for? Similarly, if you let $\alpha =\sqrt{2}$, you get $\alpha ^2 -2=0$. The remaining one is similar. – Git Gud Feb 15 '13 at 7:23
@MathGeek : At which point do you first fail to understand? – Michael Hardy Feb 15 '13 at 12:20
it is the wordings actually that are not making sense to me like for question 5 i dont even know what its talking about. or like for number 1, it didnt make sense now it actually does and i know what its talking about – MathGeek Feb 15 '13 at 14:54

Hint

1. $a/b$ is solution of $bx-a=0$.

2. Since $C_0$, $C_1$ is countable, there exists injective map $f_0:C_0\to\mathbb{N}$, $f_1:C_1\to\mathbb{N}$. Define $f:C_0\times C_1 \to \mathbb{N}^2$ such that $f(c_0,c_1)=(f_0(c_0),f_1(c_1))$. Then $f$ is injective. And $\mathbb{N}^2$ is countable. And If $C_0\times\cdots\times C_n$ and $C_{n+1}$ is countable, take $C_0 \mapsto C_0\times\cdots\times C_n$, $C_1\mapsto C_{n+1}$ and imitate before proof.

3. $a_nx^n+\cdots+a_1 x+a_0 \mapsto (a_0,a_1,\cdots,a_n)$

4. Let $p(x)=a_nx^n+\cdots+a_1x+a_0$, and $p(x)$ have (distinct) $k$ roots $x_1<x_2<\cdots<x_k$. And by the given fact, $k\le n$.

5. Sef of all real number is uncountable.

-