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$
$\endgroup$
3
-
$\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$– ArthurCommented Jul 4, 2018 at 21:30
-
$\begingroup$ @XanderHenderson That's a red herring - no amount of choice is needed here, at all. $\endgroup$– Noah SchweberCommented Jul 4, 2018 at 21:33
-
$\begingroup$ @Noah: No amount is some amount... what kind of a logician are you? :P $\endgroup$– Asaf Karagila ♦Commented Jul 4, 2018 at 21:47
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
0
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.
answered Jul 4, 2018 at 21:31
$\begingroup$
$\endgroup$
2
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.
answered Jul 4, 2018 at 21:30
-
$\begingroup$ A bit less overkill than talking about well orderings. $\endgroup$– Jack MCommented Jul 5, 2018 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 ♦Commented Jul 5, 2018 at 11:31