Functions and Relations

Previously, 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:

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 different ways:

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.

Alternatively, the range may also be called the codomain of the relation.

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{array}{rl}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{array}$$

Transformations

Beyond lifted operations, we can also define several fundamental transformations over relations.

Note that with composition that we "run the relation" from right-to-left, first through $R$ and then through $S$.

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),\dots \}$$

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. Next, 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.

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.

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.

Refinements of Relations

With totality and uniqueness defined, we can define particular refinements relations in terms of these properties.

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.