Lecture 3. Relations #

Learning objectives #

After studying this chapter you should be able to:

• state precisely what a binary relation and an $n$-ary relation are, and move fluently between the three standard representations (set of pairs, Boolean matrix, digraph);
• recognise and prove the structural properties of a relation — reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive — including their algebraic characterisations ($\Delta_A\subseteq R$, $R=R^{-1}$, $R^2\subseteq R$, $R\cap R^{-1}\subseteq\Delta_A$);
• compute inverses and compositions, and justify why composition is realised by the Boolean matrix product and why it is associative;
• construct the reflexive, symmetric and transitive closures of a relation, prove the formula $t(R)=\bigcup_{k\ge1}R^{k}$, and explain why the union is finite on a finite set;
• prove the Fundamental Theorem of Equivalence Relations (equivalence relations $\leftrightarrow$ partitions) in both directions and apply it to congruence classes in modular arithmetic;
• analyse partial orders: comparability, Hasse diagrams, minimal/maximal and least/greatest elements, bounds, and a first look at lattices;
• connect the theory to computer science, especially the relational database model and relational algebra.

This chapter builds directly on Lecture 1 (subsets, power sets) and Lecture 2 (set operations, ordered tuples, and the Cartesian product). It is used later whenever we group outcomes into cases — for example in Lecture 13, where an equivalence relation on a sample space partitions it into the disjoint events that make counting and probability tractable.

3.1 Overview and motivation #

Sets on their own describe collections of objects, but almost every interesting mathematical or computational statement is about how objects are linked: “$x$ is less than $y$”, “student $s$ received mark $m$ in subject $j$”, “city $a$ has a direct flight to city $b$”, “web page $u$ links to page $v$”, “process $p$ must run before process $q$”. A relation is the mathematical object that captures exactly this idea of a link between elements — nothing more and nothing less.

The whole subject rests on one deceptively small idea from Lecture 2: an ordered pair $(a,b)$ remembers not only which two objects are involved but also which comes first. (Recall Kuratowski’s set-theoretic encoding $(a,b)=\{\{a\},\{a,b\}\}$, which makes $(a,b)=(c,d)$ hold iff $a=c$ and $b=d$.) A relation is then simply a set of such pairs selected out of a Cartesian product. Everything else in this chapter — matrices, digraphs, equivalence classes, orders, database tables — is a consequence of taking that one definition seriously.

Three themes recur throughout:

1. One object, several faces. A relation is simultaneously a set of tuples, a Boolean matrix, and a directed graph. Each face makes some questions trivial: the matrix face turns “is there a two-step path?” into arithmetic; the graph face makes reachability visible; the set face makes union/intersection obvious.
2. Structure via properties. A handful of properties (reflexive, symmetric, transitive, …) carve out the two most important species of relation: equivalence relations, which formalise “the same for our purposes”, and partial orders, which formalise “ranking, possibly with ties left incomparable”.
3. From theory to systems. The generalisation to $n$-ary relations is not an afterthought: it is literally the data model of every relational database, and the set operations of Lecture 2 reappear as the core of relational algebra and hence of SQL.

3.2 Tuples and the Cartesian product (recap from Lecture 2) #

A tuple is an ordered list of elements. Given sets $A,B,C$, an ordered triple is written $(a,b,c)$ with $a\in A$, $b\in B$, $c\in C$; order matters and repetition is allowed, distinguishing tuples from sets. The Cartesian product collects all such tuples:

$$X = A \times B \times C = \{(a,b,c) \mid a\in A,\ b\in B,\ c\in C\}.$$

For finite sets the product rule gives $|A\times B\times C| = |A|\cdot|B|\cdot|C|$.

Example. With $A=\{1,2,3\}$, $B=\{4,5\}$, $C=\{6,7\}$ we get $|X| = 3\cdot 2\cdot 2 = 12$ triples:

$$X = \{(1,4,6),(1,4,7),(1,5,6),(1,5,7),(2,4,6),(2,4,7),$$

$$(2,5,6),(2,5,7),(3,4,6),(3,4,7),(3,5,6),(3,5,7)\}.$$

The Cartesian product is the “universe” of all conceivable tuples; a relation picks out the tuples we actually care about.

