4. Relations, equivalence classes and order

Learning goals and definitions

Recognize equivalence relations and partial orders, prove the partition correspondence, and check well-defined quotient operations. A relation $R$ on $X$ is a subset of $X\times X$; write $xRy$ when $(x,y)\in R$.

A relation is reflexive if $xRx$ for every $x$, symmetric if $xRy$ implies $yRx$, and transitive if $xRy$ and $yRz$ imply $xRz$. An equivalence relation has all three. Its class at $x$ is $[x]=\{y\in X:yRx\}$, and $X/R$ is the set of those classes. A representative is an element used to name a class; it is not the class itself.

A partial order is reflexive, antisymmetric and transitive. Antisymmetry says that $xRy$ and $yRx$ together force $x=y$; it does not mean symmetry fails for every pair. A total order additionally makes every pair comparable. Inclusion is a partial order on $\mathcal P(X)$, usually not a total order.

Theorem: equivalence relations and partitions

Classes of an equivalence relation are nonempty, cover $X$, and any two are equal or disjoint. Conversely, every partition into nonempty disjoint blocks defines an equivalence relation by membership in the same block.

Proof. Reflexivity puts each $x$ in $[x]$, proving nonemptiness and coverage. If $z\in[x]\cap[y]$, then $zRx$ and $zRy$. By symmetry and transitivity, $xRy$. If $w\in[x]$, then $wRx$ and $xRy$, so $wRy$; hence $[x]\subseteq[y]$. Reversing $x,y$ gives equality. Conversely each point lies in a unique block. Sharing a block is reflexive and symmetric; if $x,y$ share one block and $y,z$ another, those blocks intersect and therefore coincide, proving transitivity.

Quotient operations and a worked example

For an integer $m\ge2$, define $a\sim b$ if $m\mid(a-b)$. Divisibility verifies reflexivity, symmetry and transitivity: the differences are $0$, negatives, and sums of multiples of $m$. The quotient has classes $[0],\ldots,[m-1]$ by integer division.

Define addition by $[a]+[b]=[a+b]$ and multiplication by $[a][b]=[ab]$. To be well-defined, replacing either representative must not change the resulting class. If $a-a'=ms$ and $b-b'=mt$, then $(a+b)-(a'+b')=m(s+t)$ and

$$ab-a'b'=(a-a')b+a'(b-b')=m(sb+a't).$$

Thus both rules are well-defined. In contrast, attempting to define an order on classes by $[a]\le[b]$ exactly when $a\le b$ fails: modulo three, $[0]=[3]$, but $0\le1$ and $3\nleq1$ give conflicting results for the same classes.

Worked order example. On positive integers, divisibility is a partial order. If $a\mid b$ and $b\mid a$, write $b=ka,a=\ell b$ with positive integers $k,\ell$; then $k\ell=1$, so $a=b$. It is not total because neither $2\mid3$ nor $3\mid2$.

Graded practice

1. Foundation. On $\mathbb Z$, define $aRb$ when $a-b$ is even. Prove equivalence and list the classes.
2. Core. Is $aRb$ defined by $|a-b|\le1$ on $\mathbb R$ an equivalence relation? Test every property.
3. Core. In integers modulo five, solve $[2][x]=[1]$, and explain why your answer does not depend on a chosen representative.
4. Proof. For an equivalence relation, prove $[x]=[y]$ if and only if $xRy$.

Full solutions

1. Zero is even; negating an even difference keeps it even; adding two even differences keeps it even. These prove reflexivity, symmetry and transitivity. The two classes are the even integers $[0]$ and odd integers $[1]$.
2. It is reflexive because $|a-a|=0$, and symmetric because absolute difference is symmetric. It is not transitive: $0R1$ and $1R2$, but not $0R2$. Therefore it is not an equivalence relation.
3. $2\cdot3=6\equiv1\pmod5$, so $[x]=[3]$ works. If $2x\equiv1$, multiply by $3$ to get $x\equiv3$, proving uniqueness. Multiplication of classes was proved well-defined above, so changing $x$ by a multiple of five preserves the product class.
4. If classes agree, reflexivity gives $x\in[x]=[y]$, which means $xRy$. If $xRy$, then $x\in[x]$ and $x\in[y]$, so the classes intersect and are equal by the partition theorem.

Summary and term definitions

A partition divides a set into disjoint nonempty blocks; an equivalence class is one such block induced by a relation. A quotient rule is well-defined when all representative choices give the same output. A partial order allows incomparable elements; a total order does not. Test defining properties individually, and never transport a formula to classes without the representative check.