Relations
In the previous readings, we explored the mathematical formalism of sets. Sets allow us to model collections of data. However, we frequently wish to capture relevant relationships in our data. Structured data is called as such because the data in the collection is related in some way. For example:
- An element precedes another element in a list.
- A person is friends with another person in a social network.
- One number is a divisor of another number.
To model structured data, we need some way of modeling these relationships between individual datum. In this chapter, we use sets to develop the theory of relations which will allow us to formally reason about these relationships.
Definitions and Notation
Intuitively, a relation relates two objects by some property as defined by the relation. To capture this correspondence we combine pairs with sets:
Definition (Relation): A relation \(R\) over a universe \(U\) is a subset of pairs of elements drawn from \(U\), i.e., \(R \in \mathcal{P}(U \times U)\).
Suppose we have a relation \(R\). An element of \(R\), \((a, b) \in R\) denotes that \(a\) and \(b\) are related by \(R\), which we can express in several different ways:
| Notation | Form |
|---|---|
| \((a, b) \in R\) | Set notation |
| \(R(a, b)\) | Function notation |
| \(a \; R \; b\) | Infix notation |
For example, let our universe \(U = \{\, \text{"Mary"}, \text{"Miguel"}, \text{"Li"}, \text{"Lana"} \,\}\). Then we can define a relation \(\mathsf{owes} : U ×\times U\) that captures whether one person owes another money. With this relation, the following expressions:
- \((\text{"Miguel"}, \text{"Li"}) \in \mathsf{owes}\).
- \(\mathsf{owes}(\text{"Miguel"}, \text{"Li"})\).
- \(\text{"Miguel"} \mathsf{owes} \text{"Li"}\).
All posit that Miguel owes Li money.
Note that because the order of a pair matters, these expressions do not automatically assert that Li owes Miguel money. We would need to include this fact separately: \((\text{"Li"}, \text{"Miguel"}) \in \mathsf{owes}\).
Operations Over Relations
Because we define relations in terms of sets, we can define our fundamental operations over relations using set-theoretic notation.
Domain and Range
First, we can project out the left-hand and right-hand elements of a relation, typically called the domain and range, respectively.
Definition (Domain): Let \(R\) be a relation. Define the domain of \(R\), written \(\mathrm{dom}(R)\), as:
\[ \mathrm{dom}(R) = \{\, x \mid \exists y \ldotp (x, y) \in R \,\}. \]
Definition (Range): Let \(R\) be a relation. Define the range of \(R\) as:
\[ \mathrm{range}(R) = \{\, y \mid \exists x \ldotp (x, y) \in R \,\}. \]
Alternatively, the range may also be called the codomain of the relation.
Example (Cardinality). Frequently, we may want to have the domain and range of a relation come from disparate sets \(S\) and \(T\). This is no problem for our definition of relation; we can simply define the universe to be the union of \(S\) and \(T\). Then our pairs are drawn from this union where the domain is always an element of \(S\) and the range is always an element of \(T\).
In this case, we can define a relation between sets \(S\) and natural numbers \(n\) where \(n\) is the number of elements in \(S\). We commonly call this the cardinality of a set. This is normally written \(|S| = n\), but to align with our relation notation, we can write \(\mathsf{card}(S, n)\) to denote this fact. For example:
- \((\{\, 1, 2, 3 \,\}, 3) \in \mathsf{card}\).
- \((\{\, a \,\}, 10) \notin \mathsf{card}\).
- \((\emptyset, 0) \in \mathsf{card}\).
Lifted Operations
Because relations are sets, we can lift any binary operation over sets to relations. As examples, let \(R\) and \(S\) be two relations. Then define the following lifted operations over sets to relations as:
\[\begin{align} R \cup S &= \{\, (a, b) \mid (a, b) \in R \vee (a, b) \in S \,\} \\ R \cap S &= \{\, (a, b) \mid (a, b) \in R \wedge (a, b) \in S \,\} \\ \overline{R} &= \{\, (a, b) \mid (a, b) \notin R \,\} \end{align}\]
Example (Relational Union): as a practical example of applying set-theoretic operations to relations, consider using relations to map items in a store to their stock, i.e., a relation whose domain is (abstract) objects and the codomain is natural numbers. We might have two different stores, with their own separate stocks of disparate items:
- \(R_1 = \{\, (a, 2), (b, 0), (c, 3) \,\}\).
- \(R_2 = \{\, (d, 1), (e, 5), (f, 0) \,\}\).
Then \(R_1 \cup R_2\) might represent joining together the stocks into a single store:
- \(R_1 \cup R_2 = \{\, (a, 2), (b, 0), (c, 3), (d, 1), (e, 5), (f, 0) \,\}\).
Transformations
Beyond lifted operations, we can also define several fundamental transformations over relations.
Definition (Inverse): Let \(R\) be a relation. Define the inverse of \(R\), written \(R^{-1}\), as:
\[ R^{-1} = \{\, (b, a) \mid (a, b) \in R \,\} \]
Definition (Composition): Let \(R\) and \(S\) be relations. Define the
composition of \(R\) and \(S\), written \(S
\circ R\) (LaTeX: \circ) as:
\[ S \circ R = \{\, (a, c) \mid (a, b) \in R, (b, c) \in S \,\} \]
Note that with composition that we “run the relation” from right-to-left, first through \(R\) and then through \(S\).
Definition (Image): Let \(R\) be a relation. Define the image of an element \(a\), written \(R(a)\), as:
\[ R(a) = \{\, b \mid (a, b) ∈ R \,\} \]
This final transformation is particularly useful when talking about functions which (we will discover shortly) are a special case of relations. In particular, note that if we have a function \(f\), then both the definition and notation of image coincides with “run the function”, \(f(x)\).
Function-like Relations
Functions form the heart of computation within mathematics. Consider the following partially specified relation:
\[ R_1 = \{\, (0, 1), (1, 2), (2, 3), (3, 4), \ldots \,\} \]
From inspection, you would rightfully conclude that \(R\) relates a natural number to the number one greater than it, i.e., \(R\) is the increment function. We can see that the left-hand element of a pair represents an input to the function and the right-hand element of a pair is its corresponding output.
Based on this example, it may feel like functions and relations are the same. However, not all relations are functions. For example, consider the following relation:
\[ R_2 = \{\, (0, 1), (0, 2), (0, 3) \,\}. \]
If we think of \(R_2\) as a function, what is the result of \(R_2(0)\)? It appears there are three choices—\(1\), \(2\), and \(3\)! This does not align with our intuition about how a function works where a single input to a function should generate a single output.
In actuality, functions can be thought of as a special case of relations. In this reading, we’ll develop the definitions necessary to classify certain relations as functions. These definitions will help us understand better the nature of functions as well as leverage the functions-as-relations view in our own mathematical models.
(Note: unlike our previous readings, this reading is light on exposition. You should employ the strategies we’ve discussed in the course to understand and internalize these definitions. Create small example sets that exhibit each of these definitions and try to understand the essence of the definitions by generalizing the structure of the examples.)
Totality and Uniqueness
The two main properties that separate functions from other relations are totality and uniqueness. Because functions distinguish between inputs and outputs in a non-symmetric fashion, totality and uniqueness can apply either to the inputs of the function (the “left”) or the outputs of the function (the “right”).
Totality
Totality concerns whether all the elements in the universe of some relation appear in the relation.
Definition (left totality): a relation \(R\) is left-total if all elements are related by \(R\) on the left
\[ \forall x \ldotp \exists y \ldotp (x, y) \in R. \]
Definition (right totality): a relation \(R\) is right-total if all elements are related by \(R\) on the right:
\[ \forall y \ldotp \exists x \ldotp (x, y) \in R. \]
Uniqueness
Uniqueness concerns whether an element is related to a single other element. The way that we express this property formally is that if an element is mapped to two elements, those two elements are in fact the same.
Definition (left-unique): a relation \(R\) is left-unique if every element in the relation on the left-hand side is mapped to a unique element right.
\[ \forall x, y, z \ldotp (x, y) \in R \rightarrow (z, y) \in R \rightarrow x = z. \]
Definition (right-unique): a relation \(R\) is right-unique if every element in the relation on the right-hand side is mapped to a unique element on the left.
\[ \forall x, y, z \ldotp (x, y) \in R \rightarrow (x, z) \in R \rightarrow y = z. \]
Refinements of Relations
With totality and uniqueness defined, we can define particular refinements relations in terms of these properties.
Definition (partial function): a relation is a partial function if it is right-unique.
Definition (function): a relation is a function if it is both right-unique and left-total.
To better distinguish from partial functions, we also call right-unique and left-total relations total functions. Note that a total function is one that is well-defined, i.e., “has an answer” every possible input. In contrast, a partial function may be undefined on some inputs; this corresponds to the non-existence of a pair mentioning the undefined element on the left-hand side.
Definition (injectivity): a relation is an injective function if it is a function (right-unique and left-total) as well as left-unique.
Definition (surjectivity): A relation is a surjective function if it is a function (right-unique and left-total) as well as right-total.
Definition (bijection): A relation is a bijection if it is a function (right-unique and left-total) as well as injective and surjective (left-unique and right-total).
Reading Exercise (Definitions, ‡)
Consider the following relation \(R\) over \(U = \{\, a, b, c, d, e \,\}\):
\[ R = \{\, (a, c), (b, c), (c, c), (d, c), (e, c) \,\}. \]
Does the relation fulfill each of the given properties? If so, you can simply say “yes”. If not, give a single sentence explaining why not.
- Left-total
- Right-total
- Left-unique
- Right-unique
- Partial function
- Function
- Injective function
- Surjective function
- Bijection
Equivalences
There are a number of special kinds of relations that are ubiquitous in mathematics. We have already studied functions-as-relations. Now we will explore another common kind of relation, the equivalence, which captures the notion of equality between objects in a universe.
Like functions, equivalences are a refinement of relations. In particular, a relation that enjoys these three properties, reflexivity, symmetry, and transitivity, is considered an equivalence.
Definition (Reflexivity): a relation \(R\) is reflexive if it relates every element in the universe to itself.
\[ \forall x \ldotp (x, x) \in R \]
Definition (Symmetry): a relation \(R\) is symmetric if any pair of related elements are also related “in the opposite direction.”
\[ \forall x, y \ldotp (x, y) \in R \rightarrow (y, x) \in R \]
Definition (Transitivity): a relation \(R\) is transitive if whenever any pair of elements are related with a common element in the middle, the first and last elements are also related.
\[ \forall x, y, z \ldotp (x, y) \in R \rightarrow (y, z) \in R \rightarrow (x, z) \in R \]
These three concepts form the definition of an equivalence relation.
Definition (Equivalence): a relation an equivalence if it is reflexive, symmetric, and transitive.
The standard equality relation \((=)\) over the natural numbers \(ℕ\) is an equivalence relation as it fulfills all three properties of an equivalence:
- Reflexive
- Identical numbers are considered equal.
- Symmetric
- Order doesn’t matter when asserting equality between numbers.
- Transitive
- When declaring \(x = y\) and \(y = z\), we know that these two facts establish that \(x\) and \(y\) are the same number and \(z\) and \(y\) are the same number. From this, we can conclude that \(x\) and \(z\) must also be the same number.
Proving Equivalences
To formally show that a relation is an equivalence, we must show that it obeys each of the three properties of an equivalence. We show the outline of such a proof using the following real-world example, arithmetic expressions, e.g., \(3 + 5\) or \(3 \cdot (2 - 1)\).
Let \((\equiv)\) be the following relation:
\[ (\equiv) = \{\, (e_1, e_2) \mid \text{\( e_1 \) and \( e_2 \) are arithmetic expressions that evaluate to the same value \( v \)} \,\} \]
Claim: \((\equiv)\) is an equivalence relation.
To show that \((\equiv)\) is an equivalence relation, we must show that it is reflexive, symmetric, and transitive.
Proof. \((\equiv)\) is a reflexive, symmetric, and transitive relation:
- Reflexive
- Because an arithmetic expression evaluates to a unique value, it must be the case that \(\forall e \ldotp e \equiv e\)
- Symmetric
- Let \(e_1, e_2 \in U\) and assume that \(e_1 \equiv e_2\). By the definition of \((\equiv)\), since the pair of expressions is related, they must evaluate to the same value \(v\). Because of this fact and the definition of \((\equiv)\), we know that the pair is related in the other direction, i.e., \(e_2 \equiv e_1\).
- Transitive
- Let \(e_1, e_2, e_3 \in U\) and assume that \(e_1 \equiv e_2\) and \(e_2 \equiv e_3\). By the definition of \(R\), this means that \(e_1\) and \(e_2\) evaluate to the same value, call it \(v_1\) and \(e_2\) and \(e_3\) evaluate evaluate to the same value, call it \(v_2\). However, we know that an arithmetic expression evaluates to a unique value, so it must be the case that \(v_1\) and \(v_2\) are identical since they are both the result from evaluating \(e_2\). This means that \(e_1 \equiv e_3\) as well.
Equivalence Closures
The closure of a set \(S\) under a property \(P\) is the (smallest) set \(S^* \subseteq S\) whose elements all satisfy \(P\). The concept of closure lifts to relations in the expected way. For example, let \(U = \{\, 0, \ldotp, 10 \,\}\) and \(P\) be the property of symmetry \(\forall x, y \ldotp (x, y) \in R \rightarrow (y, x) \in R\), then if \(R\) is the relation:
\[ R = \{\, (0, 3), (2, 5), (6, 9), (5, 2) \,\}, \]
Then the symmetric closure of \(R\) is the relation \(R^*\):
\[ S = \{\, (0, 3), (3, 0), (2, 5), (5, 2), (6, 9), (9, 6) \,\}. \]
We can compute the closure of any relation under a property by repeatedly applying the property to generate new pairs to add to the relation until we can no longer add new pairs.
We can apply the notion of closure to all the properties of an equivalence relation simultaneously to form an equivalence closure of a set of elements. Intuitively, the equivalence closure of a set of elements captures all the different equalities induced by the properties of equivalences.
For example, consider an artificial set \(S = \{\, a, b, c \,\}\) and suppose we know that some relation \(R\) relates the elements as follows:
\[ (a, b) \in R, (b, c) \in R. \]
If we furthermore know that \(R\) ought to be an equivalence relation, then we can compute the equivalence closure of \(R\) as follows:
- The reflexive closure of the relation relates every element to itself: \((a, a), (b, b), (c, c) \in R\).
- The symmetric closure of the relation relates every pair “in the other direction”: \((b, a), (c, b) \in R\).
- The transitive closure of the relation connects every transitive pair of elements: \((a, c) \in R\).
- Finally, we also have to consider the symmetric closure again for this new pair: \((c, a) \in R\).
In this particular case, the equivalence closure of \(R\) is all nine possible pairs of \(S\) with itself, i.e., \(S × S\). This case captures the intuition that the two original equalities are sufficient to deduce that all the elements of \(S\) are equal.
Exercise (Closure, ‡): Consider the following relation \(R\) over universe \(\mathcal{U} = \,\{ a, b, c, d, e, f \,\}\):
\[ R = \{\, (a, b), (c, e), (d, b), (f, e) \,\}. \]
Compute the equivalence closure of \(R\).
Equivalence Classes
Intuitively, an equivalence relation captures some notion of equality between objects. We can then think about grouping together sets of mutually equal objects. For example, let’s return to arithmetic expressions. The following expressions are all equivalent to each other:
- \(10\).
- \(5 + 5\).
- \(2 \times (2 + 3)\).
Because they all evaluate to \(10\). Consider creating a set of such expressions, call it \(S_4\) with the property that they all evaluate to \(4\):
\[ S_4 = \{\, e \mid \text{ \( e \) is an arithmetic expression that evaluates to \( 4 \)} \,\}. \]
Any pair of expressions within \(S_4\) are equivalent to each other. We call such a set an equivalence class.
Definition (Equivalence Classes): an equivalence class of an equivalence relation \(R\) over universe \(U\) is a set \(S\) of elements drawn from \(U\) that are pairwise equivalent according to \(R\), i.e.,
\[ \forall x, y \in S \ldotp (x, y) \in R. \]
Recall that \(x \mod y\) is the whole-number remainder of \(x \div y\). Because of the nature of division, the result of \(x \mod y\) takes on the values \(0, \ldots, y-1\). Because of this, we can consider, e.g., the equivalences classes induced by taking a number and modding it by 3. \(x \mod 3\) takes on three values, \(0\), \(1\), and \(2\), and thus, \(\mod 3\) induces three equivalence classes:
- \(E_1 = \{\, 0, 3, 6, 9, \ldots \,\}\).
- \(E_2 = \{\, 1, 4, 7, 10, \ldots \,\}\).
- \(E_3 = \{\, 2, 5, 8, 11, \ldots \,\}\).
In the context of the modulus operator, we can say that any pair of numbers in an equivalence class are equivalent modulo 3, e.g., \(4\) and \(11\) are equivalent modulo \(3\).