Equivalence Relations

Reflexive: for every integer $a$, $a - a = 0$ and $n \mid 0$, so $a \sim a$. In the scene at $n = 4$, all $12$ elements of $U$ are related to themselves.

Symmetric: suppose $a \sim b$. Then $n \mid (a - b)$, so $a - b = nk$ for some integer $k$, and therefore $b - a = -nk = n(-k)$, giving $n \mid (b - a)$, i.e. $b \sim a$.

In the scene this is checked for all $12^2 = 144$ ordered pairs of $U$.

Transitive: suppose $a \sim b$ and $b \sim c$. There are integers $k, m$ with $a - b = nk$ and $b - c = nm$; adding gives $a - c = (a - b) + (b - c) = nk + nm = n(k + m)$, so $n \mid (a - c)$, i.e. $a \sim c$.

In the scene all $12^3 = 1728$ triples check out. The three conditions hold, so congruence is an equivalence relation.

(i) By reflexivity $x \sim x$, hence $x \in [x]$. So no class is empty, and every element lies in at least one class — the classes cover $S$.

Setup for (ii): suppose some $z \in [x] \cap [y]$ exists. By definition $z \sim x$ and $z \sim y$.

Symmetry turns $z \sim x$ into $x \sim z$, and transitivity with $z \sim y$ then gives $x \sim y$.

Now show $[x] \subseteq [y]$. If $w \in [x]$ then $w \sim x$; chaining $w \sim x$ with $x \sim y$ from the setup by transitivity gives $w \sim y$ directly, i.e. $w \in [y]$.

Swapping the roles gives $[y] \subseteq [x]$, hence $[x] = [y]$.

Conclusion: if two classes overlap at all, they are equal. Hence distinct classes are disjoint, and by (i) their union is $S$ — an equivalence relation partitions its set into equivalence classes.

In the scene at $n = 4$, the four classes split the $12$ elements of $U$ into exactly $3$ each.

(a) Reflexive: $x - x = 0 \in \mathbb{Q}$, so $x \sim x$. Symmetric: if $x - y \in \mathbb{Q}$ then $y - x = -(x - y) \in \mathbb{Q}$, so $y \sim x$ (rationals stay rational under negation).

Transitive: if $x - y \in \mathbb{Q}$ and $y - z \in \mathbb{Q}$ then $x - z = (x - y) + (y - z) \in \mathbb{Q}$, so $x \sim z$ (sums of rationals are rational). This is the same skeleton as the congruence proof in problem 1, with "divisibility" replaced by "membership in $\mathbb{Q}$".

(b) $[x] = \{y \in \mathbb{R} : y - x \in \mathbb{Q}\}$; writing $y = x + (y - x)$ shows this set is exactly $x + \mathbb{Q} = \{x + q : q \in \mathbb{Q}\}$ — a shifted copy of the rationals, translated by $x$. Reals a rational distance apart are identified, and by the partition theorem (problem 2) these shifted copies tile $\mathbb{R}$ without overlap.

(c) Choosing exactly one representative from each class $x + \mathbb{Q}$ and collecting them produces a Vitali set. But there are uncountably many classes and none has a "natural" representative, so this choice requires the axiom of choice — no rule can make the picks; the axiom only guarantees existence. In the integration chapter's vitali scene, this very set is shown not to be Lebesgue measurable.

Take the representatives in $[0,1]$ (every class $x + \mathbb{Q}$ meets $[0,1]$), so $V \subseteq [0,1]$. The translates $V + q$ for $q \in \mathbb{Q} \cap [-1,1]$ are pairwise disjoint: if $(V + q_1) \cap (V + q_2) \ne \emptyset$ then two representatives differ by $q_2 - q_1 \in \mathbb{Q}$, hence lie in the same class, hence are equal, so $q_1 = q_2$. They all have the same measure as $V$ (translation invariance), they cover $[0,1]$ (each $x \in [0,1]$ differs from its representative by a rational $q$ with $|q| \le 1$), and their union lies in $[-1, 2]$.

If $V$ were measurable with $m(V) = 0$, the countable union would have measure $0$, contradicting that it covers $[0,1]$; if $m(V) > 0$, the union inside $[-1, 2]$ would have infinite measure, again a contradiction. Hence $V$ is not measurable.