Remark (why order and repetition matter). The pair $(2,5)$ is not the pair $(5,2)$, and $(3,3)$ is a perfectly good pair even though the set $\{3,3\}=\{3\}$ collapses. This is precisely why relations can express asymmetric links such as “$x$ is the parent of $y$” that a symmetric set-of-two could never record.

3.3 Binary relations as subsets of a Cartesian product #

Definition 3.1 (binary relation). A binary relation $R$ from a set $A$ to a set $B$ is any subset $R \subseteq A \times B$. When $A=B$ we say $R$ is a relation on $A$ (so $R\subseteq A\times A$). Its elements are ordered pairs $(a,b)$.

Two notations mean exactly the same thing:

$$(a,b)\in R \qquad\Longleftrightarrow\qquad aRb,$$

read “$a$ is related to $b$”. They are interchangeable because $R$ is its set of pairs — the infix statement $aRb$ is only shorthand for membership in that set. The infix form mirrors the familiar $a \le b$ or $a = b$ and is usually more readable; we shall use whichever is clearer.

There are two standard ways to specify a relation:

1. By listing the ordered pairs explicitly (an extensional definition), and
2. By a predicate, i.e. a defining property (an intensional definition): $R = \{(x,y) \mid P(x,y)\}$.

Example 3.2 (both ways, one relation). Let $A = B = \{1,2,3,4\}$ and let $R$ be “strictly less than”. Extensionally,

$$R = \{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\};$$

intensionally,

$$R = \{(x,y) \mid x\in A,\ y\in B,\ x<y\}.$$

Both describe the same six pairs. The intensional form scales to infinite sets (the relation $<$ on $\mathbb{Z}$) where listing is impossible.

More examples of the infix form $aRb$.

• $R_1={}$ “less than or equal to”: $4\,R_1\,16$, $5\,R_1\,7$, $3\,R_1\,3$.
• $R_2={}$ “is divisible by”: $4\,R_2\,2$, $9\,R_2\,3$, $7\,R_2\,1$.
• $R_3={}$ “uses the same digits as”: $132\,R_3\,123$, $34\,R_3\,43$, $121\,R_3\,1112$ (both sides use only the digits $\{1,2\}$).

Common pitfall (a relation is not a rule). A relation need not be describable by any tidy formula. On $\{1,2,3\}$ the set $\{(1,3),(3,1),(2,2)\}$ is a perfectly legitimate relation even though no arithmetic condition singles out those three pairs. Conversely, do not confuse the predicate with the relation: two different predicates ($x<y$ and “$y-x$ is a positive integer”) can define the same relation.

3.4 Domain and range #

For $R \subseteq A \times B$:

Definition 3.3. The domain of $R$ is $\operatorname{dom}(R) = \{a\in A \mid \exists b\in B,\ (a,b)\in R\}$ — the first components that actually occur. The range (or image) of $R$ is $\operatorname{ran}(R) = \{b\in B \mid \exists a\in A,\ (a,b)\in R\}$ — the second components that actually occur.

Example 3.4. For the “strictly less than” relation of Example 3.2, $\operatorname{dom}(R) = \{1,2,3\}$ (the value $4$ is less than nothing in $A$) and $\operatorname{ran}(R) = \{2,3,4\}$ (nothing is less than $1$). Both are subsets of $A$; neither need be all of $A$.

Remark. The domain and range are projections of $R$ onto its first and second coordinates. We will meet projection again in §3.11 as the relational- algebra operator $\pi$; it is the very same idea applied to $n$-ary relations.

3.5 Representing a relation #

A relation admits three interchangeable representations; picking the right one often turns a hard-looking question into an easy one.

3.5.1 As a set of ordered pairs #

The direct definition, e.g. $R = \{(1,2),(1,3),(1,4),(2,3),(2,4),(3,4)\}$. This is compact for sparse relations and makes set operations ($\cup,\cap,\setminus$) transparent.

3.5.2 As a relation matrix (Boolean / adjacency matrix) #

For a relation on a finite set $A=\{a_1,\dots,a_n\}$, build an $n\times n$ table indexed by the elements. The entry in row $a_i$, column $a_j$ is

$$m_{ij} = \begin{cases}1 & \text{if } a_iRa_j,\\[2pt] 0 & \text{otherwise.}\end{cases}$$

For the “strictly less than” relation on $\{1,2,3,4\}$:

