Back to the on-screen lesson ·
Why reflexivity makes the classes cover everything and symmetry with transitivity makes them disjoint, and why a partition is the same information read backwards.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to find the equivalence classes of a relation, name one by a representative, count them and say why they cover the set without overlapping. You will also be able to go the other way, building an equivalence relation from a partition, and to check that a definition made on classes is well defined — that it gives the same answer whichever representative is chosen, which is the check a quotient always owes.
Lesson 13 defined an equivalence relation as one that is reflexive, symmetric and transitive, and gave congruence modulo $m$ as the standard example. This lesson proves what those three properties buy: they carve the set into pieces, and the pieces never overlap.
The equivalence class of $a$, written $[a]$, is the set of everything related to $a$. A partition of $S$ is a collection of non-empty subsets such that every element of $S$ is in exactly one of them; the subsets are its blocks. A representative of a class is any one of its members, chosen to stand for the rest. The quotient set $S/{\sim}$ is the set whose elements are the classes.
Let $\sim$ be an equivalence relation on $S$, and write $[a] = \{x \in S : x \sim a\}$.
Every element is in a class. $a \sim a$ by reflexivity, so $a \in [a]$. Nothing is left out.
Two classes are equal or disjoint. Suppose $[a]$ and $[b]$ share an element $c$. Then $c \sim a$ and $c \sim b$; by symmetry $a \sim c$; by transitivity $a \sim b$. Now take any $x \in [a]$: $x \sim a \sim b$ gives $x \in [b]$, and the same argument the other way gives $[b] \subseteq [a]$. So the two classes are the same set.
That is the whole theorem, and it is worth seeing how little it needed: reflexivity for the covering, symmetry and transitivity for the disjointness, and nothing else. The classes form a partition.
And the converse holds. Given a partition, declare $x \sim y$ when they share a block; the three properties follow immediately. So equivalence relation and partition are two descriptions of the same thing, and you may use whichever is more convenient. Counting one counts the other.
Why this is used everywhere. The classes become objects in their own right: the integers modulo $m$ are the classes of congruence, the rational numbers are classes of pairs of integers, a vector space quotient is classes of vectors. Each time, an equivalence relation says stop distinguishing these, and the quotient set is what is left when you stop.
Another way: steps
To use an equivalence relation:
Another way: picture
The line, and the relation has the same integer part. Every class is one unit interval $[n, n+1)$: they tile the line with no gaps and no overlaps. Which real number you name inside one of them makes no difference to which class you are talking about, which is what having a representative means.
Once you have classes, you usually want to do arithmetic on them: $[a] + [b] = [a + b]$ for congruence modulo $m$, say. But $[a]$ has many names — $[2] = [7] = [12]$ modulo five — so the definition has to be checked to be well defined: does it give the same answer whichever representative is chosen?
For congruence it does. If $a \equiv a'$ and $b \equiv b'$ then $m$ divides $a - a'$ and $b - b'$, so it divides $(a + b) - (a' + b')$, and $[a+b] = [a'+b']$. Three lines, and without them the definition is not a definition.
It can fail. On the classes modulo five, 'the class of the larger representative' is not well defined at all, because a class has no largest member. Any time a definition reaches inside a class, this check is owed, and lesson 26 will owe it again for multiplication.
Checking the partition as a fourth property. It is a theorem, proved from the three. Proving the three and then asserting the classes overlap would be a contradiction.
Forgetting that a class is a set. $[2]$ modulo five is the infinite set $\{\ldots, -3, 2, 7, 12, \ldots\}$ and not the number $2$.
Counting classes as elements. Congruence modulo five has five classes on an infinite set; the classes are few and their members are many.
Defining something on classes without checking it. A definition that depends on the representative chosen defines nothing.
Writing $[2]$ makes it look as though $2$ is special, and it is not: $[2]$, $[7]$ and $[-3]$ are three names for one set modulo five. The habit worth building is to read $[a]$ as the class containing $a$ rather than as the class of $a$, because the first phrasing makes it obvious that another element would have named the same thing. Every apparent paradox about quotients comes from forgetting this.
Modulo four, two integers are related when their difference is a multiple of four. Start at $0$ and collect: $\{\ldots, -4, 0, 4, 8, \ldots\}$.
Collect one class by walking in steps of four.
Starting at $1$, $2$ and $3$ gives three more classes; starting at $4$ gives the first one back.
New starting points stop producing new classes.
So there are exactly four classes, one per remainder, and every integer is in exactly one. An infinite set has been cut into four pieces, and that is what makes arithmetic modulo four a finite calculation.
Finitely many classes on an infinite set.
Partition $\{1,2,3,4,5\}$ into $\{1,3,5\}$ and $\{2,4\}$. Declare $x \sim y$ when they share a block.
Start from the partition instead.
Reflexive: every element shares its block with itself. Symmetric: sharing is not directed. Transitive: two elements sharing with a third are in the same block as it and so as each other.
All three properties fall out at once.
So this is an equivalence relation, and its classes are the two blocks we started from. The correspondence goes both ways with nothing lost, which is why the two words are used almost interchangeably.
The correspondence is exact.
Check the three properties first. Every non-zero real has the same sign as itself; sharing a sign is not directed; and two numbers sharing a sign with a third share it with each other.
Three properties, quickly.
So there are classes. The class of $1$ is every positive real; the class of $-1$ is every negative real.
Name a representative and collect.
Two classes, covering the non-zero reals with no overlap. Note why zero had to be excluded: it has no sign, so it would belong to no class, and the relation would not be reflexive on the whole line. The domain is part of the relation.
Under congruence modulo $6$, two numbers are in the same class when their difference is a multiple of $6$. Give the class of each number, naming it by its remainder.
| Class | |
|---|---|
| $20$ | |
| $27$ | |
| $35$ | |
| $18$ |
How many equivalence classes does congruence modulo $7$ have on the integers?
Answer:
On the reals, let $x \sim y$ when $x$ and $y$ have the same integer part. Give the class of $6$.
This task has no paper form; do it on a device.
Put in order the steps of showing that 'same remainder on division by $m$' partitions the integers.
Number the steps in order (write the number in the box):
In how many ways can a set of $4$ elements be split into non-empty blocks, with every element in exactly one block?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
Under congruence modulo $4$, two numbers are in the same class when their difference is a multiple of $4$. Give the class of each number, naming it by its remainder.
| Class | |
|---|---|
| $19$ | |
| $26$ | |
| $31$ | |
| $12$ |
You can find and count the classes of an equivalence relation and build one from a partition. Say in your own words which property makes the classes cover the set and which two make them disjoint, and why a class is not the same thing as the representative that names it. Next: functions, and the three ways one can be well behaved.
10. Your turn: what are the classes of 'has the same sign' on the non-zero reals?, step 3