Showing that the set of all algebraic numbers is countable [duplicate]

Is this a valid proof (Problem 1.23)?

Let the roots of a polynomial of $n$th degree (whose coefficients are rational) be written as:

$$P_n^{\mathbb{Q}}$$

and the polynomial is then:

$$a_nx^n+a_{n-1}x^{n-1}+...+a_0x^0$$

where $a_i \in \mathbb{Q}$ where $0 \leq i \leq n$ and $i \in \mathbb{N}$

Then $P_n^{\mathbb{Q}}$ will have at most $n$ roots.

Then the set of all roots is:

$$A = \cup_{n \in \mathbb{N}}P_n^{\mathbb{Q}}$$

Then $A$ is countable because: 1) There is a countable number of the sets of roots of the polynomial by definition i.e. ($\cup_{n \in \mathbb{N}} P_n^{\mathbb{Q}}$). 2) The number of elements in each set is countable.

And we know that the countable union of the countable sets is countable.

EDIT: My question is different to the one linked, because I am merely asking whether my proof is valid.

• I am asking to validate whether my proof is correct..
– Naz
Feb 23, 2017 at 21:23
• I don't think it does work. The number of n degree polynomials is |$\mathbb Q^n$| and so the number of algebraic numbers is $\le \sum n(|\mathbb Q^n|)\n \rightarrow \infty$ but $|Q^{\infty}|$ is uncountable. It's a subtle point and it trips me up every time but there is an obscure hint to not take n degree polynmoials but all polynomials where $|a_n| < M$ Feb 23, 2017 at 21:52
• @fleablood could you please edit your equations. I cannot quite understand in that second part after $|\mathbb {Q}^n|$ what you are trying to say. Thanks
– Naz
Feb 23, 2017 at 21:56
• Hmmm.... I'm tripping up again. For $n$ there is a 1-1 between $Q^n$ and {n-degree polynomials}. And there are at most $n$ roots for each one. So |{solutions to n-degree polynomials}| $\le$ n|{n-degree poynomials}| = n|$Q^n$| which is countable. So alegraic numbers $\cup{solutions to n-degree polynomials} is countabe. ... except ... I'm SURE there is an error. But I'm not sure what it was. Maybe it is that mapping is not surjective so not 1-1 (not by a long shot). But it is injective and that should be enough. I always get confused with this one. Feb 23, 2017 at 22:09 •$A = \cup_{n \in \mathbb{N}}P_n^{\mathbb{Q}}$needs to be rewritten as$A = \cup_{n \in \mathbb{N}}(\cup_{P_n = a_nx^n+ .... + a_0:(a_i \in \mathbb Q)}P_n^{\mathbb Q})$... which is a countable union of a countable union of finite sets which ought to be countable. BUT I can't shake the feeling there is something wrong. Feb 23, 2017 at 22:15 2 Answers The idea is right but the execution needs more precision. Your notation seems to equivocate between: (a) A polynomial of degree n; (b) A set of polynomials of degree n; (c) A set of roots of a polynomial; (d) A set of roots of a set of polynomials. A better phrasing is to take the union, over individual polynomials, of the root sets of each individual polynomial. For this, you need to show that the set of polynomials over$\mathbb{Q}$is countable (you already have the set of roots of a given polynomial is countable [finite actually]). • there is a countable number of$\mathbb{Q}$and so there is a countable number of combinations of$\mathbb{Q}$coefficients in a polynomial, I think – Naz Feb 23, 2017 at 21:42 Okay. I think the biggest problem with what you are attempting to do is that in equating the algebraic numbers to a countable union of countable sets, requires a lot of steps. If$a$is an algebraic number then it is the$i-th$root of an$n$degree polynomial with rational coefficient. So if$a$is a root of an$n$degree polynomial we can map$a$into$\mathbb N_n \times \mathbb Q^{n+1}$where$\phi (a) = (k, (a_0, ....., a_{n})$where$k \in \mathbb N_n = \{1,2,3....,n\}$is the which of the$n$possible roots of the polynomial$a_nx^n + .... + a_1x + a_0$,$a$is. Then the set of alegbraic numbers$A \cong \phi(A) = \{\phi(a)|a \in A\} \subset \cup_{n\in \mathbb N}(\mathbb N_n\times \mathbb Q^{n+1})$. Each$\mathbb N_n\times \mathbb Q^{n+1}$is countable as the countable cross product of countable sets is countable. And so$\phi(A)$is a subset of a countable union of countable sets and is countable. And the$\phi$is a injective map so$A$injectively maps into a countable set. So is countable. A slightly more direct representation is to note: If$a$is a root of$a_nx^n + .... + a_0$then$a$is a root to$b_nx^n + .... + b_0$where if each$a_i = j_i/k_i; j_i, k_i \in \mathbb Z$then$b_i = a_i\text{least common multiple}(k_i)$. So we can define the alegbraic numbers to be the roots of polynomials with integer coefficients. For any integer$N > 0$there are finitely many solutions to$n + |a_0| + .... |a_n| = N; a_n \ne 0; a_i \in \mathbb Z$. Let$B_N = \{a| a \text{ is a root to } a_nx^n + .... + a_0; n + |a_0| + .... |a_n| = N; a_n \ne 0; a_i \in \mathbb Z\}$.$B_N$is a finite set as there are only finitely many such polynomials and each with only finitely many roots. So$A = \cup_{N\in \mathbb N}B_N\$ which is countable as it is the countable union of finite sets.

I don't know. I think the first way, your way, is more direct and obvious but harder to find the exact notation. I've seen the second way presented a lot more often but it seems ... harder to me. But that's probably just me.