The matrix form is ideal for checking structural properties by inspection and for computing compositions and closures (below). Its size is fixed at $n^2$ bits regardless of how many pairs are present, so it is best for dense relations.

3.5.3 As a directed graph (digraph) #

Draw one vertex (node) per element and one arrow $a \to b$ for every pair $(a,b)\in R$. A pair $(a,a)$ becomes a self-loop at $a$. For “strictly less than” on $\{1,2,3,4\}$ the digraph has four vertices with arrows from every smaller number to every larger one.

Two extreme relations are worth naming, both instantly recognisable in matrix form:

• Universal (full) relation — $R = A\times A$; every pair is related, so the matrix is all ones.
• Empty relation — $R = \varnothing$; no pair is related, so the matrix is all zeros.

A third, quietly important, is the identity (diagonal) relation

$$\Delta_A = \{(a,a)\mid a\in A\},$$

also called the equality relation; its matrix is the identity matrix $I_n$ and its digraph is a self-loop at every vertex and nothing else. We will use $\Delta_A$ constantly when defining reflexive closures and powers of a relation.

Remark (bridge to Lecture 10). A relation on a set is exactly the data of a directed graph, and a symmetric relation with no self-loops is exactly an undirected graph. The matrix $M_R$ is the graph’s adjacency matrix. Graph theory (Lecture 10) can therefore be read as the study of relations from a visual, combinatorial angle.

3.6 Properties of binary relations #

Let $R$ be a relation on a set $A$. The following properties classify how $R$ behaves; each has a crisp logical definition, a matrix “fingerprint”, and — as we prove in §3.6.1 — a slick algebraic form.

Definition 3.5. The relation $R$ on $A$ is

• reflexive if $\forall a\in A:\ aRa$. Matrix: the whole main diagonal is $1$.
• irreflexive if $\forall a\in A:\ \lnot(aRa)$. Matrix: the whole diagonal is $0$.
• symmetric if $\forall a,b:\ aRb \Rightarrow bRa$. Matrix: $M=M^{\mathsf T}$.
• antisymmetric if $\forall a,b:\ (aRb \wedge bRa) \Rightarrow a=b$. Matrix: no off-diagonal mirror pair $m_{ij}=m_{ji}=1$ with $i\ne j$.
• asymmetric if $\forall a,b:\ aRb \Rightarrow \lnot(bRa)$. Matrix: zero main diagonal and no mirror pair $m_{ij}=m_{ji}=1$ (equivalently $R\cap R^{-1}=\varnothing$).
• transitive if $\forall a,b,c:\ (aRb \wedge bRc) \Rightarrow aRc$. Matrix: wherever a two-step path exists, the direct entry is also $1$.
• antitransitive if $\forall a,b,c:\ (aRb \wedge bRc) \Rightarrow \lnot(aRc)$ — a two-step path never has its direct shortcut. Example: the successor chain $\{(1,2),(2,3),(3,4)\}$ on $\{1,2,3,4\}$; or “beats” in rock–paper–scissors.

Common pitfall (reflexive vs. irreflexive are not opposites). A relation can be neither. On $\{1,2\}$ the relation $\{(1,1)\}$ has $1R1$ but not $2R2$, so it is neither reflexive (misses $2R2$) nor irreflexive (has $1R1$). “Not reflexive” means some diagonal entry is missing; “irreflexive” means every diagonal entry is missing. Likewise symmetric and antisymmetric are not opposites: the identity relation $\Delta_A$ is both, while $\{(1,2),(2,1),(1,3)\}$ is neither.

Proposition 3.6 (asymmetric $=$ irreflexive $+$ antisymmetric). $R$ is asymmetric iff $R$ is both irreflexive and antisymmetric.

Proof. ($\Rightarrow$) Suppose $R$ is asymmetric. Taking $b=a$ in the definition, $aRa\Rightarrow\lnot(aRa)$, which forces $\lnot(aRa)$ for every $a$; hence $R$ is irreflexive. For antisymmetry, suppose $aRb$ and $bRa$; asymmetry applied to $aRb$ gives $\lnot(bRa)$, contradicting $bRa$. So the hypothesis $aRb\wedge bRa$ is never satisfiable, and the implication “$aRb\wedge bRa\Rightarrow a=b$” holds vacuously. ($\Leftarrow$) Suppose $R$ is irreflexive and antisymmetric, and suppose $aRb$. If also $bRa$, antisymmetry gives $a=b$, whence $aRa$ — contradicting irreflexivity. Therefore $\lnot(bRa)$, and $R$ is asymmetric. $\;\blacksquare$

