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.

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.