Equivalence Relations | Real Analysis

Congruence modulo

n

as an equivalence relation: the three axioms — reflexive, symmetric, transitive — are brute-force verified on every element, pair, and triple of

U = \{0, \dots, 3n-1\}

, and the classes

[r] = \{r, r+n, r+2n\}

visibly partition the set as

n

slides.

Examples & Exercises

Prove completely that the relation $a \sim b \iff n \mid (a - b)$ on the integers $\mathbb{Z}$ is an equivalence relation — pull each of the three conditions, reflexive, symmetric, transitive, down to the arithmetic of divisibility.

a \sim b \;\iff\; a \equiv b \pmod n

n \mid (a-b),\; n \mid (b-c) \;\Rightarrow\; n \mid (a-c) = (a-b) + (b-c)

n = 4

U

is the

12

numbers

0

through

11

, and the classes are

[0] = \{0, 4, 8\}

[1] = \{1, 5, 9\}

[2] = \{2, 6, 10\}

[3] = \{3, 7, 11\}

. Examples:

7 \sim 3

(

7 - 3 = 4

), but

7 \sim 4

is false (

7 - 4 = 3

is not divisible by

4

Show proof

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.

Prove the partition theorem completely: for an equivalence relation $\sim$ on a set $S$ , (i) every $x$ belongs to its own equivalence class $[x]$ , and (ii) if $[x]$ and $[y]$ share even one element then $[x] = [y]$ . Deduce that distinct classes are disjoint and that the classes together cover $S$ .

[x] = \{y \in S : y \sim x\}

z \in [x] \cap [y] \;\Rightarrow\; [x] = [y]

n = 4

: the four classes

[0] = \{0, 4, 8\}

[1] = \{1, 5, 9\}

[2] = \{2, 6, 10\}

[3] = \{3, 7, 11\}

are pairwise disjoint and their union is all of

U

— the partition theorem in a finite example.

Show proof

(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$ ; from the setup, $x \sim y$ , so symmetry gives $y \sim x$ and transitivity from $w \sim x$ yields $w \sim y$ , 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.

Define a relation on $\mathbb{R}$ by $x \sim y \iff x - y \in \mathbb{Q}$ . (a) Prove it is an equivalence relation, (b) determine the shape of its equivalence classes ( $[x] = x + \mathbb{Q}$ ), and (c) explain why collecting one representative from each class of this partition is exactly the Vitali-set construction.

x \sim y \iff x - y \in \mathbb{Q}

[x] = x + \mathbb{Q} = \{x + q : q \in \mathbb{Q}\}

n = 2

: the finite prototype — the two classes

[0] = \{0, 2, 4\}

and

[1] = \{1, 3, 5\}

partition

U = \{0, \dots, 5\}

. This problem's relation swaps "same remainder" for "same rational difference".

Show proof

(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: countably many measurable rational translates cannot reassemble into a bounded interval.