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$ , functions with their images and preimages, the quantifiers, and divisibility: $a ∣ b$ when $b = a k$ for some integer $k$ . It also uses the division algorithm from the lesson on direct proof: for integers $a$ and $n$ with $n > 0$ there are unique integers $q$ and $r$ with $a = q n + r$ and $0 \leq r < n$ .

Relations as sets of pairs

A relation from a set $A$ to a set $B$ is a subset $R$ of $A \times B$ , and a relation on $A$ is a relation from $A$ to $A$ , a subset of $A \times A$ . When the pair $(a, b)$ belongs to $R$ we say $a$ is related to $b$ and write $a R b$ , or $a \sim b$ when the relation has a symbol of its own. 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 ∣ b$ . As a set of pairs this is

{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 4), (3, 3), (4, 4)}

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 small relation on a finite set can be drawn. Put a dot for each element and an arrow from $a$ to $b$ whenever $a \sim b$ , with a loop at $a$ when $a \sim a$ . The drawing, a directed graph, carries exactly the information of the set of pairs, and each property defined below becomes a visible feature of it: a loop at every dot, arrows that always come in opposite pairs, a short cut for every path of two arrows.

A function from $A$ to $B$ fits the same mould. Its graph, ${(a, f (a)) : a \in A}$ , is a relation from $A$ to $B$ in which every $a \in A$ appears as a first coordinate exactly once, so functions are the relations with that property, as the previous lesson defined them. 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.

Every relation $R$ from $A$ to $B$ has an inverse (or converse) relation $R^{- 1} = {(b, a) : (a, b) \in R}$ from $B$ to $A$ , obtained by reversing every pair. The inverse of "divides" is "is a multiple of". The inverse of the graph of a function is again a relation, and it is the graph of a function exactly when the function is a bijection, which is the theorem on inverses from the previous lesson in this language.

Reflexive, symmetric and transitive

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

reflexive: \forall a \in A (a \sim a)

symmetric: \forall a, b \in A (a \sim b \Rightarrow b \sim a)

transitive: \forall a, b, c \in A ((a \sim b \land b \sim c) \Rightarrow a \sim c)

