I am not too familiar with infinites and I don't trust myself with them, I am not sure if any step I took supposed something that I shouldn't have. Below I am presenting an exercise in the book "Mathematics++" and my proof.
The statement
We recall that real numbers $\xi_1,\dots, \xi_n$ are algebraically independent (over the rational) if there is no nonzero polynomial $f\in\mathbb{Q}[x_1,\dots,x_n]$ with $f(\xi_1,\dots, \xi_n)=0$. Prove that for every $n$ there exist $n$ algebraically independent real numbers. Hint: one can use a cardinality argument or a measure argument, for example.
My proof
Suppose, for the sake of contradiction, that for a number $n$, all $n$-tuples $\xi\in\mathbb{R}^n$ are algebraically dependent.
Let $F:\mathbb{R}^n\to \mathbb{Q}[x_1,\dots,x_n]$ be a function which maps a tuple $\xi$ to a nonzero polynomial $f\in\mathbb{Q}[x_1,\dots,x_n]$ such that $f(\xi) = 0$ (for example we can choose the polynomial of smallest degree and of smallest lexilographic order of coefficients, but I don't think those detail need to be clarified).
Given $F$, and since $\mathbb{Q}[x_1,\dots,x_n]$ is a countable set, we can find a way to count $\mathbb{R}^n$. Indeed, let's enumerate the polynomials in $\mathbb{Q}[x_1,\dots,x_n]$ as $Q =\{q_1, q_2\dots \}$. Let $i$ iterate through $\{1, 2\dots\}$, for a polynomial $q_i$ consider the set $F^{-1}(q_i)=\{\xi\in\mathbb{R}^n\ |\ F(\xi) = q_i\}$. Since $q_i$ can only have a finite amount of roots, $F^{-1}(q_i)$ is finite and so is countable. That way for a specific $i$, we can enumerate the tuples $\xi\in F^{-1}(q_i)$. Since every $\xi\in\mathbb{R}^n$ is assiged to a polynomial $F(\xi)$, we will eventually count all of $\mathbb{R}^n$, which is a contradiction since $\mathbb{R}$ is uncountable.
Your idea works if you use induction. Once you have $\xi_1, \dots, \xi_n$ that are algebraically independent, observe that $\{x \mid \xi_1, \dots, \xi_n, x$ are not algebraically independent$\}$ is countable. That's because there are only countably many polynomials with rational coefficients, and each polynomial with a non-zero coefficient for at least one term containing $x$ corresponds to only finitely many choices of $x$ (since $\xi_1, \dots, \xi_n$ are fixed).
By the way, the axiom of choice isn't needed for this argument since the finitely many $x\text{'s}$ for each polynomial can be ordered linearly using the usual ordering on $\mathbb R.$