Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
I know there are uncountable number of equivalence classes defined by the relation defined here: Equivalence classes of "$x \sim y \Longleftrightarrow x -y $ is rational". (the relation is defined on the set $[0,1)$)
Each of those equivalence class contains countable number of elements.
This textbook says we need the Axiom of Choice to pick one element from each equivalence class. Why? Is it because we always need the Axiom of Choice when picking an element from an uncountable number of sets?
No, it’s because there is no way simultaneously to specify a particular element of each class. If I let $X=\Bbb R\times\Bbb R$, and for each $r\in\Bbb R$ let $A_r=\{r\}\times\Bbb R$, I can easily pick one element from each $A_r$, even though each $A_r$ is uncountable: for instance, from $A_r$ I can choose the element $\langle r,0\rangle$. I have a recipe for specifying one particular element. I have many such recipes, in fact: I could just as well pick $\langle r,r\rangle$ as the representative of $A_r$.
In the other direction, there are models of set theory that show that one might need the axiom of choice to pick a representative from each member of a family of two-element sets. In short, the cardinality of the individual sets is not the issue.
Brian M. Scott has given a terrific run-down of the general theory, but to get into more specifics about the particular construction you are interested in, we know that we need some fairly strong Choice principle because of Robert Solovay's celebrated result:
Theorem: Assuming the consistency of some large cardinal hypothesis, the theory $ZF + DC + \text{all sets of reals are Lebesgue measurable}$ is consistent.
What this means is that the construction of a Vitali set (or any non-measurable set) cannot in general be carried out without assuming a Choice principle stronger than Dependent Choice.
The axiom of choice is needed when there is no uniform choice from the sets that you wish to choose from.
Given any non-empty set $A$, $2^A$ is a product of the set $\{0,1\}$ over the index set $A$. This product is never empty, we can always insist on choosing $0$.
Another example is whenever $A$ can be well-ordered, we can always choose from families of subsets of $A$. How? Simply fix a well-order of $A$, then every non-empty set has a least element and that is our uniform choice. So uniform choice means that we can more or less formulate what would be the choice from each set (there is some delicacy here still).
So what about $\Bbb{R/Q}$? Well, it turns out that we don't have a uniform choice from these sets, and it sort of make sense in a way. All the equivalence classes are dense subsets of $\Bbb R$, and we don't have too much information on them beyond that. But this is not a proof that we can't make this choice, it's just reasoning.
The proof that we cannot make this sort of choice comes from the fact that there are models of set theory where the axiom of choice fails, and every set of real numbers is Lebesgue measurable. In such model, certainly there is no Vitali set - that is a system of representatives for $\Bbb{R/Q}$ - and therefore there is no choice function from $\Bbb{R/Q}$.
In fact, just to make things weirder, let me give you the extent of which the axiom of choice is needed. It is possible to have a universe of set theory, where there is a countable set of pairs, but we cannot choose from from each pair. This is because we don't have a uniform way of matching them up with $\{0,1\}$.
The axiom of choice exactly says that any product of non-empty sets is non-empty.
Let $\rm I$ be the set of equivalence classes of your relation and $(\mathrm C_i)_{i \in \rm I}$ the equivalence classes, then you are exactly saying that there exists an element in $$ \prod_{i\in \mathrm I} \mathrm C_i$$