A strict order such as $<$ on $\mathbb{Z}$ is the archetypal asymmetric relation.

Worked example 3.7 (checking properties from a matrix). Consider $R$ on $\{1,2,3,4\}$:

So $R=\{(1,3),(1,4),(2,1),(2,3),(2,4)\}$.

• Reflexive? No — the diagonal is all $0$ (in fact $R$ is irreflexive).
• Symmetric? No — $(2,1)\in R$ but $(1,2)\notin R$.
• Antisymmetric? Yes — there is no mirror pair $m_{ij}=m_{ji}=1$ with $i\ne j$.
• Transitive? Yes — the only two-step chains start at $2$: $2R1$ then $1R3$ needs $2R3$ ✓, and $2R1$ then $1R4$ needs $2R4$ ✓. Every other chain dies immediately because rows $3$ and $4$ are empty. Since all required “shortcuts” are present, $R$ is transitive.

Worked example 3.8 (a symmetric relation). The matrix

satisfies $M=M^{\mathsf T}$, so $R$ is symmetric: every arrow $a\to b$ is matched by $b\to a$, and in the digraph edges come in bidirectional pairs. It is not transitive: $2R1$ and $1R3$ but $\lnot(2R3)$.

3.6.1 Algebraic characterisations #

Each property can be phrased purely in the algebra of relations — using the identity relation $\Delta_A$, the inverse $R^{-1}$ (§3.7) and composition $R^2=R\circ R$. These forms are the ones that make later proofs short.

Theorem 3.9. For a relation $R$ on $A$:

1. $R$ is reflexive $\iff \Delta_A \subseteq R$.
2. $R$ is symmetric $\iff R = R^{-1}$.
3. $R$ is antisymmetric $\iff R \cap R^{-1} \subseteq \Delta_A$.
4. $R$ is transitive $\iff R^2 \subseteq R$ (equivalently $R\circ R\subseteq R$).

Proof. (1) $\Delta_A\subseteq R$ says $(a,a)\in R$ for all $a$, i.e. $aRa$ for all $a$ — the definition of reflexive.

(2) By definition $R^{-1}=\{(b,a)\mid (a,b)\in R\}$. If $R$ is symmetric and $(a,b)\in R^{-1}$ then $(b,a)\in R$, so by symmetry $(a,b)\in R$; hence $R^{-1}\subseteq R$. The reverse inclusion $R\subseteq R^{-1}$ is symmetric (swap roles), giving $R=R^{-1}$. Conversely if $R=R^{-1}$ and $aRb$, then $(a,b)\in R=R^{-1}$, so $(b,a)\in R$, i.e. $bRa$; thus $R$ is symmetric.

(3) Suppose $R$ is antisymmetric and $(a,b)\in R\cap R^{-1}$. Then $(a,b)\in R$ (so $aRb$) and $(a,b)\in R^{-1}$ (so $(b,a)\in R$, i.e. $bRa$); antisymmetry gives $a=b$, so $(a,b)\in\Delta_A$. Conversely, suppose $R\cap R^{-1}\subseteq\Delta_A$ and $aRb\wedge bRa$. Then $(a,b)\in R$ and $(a,b)\in R^{-1}$, so $(a,b)\in R\cap R^{-1}\subseteq\Delta_A$, whence $a=b$.

(4) Suppose $R$ is transitive and $(a,c)\in R^2=R\circ R$. Then there is $b$ with $(a,b)\in R$ and $(b,c)\in R$; transitivity gives $(a,c)\in R$. Hence $R^2\subseteq R$. Conversely suppose $R^2\subseteq R$ and $aRb\wedge bRc$. Then $(a,c)\in R\circ R=R^2\subseteq R$, so $aRc$; thus $R$ is transitive. $\;\blacksquare$

Remark. Part (4) is the engine behind transitive closure (§3.8): “make $R$ transitive” means “keep composing $R$ with itself until nothing new appears”.

3.6.2 Counting relations with a given property #

Because a relation on an $n$-element set is exactly a filling of an $n\times n$ grid of bits, counting them is pure combinatorics — a favourite source of exam problems and a first taste of the counting techniques of later lectures.

