0
$\begingroup$

This question already has an answer here:

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.

$\endgroup$

marked as duplicate by Chris Brooks, C. Falcon, Juniven, Adam Hughes, R_D Feb 24 '17 at 4:42

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

  • $\begingroup$ I am asking to validate whether my proof is correct.. $\endgroup$ – i squared - Keep it Real Feb 23 '17 at 21:23
  • $\begingroup$ 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$ $\endgroup$ – fleablood Feb 23 '17 at 21:52
  • $\begingroup$ @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 $\endgroup$ – i squared - Keep it Real Feb 23 '17 at 21:56
  • $\begingroup$ 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. $\endgroup$ – fleablood Feb 23 '17 at 22:09
  • $\begingroup$ $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. $\endgroup$ – fleablood Feb 23 '17 at 22:15
3
$\begingroup$

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]).

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – i squared - Keep it Real Feb 23 '17 at 21:42
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.