Similar to Proving that the set of algebraic numbers is countable without AC "A complex number $z$ is said to be algebraic if there are integers $a_0,\dots,a_n$, not all zero, such that $ a_0 z^n + a_1 z^{n-1} + \cdots + a_{n-1}z + a_n = 0. $ Prove that the set of algebraic numbers is countable. Prove that there are real numbers which are not algebraic. Note: you can assume that a polynomial of degree $n$ over a field has at most $n$ roots in the field."
I'm not familiar with Axiom of Choice so I'll attempt to proof it without. Any feedback about my proof would be appreciated as I'm still inexperienced with proofs in general.
Proof:
Let $A$ be the set of all integers. From a previous example (in the textbook) $A$ is countable. Then the values of $(a_0, \dots, a_n)$ forms an $n$-tuple, where $a_k \in A(k=1,\dots ,n)$. Then it suffices to prove that the set of all possible $n$-tuples, $B$ is countable as the set of all algebraic sets is a subset of $B$. $ \textbf{Theorem: }\text{Every infinite subset of a countable set $A$ is countable.} $ So to prove that any subset of a countable set is also countable, then we want to show that any finite subset of a countable set is also countable. But this is obvious from the definition as all finite sets are also countable. Then the set of algebraic numbers is countable.
Now if $z \in \mathbb{R}$ then algebraic numbers satisfy the polynomial with roots in $\mathbb{R}$. Suppose $\forall z \in \mathbb{R}$, $z$ is algebraic. Then for any $r \in \mathbb{R}$, the above equation evaluates to $0$ for $z=r$. Then $r$ is a root for the polynomial $a_0 r^n + a_1 r^{n-1} + \cdots a_{n-1} r + a_n$. If $\mathbb{R}$ is a field, then a polynomial of degree $n$ over $\mathbb{R}$ has at most $n$ roots. Instead of proving all of the field axioms for $\mathbb{R}$ we cite a theorem from the previous chapter: $ \textbf{Theorem: }\text{There exists an ordered field R which has the least-upper-bound property.} $ Then there are an infinite number of roots for the polynomial $a_0 r^n + a_1 r^{n-1} + \cdots a_{n-1} r + a_n$. Contradiction.