Proposition 3.10. On a set with $|A|=n$:

• the number of relations is $2^{n^2}$;
• the number of reflexive relations is $2^{\,n^2-n}$;
• the number of symmetric relations is $2^{\,n(n+1)/2}$;
• the number of antisymmetric relations is $2^{\,n}\,3^{\,\binom{n}{2}}$.

Proof. Each of the $n^2$ cells is independently $0$ or $1$, giving $2^{n^2}$ relations. For reflexive relations the $n$ diagonal cells are forced to $1$ and the remaining $n^2-n$ cells are free: $2^{\,n^2-n}$. For symmetric relations the $n$ diagonal cells are free and the $\binom{n}{2}$ cells strictly above the diagonal are free, while each cell below the diagonal is forced to equal its mirror; this gives $2^{\,n+\binom{n}{2}}=2^{\,n(n+1)/2}$. For antisymmetric relations the $n$ diagonal cells are free ($2^n$ choices), while each of the $\binom{n}{2}$ mirror-pairs $\{(i,j),(j,i)\}$ with $i<j$ may be filled in exactly $3$ admissible ways — $00$, $10$, or $01$ (but not $11$) — giving $2^{\,n}\,3^{\,\binom{n}{2}}$. $\;\blacksquare$

Example 3.11. For $n=3$: $2^{9}=512$ relations in all; $2^{6}=64$ reflexive; $2^{6}=64$ symmetric; $2^{3}\,3^{3}=8\cdot27=216$ antisymmetric; and $2^{\binom32}=2^{3}=8$ relations that are both reflexive and symmetric (diagonal forced to $1$, the three upper cells free).

3.7 Inverse and composition of relations #

Definition 3.12 (inverse). The inverse (or converse) of $R\subseteq A\times B$ is

$$R^{-1} = \{(b,a) \mid (a,b)\in R\} \subseteq B\times A,$$

so that $bR^{-1}a \iff aRb$. In matrix terms $M_{R^{-1}} = M_R^{\mathsf T}$; in the digraph, every arrow is reversed.

For instance the inverse of “less than” is “greater than”, and the inverse of “is a child of” is “is a parent of”. By Theorem 3.9(2), $R$ is symmetric exactly when $R=R^{-1}$.

Definition 3.12a (complement). The complement of a relation $R$ on a set $A$ is $\overline{R} = (A\times A)\setminus R$ — the pairs $R$ omits — so that $a\,\overline{R}\,b \iff \lnot(aRb)$. In matrix terms every entry flips $0\leftrightarrow 1$; in the digraph, present and absent arrows swap. For example, the complement of $<$ is $\ge$, and the complement of $=$ is $\ne$.

Definition 3.13 (composition). Given $R\subseteq A\times B$ and $S\subseteq B\times C$, their composition $S\circ R \subseteq A\times C$ is

$$S\circ R = \{(a,c) \mid \exists\, b\in B:\ (a,b)\in R \text{ and } (b,c)\in S\}.$$

Read $S\circ R$ right-to-left: “$R$ first, then $S$”, exactly as with function composition $g\circ f$. Composition chains relations through a common middle set.

Common pitfall (order matters, and it flips for matrices). In general $S\circ R \ne R\circ S$; they may even live in different Cartesian products. And note the reversal in the matrix formula below: the composite $S\circ R$ corresponds to the product $M_R M_S$, with the factors in the opposite order to the composition symbols.

Worked example 3.14. Let $A=\{1,2\}$, $B=\{x,y,z\}$, $C=\{p,q\}$, with $R=\{(1,x),(1,y),(2,z)\}$ and $S=\{(x,p),(y,q),(z,q)\}$. Tracing paths $1\to x\to p$, $1\to y\to q$, $2\to z\to q$ gives

$$S\circ R = \{(1,p),\ (1,q),\ (2,q)\}.$$

3.7.1 Composition via the Boolean matrix product #

The Boolean matrix product multiplies two $0/1$ matrices like ordinary matrices but with logical OR ($\vee$) in place of $+$ and logical AND ($\wedge$) in place of $\cdot$. For an $m\times n$ matrix $P$ and an $n\times p$ matrix $Q$,

$$\bigl(P\odot Q\bigr)_{ik} = \bigvee_{j=1}^{n}\bigl(p_{ij}\wedge q_{jk}\bigr).$$

