Equivalence relations

A function pairs each input with exactly one output, but "divides", "has the same birthday as" and "leaves the same remainder on division by $5$ as" pair things far more freely, and they need a language of their own.

The previous lesson closed on the observation that many useful relations are not functions at all. This lesson defines relations, picks out the ones that say two things are "the same for present purposes", and shows that each of them cuts its set into pieces, which is how modular arithmetic and the fractions are built. It assumes sets, the Cartesian product $A\times B$ of all ordered pairs $(a,b)$ with $a\in A$ and $b\in B$, the quantifiers, and divisibility: $a\mid b$ when $b=ak$ for some integer $k$.

Relations as sets of pairs

A relation on a set $A$ is a subset of $A\times A$. When the pair $(a,b)$ belongs to it we say $a$ is related to $b$ and write $a\sim b$. A relation is exactly the set of pairs it holds between, so two relations are equal when they contain the same pairs, however differently they were described.

Take $A=\{1,2,3,4\}$ and let $a\sim b$ mean $a\mid b$. As a set of pairs this is

eight of the sixteen pairs in $A\times A$. Order matters, since $(2,4)$ is in the set and $(4,2)$ is not. A relation on $A$ can be any subset of $A\times A$, and a set of $n$ elements has $n^2$ ordered pairs, so it carries $2^{n^2}$ relations: for $A=\{1,2,3\}$, $2^9=512$.

A function from $A$ to $B$ fits the same mould. Its graph, $\{(a,f(a)):a\in A\}$, is a set of pairs in which every $a\in A$ appears as a first coordinate exactly once, so functions are the relations with that property. On $ℝ$, $x\sim y$ when $y=x^2$ is a function. The relation $x\sim y$ when $x=y^2$ is not, and it fails both ways: $4$ is related to $2$ and to $-2$, and $-1$ is related to nothing. Divisibility above is not one either, since $1$ is related to four elements.

Reflexive, symmetric and transitive

Three properties of a relation $\sim$ on $A$ matter here, each a universal statement:

A relation with all three is an equivalence relation. Equality is the model, and "has the same birthday as" is another: everyone shares a birthday with themselves, sharing is mutual, and two people who share with a third share with each other.

Being universal, each property is broken by a single counterexample, and three relations on $ℝ$ show that any two can hold without the third. The order $x\le y$ is reflexive and transitive but not symmetric, since $1\le 2$ and not $2\le 1$. "Close to", meaning $|x-y|\le 1$, is reflexive and symmetric but not transitive: $0$ is close to $1$ and $1$ to $2$, but $0$ is not close to $2$. And $x\sim y$ when $xy>0$ is symmetric and transitive (if $xy>0$ and $yz>0$, then $x$ and $z$ both have the sign of $y$) but not reflexive, since $0\cdot 0=0$.

That last example refutes a tempting proof: "if $a\sim b$ then $b\sim a$, so $a\sim a$ by transitivity". Each step is valid, but the argument needs some $b$ with $a\sim b$ to start from, and for $a=0$ there is none. Reflexivity asks about every $a$, including those related to nothing.

Proving a relation is an equivalence

Such a proof is three short proofs, one per property, each a universal conditional: take arbitrary elements, assume the hypothesis, and reach the conclusion from the definition of the relation.

Example. On $ℝ$, let $x\sim y$ when $x-y\in \mathbb{Z}$. Prove that $\sim$ is an equivalence relation.

Reflexive: let $x\in ℝ$. Then $x-x=0$, an integer, so $x\sim x$. Symmetric: let $x\sim y$, so $x-y=k$ for some integer $k$. Then $y-x=-k$, also an integer, so $y\sim x$. Transitive: let $x\sim y$ and $y\sim z$, so $x-y=k$ and $y-z=m$ for integers $k$ and $m$. Adding, $x-z=k+m$, an integer, so $x\sim z$. All three hold, so $\sim$ is an equivalence relation.

Here $2.7\sim 0.7\sim -3.3$: two reals are related when they have the same fractional part. The three steps used that the integers contain $0$ and are closed under negation and addition.

Now you. On the nonzero reals, let $x\sim y$ when $\frac{x}{y}\in \mathbb{Q}$. Prove that $\sim$ is an equivalence relation.

Equivalence classes partition the set

Given an equivalence relation $\sim$ on $A$ and $a\in A$, the equivalence class of $a$ is everything related to it:

