Recently I was told the following riddle:

Let $A=(a_1,...a_n,...a_{2n},a_{2n+1})$ a 2n+1-tuple of real numbers with the following property: Whatever number $a_i$ is removed from $A$ the remaining 2n Numbers can be divided into two n-tuples $A_1$ and $A_2$ such that $\sum\limits_{i=1}^n (A_{1})_i=\sum\limits_{i=1}^n (A_{2})_i$. Prove that in this case $a_1=a_2=...=a_{2n}=a_{2n+1}$.

The guy who told me the riddle suggested prooving the statement over the Rationals and then using the axiom of choice. As I was a bit irritated I asked again and he told me that the satement over the reals is indeed dependent of the axiom of choice.

Over the natural numbers (and by multiplying with all the divisors also over the rationals) the proof isn't really difficult. But neither I can prove it over the reals nor i can imagine how a statement about finite many numbers should be dependent on the axiom of choice. Does anyone have a poof or can explain how this could require the axiom of choice?

Thanks for your answers.

  • $\begingroup$ The axiom of choice obviously is true in the case of finite sets. $\endgroup$ – Peter Apr 29 '16 at 9:21
  • 3
    $\begingroup$ Go to your friend and tell him "[citation needed]". My guess is that he immediately thought about taking a Hamel basis for $\Bbb R$ over $\Bbb Q$ and using that. While valiant, for a finite tuple you can just look at the smallest field including all the members of the tuple, and that is a countable field. So no choice would be needed to get a Hamel basis there. $\endgroup$ – Asaf Karagila Apr 29 '16 at 9:25
  • $\begingroup$ Ok,this seems possible. Next time I see him I'm gona ask him again about this. Using a Hamel-Basis seems sufficient. Thanks. $\endgroup$ – Takirion Apr 29 '16 at 9:49
  • $\begingroup$ Admittedly, I'm not entirely sure how to solve this over $\Bbb{N,Q}$ or $\Bbb R$. Or how to use a Hamel basis in order to move from $\Bbb Q$ to $\Bbb R$. $\endgroup$ – Asaf Karagila Apr 29 '16 at 12:20
  • $\begingroup$ To solve this over $\mathbb{N}$ show that $a_1\equiv,\ldots\equiv a_{2n+1} \mod 2^k$ for all $k\in \mathbb{N}$. For the step to $\mathbb{Q}$ multiply with the common denominator. For the Step to \mathbb{R} choose a $\mathbb{Q}$-Basis of $\mathbb{R}$ (with AC) or of $<a_1,...,a_{2n+1}>$ (without AC). Then apply the Theorem to each component. $\endgroup$ – Takirion Apr 29 '16 at 14:58

Too long for a comment: Certainly no choice can be required here. The comments sketch a solution, but even without knowing the solution, this follows from a general fact: Shoenfield absoluteness. Shoenfield absoluteness (among other things) isolates a class of statements which, if provable from ZFC, are also provable from ZF. Certainly not every statement has this "absoluteness" property (e.g. the Axiom of Choice certainly doesn't :P) but a wide class do: the $\Pi^1_2$ sentences. It is not hard to see that the result in the question is $\Pi^1_2$ (actually, even better - $\Pi^1_1$, so Mostowski absoluteness is already enough, but meh :P), so if we can prove it with choice, we can prove it without choice.

I haven't defined "$\Pi^1_2$" here because it's a bit lengthy; if you look around this site you'll find it explained. Roughly speaking, a $\Pi^1_2$ sentence has the form "For every real $r$, there is some real $s$ such that [property]," where the property in question involves quantification only over natural numbers. Finite tuples of reals can be coded by single reals, so the statement above is of this form. It turns out we don't even need the "there is some real $s$," if we're a bit clever!

To de-mystify a bit: in any model $V$ of $ZF$, we can define a sub-class $L$ and show that $L$ satisfies $ZFC$ (this was done by Godel). Now, Shoenfield absoluteness says that if $\varphi$ is $\Pi^1_2$, then - for each $V\models ZF$ - $\varphi$ is true in $V$ iff $\varphi$ is true in $L$ (really I should say "the thing $V$ thinks is $L$"). Since $L$ always satisfies ZFC, that means that if ZFC proves $\varphi$, then - since $\varphi$ will always be true in $V$'s $L$ - $\varphi$ will always be true in $V$. Hence $\varphi$ is true in any model of $ZF$.

Of course this doesn't touch the proof at all, which is quite hard, but that's a story for another question.

  • 1
    $\begingroup$ Mmmmm... Shoenfield... $\endgroup$ – Asaf Karagila May 2 '16 at 8:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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