# 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\).