Relations and Equivalence Relations

Main idea

A relation just records which pairs of things are connected. When a relation behaves like "is the same as" in some respect (everything relates to itself, it works both ways, and it chains), it's an equivalence relation, and it sorts the whole set into non-overlapping groups of things that count as the same.

Reflexive, symmetric, transitive

{\htmlData{sym=1}{a}} {\htmlData{sym=0}{\sim}} {\htmlData{sym=1}{a}}, \qquad {\htmlData{sym=1}{a}} {\htmlData{sym=0}{\sim}} b \Rightarrow b {\htmlData{sym=0}{\sim}} {\htmlData{sym=1}{a}}, \qquad ({\htmlData{sym=1}{a}} {\htmlData{sym=0}{\sim}} b \wedge b {\htmlData{sym=0}{\sim}} c) \Rightarrow {\htmlData{sym=1}{a}} {\htmlData{sym=0}{\sim}} c

What the symbols mean

$\sim$
Is related to
The relation in question, such as 'has the same remainder mod 3 as'.
$a$
An element
Any element of the set.

Explanation

A relation is simply a yes-or-no question you can ask about any two things in a set: "is $a$ related to $b$ ?" Think "is a sibling of," "is less than," or "has the same remainder as." The three formulas look abstract, but they're three common-sense rules written in symbols: $a \sim a$ (everything is related to itself), $a \sim b \Rightarrow b \sim a$ (it works both ways) and the last one (if $a$ is related to $b$ and $b$ to $c$ , then $a$ is related to $c$ ). The squiggle $\sim$ just means "is related to." Rules like these are what make a relation behave like "is the same as," and that's where this lesson is headed.

Formally, a relation on $A$ is a subset of $A \times A$ , the set of related pairs, using the Cartesian product from the first lesson of this unit. Picture it as a grid of dots, one for each related pair $(a, b)$ .

Reflexive: every element is related to itself (the whole diagonal is filled).
Symmetric: $a \sim b$ forces $b \sim a$ (the picture is mirror-symmetric across the diagonal).
Transitive: related to related is related.
Antisymmetric: $a \sim b$ and $b \sim a$ only when $a = b$ . We'll need this one for orders in the next lesson.

An equivalence relation is reflexive, symmetric and transitive. Notice those are exactly the properties of "equals," which is the point: an equivalence relation is a way of saying two things are "the same" in some respect, like "has the same birthday as" or "is congruent mod $n$ to." Its equivalence classes (everything related to a given element) partition the set: every element lands in exactly one class. Why can't two classes partly overlap? If $c$ were in both $a$ 's class and $b$ 's class, then $a \sim c$ and $c \sim b$ (using symmetry), so $a \sim b$ by transitivity, and the two classes would be the same class after all. Congruence mod 3 splits the integers into $\{\dots, 0, 3, 6, \dots\}$ , $\{\dots, 1, 4, 7, \dots\}$ and $\{\dots, 2, 5, 8, \dots\}$ .

It works in reverse too: any partition defines an equivalence relation, namely "is in the same part as."

A common mistake. It's tempting to think a symmetric, transitive relation is automatically reflexive, because $a \sim b$ and $b \sim a$ give $a \sim a$ by transitivity. That argument only works if $a$ is related to something. An element related to nothing at all never gets $a \sim a$ , so reflexivity has to be checked on its own.

See it

s

1.00

n

3.00

Every possible pair (a, b) with a and b from 1 to 12, with the related pairs highlighted. Slide s to switch relations: 1 is a ≡ b (mod n), 2 is "a divides b" and 3 is a ≤ b. Notice that only congruence mod n is a mirror image across the diagonal, in neat stripes every n steps, because it's the only symmetric one. All three fill the diagonal, since each is reflexive.

Worked examples

Example 1

List the equivalence classes of congruence mod 3 on $\{0, 1, \dots, 8\}$ .

1
Two numbers are congruent mod 3 exactly when they leave the same remainder on division by 3, so group the numbers by remainder: 0, 1 or 2.

$\{0, 3, 6\}$ , $\{1, 4, 7\}$ , $\{2, 5, 8\}$

Practice

Type your answer and check it. Solve them all to complete the lesson.

Problem 1+5 XP

Is "divides" on the positive integers symmetric?

Problem 2+5 XP

How many equivalence classes does congruence mod 5 have on the integers?

Problem 3+5 XP

How many ordered pairs are in the relation $\le$ on $\{1, 2, 3, 4\}$ ?

Problem 4+5 XP

How many different relations are there on a 3-element set?

Problem 5+5 XP

On a social network, "follows" is a relation on users, while "is friends with" is another. Which property does "follows" usually lack?

Problem 6+5 XP

Congruence mod 4 splits the integers into four equivalence classes. Which number from 0 to 3 is in the same class as $-7$ ?

Challenge problem+25 XP

The hardest one here. Get it, and you've got this lesson.

How many different equivalence relations are there on a 3-element set $\{a, b, c\}$ ?

Where it's used

Deduplicating records that refer to the same customer and finding connected regions in an image are both about building equivalence classes.

Functions: One-to-One and Onto Partial Orders and Hasse Diagrams