Theorem 3.15 (composition = Boolean product). Let $R\subseteq A\times B$ and $S\subseteq B\times C$ with $A=\{a_1,\dots,a_m\}$, $B=\{b_1,\dots,b_n\}$, $C=\{c_1,\dots,c_p\}$. Then

$$M_{S\circ R} \;=\; M_R \odot M_S .$$

Proof. Write $M_R=[r_{ij}]$ (so $r_{ij}=1 \iff (a_i,b_j)\in R$) and $M_S=[s_{jk}]$ (so $s_{jk}=1 \iff (b_j,c_k)\in S$). Fix indices $i,k$. By the definition of the Boolean product,

$$\bigl(M_R\odot M_S\bigr)_{ik}=1 \iff \exists\, j\in\{1,\dots,n\}:\ r_{ij}\wedge s_{jk}=1 \iff \exists\, j:\ r_{ij}=1 \text{ and } s_{jk}=1.$$

By the meaning of the matrix entries this says

$$\exists\, b_j\in B:\ (a_i,b_j)\in R \text{ and } (b_j,c_k)\in S,$$

which is precisely the defining condition for $(a_i,c_k)\in S\circ R$ (Definition 3.13). Hence $\bigl(M_R\odot M_S\bigr)_{ik}=1 \iff (a_i,c_k)\in S\circ R \iff \bigl(M_{S\circ R}\bigr)_{ik}=1$. As the two matrices agree in every entry, they are equal. $\;\blacksquare$

Worked example 3.16 (Example 3.14, done by matrix). Index $A=(1,2)$, $B=(x,y,z)$, $C=(p,q)$:

$$M_R=\begin{pmatrix}1&1&0\\0&0&1\end{pmatrix},\qquad M_S=\begin{pmatrix}1&0\\0&1\\0&1\end{pmatrix}.$$

Then

$$M_R\odot M_S=\begin{pmatrix}(1\wedge1)\vee(1\wedge0)\vee(0\wedge0) & (1\wedge0)\vee(1\wedge1)\vee(0\wedge1)\\[2pt](0\wedge1)\vee(0\wedge0)\vee(1\wedge0) & (0\wedge0)\vee(0\wedge1)\vee(1\wedge1)\end{pmatrix} =\begin{pmatrix}1&1\\0&1\end{pmatrix},$$

i.e. $S\circ R=\{(1,p),(1,q),(2,q)\}$, reproducing the hand computation.

Remark (why OR, not $+$). A relation records only whether a connecting element exists, never how many. Using ordinary $+$ would count the number of intermediate $b$’s (e.g. give a $2$), which is meaningless for a $0/1$ relation. Replacing $+$ by $\vee$ (equivalently, capping every sum at $1$) keeps us inside $\{0,1\}$ and matches the existential quantifier “$\exists b$” in Definition 3.13.

3.7.2 Associativity, and powers of a relation #

Theorem 3.17 (associativity of composition). For $R\subseteq A\times B$, $S\subseteq B\times C$, $T\subseteq C\times D$,

$$T\circ(S\circ R) = (T\circ S)\circ R.$$

Proof. Both sides are subsets of $A\times D$; we show they contain the same pairs. For arbitrary $(a,d)\in A\times D$,

$$\begin{aligned} (a,d)\in T\circ(S\circ R) &\iff \exists c\in C:\ (a,c)\in S\circ R \ \wedge\ (c,d)\in T\\ &\iff \exists c\in C:\ \bigl(\exists b\in B:\ (a,b)\in R \wedge (b,c)\in S\bigr)\wedge (c,d)\in T\\ &\iff \exists b\in B\ \exists c\in C:\ (a,b)\in R \wedge (b,c)\in S \wedge (c,d)\in T. \end{aligned}$$

On the other side,

$$\begin{aligned} (a,d)\in (T\circ S)\circ R &\iff \exists b\in B:\ (a,b)\in R \ \wedge\ (b,d)\in T\circ S\\ &\iff \exists b\in B:\ (a,b)\in R \wedge \bigl(\exists c\in C:\ (b,c)\in S \wedge (c,d)\in T\bigr)\\ &\iff \exists c\in C\ \exists b\in B:\ (a,b)\in R \wedge (b,c)\in S \wedge (c,d)\in T. \end{aligned}$$

