Relations
Relations between sets, their properties, equivalence relations, partitions and functions
The topics of this chapter, and their order, follow the course calendar and Kameron Decker Harris’s Fall 2026 lecture notes on relations. These come from those notes:
- a relation from a set \(A\) to a set \(B\) as a subset of \(A \times B\), and a relation on a set \(A\) as a subset of \(A \times A\);
- the notation \(a \mathrel{R} b\) for \((a, b) \in R\);
- arrow diagrams, directed graphs and zero-one matrices as ways to draw a relation;
- reading reflexivity and symmetry from a matrix or a directed graph;
- the inverse of a relation, and the powers of a relation;
- the powers of a relation whose arrows go around a cycle, adapted here from a cycle of four elements to rock, paper, scissors;
- equivalence relations and equivalence classes;
- a function from \(A\) to \(B\) as a relation that relates each element of \(A\) to exactly one element of \(B\);
- the domain, codomain and range of a function;
- injective, surjective and bijective functions, the identity function, and the fact that a function has an inverse function exactly when it is bijective.
The definitions included from mds come from that site, and the definitions of an antisymmetric relation, the composition of relations and a partition follow the standard ones cited with them. The exercises, the other examples, the Racket functions and all the proofs are new.
1 Relations
2 Drawing relations
Example 5 (An arrow diagram of words and letters) Figure 1 is the arrow diagram (Definition 3) of the relation \(H\) of Example 1. Each of the five pairs of \(H\) is one arrow. Two arrows leave cat, and two arrive at o.
Example 6 (The directed graph of “beats”) Figure 2 is the directed graph (Definition 4) of the relation \(B\) of Example 4. Each element of \(G\) appears once, where an arrow diagram (Definition 3) of \(B\) would draw \(G\) twice, once in each column. Starting from any element and following the arrows leads around the triangle, and back to the start after three arrows.
3 Properties of relations
Example 8 (Words that share a letter) Let \(V = {\mathopen{}\left\{\text{cat}, \text{cow}, \text{dog}, \text{pig}\right\}\mathclose{}}\), and on \(V\) let \(a \mathrel{T} b\) when the words \(a\) and \(b\) have at least one letter in common (Remark 1). For example, \(\text{cat} \mathrel{T} \text{cow}\), since both have a c, and \(\text{cow} \mathrel{T} \text{dog}\), since both have an o, but \((\text{cat}, \text{dog}) \notin T\). Figure 3 is the directed graph (Definition 4) of \(T\). Each word has a letter in common with itself, so each point has an arrow that comes back to it.
4 Relations in Racket
5 Inverses and composition
Proof. (\(\Rightarrow\)) Suppose \(R\) is symmetric. We show \(R^{-1} = R\) by double inclusion (Theorem: Equal sets are subsets of each other).
- Let \((a, b) \in R^{-1}\). Then \((b, a) \in R\), by the definition of \(R^{-1}\). Since \(R\) is symmetric, \((a, b) \in R\). So \(R^{-1} \subseteq R\).
- Let \((a, b) \in R\). Since \(R\) is symmetric, \((b, a) \in R\), so \((a, b) \in R^{-1}\), by the definition of \(R^{-1}\). So \(R \subseteq R^{-1}\).
(\(\Leftarrow\)) Suppose \(R^{-1} = R\), and let \(a \mathrel{R} b\). Then \((b, a) \in R^{-1}\), by the definition of \(R^{-1}\), and \(R^{-1} = R\), so \(b \mathrel{R} a\). So \(R\) is symmetric.
Proof. (\(\Rightarrow\)) Suppose \(R\) is transitive, and let \((a, c) \in R^2 = R \circ R\). By the definition of composition (Definition 11), \(a \mathrel{R} b\) and \(b \mathrel{R} c\) for some \(b \in S\). Since \(R\) is transitive, \(a \mathrel{R} c\). So \(R^2 \subseteq R\) (Definition: Subset).
(\(\Leftarrow\)) Suppose \(R^2 \subseteq R\), and let \(a \mathrel{R} b\) and \(b \mathrel{R} c\). Then \((a, c) \in R \circ R = R^2\), by the definition of composition, so \((a, c) \in R\). So \(R\) is transitive.
6 Equivalence relations
Proof. The steps of Example 18 work for any function in place of \(\operatorname{len}\).
Reflexive. For each \(a \in A\), \(f(a) = f(a)\), so \(a \sim a\).
Symmetric. If \(a \sim a'\), then \(f(a) = f(a')\), so \(f(a') = f(a)\), and \(a' \sim a\).
Transitive. If \(a \sim a'\) and \(a' \sim a''\), then \(f(a) = f(a')\) and \(f(a') = f(a'')\), so \(f(a) = f(a'')\) (Theorem: Equalities are transitive), and \(a \sim a''\).
Proof. (\(\Leftarrow\)) Suppose \([a] = [b]\). Since \(\sim\) is reflexive, \(a \sim a\), so \(a \in [a]\). So \(a \in [b]\), which means \(a \sim b\).
(\(\Rightarrow\)) Suppose \(a \sim b\). We show \([a] = [b]\) by double inclusion (Theorem: Equal sets are subsets of each other).
- Let \(x \in [a]\), so \(x \sim a\). Since \(a \sim b\) and \(\sim\) is transitive, \(x \sim b\), so \(x \in [b]\). So \([a] \subseteq [b]\).
- Let \(x \in [b]\), so \(x \sim b\). Since \(\sim\) is symmetric, \(a \sim b\) gives \(b \sim a\), and then transitivity gives \(x \sim a\), so \(x \in [a]\). So \([b] \subseteq [a]\).
7 Partitions
Proof. Each class \([a]\) is a subset of \(S\), by Definition 14. We check the three conditions of Definition 15.
Nonempty. Since \(\sim\) is reflexive, \(a \sim a\), so \(a \in [a]\).
Different classes are disjoint. Let \([a]\) and \([b]\) be two classes that share an element \(x\). Then \(x \sim a\) and \(x \sim b\). Since \(\sim\) is symmetric, \(a \sim x\), and since \(\sim\) is transitive, \(a \sim b\). So \([a] = [b]\), by Theorem 4. So two different classes share no element.
Every element is in a class. Each \(a \in S\) is in its own class \([a]\), as in the first step.
Proof. Reflexive. Each \(a \in S\) is in some set in \(\mathcal{C}\), so \(a\) and \(a\) are in the same set, and \(a \sim a\).
Symmetric. If \(a\) and \(b\) are in the same set in \(\mathcal{C}\), then so are \(b\) and \(a\).
Transitive. Suppose \(a \sim b\) and \(b \sim c\): \(a\) and \(b\) are in a set \(X \in \mathcal{C}\), and \(b\) and \(c\) are in a set \(Y \in \mathcal{C}\). Then \(b \in X \cap Y\). Different sets in \(\mathcal{C}\) are disjoint, so \(X = Y\), and \(a\) and \(c\) are both in \(X\), so \(a \sim c\).
Each class is a set in \(\mathcal{C}\). Let \(a \in S\), and let \(X\) be the set in \(\mathcal{C}\) that holds \(a\). An element \(b\) has \(b \sim a\) exactly when \(b\) is in the set that holds \(a\), which is \(X\). So \([a] = X\).
Each set in \(\mathcal{C}\) is a class. Let \(X \in \mathcal{C}\). Since \(X\) is nonempty, it holds some element \(a\), and then \(X = [a]\), by the previous step.
8 Functions as relations
Proof. (\(\Rightarrow\)) Suppose \(R = {\mathopen{}\left\{(a, f(a)) : a \in A\right\}\mathclose{}}\) for a function \(f : A \to B\), and let \(a \in A\). Then \(a \mathrel{R} f(a)\). If also \(a \mathrel{R} b\), then \((a, b) = (a', f(a'))\) for some \(a' \in A\), so \(a' = a\) and \(b = f(a)\) (Definition: Ordered pair). So \(f(a)\) is the only element of \(B\) related to \(a\).
(\(\Leftarrow\)) Suppose each \(a \in A\) is related to exactly one element of \(B\), and let \(f(a)\) be that element. Then \(f\) assigns exactly one element of \(B\) to each \(a \in A\), so it is a function \(f : A \to B\). Its graph is \(R\), since \((a, b) \in R\) exactly when \(b\) is the element related to \(a\), which is \(f(a)\).
Two functions \(f, g : A \to B\) with the same graph \(R\) have \(f(a) = g(a)\) for every \(a \in A\), since each is the one element related to \(a\) by \(R\). So they are the same function.
9 Inverse functions and composition
Proof. (\(\Rightarrow\)) Suppose \(g : B \to A\) is an inverse function of \(f\).
Injective. If \(f(a) = f(a')\), then \(a = g(f(a)) = g(f(a')) = a'\).
Surjective. Each \(b \in B\) has \(b = f(g(b))\), so \(b\) is the value of \(f\) at \(g(b) \in A\).
(\(\Leftarrow\)) Suppose \(f\) is bijective, and let \(b \in B\). Since \(f\) is surjective, some \(a \in A\) has \(f(a) = b\), and since \(f\) is injective, only one \(a\) does. Let \(g(b)\) be that \(a\). Then \(g : B \to A\) is a function with \(f(g(b)) = b\) for every \(b \in B\). For \(a \in A\), \(g(f(a))\) is the one element \(a'\) with \(f(a') = f(a)\), which is \(a\) itself. So \(g\) is an inverse function of \(f\).
The graph of the inverse. In both cases, \(f(g(b)) = b\) for every \(b \in B\) and \(g(f(a)) = a\) for every \(a \in A\). Let \(a \in A\) and \(b \in B\). If \(g(b) = a\), then \(f(a) = f(g(b)) = b\). If \(f(a) = b\), then \(g(b) = g(f(a)) = a\). So \((b, a)\) is in the graph of \(g\) exactly when \((a, b)\) is in the graph of \(f\).
Proof. Let \(a \in A\) and \(c \in C\). By the definition of composition of relations, \((a, c) \in \Gamma_f \circ \Gamma_g\) exactly when some \(b \in B\) has \((a, b) \in \Gamma_g\) and \((b, c) \in \Gamma_f\), that is, \(b = g(a)\) and \(c = f(b)\). Only \(b = g(a)\) can work, so this holds exactly when \(c = f(g(a)) = (f \circ g)(a)\), which is when \((a, c) \in \Gamma_{f \circ g}\).