Find a set of $n$ real numbers such that none can be created by combining the others with elementary operations ($+, -, \times, /$).


This question came up in my attempt to prove an $n$ dimensional version of the fundamental theorem of algebra; however, I am interested in the answer to this regardless of the relevance it has to the associated question.


I have thought about this a bit, and so far my best guess is the square roots of the first $n$ primes. Clearly, this fulfills the above property on just multiplication, but I am not sure how to prove this for addition, and especially for a combination of the two. It would probably involve some very strong statements about sums of square roots, but I'm not sure how to proceed. Any help would be appreciated. (I'm also not sure how to tag this, as I don't know what branch of math questions like this belong to. If anyone could help there that'd be appreciated as well.)

  • As far as "an $n$-dimensional version of the fundamental theorem of algebra", you might look up the Hilbert Nullstellensatz: one of the formulations says essentially that a system of polynomial equations in $n$ complex variables has a solution, unless there's an "obvious reason" that the system is inconsistent, i.e. for $f_1(x_1, \ldots, x_n) = \cdots = f_m(x_1, \ldots, x_n) = 0$, such an "obvious inconsistency" would consist of polynomials $g_1, \ldots, g_m$ such that $g_1 f_1 + \cdots + g_m f_m = 1$. – Daniel Schepler Oct 15 at 20:54
  • @DanielSchepler thank you, it's an interesting read. I'm not sure it applies to the generalization I'm trying to prove though. In particular, I'm trying to prove that for any polynomial in $n$ variables (and integer coefficients for simplicity), there is a unique way to factor it into the form $(x_n - P_1)(x_n-P_2)...(x_n-P_k)$ where each $P_i$ is a polynomial in the remaining $n-1$ variables. (I'm going to ask you not to try and help me with this, as I would like to come up with the proof myself) – DreamConspiracy Oct 15 at 21:19
  • At DRF's follow-up question Asaf states that von Neumann constructed an explicit uncountable set of algebraically independent reals without using the axiom of choice, but I guess the proof requires much higher-level mathematics. – user21820 Oct 16 at 9:03
up vote 13 down vote accepted

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$.

  • +1 much nicer than my set, but also smaller.:) – DRF Oct 15 at 14:08
  • Thank you, this is exactly what I was looking for. – DreamConspiracy Oct 15 at 14:11

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.

  • 1
    Very cool use of Turing jumps. – DRF Oct 15 at 18:33
  • 1
    @DRF: When I have a Turing hammer, everything looks like computational nails. =D – user21820 Oct 15 at 18:38
  • This is akin to "If I can't have it, no one can". – orlp Oct 16 at 7:47
  • @orlp: Sorry, I don't get your comment/joke. – user21820 Oct 16 at 8:55
  • @user21820 Well, we are facing an "adversary" that wants to compute the next element of the set with simple operations. And then you come along and say "not only you don't get to compute this number, no one gets to" :) – orlp Oct 16 at 9:47

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.

  • This is helpful, but I was looking for a more constructive proof. +1 anyway of course – DreamConspiracy Oct 15 at 14:11
  • 1
    Heh. This is constructive. Didn't you see I constructed the sequence. It's right there.:D I understand of course. I'm pretty sure you can't get anything better size wise than your/Hagen's result, in a "constructive" way. – DRF Oct 15 at 14:25
  • @DreamConspiracy: If by constructive you mean an a set of computable reals, then probably the square-roots of the primes is the simplest. But if you mean no axiom of choice, see my answer for an alternative. =) – user21820 Oct 15 at 18:14
  • @user21820 Oh I meant you can't get one of a cardinality bigger than countable. The primes one doesn't need AC. I suppose it's actually computable. I do wonder if it's obvious (or even true) that without AC it's consistent there is no uncountable set of reals that is "arithmetically independent". – DRF Oct 15 at 18:33
  • 3
    I'm quite surprised that such a seemingly simple question has spawned three completely different approaches. Very interesting – DreamConspiracy Oct 15 at 20:42

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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