The two final conditions differ only in the order of the independent existential quantifiers $\exists b\,\exists c$ versus $\exists c\,\exists b$; since $b$ and $c$ range over unrelated sets, both simply assert the existence of a pair $(b,c)\in B\times C$ with the stated three-part property. Hence the conditions are logically equivalent, and the two sets coincide. $\;\blacksquare$

Associativity is exactly what lets us write powers of a relation on $A$ without brackets. Define

$$R^{1}=R,\qquad R^{k+1}=R\circ R^{k}\quad(k\ge1),$$

and, for reflexive/transitive purposes, $R^{0}=\Delta_A$. By Theorem 3.17, $R^{i}\circ R^{j}=R^{\,i+j}$ regardless of grouping, and by Theorem 3.15 the powers are computed by repeated Boolean matrix products: $M_{R^{k}}=M_R^{\odot k}$.

Lemma 3.18 (powers count paths). For $k\ge1$, $(a,b)\in R^{k}$ iff there exist $x_0,x_1,\dots,x_k\in A$ with $x_0=a$, $x_k=b$, and $(x_{t-1},x_t)\in R$ for every $t=1,\dots,k$ — that is, iff there is a directed walk of length $k$ from $a$ to $b$ in the digraph of $R$.

Proof. Induction on $k$. Base $k=1$: $R^{1}=R$, and a walk of length $1$ from $a$ to $b$ is exactly a single edge $(a,b)\in R$. Step: assume the claim for $k$. Then

$$(a,b)\in R^{k+1}=R\circ R^{k} \iff \exists\, c\in A:\ (a,c)\in R^{k}\ \wedge\ (c,b)\in R.$$

By the induction hypothesis $(a,c)\in R^{k}$ iff there is a walk $a=x_0,\dots,x_k=c$ of length $k$; appending the edge $(c,b)\in R$ yields a walk $a=x_0,\dots,x_k=c,\ x_{k+1}=b$ of length $k+1$. Conversely any length-$(k+1)$ walk from $a$ to $b$ splits at its penultimate vertex $c=x_k$ into a length-$k$ walk $a\to c$ (so $(a,c)\in R^{k}$) followed by the edge $(c,b)\in R$. Hence $(a,b)\in R^{k+1}$ iff such a walk exists. $\;\blacksquare$

This “walks” reading is the key to understanding transitive closure, to which we now turn.

3.8 Closures of a relation #

Sometimes a relation lacks a property we need. The closure of $R$ with respect to a property $\mathcal{P}$ is the smallest relation that contains $R$ and has property $\mathcal{P}$ — it adds as few pairs as possible. “Smallest” means: it is contained in every relation that contains $R$ and has $\mathcal{P}$. (When such a smallest relation exists it is automatically unique, since if $C_1,C_2$ were both smallest then $C_1\subseteq C_2$ and $C_2\subseteq C_1$.)

3.8.1 Reflexive and symmetric closures #

Definition/Theorem 3.19. Let $R$ be a relation on $A$.

• The reflexive closure is $r(R)=R\cup\Delta_A$.
• The symmetric closure is $s(R)=R\cup R^{-1}$. Each is the smallest relation with the stated property containing $R$.

Proof. Reflexive. $r(R)\supseteq\Delta_A$, so it is reflexive (Theorem 3.9(1)), and $r(R)\supseteq R$. If $T$ is any reflexive relation with $R\subseteq T$, then $\Delta_A\subseteq T$ (reflexivity) and $R\subseteq T$, hence $r(R)=R\cup\Delta_A\subseteq T$. So $r(R)$ is smallest.

Symmetric. First $s(R)$ is symmetric: take $(a,b)\in s(R)$. If $(a,b)\in R$ then $(b,a)\in R^{-1}\subseteq s(R)$; if $(a,b)\in R^{-1}$ then $(b,a)\in R\subseteq s(R)$; either way $(b,a)\in s(R)$. Clearly $R\subseteq s(R)$. Now let $T$ be symmetric with $R\subseteq T$. Then $R\subseteq T$ implies $R^{-1}\subseteq T^{-1}$, and $T=T^{-1}$ by symmetry (Theorem 3.9(2)), so $R^{-1}\subseteq T$. Hence $s(R)=R\cup R^{-1}\subseteq T$, and $s(R)$ is smallest. $\;\blacksquare$

