Relations on Sets

definitions
discrete-math
set-theory
relations

A relation records which elements are related to which, and nothing more: any set of ordered pairs. Functions are the special relations with exactly one partner for each input. The properties a relation on one set can have are in reflexive-symmetric-and-transitive-relations. The lecture is 2026-09-17-relations-reflexivity-symmetry-transitivity.

The definition

Any subset \(\rho\) of \(A \times B\) is a binary relation from \(A\) to \(B\).

A relation on a set \(A\) is a binary relation from \(A\) to \(A\), that is, a subset of \(A \times A\).

If \((x, y) \in \rho\) we write \(x \mathrel{\rho} y\) and read it “\(x\) is related in \(\rho\) to \(y\)”. If \((x,y) \notin \rho\) we write \(x \mathrel{\not\rho} y\). The two notations mean exactly the same thing and either is fine in an answer. Relations are usually named with Greek letters: \(\rho\) (rho), \(\sigma\) (sigma), \(\tau\) (tau).

Order matters. \((1,0)\) and \((0,1)\) are different pairs, so \(1 \mathrel{\rho} 0\) and \(0 \mathrel{\rho} 1\) are different statements, and one can hold without the other. The first coordinate is where an arrow starts, and the second is where it ends.

For example, with \(A = \{1,2,3,4\}\) and \(B = \{0,2,4,6,8\}\), \[\rho = \{(1,0), (3,4), (4,0), (4,4), (4,6)\}\] is a relation from \(A\) to \(B\): \(1 \mathrel{\rho} 0\), \(3 \mathrel{\rho} 4\), \(4 \mathrel{\rho} 0\), \(4 \mathrel{\rho} 4\), \(4 \mathrel{\rho} 6\), and nothing else is related.

Functions are relations

The definition of a function (functions-on-general-sets) is the definition of a relation with one extra condition:

A subset \(f\) of \(A \times B\) is a function from \(A\) to \(B\) if for each \(a \in A\), there is a unique \(b \in B\) such that \((a,b) \in f\).

So every function is a relation, and a relation is not necessarily a function. A relation may give an element of \(A\) no partner, or several; a function must give each exactly one. Written as a relation, \(f(a) = b\) is just \(a\,f\,b\), since \(f(a) = b \leftrightarrow (a,b) \in f\).

Figure 1: A relation is a choice of points from the grid \(A \times B\). Each column is an element of \(A\) and each row an element of \(B\), and the filled points are the pairs in the relation. Left: the relation \(\rho\) is any choice of points — column 2 is empty, column 4 has three. Right: a function \(f\) is a choice with exactly one point in every column, the unique \(b\) for each \(a\). Nothing restricts the rows in either: in \(f\), row 4 has two points and rows 6 and 8 have none.

Relations defined by a condition

Listing pairs only works for small finite sets. Usually a relation on \(A\) is defined by a condition on \(x\) and \(y\):

  • \(x \mathrel{\rho} y \leftrightarrow x > y\) for all \(x, y \in A\);
  • \(X \mathrel{\rho} Y \leftrightarrow X \cap Y = \emptyset\) for all \(X, Y \in A\) (here \(A\) is a set of sets, such as \(\mathcal{P}(\mathbb{Z}^{+})\));
  • \(m \mathrel{\rho} n \leftrightarrow 6 \mid (m - n)\) for all \(m, n \in A\);
  • \(x \mathrel{\rho} y \leftrightarrow xy \equiv 1 \pmod 7\) on \(\{0, 1, \dots, 6\}\).

To decide whether a particular pair is related, substitute and check. \(5 \mathrel{\rho} 2\) under \(x > y\) because \(5 > 2\), and \(2 \mathrel{\not\rho} 5\). Under \(6 \mid (m-n)\), \(13 \mathrel{\rho} 1\) because \(13 - 1 = 12 = 6 \cdot 2\), and \(13 \mathrel{\not\rho} 2\). The relation is the set of all pairs that pass: \(\rho = \{(x,y) \in A \times A : x > y\}\).

Arrow diagrams

A relation on a finite set is drawn as an arrow diagram, also called a directed graph: one dot per element, and an arrow from \(x\) to \(y\) for each pair \((x,y) \in \rho\). An arrow from an element to itself is a loop. The two drawings of a relation on \(A\) are compared in 2026-09-17-relations-reflexivity-symmetry-transitivity. With two copies of \(A\) side by side, as for a function, loops become horizontal arrows and are easy to miss. With a single copy of \(A\), loops, arrows in both directions and paths of two arrows can all be seen at a glance, and those are what the properties of relations are about.

Reading a diagram back into pairs: each arrow is one pair, loops included. Forgetting the loops is the usual slip.

Figure 2: The relation \(m \mathrel{\rho} n \leftrightarrow 6 \mid (m-n)\) on \({0, 1, \dots, 11}\), drawn with a single copy of the set. Two numbers are related exactly when they leave the same remainder on division by 6, so the diagram falls apart into six separate pieces, one per remainder: each number has a loop, since \(6 \mid 0\), and each pair such as 1 and 7 is joined both ways, since \(7 - 1\) and \(1 - 7\) are both multiples of 6. Nothing joins different pieces. A diagram that splits into clusters like this marks a special kind of relation, the equivalence relations.

Common mistakes

  • Treating a relation like a function. \(\rho(x)\) means nothing. A relation can have many partners for \(x\), or none, so there is no “value” to name. Write \(x \mathrel{\rho} y\) or \((x,y) \in \rho\).
  • Reversing the pair. \(x \mathrel{\rho} y\) is the arrow from \(x\) to \(y\). Under \(x > y\), \(5 \mathrel{\rho} 2\) but not \(2 \mathrel{\rho} 5\).
  • Dropping loops when reading pairs off a diagram, or when drawing one.
  • Forgetting the set. A relation is on a particular set. “\(xy \equiv 1 \pmod 7\)” on \(\{0, \dots, 6\}\) has 6 pairs, on \(\mathbb{Z}\) infinitely many. Always state or check the set.

See also