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\}. \]
- 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).
Students enlisted for courses at a university is a relation on the set of students and the set of courses. For example, \[\{(\text{Anna, Math}), (\text{Anna, Chem}), (\text{Niels, Math}), (\text{Niels, Lit})\} \] is the graph of a relation on the domain \(\{\text{Anna, Niels}\}\) and the codomain \(\{\text{Math, Chem, Lit}\}\).
- 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)
- 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.