# 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 **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} $$ ![Relation matrix on a small set: the entry in row $i$, column $j$ is $1$ exactly when $i$ is related to $j$](img/l03_rel_matrix.png) For the "strictly less than" relation on $\{1,2,3,4\}$: | $x \backslash y$ | 1 | 2 | 3 | 4 | |---|---|---|---|---| | **1** | 0 | 1 | 1 | 1 | | **2** | 0 | 0 | 1 | 1 | | **3** | 0 | 0 | 0 | 1 | | **4** | 0 | 0 | 0 | 0 | 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. ![A relation drawn as a digraph: one node per element, an arrow $a\to b$ for each pair $(a,b)\in R$, and a self-loop for a pair $(a,a)$](img/l03_rel_digraph.png) ![The strict order "less than" on {1,2,3,4} as a digraph: an arrow from every smaller number to every larger one, with no self-loops](img/l03_less_digraph.png) 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\}$: | $x \backslash y$ | 1 | 2 | 3 | 4 | |---|---|---|---|---| | **1** | 0 | 0 | 1 | 1 | | **2** | 1 | 0 | 1 | 1 | | **3** | 0 | 0 | 0 | 0 | | **4** | 0 | 0 | 0 | 0 | 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 | $x \backslash y$ | 1 | 2 | 3 | 4 | |---|---|---|---|---| | **1** | 0 | 1 | 1 | 0 | | **2** | 1 | 0 | 0 | 0 | | **3** | 1 | 0 | 0 | 0 | | **4** | 0 | 0 | 0 | 0 | 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 **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. ![Composition $S\circ R$ chains two relations through a middle set $B$: follow an arrow $A\to B$ then $B\to C$ to obtain a pair in $A\to C$](img/l03_composition.png) **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 **Definition 3.25 (equivalence relation).** A relation on $A$ that is > simultaneously **reflexive**, **symmetric** and **transitive** is an > **equivalence relation**. We usually write it $\sim$ (or $\equiv$) and read > $a\sim b$ as "$a$ is equivalent to $b$". Equivalence relations formalise "being the same *for our present purposes*": having the same remainder on division by $n$, the same colour, the same connected component, the same last digit, the same value under some measurement. They are the tool by which we deliberately *forget* irrelevant distinctions. > **Definition 3.26 (equivalence class).** For $a\in A$, the **equivalence class** > of $a$ is $[a]=\{x\in A\mid x\sim a\}$ — everything equivalent to $a$. Any > $b\in[a]$ is called a **representative** of the class. We also need the companion notion from Lecture 2. > **Definition 3.27 (partition).** A **partition** of a set $A$ is a collection > $\mathcal{P}$ of subsets (the **blocks** or **cells**) of $A$ such that > (i) every block is **nonempty**; (ii) distinct blocks are **disjoint**; and > (iii) the blocks **cover** $A$, i.e. $\bigcup\mathcal{P}=A$. ![The equivalence classes of a set are nonempty, pairwise disjoint, and together cover it — exactly a partition into blocks](img/l03_eq_classes.png) ### 3.9.1 The Fundamental Theorem of Equivalence Relations We first isolate the two facts on which everything hinges. > **Lemma 3.28.** Let $\sim$ be an equivalence relation on $A$. For all > $a,b\in A$, $\;a\sim b \iff [a]=[b]$. *Proof.* ($\Rightarrow$) Suppose $a\sim b$. We show $[a]\subseteq[b]$: if $x\in[a]$ then $x\sim a$; combined with $a\sim b$, transitivity gives $x\sim b$, so $x\in[b]$. By symmetry $a\sim b$ also gives $b\sim a$, and the same argument yields $[b]\subseteq[a]$. Hence $[a]=[b]$. ($\Leftarrow$) Suppose $[a]=[b]$. By reflexivity $a\sim a$, so $a\in[a]=[b]$, which means $a\sim b$. $\;\blacksquare$ > **Lemma 3.29 (classes are equal or disjoint).** Let $\sim$ be an equivalence > relation on $A$. For all $a,b\in A$, either $[a]=[b]$ or $[a]\cap[b]=\varnothing$. *Proof.* Suppose the classes are **not** disjoint; we show they are equal. Pick $c\in[a]\cap[b]$. Then $c\sim a$ and $c\sim b$. By symmetry $a\sim c$, and with $c\sim b$ transitivity gives $a\sim b$; Lemma 3.28 then yields $[a]=[b]$. So whenever the classes meet they coincide, which is exactly the stated dichotomy. $\;\blacksquare$ > **Theorem 3.30 (Fundamental Theorem of Equivalence Relations).** Let $A$ be a > nonempty set. > 1. If $\sim$ is an equivalence relation on $A$, then the set of equivalence > classes $A/{\sim}=\{[a]\mid a\in A\}$ is a **partition** of $A$. > 2. Conversely, if $\mathcal{P}$ is a partition of $A$, then the relation > $\sim_{\mathcal{P}}$ defined by > $$ a\sim_{\mathcal{P}}b \iff a,b \text{ lie in the same block of }\mathcal{P} $$ > is an **equivalence relation** on $A$, and its equivalence classes are exactly > the blocks of $\mathcal{P}$. > 3. The two constructions are mutually inverse: they set up a **bijection** > between equivalence relations on $A$ and partitions of $A$. *Proof of (1).* We check the three conditions of Definition 3.27 for $A/{\sim}$. - *Nonempty blocks.* By reflexivity $a\sim a$, so $a\in[a]$; hence no class is empty. - *Cover.* Each class $[a]\subseteq A$, and every element $a$ lies in the class $[a]$, so $\bigcup_{a\in A}[a]=A$. - *Disjointness.* Two distinct classes are disjoint by Lemma 3.29 (if they intersected they would be equal, not distinct). Thus the distinct classes form a partition of $A$. $\;\blacksquare$ *Proof of (2).* Write $a\sim b$ for $a\sim_{\mathcal P}b$. Because the blocks of $\mathcal{P}$ cover $A$ and are pairwise disjoint, **every** $a\in A$ lies in **exactly one** block; call it $B(a)$. Then by definition $a\sim b\iff B(a)=B(b)$. - *Reflexive:* $B(a)=B(a)$, so $a\sim a$. - *Symmetric:* $B(a)=B(b)\Rightarrow B(b)=B(a)$, so $a\sim b\Rightarrow b\sim a$. - *Transitive:* $B(a)=B(b)$ and $B(b)=B(c)$ give $B(a)=B(c)$, so $a\sim b, b\sim c\Rightarrow a\sim c$. Hence $\sim$ is an equivalence relation. Its class of $a$ is $[a]=\{x\mid B(x)=B(a)\}=B(a)$, the block containing $a$. So the equivalence classes are precisely the blocks of $\mathcal{P}$. $\;\blacksquare$ *Proof of (3).* Start from an equivalence relation $\sim$, form the partition $A/{\sim}$, then form its "same-block" relation. Two elements share a block iff they lie in the same class, i.e. iff $[a]=[b]$, iff (Lemma 3.28) $a\sim b$; so we recover $\sim$. Conversely, start from a partition $\mathcal{P}$, form $\sim_{\mathcal P}$, then take its classes; by part (2) these are exactly the blocks of $\mathcal{P}$, so we recover $\mathcal{P}$. The two constructions are therefore inverse to each other, establishing the bijection. $\;\blacksquare$ **Remark (why this matters).** Theorem 3.30 says that "equivalence relation" and "partition" are two *languages for the same phenomenon*. Whenever you sort objects into non-overlapping categories that between them cover everything, you have — like it or not — defined an equivalence relation, and vice versa. This is why the theorem is invoked all over mathematics and CS: connected components of a graph, congruence classes of integers, types in a type system, disjoint-set (union–find) data structures, and — in **Lecture 13** — the decomposition of a sample space into mutually exclusive, exhaustive events on which probabilities are summed. The set of classes $A/{\sim}$ is called the **quotient set** of $A$ by $\sim$, and $B_n:=|\{\text{partitions of an }n\text{-set}\}|$ (equivalently, the number of equivalence relations on it) is the **Bell number**; $B_1,B_2,B_3,B_4=1,2,5,15$. **Worked example 3.31 (three views of one equivalence relation).** On $A=\{0,1,2,3,4,5\}$ define $a\sim b\iff 3\mid(a-b)$ ("congruent modulo $3$"). It is reflexive ($3\mid0$), symmetric ($3\mid(a-b)\Rightarrow3\mid(b-a)$) and transitive (if $3\mid(a-b)$ and $3\mid(b-c)$ then $3\mid(a-c)$), hence an equivalence relation. Its classes are $$ [0]=\{0,3\},\quad [1]=\{1,4\},\quad [2]=\{2,5\}, $$ giving the partition $\bigl\{\{0,3\},\{1,4\},\{2,5\}\bigr\}$ of $A$. Conversely, starting from *this* partition and declaring two numbers equivalent when they share a block returns exactly $\equiv\pmod 3$ — the round trip promised by Theorem 3.30(3). ### 3.9.2 Application: congruence classes and modular arithmetic Fix an integer $n\ge1$. On the *whole* set $\mathbb{Z}$ define $$ a\equiv b\pmod n \iff n\mid (a-b). $$ > **Theorem 3.32.** Congruence modulo $n$ is an equivalence relation on > $\mathbb{Z}$ with exactly $n$ classes, namely the **residue classes** > $[0],[1],\dots,[n-1]$, where $[r]=\{r+kn\mid k\in\mathbb{Z}\}$. *Proof.* **Reflexive:** $n\mid(a-a)=0$. **Symmetric:** if $a-b=kn$ then $b-a=(-k)n$, so $n\mid(b-a)$. **Transitive:** if $a-b=kn$ and $b-c=\ell n$ then $a-c=(k+\ell)n$, so $n\mid(a-c)$. Hence $\equiv\pmod n$ is an equivalence relation. By the division algorithm every integer $a$ can be written $a=qn+r$ with a unique remainder $r\in\{0,1,\dots,n-1\}$; then $a-r=qn$, so $a\equiv r$ and $a\in[r]$. Thus the classes $[0],\dots,[n-1]$ cover $\mathbb{Z}$. They are distinct because if $0\le r **Theorem 3.33 (arithmetic is well-defined mod $n$).** If $a\equiv a'\pmod n$ and > $b\equiv b'\pmod n$, then $a+b\equiv a'+b'\pmod n$ and $ab\equiv a'b'\pmod n$. *Proof.* Write $a'=a+ns$ and $b'=b+nt$ for integers $s,t$. Then $$ a'+b'=(a+b)+n(s+t), $$ so $n\mid\bigl((a'+b')-(a+b)\bigr)$, i.e. $a+b\equiv a'+b'$. And $$ a'b'=(a+ns)(b+nt)=ab+n\,(at+bs+nst), $$ so $n\mid(a'b'-ab)$, i.e. $ab\equiv a'b'$. $\;\blacksquare$ Consequently the definitions $[a]+[b]:=[a+b]$ and $[a]\cdot[b]:=[ab]$ do not depend on which representatives $a,b$ we pick — the operations are **well-defined** on $\mathbb{Z}_n$, turning it into a finite arithmetic system. **Common pitfall (well-definedness is not automatic).** Not every formula on representatives descends to classes. On $\mathbb{Z}_3$ the "operation" $[a]\mapsto[2^{a}]$ is **ill-defined**: $0\equiv3\pmod3$ but $2^{0}=1$ while $2^{3}=8\equiv2\pmod3$, so the answer depends on the representative. Theorem 3.33 is a genuine theorem, not a triviality, precisely because such failures are possible. **CS connections.** Modular arithmetic is the arithmetic of finite machines and is everywhere in computing: hash functions and hash tables ($h(k)=k\bmod m$), checksums and cyclic redundancy checks, pseudo-random generators, cyclic buffers (indices mod capacity), clock arithmetic, and the public-key cryptosystem **RSA**, whose security rests on modular exponentiation. All of these silently rely on the fact that congruence classes form a well-behaved arithmetic (Theorems 3.32–3.33). ## 3.10 Partial orders, Hasse diagrams, and a first look at lattices > **Definition 3.34 (partial order, poset).** A relation $\preceq$ on $A$ that is > **reflexive**, **antisymmetric** and **transitive** is a **partial order**. The > pair $(A,\preceq)$ is a **partially ordered set** (**poset**). We write $a\prec b$ > for "$a\preceq b$ and $a\ne b$" (the associated **strict** order). Partial orders model **ranking with possible incomparabilities**: precedence of tasks, refinement of specifications, subset containment, divisibility, information order. Compare with equivalence relations: swap *symmetry* for *antisymmetry* and the character changes completely — from "grouping equals" to "ordering unequals". ### 3.10.1 Comparability and total orders > **Definition 3.35.** In a poset $(A,\preceq)$, elements $a,b$ are **comparable** > if $a\preceq b$ or $b\preceq a$; otherwise they are **incomparable** (written > $a\parallel b$). If **every** pair is comparable, $\preceq$ is a **total** (or > **linear**) **order**, and $(A,\preceq)$ is a **chain**. Examples: $\le$ on $\mathbb{Z}$, $\mathbb{Q}$ or $\mathbb{R}$ is total; alphabetical/lexicographic order on strings is total; but subset order and divisibility are only partial. **Worked example 3.36 (divisibility is a partial order).** Divisibility $a\mid b$ on $D=\{1,2,3,4,6,12\}$ (the positive divisors of $12$) is a partial order: $a\mid a$ (reflexive); for positive integers $a\mid b$ and $b\mid a$ force $a=b$ (antisymmetric); and $a\mid b$, $b\mid c$ give $a\mid c$ (transitive). It is only *partial*: $2\mid3$ and $3\mid2$ both fail, so $2\parallel3$; likewise $4\parallel6$. ### 3.10.2 Hasse diagrams Drawing every arrow of a partial order is wasteful: reflexive loops and transitivity-forced edges clutter the picture. A **Hasse diagram** strips it to essentials. > **Definition 3.37 (cover; Hasse diagram).** In a poset, $b$ **covers** $a$ > (written $a\lessdot b$) if $a\prec b$ and there is **no** $c$ with $a\prec c\prec b$. > The **Hasse diagram** draws one node per element and one line for each covering > pair, placing the *smaller* element **lower**; direction is read off the vertical > position, so no arrowheads are needed. Reflexive loops and transitively implied > edges are omitted. **Worked example 3.38 (Hasse diagram of $(D,\mid)$).** For $D=\{1,2,3,4,6,12\}$ the covering pairs are $$ 1\lessdot2,\quad 1\lessdot3,\quad 2\lessdot4,\quad 2\lessdot6,\quad 3\lessdot6,\quad 4\lessdot12,\quad 6\lessdot12, $$ (e.g. $1\lessdot4$ is **not** a cover because $1\prec2\prec4$, and $3\lessdot12$ is not a cover because $3\prec6\prec12$). An ASCII sketch (with $1$ at the bottom and $12$ at the top): ``` 12 / \ 4 6 | / \ 2 -/ 3 | / 1 ---/ ``` ![Hasse diagram of the divisors of $12$ ordered by divisibility: $1$ at the bottom, $12$ at the top, with an upward line for each covering pair](img/l03_hasse.png) Here the seven line-segments realise the seven covers above: $12$ sits over $4$ and $6$; $4$ over $2$; $6$ over both $2$ and $3$; and $1$ under both $2$ and $3$. All other relationships (such as $1\mid12$ or $2\mid12$) are recovered by following lines *upward* and using transitivity. ### 3.10.3 Minimal, maximal, least and greatest elements Let $(A,\preceq)$ be a poset and $S\subseteq A$. > **Definition 3.39.** > - $m\in S$ is a **minimal** element of $S$ if no $x\in S$ satisfies $x\prec m$ > (nothing in $S$ lies *strictly below* $m$). > - $m\in S$ is a **maximal** element of $S$ if no $x\in S$ satisfies $m\prec x$. > - $\ell\in S$ is the **least** (or **minimum**) element if $\ell\preceq x$ for > **every** $x\in S$. > - $g\in S$ is the **greatest** (or **maximum**) element if $x\preceq g$ for > **every** $x\in S$. **Common pitfall (minimal $\ne$ least).** *Minimal* means "nothing below it"; *least* means "below everything". A poset may have several minimal elements and no least element. In $(D,\mid)$ the whole set has least element $1$ and greatest element $12$; but the *subset* $\{2,3,4,6\}$ has **two** minimal elements ($2$ and $3$) and no least element, and two maximal elements ($4$ and $6$) with no greatest. > **Theorem 3.40 (uniqueness).** A subset $S$ of a poset has **at most one** least > element and at most one greatest element. *Proof.* Suppose $\ell,\ell'$ are both least elements of $S$. Since $\ell$ is least and $\ell'\in S$, $\ell\preceq\ell'$. Since $\ell'$ is least and $\ell\in S$, $\ell'\preceq\ell$. Antisymmetry gives $\ell=\ell'$. The greatest-element case is dual (reverse every $\preceq$). $\;\blacksquare$ Because of Theorem 3.40 we may speak of *the* least element $\min S$ and *the* greatest element $\max S$ when they exist. > **Theorem 3.41 (least $\Rightarrow$ unique minimal).** If $S$ has a least element > $\ell$, then $\ell$ is the **unique** minimal element of $S$. *Proof.* First, $\ell$ is minimal: if $x\in S$ and $x\preceq\ell$, then $\ell\preceq x$ (as $\ell$ is least), so antisymmetry gives $x=\ell$; hence no element is strictly below $\ell$. Now let $m$ be any minimal element of $S$. Since $\ell$ is least, $\ell\preceq m$. If $\ell\ne m$ then $\ell\prec m$ with $\ell\in S$, contradicting the minimality of $m$. Therefore $m=\ell$, so $\ell$ is the only minimal element. $\;\blacksquare$ > **Theorem 3.42 (finite posets have extremal elements).** Every finite nonempty > poset $(A,\preceq)$ has at least one minimal element and at least one maximal > element. *Proof (minimal; maximal is dual).* Note $\prec$ is irreflexive ($a\prec a$ would require $a\ne a$). Pick any $a_0\in A$. If $a_0$ is minimal, stop. Otherwise choose $a_1\prec a_0$; if $a_1$ is minimal, stop; otherwise choose $a_2\prec a_1$, and so on, generating $a_0\succ a_1\succ a_2\succ\cdots$. These elements are pairwise distinct: if $a_i=a_j$ with $i **Definition 3.43.** Let $S\subseteq A$ in a poset $(A,\preceq)$. An element > $u\in A$ is an **upper bound** of $S$ if $s\preceq u$ for all $s\in S$; a > **lower bound** $\ell$ satisfies $\ell\preceq s$ for all $s\in S$. The **least > upper bound** (**supremum**, **join**), if it exists, is the least element of the > set of upper bounds, written $\sup S$; for two elements it is $a\vee b$. Dually the > **greatest lower bound** (**infimum**, **meet**) is $\inf S$, written $a\wedge b$. By Theorem 3.40, joins and meets are unique when they exist. > **Definition 3.44 (lattice).** A poset $(A,\preceq)$ is a **lattice** if every > pair of elements $a,b$ has both a join $a\vee b$ and a meet $a\wedge b$. **Example 3.45 (three familiar lattices).** - **Power set** $(\mathcal{P}(U),\subseteq)$: here $A\vee B=A\cup B$ and $A\wedge B=A\cap B$ (Lecture 2's operations are literally join and meet). Its Hasse diagram for $U=\{a,b\}$ is the diamond ``` {a,b} / \ {a} {b} \ / ∅ ``` - **Divisibility** $(\mathbb{Z}^{+},\mid)$: $a\vee b=\operatorname{lcm}(a,b)$ and $a\wedge b=\gcd(a,b)$. The poset $(D,\mid)$ of Example 3.38 is a finite lattice; e.g. $4\vee6=\operatorname{lcm}(4,6)=12$ and $4\wedge6=\gcd(4,6)=2$. - **Total orders** are lattices with $a\vee b=\max(a,b)$ and $a\wedge b=\min(a,b)$. **Example 3.46 (a poset that is *not* a lattice).** Take $A=\{a,b,c,d\}$ with $a\prec c,\ a\prec d,\ b\prec c,\ b\prec d$ and $c\parallel d$, $a\parallel b$ (a "crown"). ASCII (the two middle segments cross at $\times$): ``` c d | \ / | | × | | / \ | a b ``` The pair $\{a,b\}$ has upper bounds $c$ and $d$, but $c\parallel d$, so there is no *least* upper bound; $a\vee b$ does not exist and $A$ is not a lattice. (Dually, $\{c,d\}$ has no meet.) **Remark (forward pointer).** A lattice that is also **bounded** (has a least element $0$ and greatest element $1$), **distributive**, and **complemented** is a **Boolean algebra** — the algebraic skeleton of propositional logic and digital circuits. The power-set lattice $(\mathcal{P}(U),\subseteq)$ is the prototype. We return to Boolean algebra in a later lecture; for now, note how the set operations of Lecture 2 already exhibit the lattice structure in miniature. ## 3.11 $n$-ary relations and the relational database model > **Definition 3.47 ($n$-ary relation).** An **$n$-ary relation** is a subset > $R\subseteq A_1\times A_2\times\cdots\times A_n$; its elements are $n$-tuples. > Binary relations are the case $n=2$, and the Cartesian product itself is the > universal $n$-ary relation. ![A database table is an $n$-ary relation: each row is a tuple, each column an attribute with its own domain](img/l03_db_table.png) **Motivating example (students · subjects · marks).** Let $$ \text{STUDENTS}=\{\text{Shevchenko},\text{Franko},\text{Kosach}\}, $$ $$ \text{SUBJECTS}=\{\text{Discrete Math},\text{Algebra},\text{Programming}\}, $$ $$ \text{MARKS}=\{A,B,C,D,E,F,Fx\}. $$ An examination record is a ternary relation $R\subseteq\text{STUDENTS}\times\text{SUBJECTS}\times\text{MARKS}$, e.g. $$ R=\{(\text{Shevchenko},\text{Programming},B),\ (\text{Kosach},\text{Algebra},A),\ (\text{Franko},\text{Discrete Math},E)\}. $$ This is exactly a database **table**: each tuple is a **row (record)**, each factor $A_i$ is a **column (attribute)** with its own domain, and $n$ is the number of columns (the table's **arity**). | STUDENT | SUBJECT | MARK | |---|---|---| | Shevchenko | Programming | B | | Kosach | Algebra | A | | Franko | Discrete Math | E | **Remark (a set has no duplicates and no order).** Because a relation is a *set* of tuples, a table in this idealised model has no duplicate rows and no inherent row order — mirroring the mathematical fact that $\{x,x\}=\{x\}$ and that sets are unordered. Real SQL tables relax this (bags, not sets), but the theory is set-based. ### 3.11.1 Relational algebra Since relations are sets, the operations of Lecture 2 apply between two relations of the **same shape** (same sequence of attribute domains): **union** $R\cup S$, **intersection** $R\cap S$, and **difference** $R\setminus S$. Adding a few relation-specific operators yields **relational algebra**, the theory underlying SQL, introduced by E. F. Codd in 1970. - **Selection** $\sigma_{\varphi}(R)$ — keep the rows (tuples) satisfying a condition $\varphi$; $\sigma$ chooses a *subset of the tuples*. (SQL `WHERE`.) - **Projection** $\pi_{i_1,\dots,i_k}(R)$ — keep only certain columns, discarding the others (and any duplicate rows that result); $\pi$ chooses a subset of the *attributes*. (SQL `SELECT` of specific columns.) - **Cartesian product** $R\times S$ — pair every row of $R$ with every row of $S$ (the same product as in §3.2). - **Natural join** $R\bowtie S$ — combine rows of $R$ and $S$ that **agree on their shared attribute(s)**; a filtered, matched Cartesian product. It is the workhorse that reconnects data split across tables. **Worked example 3.48 (projection, selection, join).** Let | ENROLL: STUDENT | COURSE | |---|---| | Kosach | Algebra | | Kosach | DM | | Franko | DM | and | OFFER: COURSE | ROOM | |---|---| | Algebra | 101 | | DM | 205 | Then $\pi_{\text{STUDENT}}(\text{ENROLL})=\{\text{Kosach},\text{Franko}\}$ (the duplicate Kosach collapses); $\sigma_{\text{COURSE}=\text{DM}}(\text{ENROLL})$ keeps the two DM rows; and the natural join on COURSE is | ENROLL ⋈ OFFER: STUDENT | COURSE | ROOM | |---|---|---| | Kosach | Algebra | 101 | | Kosach | DM | 205 | | Franko | DM | 205 | each enrolment matched to the room where its course is offered. So the abstract notion of an $n$-ary relation is not merely theory: it is the data model every relational database implements, and the humble set operations of Lecture 2 are its computational core. ## 3.12 Functions as a special kind of relation > **Definition 3.49 (functional relation; function).** A relation > $F\subseteq A\times B$ is **functional** (single-valued) if each $x\in A$ relates > to **at most one** $y\in B$: whenever $(x,y)\in F$ and $(x,y')\in F$, then $y=y'$. > If in addition every $x\in A$ relates to **exactly one** $y$, then $F$ is a > **total function** $f:A\to B$, and we write $y=f(x)$ in place of $(x,y)\in F$. Thus a function *is* a relation — one obeying the single-valuedness condition. Its **domain** is its set of inputs and its **range** is the set of attained outputs — the very domain/range of §3.4. Functions may be **injective** (distinct inputs give distinct outputs), **surjective** (every element of $B$ is attained), or **bijective** (both) — the properties we have just defined, which recur throughout the course (for example in counting and in graph isomorphism). **Common pitfall (which relations fail to be functions).** On $\{1,2,3\}$ the relation $\{(1,2),(1,3)\}$ is **not** a function: the input $1$ has two outputs, so single-valuedness fails. The relation $\{(1,2),(2,2)\}$ *is* a (partial) function even though two inputs share the output $2$ — single-valuedness restricts *outputs per input*, not *inputs per output*. And a *total* function additionally forbids the input $3$ from having no output at all. **Remark.** Reading a function as its **graph** $\{(x,f(x))\}\subseteq A\times B$ is not a mere formality: it is how functions are defined rigorously in set theory, and how they are stored (as key–value tables) in computing. ## Historical note The set-theoretic viewpoint on relations grew out of **Georg Cantor's** creation of set theory in the 1870s–1880s. The now-standard encoding of the ordered pair, $(a,b)=\{\{a\},\{a,b\}\}$, is due to **Kazimierz Kuratowski** (1921) and is what lets relations be defined purely as sets (Lecture 2). Modular arithmetic — our flagship equivalence relation — was placed on a firm footing by **Carl Friedrich Gauss** in the *Disquisitiones Arithmeticae* (1801), which introduced the congruence notation $a\equiv b\pmod n$. The systematic theory of order and lattices was developed by **Richard Dedekind** around 1900 (his *Dualgruppen*) and brought to maturity by **Garrett Birkhoff**, whose *Lattice Theory* (1940) is the classic reference; the diagrams are named after **Helmut Hasse**. The transitive-closure algorithm of §3.8 is due to **Stephen Warshall** (1962). Finally, the entire $n$-ary story found its most consequential application when **Edgar F. ("Ted") Codd** of IBM published *A Relational Model of Data for Large Shared Data Banks* (Communications of the ACM, 1970), founding the relational database — arguably the single most commercially important application of discrete mathematics. ## Chapter summary - A **relation** is a subset of a Cartesian product; a **binary relation** is $R\subseteq A\times B$, with $(a,b)\in R$ written $aRb$. Specify it **by listing** or **by a predicate**; represent it as a **set of pairs**, a **Boolean matrix**, or a **digraph**. The **identity relation** $\Delta_A$ and the universal/empty relations are the reference points. - **Domain** and **range** collect the first and second components that occur. - Core **properties** — reflexive, irreflexive, symmetric, antisymmetric, asymmetric, transitive (and the rarer antitransitive) — each have a matrix fingerprint and an algebraic form: $\Delta_A\subseteq R$; $R=R^{-1}$; $R\cap R^{-1}\subseteq\Delta_A$; $R^{2}\subseteq R$ (Theorem 3.9). Counting relations with a property is combinatorics (Proposition 3.10). - **Inverse** $R^{-1}$ transposes the matrix / reverses arrows. **Composition** $S\circ R$ chains relations and equals the **Boolean matrix product** $M_R\odot M_S$ (Theorem 3.15); composition is **associative** (Theorem 3.17), so powers $R^{k}$ are well-defined and count **walks of length $k$** (Lemma 3.18). - **Closures** add the fewest pairs to gain a property: $r(R)=R\cup\Delta_A$, $s(R)=R\cup R^{-1}$, and $t(R)=\bigcup_{k\ge1}R^{k}$ (Theorem 3.21), a **finite** union $\bigcup_{k=1}^{n}R^{k}$ on an $n$-element set (Theorem 3.22, via pigeonhole); Warshall's algorithm computes it in $O(n^{3})$. - **Equivalence relations** (reflexive + symmetric + transitive) correspond exactly to **partitions** via the **Fundamental Theorem** (Theorem 3.30), proved in both directions. The prototype is **congruence mod $n$**, whose classes support well-defined modular arithmetic (Theorems 3.32–3.33). - **Partial orders** (reflexive + antisymmetric + transitive) are drawn as **Hasse diagrams**. Distinguish **minimal/maximal** from **least/greatest**: least/greatest are unique when they exist (Theorem 3.40) and finite posets always have extremal elements (Theorem 3.42). Adding **joins** and **meets** for every pair gives a **lattice**; power sets and divisibility are the standard examples. - **$n$-ary relations** are precisely the **tables** of the relational database model, manipulated by **relational algebra** (selection, projection, product, natural join). A **function** is the special case of a single-valued relation. ## Exercises ### Warm-up **W1.** Let $A=\{1,2,3,4\}$ and $R=\{(1,1),(1,2),(2,3),(3,4),(4,4)\}$. (a) Write the relation matrix. (b) Give $\operatorname{dom}(R)$ and $\operatorname{ran}(R)$. (c) Decide whether $R$ is reflexive, symmetric, antisymmetric, transitive. **W2.** For the $R$ of W1, compute $R^{-1}$ as a set of pairs and give its matrix. How is $M_{R^{-1}}$ related to $M_R$? **W3.** On $\{a,b,c\}$ let $R=\{(a,b),(b,c),(a,c)\}$ and $S=\{(b,a),(c,b)\}$. Compute $S\circ R$ and $R\circ S$. Are they equal? **W4.** For each relation on $\{1,2,3\}$ decide which of reflexive / symmetric / antisymmetric / transitive it has: (a) $\varnothing$; (b) $A\times A$; (c) $\Delta_A=\{(1,1),(2,2),(3,3)\}$. **W5.** List the equivalence classes of congruence modulo $4$ on $\{0,1,\dots,11\}$, and write the induced partition. **W6.** For $R=\{(1,2),(2,1),(2,3)\}$ on $\{1,2,3\}$ give the reflexive closure $r(R)$ and the symmetric closure $s(R)$. ### Standard **S7.** Let $R=\{(1,2),(2,3),(3,4),(4,1)\}$ on $\{1,2,3,4\}$. Compute $R^{2},R^{3},R^{4}$ and hence $t(R)$. Is $t(R)$ the universal relation? Explain using Theorem 3.22 why you need not compute beyond $R^{4}$. **S8.** On $\mathbb{Z}$ define $a\sim b\iff a$ and $b$ have the same parity (both even or both odd). Prove $\sim$ is an equivalence relation and describe its classes as a partition of $\mathbb{Z}$. **S9.** Consider divisibility on $D_{24}=\{1,2,3,4,6,8,12,24\}$. (a) State why it is a poset. (b) List all covering pairs and describe the Hasse diagram. (c) Identify the least, greatest, minimal and maximal elements. (d) Is $(D_{24},\mid)$ a lattice? Compute $8\vee12$ and $8\wedge12$. **S10.** On an $n$-element set, count (a) all relations, (b) reflexive relations, (c) symmetric relations, (d) relations that are both reflexive and symmetric. Evaluate each for $n=3$. **S11.** Let $M_R=\begin{pmatrix}1&0&1\\0&1&0\\1&0&0\end{pmatrix}$ on $\{1,2,3\}$. Use the Boolean matrix product to compute $M_{R^{2}}$ and list $R^{2}$. Is $R$ transitive? Justify via Theorem 3.9(4). **S12.** Prove that if $R$ and $S$ are transitive relations on $A$, then $R\cap S$ is transitive. Then give a concrete example on $\{1,2,3\}$ of two transitive relations whose **union** is not transitive. **S13.** The partition $\{\{1,4\},\{2\},\{3,5\}\}$ of $\{1,2,3,4,5\}$ induces an equivalence relation $\sim$. List all pairs of $\sim$ and state $|{\sim}|$. **S14.** With ENROLL and OFFER as in Example 3.48, write out (a) $\sigma_{\text{STUDENT}=\text{Kosach}}(\text{ENROLL})$, (b) $\pi_{\text{COURSE}}(\text{ENROLL})$, and (c) the natural join $\text{ENROLL}\bowtie\text{OFFER}$, explaining in one sentence what each result represents. ### Challenge **C15.** Prove that composition distributes over union: $T\circ(R\cup S)=(T\circ R)\cup(T\circ S)$ for relations of compatible shapes. Show also that $T\circ(R\cap S)\subseteq(T\circ R)\cap(T\circ S)$, and give an example where the inclusion is **strict**. **C16 (equivalence closure).** (a) Prove that the intersection of any nonempty family $\{E_i\}_{i\in I}$ of equivalence relations on $A$ is again an equivalence relation. (b) Deduce that for any relation $R$ on $A$ there is a **smallest** equivalence relation $e(R)$ containing $R$. (c) Prove that $e(R)=t\bigl(R\cup R^{-1}\cup\Delta_A\bigr)$. **C17.** Let $(A,\preceq)$ be a poset. (a) Prove that if $A$ is finite and nonempty then it has a maximal element. (b) Prove that if a **finite** poset has a **unique** maximal element, that element is the greatest. (c) Give an **infinite** poset with a unique maximal element that is *not* greatest. **C18.** (a) Prove that the number of symmetric relations on an $n$-set is $2^{\,n(n+1)/2}$ and the number of antisymmetric relations is $2^{\,n}3^{\,\binom{n}{2}}$. (b) How many relations are **both** symmetric and antisymmetric? Identify them explicitly. (c) Explain why the count of **equivalence** relations is the Bell number $B_n$, and compute $B_4$. ## Selected answers & hints **W1.** (a) Rows/cols indexed $1,2,3,4$: | $x\backslash y$ | 1 | 2 | 3 | 4 | |---|---|---|---|---| | **1** | 1 | 1 | 0 | 0 | | **2** | 0 | 0 | 1 | 0 | | **3** | 0 | 0 | 0 | 1 | | **4** | 0 | 0 | 0 | 1 | (b) $\operatorname{dom}(R)=\{1,2,3,4\}$, $\operatorname{ran}(R)=\{1,2,3,4\}$. (c) Not reflexive ($(2,2),(3,3)\notin R$); not symmetric ($(1,2)\in R$, $(2,1)\notin R$); antisymmetric (no off-diagonal mirror pair); not transitive ($(1,2),(2,3)\in R$ but $(1,3)\notin R$). **W3.** $S\circ R$ ("$R$ then $S$"): $a\to b\to a$ gives $(a,a)$; $b\to c\to b$ gives $(b,b)$; $a\to c\to b$ gives $(a,b)$. So $S\circ R=\{(a,a),(b,b),(a,b)\}$. $R\circ S$ ("$S$ then $R$"): $b\to a\to b$, $b\to a\to c$, $c\to b\to c$ give $\{(b,b),(b,c),(c,c)\}$. They are **not** equal — composition is not commutative. **W5.** $[0]=\{0,4,8\}$, $[1]=\{1,5,9\}$, $[2]=\{2,6,10\}$, $[3]=\{3,7,11\}$; partition $\bigl\{\{0,4,8\},\{1,5,9\},\{2,6,10\},\{3,7,11\}\bigr\}$. **S7.** $R^{2}=\{(1,3),(2,4),(3,1),(4,2)\}$, $R^{3}=\{(1,4),(2,1),(3,2),(4,3)\}$, $R^{4}=\Delta_A=\{(1,1),(2,2),(3,3),(4,4)\}$. Their union with $R$ is all $16$ pairs, so $t(R)=A\times A$, the **universal** relation. Since $|A|=4$, Theorem 3.22 guarantees $t(R)=\bigcup_{k=1}^{4}R^{k}$, so no higher power is needed (indeed $R^{5}=R$). **S8.** *Reflexive:* $a$ has the same parity as itself. *Symmetric:* if $a,b$ share parity then so do $b,a$. *Transitive:* if $a,b$ share parity and $b,c$ share parity, then $a,c$ share parity (parity is a two-valued attribute). Classes: the evens $[0]=2\mathbb{Z}$ and the odds $[1]=2\mathbb{Z}+1$; partition $\{2\mathbb{Z},\,2\mathbb{Z}+1\}$. (This is congruence mod $2$, a special case of Theorem 3.32.) **S10.** (a) $2^{n^{2}}$; (b) $2^{\,n^{2}-n}$; (c) $2^{\,n(n+1)/2}$; (d) $2^{\,\binom{n}{2}}=2^{\,n(n-1)/2}$. For $n=3$: $512,\ 64,\ 64,\ 8$ respectively. **S12.** If $(a,b),(b,c)\in R\cap S$ then both pairs lie in $R$ (so $(a,c)\in R$ by transitivity of $R$) and both lie in $S$ (so $(a,c)\in S$); hence $(a,c)\in R\cap S$. Counterexample for union: $R=\{(1,2)\}$ and $S=\{(2,3)\}$ are each transitive (no composable pairs within either), but $R\cup S=\{(1,2),(2,3)\}$ lacks $(1,3)$ and is not transitive. **C16.** *Hints.* (a) Reflexivity: each $E_i\supseteq\Delta_A$, so $\bigcap_i E_i\supseteq\Delta_A$. Symmetry and transitivity: if a pair (or two composable pairs) lie in the intersection, they lie in **every** $E_i$, which is symmetric/transitive, so the required consequence lies in every $E_i$, hence in the intersection. (b) Apply (a) to the family of **all** equivalence relations containing $R$ (nonempty, since $A\times A$ is one); their intersection is the smallest such, namely $e(R)$. (c) Show $Q:=t(R\cup R^{-1}\cup\Delta_A)$ is an equivalence relation containing $R$ (reflexive since $\Delta_A\subseteq$ it, symmetric because $R\cup R^{-1}\cup\Delta_A$ is symmetric and transitive closure preserves symmetry, transitive by construction), so $e(R)\subseteq Q$; conversely any equivalence relation $E\supseteq R$ contains $R^{-1}$ (symmetry), $\Delta_A$ (reflexivity) and all their walks (transitivity), so $Q\subseteq E$, giving $Q\subseteq e(R)$. **C17.** *Hints.* (a) Mirror Theorem 3.42 with ascending chains. (b) In a finite poset every element lies below some maximal element (ascend a chain until it stops); if the maximal element is unique, every element lies below **it**, so it is greatest. (c) Take $A=\{u\}\cup\{1,2,3,\dots\}$ with the usual order on the positive integers (ascending forever, no maximum) and $u$ incomparable to all of them: $u$ is the unique maximal element but $u\not\succeq1$, so $u$ is not greatest. ## Further reading - Kenneth H. Rosen, *Discrete Mathematics and Its Applications*, 8th ed., Chapter 9 ("Relations"): §9.1 relations and their properties, §9.3 representing relations, §9.4 closures (Warshall's algorithm), §9.5 equivalence relations, §9.6 partial orderings and lattices. - Susanna S. Epp, *Discrete Mathematics with Applications*, 5th ed., Chapter 8 ("Relations"): reflexivity/symmetry/transitivity, equivalence relations and partitions, partial-order relations. - E. F. Codd, "A Relational Model of Data for Large Shared Data Banks", *Communications of the ACM* 13(6), 1970 — the origin of the relational database connection in §3.11. - (For the order-theory strand) Garrett Birkhoff, *Lattice Theory*, American Mathematical Society — the classic reference behind §3.10.4.