Relations

A relation R from A to B is a subset of A × B. Out of all the possible pairs, a rule picks out the ones we want. If (a, b) ∈ R, we say a is related to b, and b is the image of a (a is a pre-image of b).

Example: A = {2, 3, 4}, B = {3, 5, 6, 8, 9} and R = {(x, y) : x divides y}. Check every pair:

• 2 divides 6 and 8; 3 divides 3, 6 and 9; 4 divides 8.
• So R = {(2, 6), (2, 8), (3, 3), (3, 6), (3, 9), (4, 8)}.

Three sets describe a relation:

• Domain: the set of first elements, {2, 3, 4}.
• Range: the set of second elements (the images), {3, 6, 8, 9}.
• Codomain: the whole of B, {3, 5, 6, 8, 9}. The range is always a subset of the codomain; here 5 is in the codomain but is nobody's image.

A relation can be written in roster form (list the pairs), in set-builder form (give the rule), or as an arrow diagram: draw A and B as two ovals and an arrow from each a to each b it is related to.

How many relations? Each relation is a subset of A × B. If n(A) = p and n(B) = q, A × B has pq elements, so there are 2^(pq) relations (one of them the empty relation φ). From a 2-element set to a 3-element set there are 2⁶ = 64.

A relation from A to A itself is a relation on A. On N, take R = {(a, b) : a + 2b = 10}. Trying b = 1, 2, 3, 4 gives a = 8, 6, 4, 2 (b = 5 would make a = 0, not natural). So R = {(8, 1), (6, 2), (4, 3), (2, 4)}, with domain {2, 4, 6, 8} and range {1, 2, 3, 4}.

The inverse relation R⁻¹ just turns every pair round: here R⁻¹ = {(1, 8), (2, 6), (3, 4), (4, 2)}. The domain of R becomes the range of R⁻¹, and the range of R becomes the domain of R⁻¹.