Relations

Think about your school timetable. Each row pairs a time slot with a subject: (Monday 8 am, Mathematics), (Monday 9 am, English), (Tuesday 8 am, Science), and so on. The timetable is not a set of times, and not a set of subjects — it is a set of pairings. Each pairing links one element from the set of time slots to one element from the set of subjects.

That linking idea — "this element from set A is paired with that element from set B" — is exactly what a relation is. A relation is a collection of ordered pairs, and each pair records one specific link between the two sets. The concept is deceptively simple: it is just a subset of all possible pairs. But from this one idea, you get the language to describe timetables, family trees, divisibility, congruence, "less than," "equal to," and eventually functions themselves (which are just relations with an extra rule).

The Cartesian product

Before you can pick certain pairs, you need the full menu of all possible pairs.

Take A = \{1, 2\} and B = \{x, y, z\}. Then:

There are |A| \times |B| = 2 \times 3 = 6 pairs. Every element of A gets paired with every element of B, and the pairing is ordered — the pair (1, x) is different from (x, 1) (in fact, (x, 1) would live in B \times A, not A \times B).

You can visualise A \times B as a grid. Put the elements of A along one axis and the elements of B along the other. Each cell in the grid is one ordered pair.

Two things to note:

• Order matters in the pair. (1, x) and (x, 1) are different ordered pairs. The first coordinate always comes from A and the second from B.
• A \times B \neq B \times A in general. The pairs are reversed, and unless A = B, the two products are different sets with different types of entries.
• |A \times B| = |A| \cdot |B|. If A has m elements and B has n, the product has mn pairs. For each of the m choices from A, there are n choices from B, giving m \times n pairs total.

Definition of a relation

Every subset of the grid above is a valid relation. The subset \{(1, x), (2, y)\} is a relation that pairs 1 with x and 2 with y. The empty set \varnothing is a relation (no element is related to anything). The full product A \times B is also a relation (every element is related to every element). Everything in between is a relation too.

Here is a concrete example. Let A = \{1, 2, 3, 4\} and define the relation R on A by the rule "a divides b" — that is, (a, b) \in R if and only if a divides b with no remainder. Then:

The number 1 divides everything, so it pairs with all four elements. The number 2 divides 2 and 4. The numbers 3 and 4 divide only themselves (within the set \{1,2,3,4\}).

Domain, codomain, and range

Three pieces of vocabulary describe the "reach" of a relation.

• The domain of R is the set of all first coordinates that actually appear in R: \text{dom}(R) = \{a \in A \mid (a, b) \in R \text{ for some } b \in B\}.
• The codomain is the entire set B — the set where the second coordinates could live, whether they actually appear or not.
• The range (or image) of R is the set of all second coordinates that actually appear: \text{range}(R) = \{b \in B \mid (a, b) \in R \text{ for some } a \in A\}.

The range is always a subset of the codomain: \text{range}(R) \subseteq B. The domain is always a subset of A: \text{dom}(R) \subseteq A. When R is the empty relation, both are empty.

For the divisibility relation above: domain = \{1, 2, 3, 4\} (every element divides something), codomain = \{1, 2, 3, 4\} (same set), and range = \{1, 2, 3, 4\} (every element is divisible by something). In this case domain and range coincide with A, but that is not always the case.

Take a different example: let A = \{1, 2, 3\}, B = \{a, b, c, d\}, and R = \{(1, a), (3, c)\}. Then domain = \{1, 3\} (the element 2 from A does not appear as a first coordinate), codomain = \{a, b, c, d\} (all of B), and range = \{a, c\} (only two of the four elements of B actually appear).

Types of relations on a set

When R is a relation on a set A (that is, R \subseteq A \times A), three properties classify its behaviour. These properties will show up everywhere in later mathematics — in equivalence relations, in order relations, and in the definition of congruence.

Reflexive

A relation R on A is reflexive if every element is related to itself:

