Home / Courses / Intro to Proofs / Unit 7

Intro to Proofs Unit 7: Relations and Equivalence Relations

Relations describe how elements of a set are connected. Equivalence relations sort a set into classes of 'alike' elements, and congruence modulo n is the key example.

Covers: Relations as sets of ordered pairs, Reflexive, symmetric, transitive and antisymmetric, Equivalence relations, Equivalence classes, Partitions, Congruence modulo n, Partial orders

Study guide

A relation R on a set A is any subset of A × A; we write a R b when (a, b) ∈ R. Four properties matter most. R is reflexive if a R a for every a ∈ A. R is symmetric if a R b implies b R a. R is transitive if a R b and b R c imply a R c. R is antisymmetric if a R b and b R a imply a = b. Reflexivity is a 'for all' statement, while the others are conditionals, so the empty relation is symmetric, transitive and antisymmetric but not reflexive on a nonempty set. Always check each property directly from its definition.

An equivalence relation is reflexive, symmetric and transitive. It behaves like a generalized equality: 'has the same remainder', 'has the same birth year', 'has the same square'. The equivalence class of a is [a] = {x ∈ A : x ~ a}. Two classes are either identical or disjoint, and every element is in its own class, so the classes form a partition of A: nonempty, pairwise disjoint blocks whose union is A. Conversely, every partition defines an equivalence relation (same block). So counting equivalence relations on a finite set is the same as counting its partitions.

Congruence modulo n is the central example: a ≡ b (mod n) when n | (a − b). It is reflexive (n | 0), symmetric (if a − b = nk then b − a = n(−k)), and transitive (add the differences). Its classes are the residue classes [0], [1], ..., [n − 1]. Congruences can be added and multiplied: if a ≡ a′ and b ≡ b′, then a + b ≡ a′ + b′ and ab ≡ a′b′ (mod n). Many relations reduce to congruences after a little algebra, such as 4 | (3a + b), which is the same as a ≡ b (mod 4).

To prove a relation is an equivalence relation, prove the three properties separately for arbitrary elements. To show it is not, give a specific counterexample to one property, such as 0 R 1 and 1 R 2 but not 0 R 2 for |a − b| ≤ 1. A partial order is reflexive, antisymmetric and transitive instead; examples are ≤ on ℝ, ⊆ on sets, and divisibility on the positive integers. Note that symmetric and antisymmetric are not opposites: a relation of only pairs (a, a) is both, and some relations are neither.

Key ideas

• A relation on A is just a subset of A × A.
• Reflexive needs every element; symmetric and transitive are conditionals that can hold vacuously.
• An equivalence relation is reflexive, symmetric and transitive.
• Equivalence classes are either equal or disjoint and together partition the set.
• Equivalence relations and partitions correspond one to one.
• Congruence mod n has exactly n classes, one per remainder.
• A partial order replaces symmetry with antisymmetry.

Formulas and rules

Common mistakes

• Checking reflexivity for only some elements instead of all of A.
• Arguing that symmetry and transitivity imply reflexivity.
• Treating symmetric and antisymmetric as opposites.
• Forgetting that an equivalence class contains the element itself.
• Proving transitivity with specific numbers instead of arbitrary elements.

Before the test, make sure you can

• Determine whether a given relation is reflexive, symmetric, transitive or antisymmetric.
• Prove that a relation is an equivalence relation.
• Give a counterexample showing a relation fails a property.
• Describe the equivalence classes of a given equivalence relation.
• Convert between an equivalence relation and its partition.
• Compute with congruences modulo n and list residue classes.
• Distinguish equivalence relations from partial orders.

Words to know

Relation

A subset R of A × A; a R b means (a, b) ∈ R.

Reflexive

a R a for every a in the set.

Symmetric

Whenever a R b, also b R a.

Transitive

Whenever a R b and b R c, also a R c.

Antisymmetric

If a R b and b R a, then a = b.

Equivalence relation

A relation that is reflexive, symmetric and transitive.

Equivalence class

[a] = the set of all elements equivalent to a.

Partition

A set of nonempty, pairwise disjoint subsets whose union is the whole set.

Congruence mod n

a ≡ b (mod n) means n divides a − b.

Residue class

An equivalence class under congruence mod n, such as [2] = {..., −1, 2, 5, ...} mod 3.

Partial order

A relation that is reflexive, antisymmetric and transitive.

Representative

Any element chosen to name its equivalence class.

Quotient set

A/~, the set of all equivalence classes.

Bell number

The number of partitions (equivalently, equivalence relations) of an n-element set: 1, 2, 5, 15, 52, ....

Sample practice questions

30 more questions like these, from level 1 to 5, are in the practice set.