3.8.2 Transitive closure and the connectivity relation #

The transitive closure is subtler: adding shortcuts for existing two-step paths may create new two-step paths, which need their own shortcuts, and so on. The correct construction gathers all finite walks.

Definition 3.20. The transitive closure of $R$ is denoted $t(R)$ or $R^{+}$, and the reflexive–transitive closure (or connectivity relation) is $R^{*}=\Delta_A\cup R^{+}=\bigcup_{k\ge0}R^{k}$.

Theorem 3.21 (transitive-closure formula). For any relation $R$ on a set $A$,

$$t(R)=\bigcup_{k\ge1}R^{k}=R\cup R^{2}\cup R^{3}\cup\cdots .$$

That is, $R^{+}:=\bigcup_{k\ge1}R^{k}$ is transitive, contains $R$, and is contained in every transitive relation containing $R$.

Proof. Write $R^{+}=\bigcup_{k\ge1}R^{k}$. We verify the three defining properties.

(i) $R\subseteq R^{+}$. Immediate, since $R=R^{1}$ is one of the terms of the union.

(ii) $R^{+}$ is transitive. Suppose $(a,b)\in R^{+}$ and $(b,c)\in R^{+}$. Then $(a,b)\in R^{i}$ for some $i\ge1$ and $(b,c)\in R^{j}$ for some $j\ge1$. By Lemma 3.18 there is a walk of length $i$ from $a$ to $b$ and a walk of length $j$ from $b$ to $c$; concatenating them (the first ends where the second begins) yields a walk of length $i+j$ from $a$ to $c$. By Lemma 3.18 again, $(a,c)\in R^{\,i+j} \subseteq R^{+}$. Hence $R^{+}$ is transitive.

(iii) Minimality. Let $T$ be any transitive relation with $R\subseteq T$. We show $R^{k}\subseteq T$ for all $k\ge1$ by induction. Base: $R^{1}=R\subseteq T$. Step: assume $R^{k}\subseteq T$. Take $(a,b)\in R^{k+1}=R\circ R^{k}$; then there is $c$ with $(a,c)\in R^{k}$ and $(c,b)\in R$. By the induction hypothesis $(a,c)\in T$, and $(c,b)\in R\subseteq T$; transitivity of $T$ gives $(a,b)\in T$. Thus $R^{k+1}\subseteq T$. By induction $R^{k}\subseteq T$ for every $k$, so $R^{+}=\bigcup_{k\ge1}R^{k}\subseteq T$.

By (i)–(iii), $R^{+}$ is a transitive relation containing $R$ and contained in every such relation; hence it is the smallest one, i.e. $t(R)=R^{+}$. $\;\blacksquare$

On an infinite set the union may be genuinely infinite (think of the successor relation $n\mapsto n+1$ on $\mathbb{N}$, whose transitive closure is $<$). On a finite set, however, the union stops early.

Theorem 3.22 (termination on a finite set). If $|A|=n$, then

$$t(R)=\bigcup_{k=1}^{n}R^{k}=R\cup R^{2}\cup\cdots\cup R^{n}.$$

Proof. Since $t(R)=\bigcup_{k\ge1}R^{k}$ by Theorem 3.21, it suffices to prove that every $R^{k}$ with $k>n$ is already contained in $\bigcup_{i=1}^{n}R^{i}$; the inclusion $\bigcup_{i=1}^{n}R^{i}\subseteq t(R)$ is clear. So suppose $(a,b)\in R^{k}$ for some $k$. Among all lengths $\ell\ge1$ for which $(a,b)\in R^{\ell}$, choose the minimum such $\ell$; by Lemma 3.18 there is a walk

$$a=x_0,\,x_1,\,\dots,\,x_\ell=b,\qquad (x_{t-1},x_t)\in R.$$

We claim $\ell\le n$. Suppose not, so $\ell\ge n+1$; then the walk lists $\ell+1\ge n+2$ vertices $x_0,\dots,x_\ell$, all drawn from the $n$-element set $A$. By the pigeonhole principle two of them coincide: $x_s=x_r$ for some $0\le s<r\le \ell$. Excise the loop between positions $s$ and $r$ to obtain the shorter sequence

$$a=x_0,\dots,x_s\;(=x_r),\,x_{r+1},\dots,x_\ell=b.$$