Relations and Functions

Suppose that Selmer is taller than Kostas. Then Selmer stands in a certain relation to Kostas, and vice versa as well. What relation? The relation `taller than.' But how can such a relation be represented in austere, mathematical terms? The traditional answer, one that we will affirm, is to say that relations are to be defined in terms of set membership. For example, the relation `taller than,' given that we're talking about humans, can be defined as the set of all pairs of humans (x, y) such that x is taller than y. As another example, consider the relation `greater than,' where the domain in question is the set of natural numbers {0, 1, 2, 3, 4, }. In this case, the relation `greater than' can be identified with the set

$$\{ (x, y) \, \vert \, x > y \}$$

.

You will notice some new notation here: (x, y). This is how we denote an ordered pair. Ordered pairs are not the same thing as sets. The set $\{5, 2\} = \{2, 5\}$, but $(5, 2) \not= (2, 5)$. Two ordered pairs (a, b) and (c, d) are equal exactly when a = c and b = d.

Given the concept of ordered pairs, we can define the Cartesian product of two sets A and B, denoted A x B, to be the set of all ordered pairs (x, y) such that $x \in A$ and $y \in B$. For example, if A is {2, 4, 6}, and B is {3, 5, 7}, then $\{2, 4, 6\} \times \{3, 5, 7\}$ is

$$\{ (2, 3), (2, 5), (2, 7), (4, 3), (4, 5), (4, 7), (6, 3), (6, 5), (6, 7)\}.$$

Cartesian product can be extended to any number of sets. The n-fold Cartesian product $A_1 \times A_2 \times \ldots \times A_n$ is the set of all n-tuples $(a_1, \ldots, a_n)$, where $a_i \in A_i$, for i from 1 to n. The n-fold Cartesian product of A with itself, $A \times \ldots \times A$, is written Aⁿ. For example, N³ is the set of all 3-tuples (or triples) of natural numbers.

A binary relation on two sets A and B is a subset of A x B. For example, the ordinary less-than relation < is a binary relation on N; more formally, < is

$$\{(x, y) \, \vert \, x < y \mbox{ and } x, y \in \mbox{{\bf N}}\}.$$

An n-ary relation on sets $A_1, A_2, \ldots, A_n$ is a subset of $A_1 \times A_2 \times \ldots \times A_n$.

Chances are that if you're holding this book you've already been asked to deal with functions. If you were ever asked to do simple arithmetic (and of course you were, long ago), you were asked to deal with functions. Consider ordinary addition. Ordinary addition is a function from N x N to N (written $f : A \times A \rightarrow B$): you ``plug into" this function pairs of numbers, for example (3,4), and receive back individual numbers, in this case 7. Of course, we usually write this fact as 3 + 4 = 7.

Taling of ``plugging in" things to a function, as you can probably guess, is too informal. What, precisely, is a function? A function $f : A \rightarrow B$ associates each member of A with a unique member of B. To spell it out explicitly: A function $f : A \times A \rightarrow B$ is a subset of A x B such that if $(a, b) \in f$ and $(a, c) \in f$ as well, then b = c.

In a function f from A to B, A is the domain and B the range. For such a function, we follow usual notational practice and write f(a), where $a \in A$, to refer to the $b \in B$ such that $(a, b) \in f$.

There are certain kinds of functions worth isolating even at this early stage in our investigations. A function $f : A \rightarrow B$ is

• one-to-one or injective if and only if for every two elements a and a' in A where $a \not= a$, $f(a) \not= f(a')$.
• onto or surjective if and only if for every $b \in B$ there is an $a \in A$ such that f(a) = b.
• bijective iff (short for `if and only if') f is both injective and surjective.