A relation begins with a simple construction from set theory: the Cartesian product. Given sets \(A\) and \(B\), their Cartesian product is the set of every possible ordered pair
\[ A\times B=\{(a,b):a\in A,\ b\in B\}. \]
For example, let
\[ A=\{1,2\},\qquad B=\{3,4\}. \]
Pairing each element of \(A\) with each element of \(B\) gives
\[ A\times B=\{(1,3),(1,4),(2,3),(2,4)\}. \]
The same Cartesian product can be read as a table. Each ordered pair is one row, while the position in the pair determines the column:
| \(A\) | \(B\) |
|---|---|
| \(1\) | \(3\) |
| \(1\) | \(4\) |
| \(2\) | \(3\) |
| \(2\) | \(4\) |
A Relation Selects Rows
A relation from \(A\) to \(B\) is a subset of this Cartesian product:
\[ R\subseteq A\times B. \]
The Cartesian product lists every pair that is possible. A relation selects the pairs for which a particular relationship actually holds. For example,
\[ R=\{(1,3),(2,4)\} \]
is a relation from \(A\) to \(B\). In the table interpretation, \(R\) consists of only two of the four possible rows:
| \(A\) | \(B\) |
|---|---|
| \(1\) | \(3\) |
| \(2\) | \(4\) |
Thus a relation is a mathematically precise way to say which elements of \(A\) are related to which elements of \(B\). The word relation refers to this chosen set of pairs, not to all of \(A\times B\).
Relations as Database Tables
This viewpoint is familiar from relational databases. Suppose a table has the columns last_name, first_name, and age. Let \(L\) be the set of possible last names, \(F\) the set of possible first names, and \(G\) the set of permitted ages. Then
\[ L\times F\times G \]
contains every possible row of that shape. The database does not contain this entire Cartesian product. Its actual table is a relation \(D\subseteq L\times F\times G\), containing only the rows that are stored. For example:
| Last name | First name | Age |
|---|---|---|
| Müller | Klaus | \(56\) |
This row represents the ordered triple \((\text{Müller},\text{Klaus},56)\). A database relation may involve any finite number of columns; the two-set case \(R\subseteq A\times B\) is the simplest form of the same idea.
Reading and Notation
If \((a,b)\in R\), we often write
\[ a\,R\,b. \]
If \((a,b)\notin R\), we write \(a\not R b\).
Domain, Codomain, Image
For \(R\subseteq A\times B\):
\[ \operatorname{dom}(R):=\{a\in A:\exists b\in B,(a,b)\in R\}, \]
\[ \operatorname{im}(R):=\{b\in B:\exists a\in A,(a,b)\in R\}. \]
The codomain is \(B\), while \(\operatorname{im}(R)\subseteq B\) is the actual set of reached values. These must not be confused: the codomain contains every permitted second component, whereas the image contains only those second components that actually occur in \(R\).
Inverse and Composition of Relations
Inverse Relation
The inverse relation \(R^{-1}\subseteq B\times A\) is
\[ R^{-1}:=\{(b,a):(a,b)\in R\}. \]
It flips every pair. An inverse relation always exists, but it need not be an inverse function: if several elements of \(A\) are related to the same element of \(B\), then \(R^{-1}\) relates that element to several outputs.
Composition
If \(R\subseteq A\times B\) and \(S\subseteq B\times C\), then
\[ S\circ R:=\{(a,c):\exists b\in B, (a,b)\in R\land(b,c)\in S\}. \]
Composition connects two relation steps into one.
Relations on One Set
If \(R\subseteq A\times A\), then \(R\) is a relation on \(A\). Important properties are:
- Reflexive: \(\forall a\in A: aRa\).
- Symmetric: \(aRb\Rightarrow bRa\).
- Antisymmetric: \(aRb\land bRa\Rightarrow a=b\).
- Transitive: \(aRb\land bRc\Rightarrow aRc\).
- Total (connex): \(\forall a,b\in A: aRb\lor bRa\).
Two Important Classes
Equivalence Relations
A relation that is reflexive, symmetric, and transitive is an equivalence relation.
Example on integers:
\[ a\equiv b\pmod m \iff m\mid(a-b). \]
Here \(\equiv\) is the relation operator: \(a\equiv b\pmod m\) reads "\(a\) is congruent to \(b\) modulo \(m\)." The symbol \(\mid\) on the right expresses divisibility and states that \(m\) divides \(a-b\). This relation is central in modulo arithmetic.
Order Relations
A relation that is reflexive, antisymmetric, and transitive is a partial order.
If it is also total, it is a total order. On \(\mathbb{R}\), \(\le\) is a total order.
From Relations to Functions
A function is a special relation. A mapping \(f:A\to B\) specifies how each element of \(A\) is assigned to an element of \(B\). Its graph is the relation
\[ \{(x,f(x)):x\in A\}\subseteq A\times B. \]
In the table interpretation, the first column contains \(x\), and the second contains \(f(x)\). For example, let \(A=\{-2,-1,0,1,2\}\) and define \(f:A\to\{0,1,4\}\) by \(f(x)=x^2\).
| \(x\) | \(f(x)=x^2\) |
|---|---|
| \(-2\) | \(4\) |
| \(-1\) | \(1\) |
| \(0\) | \(0\) |
| \(1\) | \(1\) |
| \(2\) | \(4\) |
Its graph is the relation \(\{(-2,4),(-1,1),(0,0),(1,1),(2,4)\}\). Different inputs may have the same output, as \(-2\) and \(2\) do here. What matters is that each input has exactly one output. Not every relation has this property: a function table must satisfy two additional conditions:
- Existence: every \(x\in A\) occurs in a row.
- Uniqueness: every \(x\in A\) occurs with exactly one value \(f(x)\in B\).
A general relation may omit an element of \(A\), or it may relate one element of \(A\) to several elements of \(B\). The existence rule excludes the first possibility, and the uniqueness rule excludes the second. Thus one must check both conditions before treating a relation as a function.