Definition. A relation on $A$ that is reflexive, symmetric and transitive is an equivalence relation on $A$ .

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. An equivalence relation is a way of saying "these two are the same, for present purposes": same birthday, same remainder, same fractional part, same value. The three properties are the minimum any notion of sameness must have.

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 \leq y$ is reflexive and transitive but not symmetric, since $1 \leq 2$ and not $2 \leq 1$ . "Close to", meaning $| x - y | \leq 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 $x y > 0$ is symmetric and transitive (if $x y > 0$ and $y z > 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. The argument does prove something: in a symmetric and transitive relation, every element related to anything is related to itself.

"Close to" deserves a second look, because it is the commonest way to go wrong outside mathematics. Two measurements that agree within a tolerance are "the same" for practical purposes, but the tolerance does not chain: $0.0$ and $0.9$ agree within $1$ , as do $0.9$ and $1.8$ , while $0.0$ and $1.8$ do not. A chain of a thousand indistinguishable steps can join two very different things, which is the old paradox of the heap in modern dress. A relation that must be an equivalence cannot be defined by a tolerance.

Two further properties belong to the next lesson but are worth naming now so that they are not confused with these. A relation is irreflexive when no element is related to itself, as with $<$ , which is stronger than failing to be reflexive: the relation $x y > 0$ above is neither reflexive nor irreflexive, since $1 \sim 1$ holds and $0 \sim 0$ does not. And it is antisymmetric when $a \sim b$ and $b \sim a$ together force $a = b$ , as with $\leq$ . Symmetric and antisymmetric are not opposites: equality is both.

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. Label the three parts, and in each state what is assumed and what is to be shown.

Example. On $ℝ$ , let $x \sim y$ when $x - y \in ℤ$ . 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, and the same proof works with $ℤ$ replaced by any set of reals with those three properties, such as $ℚ$ or the multiples of $5$ .

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

Answer

Reflexive: for $x \neq 0$ , $\frac{x}{x} = 1$ , which is rational, so $x \sim x$ . Symmetric: let $\frac{x}{y} = q$ with $q$ rational. Since $x \neq 0$ , $q \neq 0$ , so $\frac{y}{x} = \frac{1}{q}$ is rational and $y \sim x$ . Transitive: let $\frac{x}{y} = q$ and $\frac{y}{z} = r$ with $q$ and $r$ rational. Then $\frac{x}{z} = \frac{x}{y} \cdot \frac{y}{z} = q r$ , which is rational, so $x \sim z$ . Hence $\sim$ is an equivalence relation. This time the proof used that the nonzero rationals contain $1$ and are closed under reciprocals and products: the multiplicative version of the Example.

Equivalence classes

An equivalence relation says which elements are "the same". Gathering each element together with everything the same as it gives the central object of this lesson.

Definition. Let $\sim$ be an equivalence relation on $A$ and $a \in A$ . The equivalence class of $a$ is the set of everything related to it:

[a] = {x \in A : x \sim a}

Any element of a class is a representative of it. The set of all equivalence classes is the quotient of $A$ by $\sim$ , written $A / \sim$ and read " $A$ modulo $\sim$ ", and the function $π : A \to A / \sim$ , $π (a) = [a]$ , is the quotient map.

Under the fractional part relation of the Example above, $[0.7] = {\dots, - 1.3, - 0.3, 0.7, 1.7, 2.7, \dots}$ , and $[0.7] = [2.7]$ : one class, two names. Each class contains exactly one number in $[0, 1)$ , the common fractional part, so the classes correspond to the points of $[0, 1)$ . Under "has the same birthday as", the class of a person is everyone born on the same day of the year, and there are at most 366 classes.

The quotient is a set whose elements are sets, and the notation hides a trap. The class $[a]$ is named after one of its elements, but it does not remember which name was used: $[0.7]$ and $[2.7]$ are the same set, as much as $\frac{1}{2}$ and $\frac{2}{4}$ are the same number. Everything that follows turns on one fact, that a class is the same whichever representative names it.

Lemma. Let $\sim$ be an equivalence relation on $A$ , and let $a, b \in A$ . The following are equivalent:

(i) $a \sim b$ ;

(ii) $[a] = [b]$ ;

(iii) $[a] \cap [b] \neq \emptyset$ .

Proof. We prove (i) $\Rightarrow$ (ii) $\Rightarrow$ (iii) $\Rightarrow$ (i).

(i) $\Rightarrow$ (ii). Suppose $a \sim b$ . We show $[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]$ .

(ii) $\Rightarrow$ (iii). By reflexivity $a \sim a$ , so $a \in [a]$ . If $[a] = [b]$ , then $a$ lies in both, and the intersection is not empty.

(iii) $\Rightarrow$ (i). Suppose $c \in [a] \cap [b]$ , so $c \sim a$ and $c \sim b$ . Symmetry gives $a \sim c$ , and transitivity applied to $a \sim c$ and $c \sim b$ gives $a \sim b$ . $□$

Each property of an equivalence relation did a visible job. Reflexivity put every element in its own class, symmetry let the relation be read in either direction, and transitivity carried membership from one class to another. The lemma says two classes are either equal or disjoint, never partly overlapping, and that is the content of the partition theorem below.

Example. On $ℝ^{2} = ℝ \times ℝ$ , let $(x, y) \sim (x', y')$ when $y - x^{2} = y' - x^{2}'$ . Prove that $\sim$ is an equivalence relation, describe its classes, and find a set containing exactly one representative of each class.

Reflexive: $y - x^{2} = y - x^{2}$ . Symmetric: an equation read from right to left is the same equation. Transitive: if $y - x^{2} = y' - x^{2}'$ and $y' - x^{2}' = y ′′ - x^{2} ′′$ , then $y - x^{2} = y ′′ - x^{2} ′′$ . So $\sim$ is an equivalence relation, and all three properties came straight from the corresponding properties of equality, because the relation compares the value of one quantity, $y - x^{2}$ , at two points.

The class of $(x_{0}, y_{0})$ is the set of points $(x, y)$ with $y - x^{2} = c$ , where $c = y_{0} - x_{0}^{2}$ : the parabola $y = x^{2} + c$ . So the classes are the parabolas $y = x^{2} + c$ , one for each real $c$ , stacked vertically and filling the plane without overlapping. The parabola $y = x^{2} + c$ crosses the $y$ axis exactly once, at $(0, c)$ , so the $y$ axis ${(0, c) : c \in ℝ}$ contains exactly one representative of each class.

Now you. On $ℝ^{2}$ , let $(x, y) \sim (x', y')$ when $x^{2} + y^{2} = x^{2}' + y^{2}'$ . Prove that $\sim$ is an equivalence relation, describe its classes, and find a set containing exactly one representative of each class.

Answer

Reflexive, symmetric and transitive follow from the same properties of equality, applied to the values of $x^{2} + y^{2}$ , exactly as in the Example. So $\sim$ is an equivalence relation.

The class of $(x_{0}, y_{0})$ is the set of points $(x, y)$ with $x^{2} + y^{2} = r^{2}$ , where $r = \sqrt{x_{0}^{2} + y_{0}^{2}} \geq 0$ . For $r > 0$ this is the circle of radius $r$ centred at the origin, and for $r = 0$ it is the single point $(0, 0)$ , since $x^{2} + y^{2} = 0$ forces $x = y = 0$ . So the classes are the circles centred at the origin together with the origin itself.

The ray ${(r, 0) : r \geq 0}$ contains exactly one representative of each class: the class of radius $r$ meets the $x$ axis at $(r, 0)$ and $(- r, 0)$ , and only the first has a non-negative first coordinate (for $r = 0$ the two coincide). Leaving out the origin would miss a class, and taking the whole $x$ axis would count every circle twice.

A set containing exactly one element of each class, like the $y$ axis in the Example or the ray in the Now you, is called a set of representatives or a transversal. For congruence modulo $n$ , later in the lesson, the remainders $0, 1, \dots, n - 1$ are the standard one.

Classes and partitions

A partition of a set $A$ is a collection of non-empty subsets of $A$ , its blocks, such that every element of $A$ lies in exactly one block. The even and odd integers partition $ℤ$ ; the positive reals, the negative reals and ${0}$ partition $ℝ$ ; birthdays partition a room. The sets ${1, 2}$ and ${2, 3}$ do not partition ${1, 2, 3}$ , because $2$ lies in both, and neither do ${1}$ and ${2}$ , because $3$ lies in neither.

Theorem (the partition theorem). Let $A$ be a set.

(i) If $\sim$ is an equivalence relation on $A$ , then its equivalence classes form a partition of $A$ .

(ii) If $Q$ is a partition of $A$ , then the relation " $a \sim b$ when $a$ and $b$ lie in the same block" is an equivalence relation on $A$ , whose equivalence classes are exactly the blocks of $Q$ .

(iii) These two constructions are inverse to each other: starting from an equivalence relation, forming its partition into classes, and then the relation "in the same class" returns the original relation; starting from a partition, forming the relation "in the same block", and then its classes returns the original partition.

Proof. (i) Each class is non-empty, since $a \in [a]$ by reflexivity, and every element of $A$ lies in at least one class, its own. If $a$ lies in two classes $[b]$ and $[c]$ , then $[b] \cap [c] \neq \emptyset$ , so $[b] = [c]$ by the lemma. So every element lies in exactly one class.

(ii) Reflexive: every $a$ lies in some block, and $a$ is in the same block as itself. Symmetric: " $a$ and $b$ lie in the same block" does not depend on the order in which they are named. Transitive: suppose $a$ and $b$ share a block $S$ , and $b$ and $c$ share a block $T$ . Then $b$ lies in both $S$ and $T$ , and since it lies in exactly one block, $S = T$ ; so $a$ and $c$ share the block $S$ . For the classes, let $a \in A$ and let $S$ be the block containing $a$ . Then $x \in [a]$ exactly when $x$ lies in the same block as $a$ , which is exactly when $x \in S$ . So $[a] = S$ , and every block is a class, because every block is non-empty and so is the class of any of its elements.

(iii) Starting from $\sim$ , two elements lie in the same class exactly when $[a] = [b]$ , which by the lemma is exactly when $a \sim b$ , so the relation "in the same class" is $\sim$ again. Starting from a partition, part (ii) showed that the classes of "in the same block" are the blocks. $□$

So equivalence relations on $A$ and partitions of $A$ are one idea described two ways, and the theorem gives a bijection between the set of equivalence relations on $A$ and the set of partitions of $A$ . Either description can be used, whichever is easier: a relation is often easier to define, and a partition easier to see. 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.

How many equivalence relations does a finite set carry?

By the partition theorem, as many as it has partitions. Write $B_{n}$ for the number of partitions of a set of $n$ elements. Counting by hand gives $B_{1} = 1$ , $B_{2} = 2$ and $B_{3} = 5$ , and it is natural to take $B_{0} = 1$ , since the empty set has exactly one partition, the empty collection of blocks (every element of $\emptyset$ lies in exactly one block, vacuously).

There is a recurrence. Take a set of $n + 1$ elements and fix one of them, $z$ . A partition is determined by two things: the set $K$ of elements not in the same block as $z$ , which can be any subset of the other $n$ elements, and a partition of $K$ into the remaining blocks. If $K$ has $k$ elements, there are $(\binom{n}{k})$ ways to choose $K$ and $B_{k}$ ways to partition it, so

B_{n + 1} = \sum_{k = 0}^{n} (\binom{n}{k}) B_{k}

From $B_{0} = B_{1} = 1$ and $B_{2} = 2$ this gives $B_{3} = 1 + 2 \cdot 1 + 1 \cdot 2 = 5$ , then $B_{4} = 1 + 3 + 6 + 5 = 15$ , $B_{5} = 1 + 4 + 12 + 20 + 15 = 52$ and $B_{6} = 203$ . These are the Bell numbers, named after Eric Temple Bell, who wrote about them in the 1930s. They grow much faster than $2^{n}$ but much slower than the $2^{n^{2}}$ relations: on a set of $4$ elements, $15$ of the $65 536$ relations are equivalence relations.

The number $52$ was known long before. In the Japanese incense game genjikō, played from the Edo period, five packets of incense are burned and the players must say which of them were the same; the $52$ possible answers, the partitions of a set of five, were drawn as small diagrams of vertical and horizontal bars and each named after a chapter of The Tale of Genji. Refining the count by the number of blocks gives the Stirling numbers of the second kind, and Problem 14 finds two of them.

Congruence modulo $n$

The most important equivalence relation in elementary mathematics compares integers by their remainders. Fix a positive integer $n$ . Integers $a$ and $b$ are congruent modulo $n$ , written $a \equiv b (mod n)$ , when $n ∣ a - b$ . So $17 \equiv 2 (mod 5)$ , since $17 - 2 = 15$ , and $- 7 \equiv 2 (mod 3)$ , since $- 7 - 2 = - 9$ . 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 (mod 12)$ .

Example. Prove that congruence modulo $n$ is an equivalence relation on $ℤ$ .

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

This is the fractional part Example over again, with the multiples of $n$ in place of the integers: the proof used only that the multiples of $n$ contain $0$ and are closed under negation and addition.

The classes are the congruence classes (or residue classes) modulo $n$ , and the class of $a$ is

[a] = {b \in ℤ : b \equiv a (mod n)} = {a + k n : k \in ℤ}

the integers reached from $a$ by adding or subtracting $n$ any number of times. When the modulus needs saying, write $[a]_{n}$ .

Theorem. Let $n$ be a positive integer. Then $a \equiv b (mod n)$ exactly when $a$ and $b$ leave the same remainder on division by $n$ . Consequently there are exactly $n$ congruence classes modulo $n$ , namely $[0], [1], \dots, [n - 1]$ , and they are all different.

Proof. Divide both numbers by $n$ : $a = q n + r$ and $b = q' n + r'$ with $0 \leq r, r' < n$ . If $r = r'$ , then $a - b = (q - q') n$ , so $a \equiv b (mod n)$ . Conversely, suppose $a - b = k n$ . Then $a = b + k n = (q' + k) n + r'$ with $0 \leq r' < n$ , which is a division of $a$ by $n$ with remainder in range, so by the uniqueness half of the division algorithm $r = r'$ .

So every integer $a$ is congruent to its remainder $r$ , and lies in the class $[r]$ , one of $[0], [1], \dots, [n - 1]$ . These $n$ classes are different, because two distinct numbers $r$ and $s$ in the range $0$ to $n - 1$ are their own remainders, which differ, so they are not congruent, and by the lemma on classes $[r] \neq [s]$ . $□$

For $n = 3$ :

[0] = {\dots, - 3, 0, 3, 6, \dots} [1] = {\dots, - 2, 1, 4, 7, \dots} [2] = {\dots, - 1, 2, 5, 8, \dots}

and these three sets partition $ℤ$ . For $n = 2$ the two classes are the even and the odd integers, so the corollary of the division algorithm that every integer is even or odd, and not both, is the partition theorem for congruence modulo $2$ . For $n = 1$ there is a single class, $ℤ$ itself, since $1$ divides everything.

The set of congruence classes modulo $n$ is written $ℤ / n ℤ$ , read " $ℤ$ mod $n ℤ$ ", where $n ℤ = {n k : k \in ℤ}$ is the set of multiples of $n$ ; some books write $ℤ_{n}$ . So

ℤ / n ℤ = {[0], [1], \dots, [n - 1]}

is a set of $n$ elements, each of which is an infinite set of integers. The remainders $0$ to $n - 1$ form a set of representatives, and there are others: ${- 1, 0, 1}$ also contains one element of each class modulo $3$ .

Now you. On $ℤ$ , let $a \sim b$ when $3 ∣ a + 2 b$ . Prove that $\sim$ is an equivalence relation, and identify its classes.

Answer

Reflexive: $a + 2 a = 3 a$ , so $a \sim a$ . Symmetric: let $a + 2 b = 3 k$ . Then $b + 2 a = 3 (a + b) - (a + 2 b) = 3 (a + b - k)$ , so $b \sim a$ . Transitive: let $a + 2 b = 3 k$ and $b + 2 c = 3 m$ . Then $a + 2 c = (a + 2 b) + (b + 2 c) - 3 b = 3 (k + m - b)$ , so $a \sim c$ .

In fact $a + 2 b = (a - b) + 3 b$ , so $3 ∣ a + 2 b$ exactly when $3 ∣ a - b$ : this is congruence modulo $3$ in disguise, and its classes are $[0]$ , $[1]$ and $[2]$ modulo $3$ . Spotting the disguise first would have given all three properties at once from the Example.

Why not just work with the remainders

0

n - 1

For integers, one could. Define an arithmetic on the set ${0, 1, \dots, n - 1}$ by "add or multiply as usual, then take the remainder", and nothing in this lesson would be lost. Many programming languages do exactly that, and the Discrete Mathematics course computes with remainders all the time.

The classes earn their place in three ways. First, they need no choice of representative. The remainders are one set of representatives among many, and statements such as $[a] + [b] = [a + b]$ , proved below, hold for every representative at once, which is what makes computations such as $[- 1]^{100} = [1]$ legitimate without first converting $- 1$ to $n - 1$ . Second, the construction works where no convenient representatives exist. In the fractional-part relation on $ℝ$ the interval $[0, 1)$ does the job, but for the fractions built at the end of this lesson, "the representative in lowest terms" needs the theory of greatest common divisors to even define, while the classes need nothing. Third, the same construction applies far beyond the integers. The notation $ℤ / n ℤ$ records that the classes are the sets $a + n ℤ$ , translates of the set of multiples of $n$ . Group theory takes any group $G$ and any suitable subgroup $H$ and forms $G / H$ from the translates of $H$ in exactly this way; linear algebra forms quotient spaces $V / W$ of a vector space by a subspace; topology glues spaces together by declaring points equivalent. In each case there is usually no preferred representative, and the classes are the only way to proceed.

The price is the obligation that the next section is about: any operation defined through representatives must be shown to be independent of them.

Well defined operations

Clock arithmetic adds hours: nine o'clock plus five hours is two o'clock. In the language of classes, that is the rule

[a] + [b] = [a + b] [a] \cdot [b] = [a b]

on $ℤ / n ℤ$ , with $n = 12$ . The rule is stated through representatives: to add two classes, pick an element of each, add the elements, and take the class of the result. A class has infinitely many representatives, and nothing yet guarantees that different choices give the same answer. If they did not, the rule would assign several values to one pair of classes, and it would not be a function at all.

Definition. Let $\sim$ be an equivalence relation on $A$ , and let $F$ be a rule that assigns to each element of $A$ an element of a set $C$ . The rule " $[a] \mapsto F (a)$ " is well defined on $A / \sim$ when

a \sim a' \Rightarrow F (a) = F (a') for all a, a' \in A

