# Relations

## Cartesian products

The Cartesian product of two sets $A$ and $B$ is the set of ordered pairs $(a,b)$ of elements $a \in A$ and $b \in B$: $A \times B \:\stackrel{\text{def.}}{=}\: \{(a,b) \colon a \in A, b \in B\}.$

Ex.
• The Cartesian product of $\{1,2\}$ and $\{\dagger, \ddagger\}$ has four elements:1)

$\{1,2\} \times \{\dagger, \ddagger\} = \{ (1, \dagger),(1, \ddagger),(2,\dagger),(2,\ddagger)\}.$

• The Cartesian product of the set of points on the real line and the set of points in the plane is the set of points in three-dimensional space:

$\mathbb R \times \mathbb R^2 = \mathbb R^3.$

## Relations

A relation (or binary relation) on two sets $A$ and $B$ is a subset $G$ of $A\times B$: $G = \{(a,b) \in A \times B \colon a \text{ satisfying some criteria}, b \text{ satisfying some criteria}\}$ The set $A$ is called the relation's domain, $B$ its codomain, and $G$ its graph. The graph of a relation can most easily be thought of as connections (edges) between 'points' in $A$ and $B$ (vertices).

Ex.
• Relations can be defined on product sets $A \times A$. For example, '$\leq$' is a relation on $\mathbb R \times \mathbb R$, whose graph is determined by $(a,b) \in G \quad\Longleftrightarrow\quad a \leq b.$

## Functions

A function (or mapping) is a relation with the property that for every $a$ in its domain there is a unique $b$ in its codomain such that $(a,b)$ is in the graph. $\forall\: a \in A \quad \exists !\: b \in B; \quad (a,b) \in G.$ To indicate this, one often writes $x, y$ and $X,Y$ instead of $a,b$ and $A, B$. Although functions are completely described by their graphs, it is common to use an extra letter, such as $f$, to express functional relations. One writes $f\colon X \to Y, \qquad x \mapsto f(x)$ or simply $y = f(x)$ to indicate the argument, $x$, and value, $y$, of a function.2)

Ex.
• The relation with graph $G = \{(x,y) \in \mathbb R \times \mathbb R \colon y = x^2\}$ defines a function $f: \mathbb R \to \mathbb R$, $x \mapsto x^2.$
• The length of a two-vector $| \cdot | \colon \mathbb R^2 \to [0,\infty), \qquad (x_1,x_2) \mapsto ( x_1^2 + x_2^2)^{1/2}$ is a function from the set of vectors in the plane to the set of non-negative real numbers.
1)
In general, $|A \times B| = |A||B|$ for finite sets.
2)
Note the difference between the function, written $f$, $f(\cdot)$, or $x \mapsto f(x)$, and its value, $f(x)$, at a particular point $x$.