The divisibility relation on \{1, 2, 3, 4\} is reflexive because every number divides itself: (1,1), (2,2), (3,3), (4,4) are all in R.

The relation "is strictly less than" on \mathbb{R} is not reflexive, because no number is strictly less than itself: (a, a) \notin R for any a.

On the grid picture, reflexive means every diagonal cell is filled.

Symmetric

A relation R on A is symmetric if the direction of the pairing never matters:

The relation "has the same birthday as" is symmetric: if Priya has the same birthday as Rahul, then Rahul has the same birthday as Priya.

The divisibility relation is not symmetric: 1 divides 2 (so (1, 2) \in R) but 2 does not divide 1 (so (2, 1) \notin R).

Transitive

A relation R on A is transitive if the links chain:

The relation "is an ancestor of" is transitive: if your grandmother is an ancestor of your mother, and your mother is an ancestor of you, then your grandmother is an ancestor of you.

The divisibility relation is transitive: if a divides b and b divides c, then a divides c. (Proof: b = ka and c = lb for some integers k, l, so c = l(ka) = (lk)a, which means a divides c.)

Equivalence relation

A relation that is reflexive, symmetric, and transitive all at once is called an equivalence relation. It is the mathematical version of "is the same as" — not literal identity, but sameness in some particular respect.

The relation "has the same remainder when divided by 3" on \mathbb{Z} is an equivalence relation. It is reflexive (every integer has the same remainder as itself), symmetric (if a and b have the same remainder, so do b and a), and transitive (if a and b share a remainder and b and c share a remainder, then a and c share that remainder too). This particular equivalence relation is called congruence modulo 3, and it partitions \mathbb{Z} into three classes: numbers with remainder 0, numbers with remainder 1, and numbers with remainder 2.

Every equivalence relation on a set A partitions A into non-overlapping equivalence classes, and conversely, every partition of A defines an equivalence relation (where two elements are related if and only if they are in the same part). This one-to-one correspondence between equivalence relations and partitions is one of the most important ideas in algebra.

Number of relations

Here is a counting question that appears on every exam. If |A| = m and |B| = n, how many relations are there from A to B?

A relation is a subset of A \times B. The Cartesian product has mn elements. From Sets — Introduction, the number of subsets of a set with k elements is 2^k. So the number of relations from A to B is:

For A = \{1, 2\} and B = \{x, y, z\}: there are 2^{2 \times 3} = 2^6 = 64 possible relations. One of them is the empty relation, one is the full Cartesian product, and the other 62 are everything in between.

For a relation on A (that is, from A to A), with |A| = n: the number of relations is 2^{n^2}. With n = 3, that is 2^9 = 512 relations on a three-element set. The number grows fast.

Interactive: exploring relations on a small set

Use the figure below to see how a relation on \{1, 2, 3\} looks on a grid. Each cell of the 3 \times 3 grid represents an ordered pair. The diagonal cells (shaded) correspond to reflexive pairs. Drag the red point along the line to select a value k from 0 to 9; the readout shows the binary representation of k, and each bit corresponds to one of the 9 cells being filled or empty, illustrating how each of the 2^9 = 512 relations is a subset of the grid.

Two worked examples

Common confusions

• "(1, 2) and (2, 1) are the same pair." No — ordered pairs are ordered. The first coordinate and the second coordinate play different roles. (1, 2) \neq (2, 1) unless both coordinates are equal. This is different from sets, where \{1, 2\} = \{2, 1\}.

• "Every relation is a function." No — a function is a special kind of relation where each element of the domain is paired with exactly one element of the codomain. A general relation can pair one element with zero, one, or many elements.

• "If a relation is not reflexive, it must be irreflexive." Not necessarily. A relation is irreflexive if no element is related to itself. But a relation can be neither reflexive nor irreflexive — for example, the relation R in Example 1 has (1,1) \in R and (2,2) \in R but (3,3) \notin R. It fails reflexivity (not all diagonal pairs are present) and also fails irreflexivity (some diagonal pairs are present).