that is, when $F$ takes the same value on all representatives of a class. For a rule in two variables, such as addition, the condition is that $a \sim a'$ and $b \sim b'$ together imply $F (a, b) = F (a', b')$ .

In the language of the previous lesson, the rule proposes the set of pairs ${([a], F (a)) : a \in A}$ as the graph of a function on $A / \sim$ . Every class appears as a first coordinate, since every class has a representative, so the first half of the definition of a function is automatic. The second half, that no class appears with two different values, is exactly the condition above. A proof that a rule is well defined is therefore a proof that it defines a function, and it must always be given.

Here is one that fails. "Send the class of $a$ modulo $3$ to the class of $a$ modulo $6$ ", $[a]_{3} \mapsto [a]_{6}$ , looks innocent. But $[0]_{3} = [3]_{3}$ , and the rule sends this one class to $[0]_{6}$ through one name and to $[3]_{6}$ through the other, and $[0]_{6} \neq [3]_{6}$ because $6 ∤ 3$ . So there is no such function. The rule $[a] \mapsto a$ from $ℤ / n ℤ$ to $ℤ$ fails for the same reason whenever $n > 1$ : $[0] = [n]$ but $0 \neq n$ .

Addition modulo $n$ , on the other hand, is well defined. Let $a \equiv a' (mod n)$ and $b \equiv b' (mod n)$ , say $a - a' = n k$ and $b - b' = n m$ . Then

(a + b) - (a' + b') = (a - a') + (b - b') = n (k + m)

so $a + b \equiv a' + b' (mod n)$ , and $[a + b] = [a' + b']$ . Clock arithmetic works whether nine o'clock is represented by $9$ , $21$ or $- 3$ .

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

Let $a \equiv a' (mod n)$ and $b \equiv b' (mod n)$ , so $a - a' = n k$ and $b - b' = n m$ for integers $k$ and $m$ . The goal is $n ∣ a b - a' b'$ , and the trick is to change one factor at a time, adding and subtracting the mixed product $a b'$ :