Under the fractional part relation above, $[0.7]=\{\dots ,-1.3,-0.3,0.7,1.7,\dots \}$, and $[0.7]=[2.7]$: one class, two names. Any element of a class is a representative of it. A partition of $A$ is a collection of nonempty subsets of $A$, its blocks, such that every element of $A$ lies in exactly one block. Birthdays cut a room into at most 366 blocks, and that always happens.

Theorem. If $\sim$ is an equivalence relation on $A$, its equivalence classes form a partition of $A$.

First, every element is in its own class: $a\sim a$ by reflexivity, so $a\in [a]$. Hence every class is nonempty and every element lies in at least one class.

Second, if $a\sim b$ then $[a]=[b]$, by double inclusion. Let $x\in [a]$, so $x\sim a$; with $a\sim b$, transitivity gives $x\sim b$, so $x\in [b]$. Conversely let $x\in [b]$, so $x\sim b$; symmetry turns $a\sim b$ into $b\sim a$, and transitivity gives $x\sim a$, so $x\in [a]$.

Third, two classes are equal or disjoint. Suppose $[a]$ and $[b]$ share an element $c$, so $c\sim a$ and $c\sim b$. Symmetry gives $a\sim c$, transitivity gives $a\sim b$, and the second step gives $[a]=[b]$. So no element lies in two different classes, and each lies in exactly one.

The converse holds too. Given a partition of $A$, let $a\sim b$ when $a$ and $b$ lie in the same block. This is reflexive because every element lies in some block, and symmetric because "the same block" ignores order. For transitivity, let $a$ and $b$ share a block $S$, and $b$ and $c$ a block $T$. Then $b$ lies in both, and since it lies in exactly one block, $S=T$, so $a$ and $c$ share a block. The classes of this relation are the blocks, so equivalence relations on $A$ and partitions of $A$ are one idea described two ways. On $\{1,2,3\}$ there are five partitions (all together, all apart, or a pair beside a singleton, in three ways), so only five of the 512 relations on that set are equivalence relations.

Congruence modulo $n$

Fix a positive integer $n$. Integers $a$ and $b$ are congruent modulo $n$, written $a\equiv b\left(\text{mod}n\right)$, when $n\mid a-b$. So $17\equiv 2\left(\text{mod}5\right)$ and $-7\equiv 2\left(\text{mod}3\right)$. The notation is Carl Friedrich Gauss's, from his Disquisitiones Arithmeticae of 1801, and a clock uses it daily: five hours after nine o'clock is two o'clock because $14\equiv 2\left(\text{mod}12\right)$.

Example. Prove that congruence modulo $n$ is an equivalence relation on $\mathbb{Z}$.

Reflexive: for $a\in \mathbb{Z}$, $a-a=0=n\cdot 0$, so $a\equiv a\left(\text{mod}n\right)$. Symmetric: let $a\equiv b\left(\text{mod}n\right)$, so $a-b=nk$ for some integer $k$. Then $b-a=n(-k)$, so $b\equiv a\left(\text{mod}n\right)$. Transitive: let $a-b=nk$ and $b-c=nm$ for integers $k$ and $m$. Adding, $a-c=n(k+m)$, so $a\equiv c\left(\text{mod}n\right)$. Congruence modulo $n$ is therefore an equivalence relation.

Its classes, the congruence classes, number exactly $n$. Division with remainder writes every integer uniquely as $a=qn+r$ with $0\le r<n$, and then $a-r=qn$, so $a\in [r]$: every integer lies in one of $[0],[1],\dots ,[n-1]$. These are different, because if $0\le r<s<n$ then $s-r$ lies strictly between $0$ and $n$, and no multiple of $n$ does. For $n=3$:

So $a\equiv b\left(\text{mod}n\right)$ says exactly that $a$ and $b$ leave the same remainder on division by $n$.

Now you. On $\mathbb{Z}$, let $a\sim b$ when $3\mid a+2b$. Prove that $\sim$ is an equivalence relation.

The fractions as classes of pairs

A fraction is written as a pair of integers, but different pairs name the same number: $\frac{1}{2}$, $\frac{2}{4}$ and $\frac{-3}{-6}$ are one rational number written three ways. An equivalence relation makes this precise, and builds $\mathbb{Q}$ from $\mathbb{Z}$ without assuming the division it is meant to create.

