Functions

This post was translated from Korean by LLM (Kimi). The translation may contain errors or awkward sentences. The Korean original is the source of truth.

In previous posts, we defined binary relations. Under this definition, the binary relation \(<\) defined on the set of natural numbers \(\mathbb{N}\) is the set

\[{<}=\{(0,1),(0,2),\ldots, (1,2),(1,3),\ldots, \}\]

Following the notation of §Binary Relation, ⁋Definition 7, \({<}(1)\) is the collection of all \(n\in\mathbb{N}\) such that \((1,n)\in\mathbb{N}\), hence

\[{<}(1)=\{2,3,\ldots\}\]

Conversely, if the set \({<}(k)\) is given for every natural number \(k\), we can also recover the set \(<\).

The discussion above remains valid for a general binary relation \((R,A,B)\). Thus, given any binary relation \(R\), it can be thought of precisely as a rule assigning to each \(a\in A\) the set \(R(a)\). In this light, a function is a binary relation such that \(R(a)\) is a singleton set for every \(a\in A\).

Definition of a Function

Definition 1 For a nonempty set \(A\), a binary relation \(f=(F,A,B)\) is called a function if \(A=\pr_1F\) and for each \(x\in A\), the set \(F(\{x\})\) is a singleton set.¹

The condition \(A=\pr_1F\) means that every element \(x\) of \(A\) corresponds to at least one \(y\in B\); the second condition means that every \(x\in A\) corresponds to at most one \(y\in B\). Hence \(f=(F,A,B)\) is a function precisely when:

For every \(x\in A\), there exists a unique \(y\in B\) such that \((x,y)\in F\).

This \(y\) is called the function value of \(f\) at \(x\), and the unique element of \(F(\{x\})\) is denoted by \(f(x)\). The set \(A=\pr_1F\) is called the domain of \(f\).

Following this notation, the image of a set \(X\subseteq A\) under the binary relation \(F\) is written \(f(X)\) rather than \(F(X)\), and the preimage of a set \(Y\subseteq B\) is written \(f^{-1}(Y)\) rather than \(F^{-1}(Y)\). (§Binary Relation, ⁋Definition 5 and §Operations on Binary Relations, ⁋Definition 1) The triple \(f=(F,A,B)\) is written more concisely as \(f:A\rightarrow B\).

The set

\[F=\{(x,y)\mid (y=f(x))\wedge(x\in A)\}\]

representing a function \(f=(F,A,B)\) may also be regarded as the graph of the function drawn on the “coordinate plane” \(A\times B\). More generally, a binary relation \(R\) may likewise be regarded as the graph of the binary relation. A function \(f\) is a constant function if \(f(x)=f(x')\) for all \(x,x'\in \pr_1 F\).

In special cases, expressions such as \(f_x\) are also used to denote function values. When using this notation, we specifically call the domain of \(f\) the index set, and we call \(F\) a family. When \(f=(F,I,A)\) is regarded as a family, \(F\) is denoted by \((f_i)_{i\in I}\).

If \(f\) is a function from a set \(A\) to itself, then \(x\in A\) is said to be fixed by \(f\) if \(f(x)=x\).

Definition 2 For any set \(A\), we define the identity function \(\id_A\) as the triple \((\Delta_A,A,A)\). That is, \(\id_A\) is the function given by \(f(x)=x\) for every \(x\in A\).

By definition, \(\id_A\) fixes every element of \(A\).

Commutative Diagrams

When working with many functions at once, it is convenient to use diagrams such as the following.

Here \(A\overset{f}{\longrightarrow}B\) is a concise notation for \(f:A\rightarrow B\).

In the situation above, if \((i\circ g)(x)=(j\circ h)(x)\) for every \(x\in B\), then the square

is said to commute. Similarly, we call the diagram

a commutative diagram if \(h(x)=(f\circ g)(x)\) for all \(x\). This situation is sometimes expressed concisely as \(h=f\circ g\), a notation which implies not only that \(H=F\circ G\) holds but also that the sources and targets on both sides coincide.

When working with diagrams, we regard the identity function \(\id_A\) on each object \(A\) as being present even when not explicitly indicated by arrows. Thus strictly speaking, the commutativity of the triangle above means not only \(h=f\circ g\) but also

\[{\id_B}\circ h=f\circ g,\qquad h\circ{\id_C}=f\circ{\id_A}\circ g,\quad\cdots\]

However, by the identity function properties examined in §Operations on Binary Relations, ⁋Definition 9, all the above equations are equivalent to \(h=f\circ g\). On the other hand,

commuting means that all three conditions

\[{\id_A}=g\circ h\circ f,\quad {\id_B}=f\circ g\circ h,\quad {\id_C}=h\circ f\circ g\]

hold. In particular, the diagram

commuting means that \(g\circ f=\id_A\) and \(f\circ g=\id_B\).

Extension and Restriction of Functions

Definition 3 Two functions \(f=(F,A,B),f'=(F',A',B')\) are compatible on a set \(S\) if \(S\) is contained in the domains of both \(f\) and \(f'\), and \(f(x)=f'(x)\) for all \(x\in S\).

Let \(f\) and \(f'\) be two functions, and suppose \(S=\pr_1 F\cap\pr_1 F'\) is non-empty. If the two functions are compatible on \(S\), then a new function \(g\) with domain \(\pr_1F\cup\pr_1F'\) can be defined by

\[g(x)=\begin{cases}f(x)&x\in \pr_1F\setminus\pr_1F'\\ f(x)=f'(x)&x\in \pr_1F\cap\pr_1F'\\ f'(x)&x\in\pr_1F'\setminus\pr_1F\end{cases}\]

This situation is captured in the following definition.

Definition 4 Let \(f=(F,A,B)\) and \(f'=(F',A',B')\) be two functions. If \(F\subseteq F'\) and \(B\subseteq B'\), then \(f'\) is called an extension of \(f\), and we say that \(f'\) extends \(f\).

Conversely, a function may be restricted to a smaller domain. Let \(f=(F,A,B)\) be a function and let \(X\subseteq A\). If we define the relation \(R\) by

\((x\mathrel{R} y)\) if and only if \(((x\in X)\wedge(y=f(x)))\)

then the collection of all \((x,y)\) satisfying this condition forms a function whose domain is \(X\). This leads to the following definition.

Definition 5 The function \(g\) defined above is called the restriction of \(f\) to \(X\), and is denoted by \(f\vert_{X}\).

---

References

[Bou] N. Bourbaki, Theory of Sets. Elements of mathematics. Springer Berlin-Heidelberg, 2013.

---

1. Strictly speaking, we have not yet defined the cardinality of a set, but this condition can be expressed as \(x,y\in R(a)\implies x=y\), for instance. ↩