Set of Elementary Real Numbers Without Elementary Combination

Your idea works, which is because of the non-trivial fact $\sqrt{p_n}\notin\Bbb Q[\sqrt 2,\sqrt 3,\ldots,\sqrt{p_{n-1}}]$. To show this, I'd resort to Galois theory, but maybe this special case allows something more elementary?

Let $p$ be a prime and $S$ be the set of real numbers of the form $a_1\sqrt{m_1}+\ldots+a_n\sqrt{m_N}$, where $a_i\in\Bbb Q$ and $1,m_1,\ldots, m_n$ are distinct square-free integers not divisible by $p$. The set $S$

• contains $\sqrt q$ for all primes $q\ne p$, obviously
• is closed under $+$ and $-$, obviously
• is a bit less obviously closed under multiplication, but noting that $a\sqrt m\cdot a'\sqrt{m'}=aa'\gcd(m,m')\sqrt{\frac m{\gcd(m,m')}\frac {m'}{\gcd(m,m')}}$ helps
• is even less obviously closed under division: Let $q_1,\ldots, q_r$ be the primes occuring in the radicands $m_i$. We can write $a_1\sqrt{m_1}+\ldots +a_n\sqrt{m_n}$ as $\alpha+\beta\sqrt {q_r}$, where only $q_1,\ldots, q_{r-1}$ occur in the radicands used for $\alpha$ or $\beta$. Then $(\alpha+\beta\sqrt {q_r})(\alpha-\beta\sqrt {q_r})=\alpha^2-q_r\beta^2$ and by induction on $r$, we may assume that $\alpha^2-q_r\beta^2$ has an inverse in $S$; multiplying it with $\alpha-q_r\sqrt \beta$ gives us an inverse of the original number

We conclude that $\sqrt p$ cannot be obtained from all other $\sqrt q$ by means of $+,-,\cdot,/$.

EDIT: After the fact, I noticed that one also needs to prove (once more, by induction) that $a_1\sqrt{m_1}+\ldots +a_n\sqrt{m_n}=0$ only if all $a_i=0$. Without this, it may happen that $\alpha-\beta\sqrt{q_r}=0$.

AC is trivially not needed to get a finite set; use induction and the fact that there are only countably many arithmetic expressions involving $n$ reals, to find some real that is not equal to any them.

It turns out that no choice is needed to get a countable set either. Let $x_n$ be the (unique) real in $[0,1)$ whose $k$-th binary digit is $1$ iff $k$ is in the $n$-th Turing jump. By the unsolvability of the halting problem relative to any jump, it is clear that $x_n$ cannot even be computed from $x_{0..n-1}$, much less be equal to some arithmetic expression involving them. Furthermore, if any $x_k$ is equal to some arithmetic expression involving $x_{0..k-1}$ and $x_{k+1..n}$, for some minimal $n$, then $x_n$ is a root of some non-zero polynomial with coefficients computable from $x_{0..n-1}$, and thus is computable from them, which is impossible. Therefore none of the $x_n$ can be equal to some arithmetic expression involving the others.

Well you can make a diagonalization argument to get $\omega_1$ many such numbers strictly through counting.

Choose an arbitrary $a_0$ and close off under $(*,+,-,/)$ this gives you a set $A_1$ that has countable size. Now assume that you have already chosen $a_i$ independent for $i< k$. Let $A_k$ be the closure of $\{a_i\}_{i<k}$ under $(*,+,-,/)$ then $A_k$ is still countable (countable iterations over countable base set with finite signature). So choose $a_{k}\in \mathbb{R}\setminus A_k$.

The above shows you can get a countable set. But it's not hard to continue. The successor stage works just as above. At a limit $\beta$ you just take $A_\beta=\bigcup_{\alpha<\beta}A_\alpha$ and then choose $a_\beta\in\mathbb{R}\setminus A_\beta$.

You can actually go all the way to $\mathfrak{c}$ in this way.

The existence can also be proved in a non-constructive manner by noticing that if we have some set or real numbers $A$ such that $|A|<\mathfrak{c}$ then it's closure still has size less than $\mathfrak{c}$.

Note: I'm assuming choice (AC) throughout here.