Selecting Vitali Representatives with the Axiom of Choice

Rational Translations and the Selection Problem

Let the underlying set be $[0,1]$. Two points are placed in the same class when their difference is rational. The resulting classes divide the interval into disjoint pieces, many of which contain no least point in the usual order. The selection problem is to choose one point from each piece. The axiom of choice guarantees that such a selection exists, even though the axiom does not prescribe a formula or an algorithm for making the choices.

This tutorial concerns a set-theoretic construction inside $[0,1]$. It makes no claim that the set of selected points is Lebesgue measurable, nor does it use a measure space. Measurability questions belong to the subsequent analysis of this construction.

Definition: For $x,y\in[0,1]$, write $x\sim y$ if and only if $x-y\in\mathbb{Q}$, where $\mathbb{Q}$ is the set of rational numbers. The equivalence class of $x$, relative to $[0,1]$, is $$ [x]=\{y\in[0,1]:y-x\in\mathbb{Q}\}=(x+\mathbb{Q})\cap[0,1]. $$

This is an equivalence relation. First, $x-x=0\in\mathbb{Q}$, so $x\sim x$. Second, if $x-y\in\mathbb{Q}$, then $y-x=-(x-y)\in\mathbb{Q}$, so $y\sim x$. Third, if $x-y$ and $y-z$ are rational, then $x-z=(x-y)+(y-z)$ is rational, so $x\sim z$. The set of all classes is denoted by $[0,1]/\sim$.

Proposition: The equivalence classes form a partition of $[0,1]$: each class is nonempty, their union is $[0,1]$, and any two classes are either equal or disjoint.

Proof. Every $x\in[0,1]$ belongs to its own class because $x-x=0\in\mathbb{Q}$. Thus the classes cover $[0,1]$, and none is empty. Now suppose $[x]\cap[y]\ne\varnothing$. Choose $z\in[x]\cap[y]$. Then $z-x$ and $z-y$ are rational, so $x-y=(x-z)+(z-y)$ is rational. For any $w\in[x]$, both $w-x$ and $x-y$ are rational, hence $w-y=(w-x)+(x-y)$ is rational and $w\in[y]$. This proves $[x]\subseteq[y]$. Reversing the roles of $x$ and $y$ gives $[y]\subseteq[x]$, so the classes are equal. Therefore classes that are not equal are disjoint. $\square$

What the Axiom of Choice Supplies

The axiom of choice says that for every set $I$ and every family $(A_i)_{i\in I}$ of nonempty sets, there is a function $c$ with domain $I$ such that $c(i)\in A_i$ for every $i\in I$. Such a function is called a choice function. Apply this statement with $I=[0,1]/\sim$ and $A_C=C$ for each equivalence class $C$. Each $A_C$ is nonempty by the definition of a class, so the axiom gives a function choosing one point from every class.

Theorem: There is a set $V\subseteq[0,1]$ such that every rational-translation equivalence class in $[0,1]$ contains exactly one point of $V$.

Proof. The family of classes $\{C:C\in[0,1]/\sim\}$ consists of nonempty sets. By the axiom of choice, there is a function $c$ on this family with $c(C)\in C$ for every class $C$. Define $V=\{c(C):C\in[0,1]/\sim\}$. Since $c(C)\in C$, each class contains at least one point of $V$. To verify uniqueness, suppose $v\in V\cap C$. Then $v=c(D)$ for some class $D$, and $v\in D$ as well as $v\in C$. The partition proposition implies $C=D$, so $v=c(C)$. Thus every class contains exactly the one selected point $c(C)$. $\square$

The theorem is an existence statement. It specifies the domain of the selection, the allowed values, and the requirement of exactly one selected point per class. It does not tell us how to compute $c(C)$ from $C$, or give a pointwise formula for membership in $V$. This distinction matters: applying the axiom of choice is a valid proof that some such $V$ exists, but it is not an explicit recipe for listing its elements.

Worked Example: The Class of a Rational Point

Find the equivalence class of $1/3$, and describe what a selector does to it.

A point $y\in[0,1]$ belongs to $[1/3]$ exactly when $y-1/3$ is rational. Since $1/3$ is rational, this is equivalent to $y$ being rational: if $y-1/3\in\mathbb{Q}$, then $y=(y-1/3)+1/3\in\mathbb{Q}$; conversely, if $y\in\mathbb{Q}$, then $y-1/3\in\mathbb{Q}$. Therefore $$ [1/3]=\mathbb{Q}\cap[0,1]. $$ For example, $0$, $1/3$, and $1$ all belong to this class, since their differences from $1/3$ are respectively $-1/3$, $0$, and $2/3$, all rational. A choice function selects one rational number $r\in[0,1]$ from this entire class. The theorem does not require that $r=1/3$, nor does it specify which rational number is selected. Check: the class contains both $0$ and $1$, but the selection rule takes exactly one of its members, not both.

Worked Example: Several Points in an Irrational Class

Verify that $x=\sqrt{2}-1$, $x+1/2$, and $x-1/3$ are three distinct points of $[0,1]$ in the same class.

