Defining an injective map from the algebraic numbers to the set of integer coefficient polynomials.

Question

Let $P$ be the set of all polynomials with integer coefficients, one variable, and deg $n \ge 1$. A number is said to be algebraic, $\mathbb{A}$, if it is real and the solution to an element of $P$. For a given $a \in \mathbb{A}$, let $f_a(x) = c_1 + c_2 x + c_3 x^2 + \dots$ be the (not necessarily unique) integer coefficient polynomial such that $f_a(a) = 0$ and let $n \in \mathbb{N}$ be the degree of $f_a$.

I am interested in defining an injective map from $\mathbb{A}$ to $P$. My initial thought was to do this with the mapping, $\phi: \mathbb{A} \rightarrow P$ given by, \begin{equation} \phi(a) = f_a \end{equation} I realized this is not an injective map because a given $a \in \mathbb{A}$ likely has more than one $f_a$, so the function is not one-to-one. My idea now is to define a mapping $\psi: \mathbb{A} \rightarrow P$ given by, \begin{equation} \psi(a) = g_a \end{equation} Where $g_a$ is the minimum degree polynomial for which $a$ is a solution. Does this make the map injective?

Answer 1

If you're just trying to show countability of algebraic number, constructing such a map isn't the best idea. One certainly exists, because both the algebraic numbers and the set of polynomials over $\mathbb{Z}$ are countably infinite, but it won't be an obvious one.

For every algebraic integer $\alpha$, there exists a unique minimal polynomial $f_\alpha\in\mathbb{Z}[x]$, where by minimal polynomial we mean monic, irreducible, and contains $\alpha$ as a root. Indeed, $f_\alpha$ is necessarily unique, as if $g_\alpha$ were another such polynomial then $\text{gcd}(f_\alpha, g_\alpha) \neq 1$ as both have $\alpha$ as a root. But since $f_\alpha$ is irreducible, this means that $\text{gcd}(f_\alpha, g_\alpha) = f_\alpha$. For the same reason, $\text{gcd}(f_\alpha, g_\alpha) = g_\alpha$, and so $f_\alpha = g_\alpha$.

But here's the issue: $f_\alpha$ generally has multiple roots, so it's the minimal polynomial for multiple algebraic integers. This is no good! To bypass this, we can just order the real roots of each $f_\alpha$ by size. So say the real roots of $f_\alpha$ are $\alpha_1, \ldots, \alpha_n$ and this is ordered by size. Then, we can construct a map $\phi: \mathbb{A}\to P$ by

$$\phi(\alpha) = (f_\alpha)^n$$ where $n$ is such that $\alpha$ is the $n$th largest real root of $f_\alpha$.

Answer 2

In a comment, you write that you’re trying to show that the algebraic numbers are countable. You don’t need an injective map to $P$ for that – you can just enumerate $P$ and each time you encounter new roots enumerate them all at once.

If you really want one, you can construct an injection to $P$ without using the axiom of choice like this: Enumerate $P$ in a standard way such that infinitely many multiples of each polynomial occur in the sequence; when you encounter a polynomial, map the greatest of its roots that hasn’t been mapped yet to that polynomial.

Answer 3

You can simplify your life by showing

Let $A$ be countable and $R\subset A\times B$ be a relation such that

• for each $a\in A$, $\{\,b\in B\mid aRb\,\}$ is countable
• For each $b\in B$, $\{\,a\in A\mid aRb\,\}$ is non-empty.

Then $B$ is countable.

To see this, use the first bullet point and a diagonal argument to show that $R$ is countable. Then use that the second bullet point gives you a surjection $R\to B$.

Apply this to $A=$ the countable set if non-zero polynomials with integer coefficients and $B=$ the set of (only real, if you prefer) algebraic numbers.