If we define a relation $\sim$ between real numbers so that $x \sim y$ holds precisely if $y - x$ is rational, then we need AC to prove that there exists a set of distinct representatives for the equivalence classes of $\sim$. Do we also need AC to prove the same for $\sim$ defined on just the algebraic numbers? After all, we then have only countably many classes. But it still seems hard?!

  • $\begingroup$ We don't need the full axiom of choice for proving the existence of distinct representatives. The full axiom of choice is much more powerful. We do need some choice-like axiom, though. I don't know about the algebraic case, but if we do need something, what we need is probably weaker still. $\endgroup$ – Arthur Jul 4 '18 at 21:30
  • $\begingroup$ @XanderHenderson That's a red herring - no amount of choice is needed here, at all. $\endgroup$ – Noah Schweber Jul 4 '18 at 21:33
  • $\begingroup$ @Noah: No amount is some amount... what kind of a logician are you? :P $\endgroup$ – Asaf Karagila Jul 4 '18 at 21:47

No, AC is no longer needed.

The key point is that we can well-order the algebraic real numbers without using choice, as follows:

  • First, fix an enumeration $\{P_i:i\in\mathbb{N}\}$ of the nonconstant polynomials with rational coefficients.

  • Now given an algebraic number $r$, let $\#(r)$ be the least $i$ such that $r$ is a solution to $P_i$.

  • Finally, for algebraic numbers $r\not=s$ write $r\triangleleft s$ iff one of the following holds:

    • $\#(r)<\#(s)$, or

    • $\#(r)=\#(s)$ and $r<s$.

  • It's now not hard to show that $\triangleleft$ well-orders the set of algebraic numbers (in fact, with order-type $\mathbb{N}$). (The key point here is that any nonconstant polynomial has finitely many roots.)

We can use this well-ordering to build a Vitali set: given an algebraic number $r$, let $rep(r)$ be the $\triangleleft$-least algebraic real which differs from $r$ by a rational number. The set $$\{rep(r): r\mbox{ is algebraic}\}$$ is then a "$\mathbb{Q}$-Vitali set" as desired.

More generally, if we can prove without choice that $A$ is a well-orderable set of reals, then we can also prove without choice that there is an "$A$-Vitali set." Put another way:

"Every well-orderable set of reals has a Vitali subset" is provable without choice.

| cite | improve this answer | |

No. The Vitali set is given by choosing from the fibers of a surjection from $\Bbb R$ to $\Bbb R/\Bbb Q$.

If you restrict your surjection to a countable set, any countable set, then you can first enumerate it as $\{r_n\mid n\in\Bbb N\}$ and then choose the least indexed $r_n$ in each fiber.

| cite | improve this answer | |
  • $\begingroup$ A bit less overkill than talking about well orderings. $\endgroup$ – Jack M Jul 5 '18 at 11:31
  • 1
    $\begingroup$ Well, it's not really of an overkill to talk about well-orders. This is really an obvious generalization. $\endgroup$ – Asaf Karagila Jul 5 '18 at 11:31

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.