The number $x=\sqrt{2}-1$ is in $[0,1]$ because $1<\sqrt{2}<2$, as follows by squaring the positive numbers in those inequalities: $1<2<4$. The other two points are $$ x+\frac12=\sqrt{2}-\frac12, \qquad x-\frac13=\sqrt{2}-\frac43. $$ For the first, $1<\sqrt{2}$ gives $\sqrt{2}-1/2>1/2>0$, and $\sqrt{2}<3/2$ gives $\sqrt{2}-1/2<1$; the latter bound follows from $2<9/4$. For the second, $4/3<\sqrt{2}<7/3$ gives $0<\sqrt{2}-4/3<1$; these bounds follow by squaring, since $16/9<2<49/9$. Thus all three points lie in $[0,1]$. Their differences from $x$ are $0$, $1/2$, and $-1/3$, which are rational, so all three lie in $[x]$. They are distinct because the three offsets $0,1/2,-1/3$ are distinct. Check: the three values differ from $x$ by exactly the stated rational offsets, so they are equivalent under the definition.

Why a Pointwise Rule Is Not Built In

One tempting idea is to choose the least member of each class. This works for some classes, but it does not work for all of them. For instance, if $x$ is irrational, then $0\notin[x]$, because $0\in[x]$ would imply $-x\in\mathbb{Q}$, and hence $x\in\mathbb{Q}$. Nevertheless, points of $[x]$ occur arbitrarily close to $0$ from above. To see this, take any $r\in(0,1)$. The interval $(-x,r-x)$ is nonempty, so by density of the rationals it contains a rational $q$. Then $x+q\in[x]$ and $0<x+q<r$. Consequently $[x]$ has no least member: any proposed member $r$ has another class member strictly between $0$ and $r$.

Worked Example: The Least-Element Rule Fails

Take $x=\sqrt{2}-1$, which is irrational. Explain why its class has no least element.

First, $0\notin[x]$: if it were, $0-x=1-\sqrt{2}$ would be rational, which would make $\sqrt{2}=1-(1-\sqrt{2})$ rational. Now let $r\in[x]$. Since $r\in[0,1]$ and $0\notin[x]$, we have $r>0$. The interval $(-x,r-x)$ has length $r>0$, so it contains a rational $q$. Put $y=x+q$. Then $y\in[x]$, and the inequalities $q>-x$ and $q<r-x$ give $0<y<r$. Thus every proposed member $r$ has a strictly smaller member $y$ in the same class. A least element cannot exist. Check: this reasoning applies to every $r\in[x]$, so it rules out a least member rather than merely showing that one particular candidate fails.

This failure is a limitation of the least-element method, not a failure of the axiom-of-choice construction. Other classes do have least members—for example, $[0]=\mathbb{Q}\cap[0,1]$ has least member $0$—but a rule that depends on taking a least member cannot be applied uniformly to every class.

A finite model helps isolate the selection requirement. It illustrates the bookkeeping, though it does not replace the axiom of choice for the family of classes in $[0,1]$.

Worked Example: Counting Choices in a Finite Partition

Let a six-element set be partitioned into the three classes $\{a,c\}$, $\{b,d,e\}$, and $\{f\}$. Count the possible selections that take exactly one point from each class.

There are $2$ choices from $\{a,c\}$, $3$ choices from $\{b,d,e\}$, and $1$ choice from $\{f\}$. Each selection is obtained by making one choice independently from each class, so the total is $2\cdot3\cdot1=6$. Listing them gives $\{a,b,f\}$, $\{a,d,f\}$, $\{a,e,f\}$, $\{c,b,f\}$, $\{c,d,f\}$, and $\{c,e,f\}$. Each listed set meets each class exactly once. Check: the six listed sets correspond to the two possible first choices paired with the three possible second choices, and each contains $f$, the sole member of the third class.

What Is—and Is Not—Specified

For the interval construction, the axiom of choice applies to a potentially very large family: there is one nonempty set for every equivalence class. The resulting choice function is defined on the set $[0,1]/\sim$, not directly by a formula that takes an arbitrary real $x$ as input. Equivalently, the selected set $V$ satisfies the precise condition $$ \text{for every }C\in[0,1]/\sim,\qquad |V\cap C|=1. $$

This condition characterizes what a representative set must do, but it does not identify a particular representative set by a computable pointwise test. There may be many different choice functions, since different classes can have different selected points. The conclusion needed here is only existence: a set with exactly one representative from each rational-translation class can be chosen. No claim about a formula, measurability, or measure of that set follows from this selection argument alone.

Common pitfall. It is incorrect to say “choose the smallest element of each class” and treat that as an application of the axiom of choice. An axiom-of-choice selection is allowed to choose any member of each nonempty set. It does not assert that each set has a least member. As shown above, irrational classes have no least member, so the least-element prescription does not define a selection on the full family.

Check Your Understanding

Use the definitions and the selection theorem to answer the following questions.

Verify directly that $1/4\sim 3/4$, and write their common equivalence class in terms of $\mathbb{Q}\cap[0,1]$.
State the domain and the membership condition for the choice function used to construct $V$.
Why does the fact that every class is nonempty suffice for the axiom-of-choice application?
Explain why an irrational class has no least member, using density of $\mathbb{Q}$.
Does the existence proof specify whether the representative of $\mathbb{Q}\cap[0,1]$ is $0$, $1/3$, or another rational number? Explain.