Mathematics.

binary relations

Equivalence Relations

Set Theory25 minDifficulty3 out of 10

You should know: relations

Overview

An equivalence relation on a set is a binary relation that is reflexive, symmetric, and transitive — capturing the everyday notion of 'being essentially the same' with respect to some criterion. Classic examples include equality itself, congruence modulo n on the integers, and 'has the same shape as' among triangles. The defining feature of an equivalence relation is that it partitions its underlying set into disjoint equivalence classes, and conversely every partition of a set arises from some equivalence relation — the two notions are exactly interchangeable.

Intuition

Think of sorting a big pile of objects into bins so that two objects go in the same bin exactly when they're 'equivalent' by whatever rule you're using — same remainder mod 5, same color, same birthday month. Reflexivity says every object belongs in its own bin's category; symmetry says the sorting rule doesn't care about order (if x matches y, y matches x); transitivity says the bins don't overlap or chain into each other — once you're in a bin, everyone in that bin is mutually equivalent. The bins themselves are the equivalence classes, and collectively they partition the whole pile with no object left out and no object in two bins.

Formal Definition

Definition

A relation ~ on a set A is an equivalence relation if it satisfies all three properties:

∀a∈A,  a∼a\forall a \in A,\; a \sim a
Reflexive
∀a,b∈A,  a∼b⇒b∼a\forall a,b \in A,\; a \sim b \Rightarrow b \sim a
Symmetric
∀a,b,c∈A,  (a∼b∧b∼c)⇒a∼c\forall a,b,c \in A,\; (a \sim b \land b \sim c) \Rightarrow a \sim c
Transitive
[a]={x∈A:x∼a},A=⨆i[ai][a] = \{x \in A : x \sim a\}, \qquad A = \bigsqcup_{i} [a_i]
Equivalence class of a; A is the disjoint union of its equivalence classes

Worked Examples

  1. Reflexive: a − a = 0, and 4 | 0.

    4∣(a−a)4 \mid (a - a)

  2. Symmetric: if 4 | (a−b) then a−b = 4k, so b−a = -4k, also a multiple of 4.

    4∣(a−b)  ⟹  4∣(b−a)4\mid(a-b) \implies 4\mid(b-a)

  3. Transitive: if 4 | (a−b) and 4 | (b−c), their sum a−c is also a multiple of 4.

    4∣(a−b)∧4∣(b−c)  ⟹  4∣(a−c)4\mid(a-b) \land 4\mid(b-c) \implies 4\mid(a-c)

  4. The equivalence classes are the four residue classes mod 4.

    [0],[1],[2],[3](each ={…,−4,0,4,8,…} shifted)[0], [1], [2], [3] \quad \text{(each } = \{\ldots,-4,0,4,8,\ldots\} \text{ shifted)}

Answer: Congruence mod 4 is an equivalence relation with exactly 4 equivalence classes: [0],[1],[2],[3].

Practice Problems

Difficulty 2/10

Is the relation 'has the same birthday' an equivalence relation on a group of people? Justify briefly.

Difficulty 3/10

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

Difficulty 5/10

A social media platform groups users by which of 6 languages their profile is set to. Explain why this grouping corresponds to an equivalence relation, and state how many equivalence classes there are (assuming every language is used by at least one user).

Quiz

An equivalence relation must satisfy which three properties?
Every equivalence relation on a set A corresponds to:
Congruence mod n on the integers has how many equivalence classes?

Summary

  • An equivalence relation is reflexive, symmetric, and transitive — the formal version of 'essentially the same as'.
  • Every equivalence relation partitions its set into disjoint equivalence classes, and every partition arises from some equivalence relation.
  • Congruence mod n is the canonical example: it partitions the integers into n residue classes [0],[1],...,[n-1].

References

  1. WebsiteWikipedia — Equivalence relation