Skip to content
Tutorials Center
My learning

Topics

Lesson 15 of 38 ยท Equivalence and Order

Equivalence Relations

Learn equivalence relations (reflexive, symmetric, transitive), equivalence classes, congruence modulo n, and how to test them in Python.

Mathematicians constantly say "these two things are the same for our purposes": two fractions that name the same number, two triangles that are congruent, two integers with the same remainder after division by 5. An equivalence relation is the exact mathematical tool for "the same in some respect". It lets you group objects into classes and then treat each class as a single object.

Definition

A relation ~ on a set A is an equivalence relation if it is

  1. reflexive: a ~ a for every a,
  2. symmetric: a ~ b implies b ~ a,
  3. transitive: a ~ b and b ~ c imply a ~ c.

You met these three properties in the lesson on properties of relations. The combination captures what "same as" ought to mean: everything is the same as itself; if one thing is the same as a second, the second is the same as the first; and sameness chains.

Examples

  • Equality on any set is an equivalence relation.
  • Same remainder mod n. On โ„ค, write a โ‰ก b (mod n) when n divides a โˆ’ b. This is an equivalence relation (you proved it for n = 3 earlier).
  • Same absolute value on โ„: x ~ y when |x| = |y|.
  • Congruent triangles, parallel lines (if you call a line parallel to itself), and "born in the same year" are equivalence relations.
  • Equivalent fractions. On pairs (p, q) of integers with q โ‰  0, say (p, q) ~ (r, s) when pยทs = qยทr. The pair (1, 2) and (2, 4) are equivalent. This is the construction of the rationals from the integers.

Non-examples

  • โ‰ค on โ„: not symmetric.
  • "Differs by at most 1" on โ„ค: reflexive and symmetric, but not transitive (1 ~ 2, 2 ~ 3, yet not 1 ~ 3).
  • "Is a friend of": usually not transitive.

Equivalence classes

Given an equivalence relation ~ on A, the equivalence class of an element a is the set of everything equivalent to it:

Text
[a] = { x โˆˆ A : x ~ a }

For congruence mod 3 on โ„ค:

Text
[0] = { ..., โˆ’6, โˆ’3, 0, 3, 6, ... }
[1] = { ..., โˆ’5, โˆ’2, 1, 4, 7, ... }
[2] = { ..., โˆ’4, โˆ’1, 2, 5, 8, ... }

Notice that [0], [1] and [2] cover all of โ„ค, and that [1] = [4] = [โˆ’2]: any member of the class can name it. These three classes are the "remainder classes", and they underlie clock arithmetic.

The key theorem

For an equivalence relation ~ on A, and any a, b โˆˆ A:

  1. a โˆˆ [a], so classes are never empty.
  2. a ~ b if and only if [a] = [b].
  3. If [a] โ‰  [b], then [a] โˆฉ [b] = โˆ….

Proof of (3). Suppose x โˆˆ [a] โˆฉ [b]. Then x ~ a and x ~ b. By symmetry a ~ x, and by transitivity a ~ b. By (2), [a] = [b]. So different classes cannot share an element.

Proof of (2), the forward direction. Assume a ~ b. If x โˆˆ [a], then x ~ a and a ~ b, so x ~ b and x โˆˆ [b]. This gives [a] โІ [b]. By symmetry, b ~ a, and the same argument gives [b] โІ [a]. The converse holds because a โˆˆ [a] = [b], so a ~ b.

In words: an equivalence relation chops its set into non-overlapping pieces. The next lesson shows that every such chopping comes from an equivalence relation.

flowchart TB
    Z["โ„ค"] --> C0["[0]: multiples of 3"]
    Z --> C1["[1]: remainder 1"]
    Z --> C2["[2]: remainder 2"]

Congruence mod 3 splits the integers into three disjoint classes.

Python Test and group by an equivalence relation

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Equivalence classes of fractions

Two pairs are equivalent when they have the same ratio, so a class of pairs is one rational number. The class of (1, 2) contains (2, 4), (3, 6), (โˆ’1, โˆ’2), and so on. Python's Fraction type stores one canonical representative of each class (lowest terms).

Python Fractions as equivalence classes

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Why this idea is everywhere

Whenever a theory says "we identify these things", an equivalence relation is hiding underneath. Clock arithmetic identifies integers by remainder. Geometry identifies congruent shapes. Programming identifies different spellings of one value. Next you will see how to build a new set whose elements are the classes themselves.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which relation on โ„ is an equivalence relation?

    Equal absolute value is reflexive, symmetric and transitive.
  2. 2. On โ„ค, what is the equivalence class of 7 under congruence mod 5?

    It contains all integers that differ from 7 by a multiple of 5, that is, those with remainder 2.
  3. 3. If [a] โ‰  [b] for an equivalence relation, then:

    Two equivalence classes are either identical or disjoint.
  4. 4. Why is 'differs by at most 1' on โ„ค not an equivalence relation?

    1 ~ 2 and 2 ~ 3, but 1 and 3 differ by 2.

Summary

  • An equivalence relation is reflexive, symmetric and transitive; it formalizes "the same in some respect".
  • The class [a] = {x : x ~ a} collects everything equivalent to a.
  • a ~ b exactly when [a] = [b]; distinct classes are disjoint.
  • Congruence mod n and equality of fractions are central examples.

Next: Partitions and Quotient Sets