• "Symmetric and transitive together imply reflexive." This is a famous trap. Suppose (a, b) \in R. Symmetric gives (b, a) \in R. Then transitive gives (a, a) \in R from the chain a \to b \to a. But this only works if there exists some b with (a, b) \in R in the first place. If some element a is not related to anything at all, the argument never starts, and you cannot conclude (a, a) \in R. The empty relation on \{1, 2\} is symmetric and transitive but not reflexive — it relates nothing to anything.

• "The number of relations on a set with n elements is 2^n." No — it is 2^{n^2}. A relation on a set with n elements is a subset of A \times A, which has n^2 pairs, so the number of subsets is 2^{n^2}. For n = 3, that is 2^9 = 512, not 2^3 = 8.

• "Domain and range are always equal to A and B." Only for the full Cartesian product. For a smaller relation, some elements of A may not appear as first coordinates (they are outside the domain) and some elements of B may not appear as second coordinates (they are outside the range).

Going deeper

Equivalence relations and quotient sets

When you have an equivalence relation \sim on a set A, the equivalence class of an element a is the set [a] = \{x \in A \mid x \sim a\}. The collection of all distinct equivalence classes is called the quotient set A / {\sim}. In Example 2, A / {\equiv_4} = \big\{\{0,4,8\},\, \{1,5,9\},\, \{2,6,10\},\, \{3,7,11\}\big\} — a set of four elements, each of which is itself a set.

Quotient sets are how mathematicians build new objects from old ones. The rational numbers, for instance, can be constructed as equivalence classes of ordered pairs of integers: the fraction \frac{a}{b} is the equivalence class of all pairs (a, b) where two pairs (a, b) and (c, d) are equivalent if ad = bc. So \frac{1}{2}, \frac{2}{4}, and \frac{3}{6} are all names for the same equivalence class. The rational number is the class, not any particular representative.

Counting special relation types

On a set with n elements, the total count of 2^{n^2} includes relations of every type. Counting only the relations that satisfy a given property is harder:

• Reflexive relations: each of the n diagonal pairs must be present, and the remaining n^2 - n pairs are free choices. So there are 2^{n^2 - n} reflexive relations.
• Symmetric relations: the n diagonal pairs can each be present or absent independently. The \frac{n^2 - n}{2} pairs above the diagonal can each be present or absent, and the pair below is forced to match. So there are 2^{n + \frac{n^2 - n}{2}} = 2^{\frac{n^2 + n}{2}} = 2^{n(n+1)/2} symmetric relations.
• Equivalence relations: this count equals the number of partitions of an n-element set, called the Bell number B_n. For n = 3, B_3 = 5. For n = 4, B_4 = 15. Bell numbers grow very quickly and have no simple closed form.

Partial orders

Drop the symmetry requirement and keep reflexivity and transitivity, and add antisymmetry (if a\, R\, b and b\, R\, a, then a = b). The result is a partial order. The divisibility relation on the positive integers is a partial order: if a \mid b and b \mid a, then a = b. Partial orders are the foundation of the lattice theory that underlies much of abstract algebra, and they show up again in combinatorics (Hasse diagrams) and computer science (dependency graphs).

Where this leads next

Relations are the scaffolding on which functions, order, and equivalence are all built.

• Functions — Introduction — a function is a relation with a uniqueness rule: every input maps to exactly one output.
• Equivalence Relations — the full theory of equivalence classes, partitions, and quotient sets.
• Sets — Introduction — the prerequisite article, if you need to revisit the notation and definitions that this article builds on.
• Set Operations — the union, intersection, and complement operations that apply to relations as sets of ordered pairs.
• Logic and Propositions — the logical connectives "and," "or," "not," and "implies" that appeared implicitly in every definition above are formalised there.