a b - a' b' = (a b - a b') + (a b' - a' b') = a (b - b') + b' (a - a') = n (a m + b' k)

Since $a m + b' k$ is an integer, $a b \equiv a' b' (mod n)$ , so $[a b] = [a' b']$ and the product class does not depend on the representatives.

Because both operations are well defined, congruences can be added and multiplied like equations: from $a \equiv a'$ and $b \equiv b'$ follow $a + b \equiv a' + b'$ and $a b \equiv a' b'$ , and by induction $a^{k} \equiv a^{k}'$ for every natural number $k$ . That is how large remainders are found without large numbers. For example, $10 \equiv 1 (mod 9)$ , so $10^{k} \equiv 1^{k} = 1 (mod 9)$ for every $k$ , and a number with decimal digits $d_{k} \dots d_{1} d_{0}$ satisfies

d_{0} + 10 d_{1} + 10^{2} d_{2} + \dots + 10^{k} d_{k} \equiv d_{0} + d_{1} + \dots + d_{k} (mod 9)

so a number and the sum of its digits leave the same remainder on division by $9$ : the old rule of "casting out nines". Similarly $2^{10} = 1024 \equiv 1 (mod 11)$ , since $1024 = 11 \times 93 + 1$ , so $2^{1000} = (2^{10})^{100} \equiv 1^{100} = 1 (mod 11)$ .

With the operations in hand, $ℤ / n ℤ$ is a number system with $n$ elements. It obeys the familiar laws, commutativity, associativity and distributivity, because each law holds for representatives and the operations are computed from representatives: for instance $[a] ([b] + [c]) = [a (b + c)] = [a b + a c] = [a] [b] + [a] [c]$ . It also behaves in unfamiliar ways. In $ℤ / 6 ℤ$ , $[2] [3] = [6] = [0]$ , a product of two non-zero classes that is zero. In $ℤ / 5 ℤ$ that never happens, and every non-zero class has a multiplicative inverse: $[1] [1] = [2] [3] = [4] [4] = [1]$ . Which $n$ behave like $5$ and which like $6$ , and why, is the subject of the Discrete Mathematics lesson on modular arithmetic, which builds on the definitions here.

Now you. Show that the rule $[a]_{12} \mapsto [a]_{4}$ , from $ℤ / 12 ℤ$ to $ℤ / 4 ℤ$ , is well defined, and that the rule $[a]_{4} \mapsto [a]_{12}$ is not. Interpret the first on a clock face.

Answer

Well defined: suppose $[a]_{12} = [a']_{12}$ , so $a - a' = 12 k$ for some integer $k$ . Then $a - a' = 4 (3 k)$ , so $a \equiv a' (mod 4)$ and $[a]_{4} = [a']_{4}$ . The value does not depend on the representative.

Not well defined: $[0]_{4} = [4]_{4}$ , since $4 ∣ 4 - 0$ , but $[0]_{12} \neq [4]_{12}$ , since $12 ∤ 4$ . The rule gives two different values for one class.

On a clock face, the first rule sorts the twelve hours into four classes by their remainder on division by $4$ : $1$ , $5$ and $9$ o'clock all go to $[1]_{4}$ , and $4$ , $8$ and $12$ o'clock to $[0]_{4}$ . It is well defined because $4 ∣ 12$ , so a full turn of the clock is a whole number of cycles of $4$ . The same argument shows that $[a]_{n} \mapsto [a]_{m}$ is well defined whenever $m ∣ n$ .

Can congruence classes be raised to powers?

A power with a class as the base is fine: $[a]^{k} = [a^{k}]$ for a natural number $k$ is repeated multiplication, and it is well defined because multiplication is. The trouble is a class in the exponent. The rule $[a]^{[b]} = [a^{b}]$ on $ℤ / n ℤ$ , with $b$ restricted to non-negative representatives, is not well defined. Modulo $3$ , $[1] = [4]$ , but $2^{1} = 2$ and $2^{4} = 16 \equiv 1 (mod 3)$ , so $[2]^{[1]}$ would be both $[2]$ and $[1]$ . The base respects congruence modulo $n$ , and the exponent does not.

The exponent does respect a different congruence. Pierre de Fermat stated in a letter of 1640 what is now called Fermat's little theorem: if $p$ is prime and $p ∤ a$ , then $a^{p - 1} \equiv 1 (mod p)$ . Granting it, if $b \equiv b' (mod p - 1)$ with $b, b' \geq 0$ , say $b = b' + (p - 1) t$ with $t \geq 0$ , then $a^{b} = a^{b'} (a^{p - 1})^{t} \equiv a^{b'} (mod p)$ . So for a base not divisible by $p$ , the exponent may be reduced modulo $p - 1$ : modulo $3$ , exponents live modulo $2$ , and indeed $2^{1} \equiv 2$ and $2^{4} \equiv 1$ differ because $1$ and $4$ are not congruent modulo $2$ . Leonhard Euler generalised this to any modulus, and the result is the arithmetic behind RSA encryption, where a message is raised to one power to encrypt it and to another, chosen through the exponent's own modulus, to decrypt it. The Discrete Mathematics lesson on Fermat, Euler and RSA proves both theorems.

The lesson for well-definedness is that an operation can respect the relation in one argument and not in another, so each argument must be checked.

Kernels and quotient maps

Several equivalence relations in this lesson had the same shape: two points of the plane were related when $y - x^{2}$ , or $x^{2} + y^{2}$ , took the same value at both. Every function produces a relation of this kind, and every equivalence relation arises this way.

Definition. Let $f : A \to B$ . The kernel of $f$ is the relation on $A$ given by $a \sim_{f} a'$ when $f (a) = f (a')$ .

The name is borrowed from algebra, where the kernel of a homomorphism is the set of elements sent to the identity, and the relation defined here is its general form. (Some books call it the equivalence kernel, or the relation "induced by" $f$ .)

Theorem. Let $f : A \to B$ .

(i) The kernel $\sim_{f}$ is an equivalence relation on $A$ , and its classes are the non-empty fibres $f^{- 1} (b)$ , for $b$ in the range $f (A)$ .

(ii) The rule $\overline{f} : A / \sim_{f} \to f (A)$ , $\overline{f} ([a]) = f (a)$ , is well defined and is a bijection.

(iii) $f = ι \circ \overline{f} \circ π$ , where $π : A \to A / \sim_{f}$ is the quotient map and $ι : f (A) \to B$ is the inclusion.

(iv) Every equivalence relation $\sim$ on a set $A$ is the kernel of its own quotient map $π : A \to A / \sim$ .

Proof. (i) Reflexivity, symmetry and transitivity of $\sim_{f}$ are those of equality, applied to the values of $f$ : $f (a) = f (a)$ ; if $f (a) = f (a')$ then $f (a') = f (a)$ ; if $f (a) = f (a')$ and $f (a') = f (a ′′)$ then $f (a) = f (a ′′)$ . The class of $a$ is ${x \in A : f (x) = f (a)}$ , which is the fibre $f^{- 1} (f (a))$ . Conversely each fibre over an element $b = f (a)$ of the range is the class of $a$ .

(ii) Well defined: if $[a] = [a']$ , then $a \sim_{f} a'$ , which means $f (a) = f (a')$ . Surjective: every element of $f (A)$ is $f (a) = \overline{f} ([a])$ for some $a$ . Injective: if $\overline{f} ([a]) = \overline{f} ([a'])$ , then $f (a) = f (a')$ , so $a \sim_{f} a'$ and $[a] = [a']$ by the lemma on classes.

(iii) For $a \in A$ , $(ι \circ \overline{f} \circ π) (a) = ι (\overline{f} ([a])) = f (a)$ .

(iv) For $a, a' \in A$ , $π (a) = π (a')$ means $[a] = [a']$ , which by the lemma on classes means $a \sim a'$ . So the kernel of $π$ is $\sim$ . $□$

Part (iii) says that every function is a surjection, then a bijection, then an injection: first collapse each fibre to a single point, then match the collapsed points one to one with the values, then include the values in the codomain. Part (iv) says that "equivalence relation" and "kernel of a function" are the same notion. Together they give a practical method. To prove a relation is an equivalence, it is enough to find a function whose equal values define it, and then the classes are the fibres and can be counted by counting the values.

In the proof of (ii), well-definedness and injectivity were the same argument read in opposite directions: " $a \sim_{f} a'$ implies $f (a) = f (a')$ " and " $f (a) = f (a')$ implies $a \sim_{f} a'$ ". That is typical. A rule on classes is well defined when it does not distinguish elements that the relation identifies, and injective when it distinguishes all the elements that the relation does not identify.

Example. On $ℤ$ , let $a \sim b$ when $a^{2} \equiv b^{2} (mod 5)$ . Show that $\sim$ is an equivalence relation, and find its classes.

The relation is the kernel of $f : ℤ \to ℤ / 5 ℤ$ , $f (a) = [a^{2}]$ , since $a^{2} \equiv b^{2} (mod 5)$ says exactly $[a^{2}] = [b^{2}]$ . So it is an equivalence relation by part (i) of the theorem, and its classes are the non-empty fibres of $f$ .

To find the fibres, note that $f (a) = [a]^{2}$ depends only on the class of $a$ modulo $5$ , because multiplication of classes is well defined. So it is enough to square the five classes: $[0]^{2} = [0]$ , $[1]^{2} = [1]$ , $[2]^{2} = [4]$ , $[3]^{2} = [9] = [4]$ and $[4]^{2} = [16] = [1]$ . The range of $f$ is ${[0], [1], [4]}$ , and the fibres are

f^{- 1} ([0]) = [0]_{5} f^{- 1} ([1]) = [1]_{5} \cup [4]_{5} f^{- 1} ([4]) = [2]_{5} \cup [3]_{5}

So there are three classes: the multiples of $5$ , the integers congruent to $1$ or $- 1$ modulo $5$ , and those congruent to $2$ or $- 2$ . The classes $[2]$ and $[3]$ are not squares modulo $5$ , so their fibres are empty and contribute no class. As a check, $3^{2} = 9$ and $7^{2} = 49$ are congruent modulo $5$ , and indeed $3 \equiv - 2$ and $7 \equiv 2$ lie in the same class.

Now you. On $ℤ$ , let $a \sim b$ when $a^{3} \equiv b^{3} (mod 7)$ . Show that $\sim$ is an equivalence relation, and find its classes.

Answer

It is the kernel of $f : ℤ \to ℤ / 7 ℤ$ , $f (a) = [a^{3}] = [a]^{3}$ , so it is an equivalence relation, with the non-empty fibres of $f$ as its classes. Since $f (a)$ depends only on $[a]_{7}$ , cube the seven classes: $0^{3} = 0$ ; $1^{3} = 1$ ; $2^{3} = 8 \equiv 1$ ; $3^{3} = 27 \equiv 6$ ; $4^{3} = 64 \equiv 1$ ; $5^{3} = 125 \equiv 6$ ; $6^{3} = 216 \equiv 6$ . (For instance $125 = 7 \times 17 + 6$ and $216 = 7 \times 30 + 6$ .)

The range is ${[0], [1], [6]}$ , and the three classes are $[0]_{7}$ , then $[1]_{7} \cup [2]_{7} \cup [4]_{7}$ , then $[3]_{7} \cup [5]_{7} \cup [6]_{7}$ . So $2 \sim 4 \sim 8 \sim 9$ and $3 \sim 5 \sim - 1$ , while $1$ and $3$ are in different classes.

What else is built by identifying things?

Much of geometry and topology. Take the fractional-part relation on $ℝ$ from the start of the lesson, $x \sim y$ when $x - y \in ℤ$ , and form the quotient $ℝ / \sim$ , usually written $ℝ / ℤ$ . Each class has exactly one representative in $[0, 1)$ , but the quotient is better pictured as a circle than as an interval. Numbers just below $1$ , such as $0.99$ , are close to numbers just above $0$ , such as $0.01$ , once $1$ and $0$ are identified, so walking right along $ℝ$ goes round and round the quotient. The kernel theorem makes this exact: the function $x \mapsto (\cos 2 π x, \sin 2 π x)$ from $ℝ$ to the unit circle is surjective, and its kernel is exactly $\sim$ , because the cosine and sine of two angles both agree exactly when the angles differ by a whole number of turns. So $ℝ / ℤ$ is in bijection with the circle. Angles, times of day and the phase of any periodic process live naturally in this quotient.

The same idea in two dimensions: on $ℝ^{2}$ , let $(x, y) \sim (x', y')$ when both $x - x'$ and $y - y'$ are integers. Each class has one representative in the unit square $[0, 1) \times [0, 1)$ , and passing to the quotient glues the left edge of the square to the right edge and the bottom edge to the top. The result is a torus, the surface of a ring doughnut, and it is the world of old arcade games in which a ship leaving the screen on one side reappears on the other. Gluing the edges of a strip with a half twist gives a Möbius band; identifying each point of a sphere with the opposite point gives the projective plane, the setting of projective geometry.

In algebra the same move builds new number systems. The complex numbers can be constructed as a quotient of the polynomials with real coefficients, by declaring two polynomials equivalent when their difference is a multiple of $x^{2} + 1$ , so that the class of $x$ becomes a square root of $- 1$ . The arithmetic of $ℤ / n ℤ$ is the simplest instance of all these constructions, and the requirement met in this lesson, that the operations be well defined, is exactly what each of them has to check.

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 $ℚ$ from $ℤ$ without assuming the division it is meant to create.

Let $P = {(a, b) \in ℤ \times ℤ : b \neq 0}$ , and for pairs in $P$ let $(a, b) \sim (c, d)$ when $a d = b c$ , the cross multiplication test stated with multiplication alone. It is reflexive, since $a b = b a$ , and symmetric, since $a d = b c$ is the same equation as $c b = d a$ . Transitivity is the real work.

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

Proof. We are given $a d = b c$ and $c f = d e$ , and must show $a f = b e$ . Multiplying the first equation by $f$ gives $a d f = b c f$ , and by the second $b c f = b d e$ . Hence $a d f = b d e$ , that is, $d (a f - b e) = 0$ . The pair $(c, d)$ lies in $P$ , so $d \neq 0$ , and a product of integers is zero only when a factor is; so $a f = b e$ . $□$

The condition $d \neq 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, and it fails exactly at the step that cancelled $d$ .

Definition. A rational number is an equivalence class $[(a, b)]$ of pairs in $P$ , written $\frac{a}{b}$ , and $ℚ = P / \sim$ is the set of these classes.

So $\frac{1}{2}$ is the set ${(1, 2), (2, 4), (- 3, - 6), (5, 10), \dots}$ , and the familiar facts about fractions become facts about classes. " $\frac{a}{b} = \frac{c}{d}$ exactly when $a d = b c$ " is the lemma on classes. "Every fraction can be written with a positive denominator" says that each class contains a pair with $b > 0$ , since $(a, b) \sim (- a, - b)$ . "Every fraction can be written in lowest terms" says that each class contains a pair with $b > 0$ and no common factor greater than $1$ , and that such a pair is unique, which is a real theorem about integers rather than a fact about notation.

The integers sit inside $ℚ$ through the map $j : ℤ \to ℚ$ , $j (n) = [(n, 1)]$ . It is injective: if $[(n, 1)] = [(m, 1)]$ then $n \cdot 1 = 1 \cdot m$ , so $n = m$ . It is not surjective, since $[(1, 2)]$ is not $[(n, 1)]$ for any integer $n$ ( $1 \cdot 1 = 2 n$ has no integer solution). Identifying each integer $n$ with $j (n)$ is how " $ℤ \subseteq ℚ$ " is meant.

Arithmetic comes next, through representatives, and it carries the obligation of the section on well defined operations. The school rules

\frac{a}{b} + \frac{c}{d} = \frac{a d + b c}{b d} \frac{a}{b} \cdot \frac{c}{d} = \frac{a c}{b d}

compute with a chosen pair from each class, and they define operations on $ℚ$ only if the answer is independent of the choice. A school favourite shows that this can fail: "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} \neq \frac{3}{7}$ because $2 \cdot 7 = 14$ and $5 \cdot 3 = 15$ . So $\oplus$ is not an operation on $ℚ$ at all.

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

First, $b d \neq 0$ because $b \neq 0$ and $d \neq 0$ , so $(a d + b c, b d)$ lies in $P$ and the result is a rational number. Now let $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$ , that is, $a b' = b a'$ and $c d' = d c'$ . We must show $(a d + b c, b d) \sim (a' d' + b' c', b' d')$ , that is, $(a d + b c) b' d' = b d (a' d' + b' c')$ . Expanding, grouping, and substituting the two hypotheses,

(a d + b c) b' d' = (a b') d d' + (c d') b b' = (b a') d d' + (d c') b b' = b d (a' d' + b' c')

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

Now you. Prove that multiplication of rationals, $[(a, b)] \cdot [(c, d)] = [(a c, b d)]$ , is well defined, and check that on integers it agrees with ordinary multiplication: $j (m) \cdot j (n) = j (m n)$ .

Answer

Since $b \neq 0$ and $d \neq 0$ , $b d \neq 0$ , so $(a c, b d) \in P$ . Let $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$ , so $a b' = b a'$ and $c d' = d c'$ . We must show $(a c) (b' d') = (b d) (a' c')$ . Rearranging and substituting,

(a c) (b' d') = (a b') (c d') = (b a') (d c') = (b d) (a' c')

so the product class does not depend on the representatives. On integers, $j (m) \cdot j (n) = [(m, 1)] \cdot [(n, 1)] = [(m n, 1)] = j (m n)$ . The same check for addition gives $[(m \cdot 1 + 1 \cdot n, 1)] = j (m + n)$ , so the new arithmetic extends the old.

With both operations defined, the laws of arithmetic on $ℚ$ are proved from those on $ℤ$ one representative at a time, as for $ℤ / n ℤ$ . The new feature is division: a non-zero rational $[(a, b)]$ has $a \neq 0$ , so $(b, a) \in P$ , and $[(a, b)] \cdot [(b, a)] = [(a b, b a)] = [(1, 1)] = j (1)$ , since $a b \cdot 1 = b a \cdot 1$ . Every non-zero rational has a multiplicative inverse, which no integer other than $1$ and $- 1$ has in $ℤ$ . The division that could not be assumed has been built.

Is a fraction really an infinite set of pairs?

It is one way to make "fraction" precise, and the point of the construction is not that anyone should think of $\frac{1}{2}$ as an infinite set while doing arithmetic. The point is that the construction exists. It shows that the rational numbers, with all their laws, can be built from the integers using nothing but sets, so that any contradiction in the theory of $ℚ$ would already be a contradiction in the theory of $ℤ$ . After the construction, what matters is how the rationals behave, and any other construction that produced a system with the same behaviour would serve equally well.

The same method goes further down and further up. The integers can be built from the natural numbers: declare pairs $(a, b)$ of natural numbers equivalent when $a + d = b + c$ , thinking of $(a, b)$ as " $a - b$ ", which avoids assuming the subtraction it creates. Problem 12 carries this out. The natural numbers themselves can be built from sets alone: in the standard construction, due to John von Neumann, the number $0$ is the empty set and each later whole number is the set of those before it, so that $1 = {0}$ , $2 = {0, 1}$ , and so on.

Going up, the real numbers cannot be built from $ℚ$ by an equivalence relation on pairs, because there are "more" reals than pairs of rationals, a fact made precise later in the course. Both classical constructions were published in 1872. Richard Dedekind defined a real number as a "cut", a way of splitting the rationals into a lower and an upper part, and $\sqrt{2}$ as the cut between the rationals whose square is below $2$ (together with all negative rationals) and the rest. Georg Cantor used sequences of rationals whose terms get closer and closer together, with two such sequences declared equivalent when their difference tends to $0$ : an equivalence relation again, on sequences rather than pairs, and a real number is a class of them. So each step of the ladder $ℕ$ , $ℤ$ , $ℚ$ , $ℝ$ above the first is built by the method of this lesson or a close relative.

Grouping and ranking

Equivalence relations group things. They say when two objects are the same for present purposes, cut a set into classes, and let the classes become objects in their own right, with operations of their own once those are shown to be well defined. Every equivalence relation is the kernel of a function, and every function is, up to a bijection, the quotient map of its kernel followed by an inclusion.

The other great kind of relation ranks things instead. The order $\leq$ on the numbers, $\subseteq$ on sets and divisibility on the positive integers are reflexive and transitive but far from symmetric: indeed they are antisymmetric, as two things each ranked below the other are the same thing. The lesson on order takes up these relations, and meets equivalence relations again at once: a relation that is merely reflexive and transitive, such as "divides" on all of $ℤ$ , where $3 ∣ - 3$ and $- 3 ∣ 3$ , becomes an order only after the elements it cannot tell apart are identified.

Problems

Work each problem on paper before opening anything; for Core and Challenge problems, try the hint before the solution.

Warm-up

1. For each relation on ${1, 2, 3}$ , decide whether it is reflexive, symmetric and transitive, giving a failing instance for each property that fails. (a) $R_{1} = {(1, 1), (2, 2), (3, 3), (1, 2), (2, 1)}$ . (b) $R_{2} = {(1, 2), (2, 3), (1, 3)}$ . (c) $R_{3} = {(1, 1), (2, 2)}$ . (d) $R_{4} = \emptyset$ .

Solution

(a) Reflexive, since $(1, 1)$ , $(2, 2)$ , $(3, 3)$ are all present. Symmetric: the only pairs with different entries are $(1, 2)$ and $(2, 1)$ , and each has its reverse. Transitive: in a chain $a \sim b \sim c$ in which one step is a loop, the conclusion $a \sim c$ is the other step, which is present; the only other chains are $1 \sim 2 \sim 1$ and $2 \sim 1 \sim 2$ , whose conclusions $(1, 1)$ and $(2, 2)$ are present. So $R_{1}$ is an equivalence relation, with classes ${1, 2}$ and ${3}$ .

(b) Not reflexive: $(1, 1) \notin R_{2}$ . Not symmetric: $(1, 2) \in R_{2}$ but $(2, 1) \notin R_{2}$ . Transitive: the only chain of two pairs is $1 \sim 2 \sim 3$ , and $(1, 3) \in R_{2}$ .

(c) Not reflexive: $(3, 3) \notin R_{3}$ . Symmetric, since each pair is its own reverse. Transitive: the only chains are $1 \sim 1 \sim 1$ and $2 \sim 2 \sim 2$ , whose conclusions are present. This is a symmetric, transitive relation that is not reflexive, and it fails at $3$ , the element related to nothing.

(d) Not reflexive: $(1, 1) \notin R_{4}$ . Symmetric and transitive vacuously, since there are no pairs for the conditions to fail at.

2. Which of these are partitions of $ℤ$ ? (a) The even integers and the odd integers. (b) The positive integers and the negative integers. (c) The sets ${3 k, 3 k + 1, 3 k + 2}$ , one for each integer $k$ . (d) The multiples of $2$ , the multiples of $3$ , and the integers divisible by neither. For each partition, describe the corresponding equivalence relation.

Solution

(a) A partition: both sets are non-empty, and every integer is even or odd and not both. The relation is " $a - b$ is even", congruence modulo $2$ .

(b) Not a partition: $0$ is in neither set.

(c) A partition. Each set has three elements, so is non-empty. Every integer $n$ lies in the set with $k$ equal to its quotient on division by $3$ , since $n = 3 k + r$ with $0 \leq r \leq 2$ , and in no other, by uniqueness of the quotient. The relation is " $a$ and $b$ have the same quotient on division by $3$ ", the kernel of the function sending each integer to its quotient; for example $3 \sim 5$ , both having quotient $1$ , while $5$ and $6$ are not related.

(d) Not a partition: $6$ is a multiple of both $2$ and $3$ , so it lies in two blocks.

3. In $ℤ / 4 ℤ$ , find the classes containing $2026$ , $- 7$ and $103$ , and compute $[3] + [3]$ , $[3] \cdot [3]$ and $[2] \cdot [2]$ . In $ℤ / 7 ℤ$ , find all classes $x$ with $[3] x = [1]$ , and in $ℤ / 8 ℤ$ all classes $x$ with $[2] x = [0]$ .

Solution

$2026 = 4 \times 506 + 2$ , so $2026 \in [2]$ . $- 7 = 4 \times (- 2) + 1$ , so $- 7 \in [1]$ . $103 = 4 \times 25 + 3$ , so $103 \in [3]$ .

$[3] + [3] = [6] = [2]$ , $[3] \cdot [3] = [9] = [1]$ and $[2] \cdot [2] = [4] = [0]$ .

In $ℤ / 7 ℤ$ there are seven classes to try, and $[3] [x]$ for $x = 0, 1, \dots, 6$ is $[0], [3], [6], [2], [5], [1], [4]$ (for instance $3 \cdot 5 = 15 = 2 \times 7 + 1$ ). So $x = [5]$ is the only solution.

In $ℤ / 8 ℤ$ , $[2] [x] = [2 x]$ is $[0]$ exactly when $8 ∣ 2 x$ , and trying $x = 0, \dots, 7$ gives $2 x = 0, 2, 4, 6, 8, 10, 12, 14$ , of which $0$ and $8$ are multiples of $8$ . So $x = [0]$ or $x = [4]$ : two solutions, and a non-zero product that is zero.

4. Write out, as a set of ordered pairs, the equivalence relation on ${1, 2, 3, 4, 5, 6}$ whose classes are ${1, 2, 3}$ , ${4, 5}$ and ${6}$ . How many pairs does it contain? In general, how many pairs does an equivalence relation on a finite set contain, in terms of the sizes of its classes?

Solution

Two elements are related exactly when they lie in the same class, so the relation is the union of $C \times C$ over the classes $C$ :

{1, 2, 3} \times {1, 2, 3} \cup {4, 5} \times {4, 5} \cup {(6, 6)}

that is, the nine pairs $(a, b)$ with $a, b \in {1, 2, 3}$ , the four pairs $(4, 4), (4, 5), (5, 4), (5, 5)$ , and $(6, 6)$ : $9 + 4 + 1 = 14$ pairs.

In general, if the classes have sizes $c_{1}, c_{2}, \dots, c_{k}$ , the relation is the union of the disjoint sets $C_{i} \times C_{i}$ , so it has $c_{1}^{2} + c_{2}^{2} + \dots + c_{k}^{2}$ pairs. The two extremes are equality, with $n$ classes of size $1$ and $n$ pairs, and the relation that relates everything, with one class and $n^{2}$ pairs.

Core

5. On the set $ℝ^{2} ∖ {(0, 0)}$ of non-zero points of the plane, let $(x, y) \sim (x', y')$ when $(x', y') = (λ x, λ y)$ for some non-zero real number $λ$ . Prove that $\sim$ is an equivalence relation, describe its classes geometrically, and prove that ${(1, m) : m \in ℝ} \cup {(0, 1)}$ contains exactly one representative of each class.

Hint

For the three properties, find the $λ$ that works in each case: $1$ , then $\frac{1}{λ}$ , then a product. For the representatives, split on whether the first coordinate is zero.

Solution

Reflexive: $(x, y) = (1 \cdot x, 1 \cdot y)$ . Symmetric: if $(x', y') = (λ x, λ y)$ with $λ \neq 0$ , then $(x, y) = (\frac{1}{λ} x', \frac{1}{λ} y')$ with $\frac{1}{λ} \neq 0$ . Transitive: if $(x', y') = (λ x, λ y)$ and $(x ′′, y ′′) = (μ x', μ y')$ with $λ, μ \neq 0$ , then $(x ′′, y ′′) = (μ λ x, μ λ y)$ with $μ λ \neq 0$ . So $\sim$ is an equivalence relation.

The class of $(x, y)$ is ${(λ x, λ y) : λ \neq 0}$ , the line through the origin and $(x, y)$ with the origin removed. So the classes are the lines through the origin, each with the origin deleted.

Representatives. Let $(x, y)$ be a non-zero point. If $x \neq 0$ , take $λ = \frac{1}{x}$ : then $(1, \frac{y}{x})$ is in the class, and it has the form $(1, m)$ . If $x = 0$ , then $y \neq 0$ , and $λ = \frac{1}{y}$ gives $(0, 1)$ in the class. So every class contains at least one point of the set.

It contains only one. If $(1, m) \sim (1, m')$ , then $(1, m') = (λ, λ m)$ , so $λ = 1$ and $m' = m$ . And $(0, 1)$ is not related to any $(1, m)$ , since every point related to $(0, 1)$ has the form $(0, λ)$ , with first coordinate $0$ . So distinct points of the set lie in distinct classes.

The quotient is the projective line: the set of directions through the origin, each line counted once. The representatives $(1, m)$ are labelled by the slope $m$ , and $(0, 1)$ is the vertical line, the one direction with no slope.

6. Find the flaw in this proof, and show that the claim is false.

Claim. The rule $f ([a]_{6}) = [a]_{4}$ defines a function from $ℤ / 6 ℤ$ to $ℤ / 4 ℤ$ .

Proof. We must check that $f$ is well defined. Suppose $[a]_{6} = [b]_{6}$ . Then $f ([a]_{6}) = [a]_{4}$ and $f ([b]_{6}) = [b]_{4}$ . Since $[a]_{6} = [b]_{6}$ , we have $a = b$ , and so $[a]_{4} = [b]_{4}$ . Hence $f$ is well defined.

Hint

What does $[a]_{6} = [b]_{6}$ actually tell you about $a$ and $b$ ?

Solution

The flaw is the step "since $[a]_{6} = [b]_{6}$ , we have $a = b$ ". Equal classes do not have equal representatives; by the lemma on classes, $[a]_{6} = [b]_{6}$ means only that $a \equiv b (mod 6)$ , that is, $6 ∣ a - b$ . The whole point of checking well-definedness is to handle two different representatives of one class, and the proof assumed the difficulty away.

The claim is false. Take $a = 0$ and $b = 6$ . Then $[0]_{6} = [6]_{6}$ , but the rule sends this class to $[0]_{4}$ through the first name and to $[6]_{4} = [2]_{4}$ through the second, and $[0]_{4} \neq [2]_{4}$ since $4 ∤ 2$ . So the rule does not define a function. By the argument of the Now you on well defined operations, $[a]_{n} \mapsto [a]_{m}$ is well defined when $m ∣ n$ , and here $4 ∤ 6$ .

7. For which positive integers $n$ does the rule $[a]_{n} \mapsto (- 1)^{a}$ define a function from $ℤ / n ℤ$ to ${1, - 1}$ ? Prove your answer.

Hint

Try $n = 2$ and $n = 3$ . The value $(- 1)^{a}$ depends only on the parity of $a$ .

Solution

Exactly when $n$ is even.

Suppose $n$ is even, say $n = 2 m$ , and let $[a]_{n} = [a']_{n}$ , so $a - a' = n k = 2 (m k)$ for some integer $k$ . Then $a - a'$ is even, so $a$ and $a'$ have the same parity (lesson on direct proof), and $(- 1)^{a} = (- 1)^{a'}$ , since $(- 1)^{a}$ is $1$ for even $a$ and $- 1$ for odd $a$ . So the rule is well defined.

Suppose $n$ is odd. Then $[0]_{n} = [n]_{n}$ , since $n ∣ n - 0$ , but $(- 1)^{0} = 1$ and $(- 1)^{n} = - 1$ because $n$ is odd. So one class receives two values, and the rule does not define a function.

(The exponent $a$ may be negative; $(- 1)^{a}$ still makes sense, since $(- 1)^{- k} = \frac{1}{(- 1)^{k}} = (- 1)^{k}$ .)

8. Equivalence relations on a set $A$ are subsets of $A \times A$ , so they can be intersected and united.

(a) Prove that if $R$ and $S$ are equivalence relations on $A$ , then $R \cap S$ is an equivalence relation on $A$ , and that the class of $a$ under $R \cap S$ is the intersection of its classes under $R$ and under $S$ .

(b) Identify the intersection of congruence modulo $2$ and congruence modulo $3$ on $ℤ$ .

Hint

For (b), use the Example in the lesson on direct proof: $6 ∣ n$ if and only if $2 ∣ n$ and $3 ∣ n$ . For (c), look for a chain that uses one relation for the first step and the other for the second.

Solution

(a) Reflexive: for $a \in A$ , $(a, a) \in R$ and $(a, a) \in S$ , so $(a, a) \in R \cap S$ . Symmetric: if $(a, b) \in R \cap S$ , then $(b, a) \in R$ and $(b, a) \in S$ by symmetry of each, so $(b, a) \in R \cap S$ . Transitive: if $(a, b)$ and $(b, c)$ are in $R \cap S$ , then both are in $R$ , so $(a, c) \in R$ , and both are in $S$ , so $(a, c) \in S$ ; hence $(a, c) \in R \cap S$ . For the classes, $x$ is in the class of $a$ under $R \cap S$ exactly when $(x, a) \in R$ and $(x, a) \in S$ , exactly when $x$ lies in both classes of $a$ .

(b) For integers $a$ and $b$ : $a$ and $b$ are related by the intersection exactly when $2 ∣ a - b$ and $3 ∣ a - b$ , which by the result quoted in the hint holds exactly when $6 ∣ a - b$ . So the intersection is congruence modulo $6$ . Its classes are intersections of classes modulo $2$ and modulo $3$ , for instance $[1]_{6} = [1]_{2} \cap [1]_{3}$ .

(c) In the union, $0$ is related to $2$ (congruent modulo $2$ ) and $2$ is related to $5$ (congruent modulo $3$ ). But $0$ is not related to $5$ : $5 - 0 = 5$ is divisible by neither $2$ nor $3$ . So the union is not transitive, and not an equivalence relation. (It is reflexive and symmetric, as a union of reflexive and symmetric relations always is.)

9. Prove or disprove that each relation on $ℝ$ is an equivalence relation. Where it is one, describe the classes. (a) $x \sim y$ when $x^{2} - y^{2} \in ℤ$ . (b) $x \sim y$ when $x y \geq 0$ . (c) $x \sim y$ when $⌊ x ⌋ = ⌊ y ⌋$ , where $⌊ x ⌋$ is the greatest integer at most $x$ .

Hint

Two of these are kernels of functions, which settles them at once. For the other, test a chain through $0$ .

Solution

(a) An equivalence relation. Directly: $x^{2} - x^{2} = 0 \in ℤ$ ; if $x^{2} - y^{2} = k \in ℤ$ then $y^{2} - x^{2} = - k \in ℤ$ ; if $x^{2} - y^{2} = k$ and $y^{2} - z^{2} = m$ with $k, m \in ℤ$ , then $x^{2} - z^{2} = k + m \in ℤ$ . (Equivalently, it is the kernel of $x \mapsto [x^{2}]$ , the class of $x^{2}$ under the fractional-part relation.) The class of $x$ is ${y : y^{2} = x^{2} + k for some k \in ℤ}$ , the set of $\pm \sqrt{x^{2} + k}$ over the integers $k \geq - x^{2}$ . For example, the class of $0$ is ${\pm \sqrt{k} : k = 0, 1, 2, \dots}$ .

(b) Not an equivalence relation. It is reflexive, since $x^{2} \geq 0$ , and symmetric, since $x y = y x$ . It is not transitive: $1 \cdot 0 \geq 0$ and $0 \cdot (- 1) \geq 0$ , so $1 \sim 0$ and $0 \sim - 1$ , but $1 \cdot (- 1) = - 1 < 0$ , so $1$ and $- 1$ are not related. The number $0$ is related to everything and joins the positive and negative numbers into one chain.

(c) An equivalence relation, since it is the kernel of the function $x \mapsto ⌊ x ⌋$ . The classes are its non-empty fibres, one for each integer $n$ : the fibre over $n$ is ${x : ⌊ x ⌋ = n} = [n, n + 1)$ . So the classes are the half-open intervals $[n, n + 1)$ , $n \in ℤ$ , which partition $ℝ$ .

10. Let $\sim$ be an equivalence relation on $A$ , with quotient map $π : A \to A / \sim$ , and let $g : A \to C$ be a function. Prove that there is a function $h : A / \sim \to C$ with $h \circ π = g$ if and only if $g$ is constant on each class, that is, $a \sim a'$ implies $g (a) = g (a')$ . Prove that such an $h$ is unique, and that it is injective if and only if $g (a) = g (a')$ implies $a \sim a'$ .

Hint

The equation $h \circ π = g$ says $h ([a]) = g (a)$ for every $a$ , so it leaves no freedom in choosing $h$ . The question is only whether that formula is well defined.

Solution

( $\Rightarrow$ ) Suppose $h \circ π = g$ , and let $a \sim a'$ . Then $[a] = [a']$ by the lemma on classes, so $g (a) = h ([a]) = h ([a']) = g (a')$ .

( $\Leftarrow$ ) Suppose $g$ is constant on each class. Define $h ([a]) = g (a)$ . This is well defined: if $[a] = [a']$ , then $a \sim a'$ , so $g (a) = g (a')$ . Every class has a representative, so $h$ is a function on all of $A / \sim$ , and $(h \circ π) (a) = h ([a]) = g (a)$ for every $a \in A$ .

Uniqueness: if $h$ and $h'$ both satisfy $h \circ π = g = h' \circ π$ , then for every class $[a]$ , $h ([a]) = g (a) = h' ([a])$ . Two functions with the same domain, codomain and values are equal, so $h = h'$ . (Equivalently: $π$ is surjective, and surjections can be cancelled on the right.)

Injectivity: suppose $g (a) = g (a')$ implies $a \sim a'$ , and let $h ([a]) = h ([a'])$ . Then $g (a) = g (a')$ , so $a \sim a'$ and $[a] = [a']$ . Conversely, suppose $h$ is injective and $g (a) = g (a')$ . Then $h ([a]) = h ([a'])$ , so $[a] = [a']$ , and $a \sim a'$ .

Together with the kernel theorem, this says a function out of a quotient is the same thing as a function on $A$ that respects the relation, which is how functions on quotients are defined in practice.

11. Decide whether each rule defines a function, and prove your answer. (a) $[(a, b)] \mapsto [(a + b, b)]$ , from $ℚ$ to $ℚ$ . (b) $[(a, b)] \mapsto [(a + 1, b + 1)]$ , from $ℚ$ to $ℚ$ . (c) $[(a, b)] \mapsto [(b, a)]$ , from $ℚ$ to $ℚ$ , and from $ℚ ∖ {0}$ to $ℚ$ . What do the rules in (a) and (c) do to a rational number?

Hint

For each rule, take two related pairs and ask whether their images are related. For (b), try two names of $\frac{1}{2}$ ; note also that $b + 1$ may be $0$ .

Solution

(a) Well defined. The pair $(a + b, b)$ lies in $P$ since $b \neq 0$ . Let $(a, b) \sim (a', b')$ , so $a b' = b a'$ . Then $(a + b) b' = a b' + b b' = b a' + b b' = b (a' + b')$ , so $(a + b, b) \sim (a' + b', b')$ . The rule is $x \mapsto x + 1$ , since $[(a, b)] + [(1, 1)] = [(a \cdot 1 + b \cdot 1, b \cdot 1)] = [(a + b, b)]$ .

(b) Not a function. First, it can leave $P$ : $[(1, - 1)]$ would be sent to the "class" of $(2, 0)$ , which is not in $P$ . And even where it stays inside $P$ it is not well defined: $(1, 2) \sim (2, 4)$ , but the images are $(2, 3)$ and $(3, 5)$ , and $2 \cdot 5 = 10 \neq 9 = 3 \cdot 3$ , so they name different rationals, $\frac{2}{3}$ and $\frac{3}{5}$ .

(c) On $ℚ ∖ {0}$ it is a well defined function. A non-zero rational $[(a, b)]$ has $a \neq 0$ (since $[(0, b)] = [(0, 1)]$ is zero, as $0 \cdot 1 = b \cdot 0$ ), so $(b, a) \in P$ . If $(a, b) \sim (a', b')$ , then $a b' = b a'$ , which is the same equation as $b a' = a b'$ , the condition for $(b, a) \sim (b', a')$ . On all of $ℚ$ the rule fails, because $[(0, 1)]$ would go to the class of $(1, 0) \notin P$ . The rule is $x \mapsto \frac{1}{x}$ .

Challenge

12. This problem builds the integers from the natural numbers, using only addition and multiplication in $ℕ$ and the cancellation law (if $x + z = y + z$ then $x = y$ ). On $ℕ \times ℕ$ , let $(a, b) \sim (c, d)$ when $a + d = b + c$ . Think of $(a, b)$ as standing for $a - b$ .

(a) Prove that $\sim$ is an equivalence relation.

(b) Prove that $[(a, b)] + [(c, d)] = [(a + c, b + d)]$ is well defined.

(d) Prove that every class contains exactly one pair of the form $(k + 1, 1)$ with $k \in ℕ$ , or $(1, 1)$ , or $(1, k + 1)$ with $k \in ℕ$ , and exactly one of these three forms occurs.

Hint

Subtraction is not available in $ℕ$ , so every step must be an equation between sums. For transitivity, add the two given equations and cancel. For (c), change one argument at a time: first show that replacing $(a, b)$ by a related pair gives a related product, then use the symmetry of the formula for the other argument. For (d), compare $a$ and $b$ .

Solution

(a) Reflexive: $a + b = b + a$ . Symmetric: $a + d = b + c$ is the same equation as $c + b = d + a$ , which says $(c, d) \sim (a, b)$ . Transitive: suppose $a + d = b + c$ and $c + f = d + e$ . Adding the equations gives $a + d + c + f = b + c + d + e$ , that is, $(a + f) + (c + d) = (b + e) + (c + d)$ , and cancelling $c + d$ gives $a + f = b + e$ , so $(a, b) \sim (e, f)$ .

(b) Let $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$ , so $a + b' = b + a'$ and $c + d' = d + c'$ . Adding, $(a + c) + (b' + d') = (b + d) + (a' + c')$ , which says $(a + c, b + d) \sim (a' + c', b' + d')$ .

(c) First change the left argument. Let $(a, b) \sim (a', b')$ , so $a + b' = b + a'$ , and let $(c, d)$ be any pair. We need $(a c + b d, a d + b c) \sim (a' c + b' d, a' d + b' c)$ , that is,

a c + b d + a' d + b' c = a d + b c + a' c + b' d

Multiplying $a + b' = b + a'$ by $c$ gives $a c + b' c = b c + a' c$ , and multiplying $b + a' = a + b'$ by $d$ gives $b d + a' d = a d + b' d$ . Adding these two equations gives exactly the required one.

Now the right argument. The formula is symmetric: swapping the two pairs gives $(c a + d b, c b + d a)$ , which is the same pair as $(a c + b d, a d + b c)$ . So replacing $(c, d)$ by a related pair also gives a related product, by the first step with the roles exchanged.

Finally, if $(a, b) \sim (a', b')$ and $(c, d) \sim (c', d')$ , change one argument and then the other: the product for $(a, b), (c, d)$ is related to that for $(a', b'), (c, d)$ , which is related to that for $(a', b'), (c', d')$ , and transitivity finishes it.

(d) Let $(a, b) \in ℕ \times ℕ$ . Exactly one of $a > b$ , $a = b$ , $a < b$ holds. If $a > b$ , then $a = b + k$ for a natural number $k$ , and $(a, b) \sim (k + 1, 1)$ , since $a + 1 = b + k + 1$ . If $a = b$ , then $(a, b) \sim (1, 1)$ , since $a + 1 = b + 1$ . If $a < b$ , then $b = a + k$ , and $(a, b) \sim (1, k + 1)$ , since $a + k + 1 = b + 1$ .

No two different pairs of these forms are related. Two pairs $(k + 1, 1)$ and $(k' + 1, 1)$ are related exactly when $k + 1 + 1 = 1 + k' + 1$ , that is, $k = k'$ , and similarly for the third form. A pair $(k + 1, 1)$ is not related to $(1, 1)$ , since that would need $k + 1 + 1 = 1 + 1$ , that is, $k = 0$ , which is not a natural number; similarly for the other combinations, $(k + 1, 1) \sim (1, k' + 1)$ would need $k + k' + 2 = 2$ . So each class contains exactly one pair of these forms.

The classes of $(k + 1, 1)$ play the part of the positive integers $k$ , the class of $(1, 1)$ is $0$ , and the classes of $(1, k + 1)$ are the negative integers $- k$ . With $[(a, b)]$ read as $a - b$ , the formulas in (b) and (c) are the rules $(a - b) + (c - d) = (a + c) - (b + d)$ and $(a - b) (c - d) = (a c + b d) - (a d + b c)$ .

13. Let $R$ be any relation on a set $A$ .

(a) Prove that the intersection $E$ of all equivalence relations on $A$ that contain $R$ is an equivalence relation containing $R$ , and that it is contained in every equivalence relation containing $R$ . It is called the equivalence relation generated by $R$ .

(b) On $ℤ$ , let $R = {(n, n + 4) : n \in ℤ} \cup {(n, n + 6) : n \in ℤ}$ . Prove that the equivalence relation generated by $R$ is congruence modulo $2$ .

Hint

For (a), there is at least one equivalence relation containing $R$ to intersect. For (b), show two inclusions: congruence modulo $2$ is one of the relations being intersected; and any equivalence relation containing $R$ relates $n$ to $n + 2$ , and hence, by induction, $n$ to $n + 2 k$ .

Solution

(a) The family of equivalence relations containing $R$ is not empty: $A \times A$ , which relates everything, is an equivalence relation containing $R$ . Let $E$ be the intersection of the family. It contains $R$ , since every member does. Reflexive: for $a \in A$ , $(a, a)$ lies in every member, so in $E$ . Symmetric: if $(a, b) \in E$ , then $(a, b)$ lies in every member, so $(b, a)$ does too, by symmetry of each member, and $(b, a) \in E$ . Transitive: if $(a, b)$ and $(b, c)$ are in $E$ , they lie in every member, so $(a, c)$ lies in every member, and $(a, c) \in E$ . Finally, an intersection of a family is contained in each member, so $E$ is contained in every equivalence relation containing $R$ . So $E$ is the smallest equivalence relation containing $R$ .

(b) Write $\equiv$ for congruence modulo $2$ , $E$ for the relation generated by $R$ , and $a \sim_{E} b$ for $(a, b) \in E$ .

$E \subseteq \equiv$ : congruence modulo $2$ is an equivalence relation, and it contains $R$ , since $(n + 4) - n = 4$ and $(n + 6) - n = 6$ are even. By (a), $E$ is contained in it.

$\equiv \subseteq E$ : first, $n \sim_{E} n + 2$ for every integer $n$ . Indeed $(n + 2, n + 6) \in R$ (taking $n + 2$ in place of $n$ in the first set), so $n + 2 \sim_{E} n + 6$ , and by symmetry $n + 6 \sim_{E} n + 2$ . Also $(n, n + 6) \in R$ , so $n \sim_{E} n + 6$ . By transitivity, $n \sim_{E} n + 2$ .

Next, $n \sim_{E} n + 2 k$ for every integer $n$ and every integer $k \geq 0$ , by induction on $k$ . For $k = 0$ this is reflexivity. If $n \sim_{E} n + 2 k$ , then since $n + 2 k \sim_{E} n + 2 k + 2$ by the first step, transitivity gives $n \sim_{E} n + 2 (k + 1)$ .

Now let $a \equiv b (mod 2)$ , so $b - a = 2 k$ for some integer $k$ . If $k \geq 0$ , then $a \sim_{E} a + 2 k = b$ . If $k < 0$ , then $a - b = 2 (- k)$ with $- k > 0$ , so $b \sim_{E} a$ , and $a \sim_{E} b$ by symmetry. So $\equiv \subseteq E$ , and the two relations are equal.

The same argument shows that the relation generated by the steps $4$ and $6$ is congruence modulo $2$ because $2 = 6 - 4$ is an integer combination of the steps. In general, steps $s$ and $t$ generate congruence modulo the greatest common divisor of $s$ and $t$ , which is Bézout's theorem in disguise.

14. Let $n \geq 2$ and $A = {1, 2, \dots, n}$ .

(a) Prove that there are exactly $2^{n - 1} - 1$ equivalence relations on $A$ with exactly two classes.

(b) Prove that there are exactly $\frac{n (n - 1)}{2}$ equivalence relations on $A$ with exactly $n - 1$ classes.

Hint

Count partitions instead, by the partition theorem. In (a), a partition into two blocks is determined by the block containing $1$ . In (b), the class sizes are forced.

Solution

By the partition theorem, equivalence relations on $A$ with $k$ classes correspond one to one with partitions of $A$ into $k$ blocks, so it is enough to count partitions.

(a) Given a partition of $A$ into two blocks, let $S$ be the block containing $1$ . Then $S$ is a subset of $A$ containing $1$ , and $S \neq A$ , because the other block is non-empty. Conversely, every subset $S$ with $1 \in S$ and $S \neq A$ gives the partition ${S, A ∖ S}$ into two blocks: both are non-empty ( $S$ contains $1$ , and $A ∖ S$ is non-empty since $S \neq A$ ), they are disjoint, and they cover $A$ . The block of this partition containing $1$ is $S$ , and a partition into two blocks is determined by either block, so the two maps are inverse to each other.

So the count is the number of subsets $S$ of $A$ with $1 \in S$ and $S \neq A$ . A subset containing $1$ is ${1} \cup T$ for exactly one subset $T$ of ${2, \dots, n}$ , and there are $2^{n - 1}$ such $T$ . Excluding $S = A$ leaves $2^{n - 1} - 1$ .

(b) In a partition of $A$ into $n - 1$ blocks, the block sizes are positive integers adding to $n$ . If every block had one element the total would be $n - 1$ , so exactly one block has two elements and the rest are singletons; a block of three or more, or two blocks of two, would push the total above $n$ . So the partition is determined by its one two-element block ${a, b}$ , and every two-element subset of $A$ arises from exactly one such partition (itself together with the singletons of the other elements). The number of two-element subsets of $A$ is $\frac{n (n - 1)}{2}$ : there are $n (n - 1)$ ordered pairs $(a, b)$ with $a \neq b$ , and each subset ${a, b}$ arises from exactly two of them.

For $n = 4$ : $2^{3} - 1 = 7$ relations with two classes, $6$ with three classes, and with the one relation with one class and the one with four, the total is $7 + 6 + 1 + 1 = 15$ , the Bell number $B_{4}$ .