Relations and Functions - Core Definitions

Relations and functions are fundamental constructs in set theory, providing the mathematical framework for describing relationships between objects. In ZFC, all mathematical concepts, including relations and functions, are ultimately defined in terms of sets.

DefinitionOrdered Pair

An ordered pair $(a, b)$ is a mathematical object where order matters. The defining property is that $(a, b) = (c, d)$ if and only if $a = c$ and $b = d$ . In set theory, we use the Kuratowski definition:

(a, b) := \{\{a\}, \{a, b\}\}

This definition satisfies the required property and constructs ordered pairs purely from sets.

The Kuratowski construction is elegant and minimal. Notice that if $a = b$ , then $(a, a) = \{\{a\}, \{a, a\}\} = \{\{a\}\}$ , and we can still recover both coordinates. The first coordinate is the element that appears in every set in the ordered pair, and the second coordinate is any element that appears.

DefinitionCartesian Product

The Cartesian product of sets $A$ and $B$ , denoted $A \times B$ , is the set of all ordered pairs with first coordinate from $A$ and second coordinate from $B$ :

A \times B = \{(a, b) : a \in A \land b \in B\}

By the axioms of pairing, union, and comprehension applied to $\mathcal{P}(\mathcal{P}(A \cup B))$ , this set exists in ZFC.

ExampleSmall Cartesian Products

Consider $A = \{1, 2\}$ and $B = \{x, y\}$ . Then:

A \times B = \{(1, x), (1, y), (2, x), (2, y)\}

If either set is empty, the product is empty: $A \times \emptyset = \emptyset$ for any set $A$ . The cardinality satisfies $|A \times B| = |A| \cdot |B|$ when both sets are finite.

DefinitionBinary Relation

A binary relation $R$ from a set $A$ to a set $B$ is a subset of the Cartesian product: $R \subseteq A \times B$ . We write $aRb$ or $(a, b) \in R$ to denote that $a$ is related to $b$ under $R$ .

The domain of $R$ is $\text{dom}(R) = \{a \in A : \exists b \in B((a, b) \in R)\}$ .

The range of $R$ is $\text{ran}(R) = \{b \in B : \exists a \in A((a, b) \in R)\}$ .

The field of $R$ is $\text{fld}(R) = \text{dom}(R) \cup \text{ran}(R)$ .

Relations provide a general framework for describing connections between objects. The relation "less than" on natural numbers is $\{(m, n) \in \omega \times \omega : m < n\}$ , which in set theory means $m \in n$ .

Remark

Relations are first-class objects in set theory—they are simply sets of ordered pairs. This allows us to manipulate relations using standard set-theoretic operations like union, intersection, and complementation. For instance, the inverse relation $R^{-1} = \{(b, a) : (a, b) \in R\}$ is also a set.

DefinitionFunction

A function (or mapping) $f$ from a set $A$ to a set $B$ , written $f: A \to B$ , is a relation $f \subseteq A \times B$ satisfying:

Total: For every $a \in A$ , there exists $b \in B$ such that $(a, b) \in f$
Single-valued: If $(a, b) \in f$ and $(a, c) \in f$ , then $b = c$

We write $f(a) = b$ when $(a, b) \in f$ . The set $A$ is called the domain of $f$ , and $B$ is called the codomain.

The function concept formalizes the intuitive idea of a rule that assigns to each input exactly one output. The totality condition ensures the function is defined everywhere on its domain, while the single-valued condition ensures uniqueness of outputs.

ExampleFunction Examples

The identity function on $A$ is $\text{id}_A = \{(a, a) : a \in A\}$
The constant function mapping everything to $c \in B$ is $\{(a, c) : a \in A\}$
The successor function on $\omega$ is $S = \{(n, n+1) : n \in \omega\}$
The characteristic function of $A \subseteq X$ is $\chi_A: X \to \{0, 1\}$ defined by:

\chi_A(x) = \begin{cases} 1 & \text{if } x \in A \\ 0 & \text{if } x \notin A \end{cases}

DefinitionImage and Preimage

Let $f: A \to B$ be a function.

The image of a set $X \subseteq A$ under $f$ is:

f[X] = \{f(x) : x \in X\} = \{b \in B : \exists x \in X(f(x) = b)\}

The preimage (or inverse image) of a set $Y \subseteq B$ under $f$ is:

f^{-1}[Y] = \{a \in A : f(a) \in Y\}

The image and preimage operations have useful properties. For instance, $f^{-1}[Y_1 \cup Y_2] = f^{-1}[Y_1] \cup f^{-1}[Y_2]$ and $f^{-1}[Y_1 \cap Y_2] = f^{-1}[Y_1] \cap f^{-1}[Y_2]$ , showing that preimage preserves all set operations.

Remark

In set theory, we distinguish between a function $f$ (a set of ordered pairs) and its action $f(a)$ (the unique $b$ such that $(a, b) \in f$ ). This distinction is sometimes blurred in informal mathematics, but it is important for foundational clarity. The notation $f^{-1}[Y]$ denotes preimage, which exists for any function, while $f^{-1}$ as a function only exists when $f$ is bijective.

Functions are the workhorses of mathematics, appearing in every area from analysis to algebra to topology. Understanding their set-theoretic foundation clarifies many subtle points and enables rigorous treatment of infinite function spaces and transfinite constructions.