Types of relations

The essentials

A relation R from a set A to a set B is a subset of A × B. When A = B we call it a relation on A. If a set A has n elements, A × A has n² ordered pairs, so the number of possible relations on A is 2^(n²). We write a R b, or (a, b) ∈ R, when a is related to b.

Relations are classified by three properties. R on A is reflexive if (a, a) ∈ R for every a in A. It is symmetric if (a, b) ∈ R always forces (b, a) ∈ R. It is transitive if (a, b) ∈ R and (b, c) ∈ R always force (a, c) ∈ R. A relation with all three properties is an equivalence relation.

Key points

• Empty relation: no pairs at all (R = ∅). Universal relation: R = A × A.
• The identity relation {(a, a) : a ∈ A} is reflexive, symmetric and transitive.
• "a − b is divisible by n" on the integers (congruence modulo n) is the standard example of an equivalence relation.
• The equivalence class [a] is the set of all elements related to a. Distinct classes never overlap, and together they cover the whole set.
• "Is perpendicular to" on lines in a plane is symmetric but not reflexive or transitive.
• "≤" on real numbers is reflexive and transitive but not symmetric.

Exam tips

• To prove a property fails, one counter-example is enough. To prove it holds, argue for every element.
• For transitivity in a small finite relation, check every chain (a, b), (b, c) one by one.

Common mistakes

• Thinking that a relation without any chain (a, b), (b, c) fails transitivity. If there is nothing to check, the condition holds automatically.
• Forgetting that reflexivity needs (a, a) for every element of the set, not just some.