Let $P=\{(a,b)\in \mathbb{Z}\times \mathbb{Z}:b\ne 0\}$, and for pairs in $P$ let $(a,b)\sim (c,d)$ when $ad=bc$, the cross multiplication test stated with multiplication alone. It is reflexive, since $ab=ba$, and symmetric, since $ad=bc$ is the same equation as $cb=da$. Transitivity is the real work.

Claim. If $(a,b)\sim (c,d)$ and $(c,d)\sim (e,f)$, then $(a,b)\sim (e,f)$.

We are given $ad=bc$ and $cf=de$, and must show $af=be$. Multiplying the first equation by $f$ gives $adf=bcf$, and by the second $bcf=bde$. Hence $adf=bde$, that is, $d(af-be)=0$. The pair $(c,d)$ lies in $P$, so $d\ne 0$, and a product of integers is zero only when a factor is; so $af=be$.

The condition $d\ne 0$ is not a formality. Allow $(0,0)$ and it is related to everything, since $a\cdot 0=b\cdot 0$. Then $(1,2)\sim (0,0)$ and $(0,0)\sim (3,5)$, but $(1,2)$ is not related to $(3,5)$, because $1\cdot 5=5$ and $2\cdot 3=6$. Transitivity would fail.

A rational number is now defined to be a class $[(a,b)]$, written $\frac{a}{b}$, and $\mathbb{Q}$ is the set of these classes. So $\frac{1}{2}$ is the set $\{(1,2),(2,4),(-3,-6),\dots \}$, and the integer $n$ reappears as the class of $(n,1)$.

Well defined operations

Arithmetic on classes is defined through representatives, and that creates an obligation. A rule that picks a representative of a class and computes with it defines something only if every representative gives the same answer. Such a rule is well defined, and until that is proved it is not yet a function.

Here is one that fails. "Send $[(a,b)]$ to $a$" looks like a function from $\mathbb{Q}$ to $\mathbb{Z}$. But $[(1,2)]=[(2,4)]$, and the rule sends this one class to $1$ through one name and to $2$ through the other. A school favourite fails the same way: "add the tops and add the bottoms" gives $\frac{1}{2}\oplus \frac{1}{3}=\frac{2}{5}$, yet with $\frac{2}{4}$ for $\frac{1}{2}$ it gives $\frac{3}{7}$, and $\frac{2}{5}\ne \frac{3}{7}$ because $2\cdot 7=14$ and $5\cdot 3=15$.

Example. Prove that addition of rationals, $[(a,b)]+[(c,d)]=[(ad+bc,bd)]$, is well defined.

First, $bd\ne 0$ because $b\ne 0$ and $d\ne 0$, so the result is a class of pairs in $P$. Now let $(a,b)\sim (a^{\prime },b^{\prime })$ and $(c,d)\sim (c^{\prime },d^{\prime })$, that is, $a{b}^{\prime }=b{a}^{\prime }$ and $c{d}^{\prime }=d{c}^{\prime }$. We must show $(ad+bc,bd)\sim (a^{\prime }{d}^{\prime }+b^{\prime }{c}^{\prime },b^{\prime }{d}^{\prime })$, that is, $(ad+bc)b^{\prime }{d}^{\prime }=bd(a^{\prime }{d}^{\prime }+b^{\prime }{c}^{\prime })$. Expanding and substituting,

So the sum depends only on the classes, and addition of rationals is well defined.

Congruence classes behave as well. Define $[a]+[b]=[a+b]$ modulo $n$. If $a\equiv a^{\prime }\left(\text{mod}n\right)$ and $b\equiv b^{\prime }\left(\text{mod}n\right)$, then $(a+b)-(a^{\prime }+b^{\prime })=(a-a^{\prime })+(b-b^{\prime })$ is a sum of multiples of $n$, so $a+b\equiv a^{\prime }+b^{\prime }\left(\text{mod}n\right)$. Clock arithmetic is arithmetic on the twelve classes modulo $12$, whether nine o'clock is represented by $9$, $21$ or $-3$.

Now you. Prove that multiplication of congruence classes modulo $n$, $[a][b]=[ab]$, is well defined.

Equivalence relations group things: they say when two objects are the same for present purposes, and cut a set into classes that become objects in their own right. The other great kind of relation ranks things instead. The order $\le$ on the numbers, $\subseteq$ on sets and divisibility on the positive integers are reflexive and transitive but far from symmetric, and the next lesson takes up these orders.