Function

Functions and Equivalent Sets

The present unit is part of the following walks

Introduction

Please note that the text on this web page gives a summary of the Unit Functions and Equivalent Sets. A full text including the proofs is available as a separate pdf document at the end of this page.

The study of functions $f : A \rightarrow B$ from a set $A$ into a set $B$ is one of the main topics in mathematics.

The present unit provides the definition of functions within the set-theoretic framework of the axiomatic of Zermelo and Fraenkel and presents first elementary properties of functions. For the background about the axioms of Zermelo and Fraenkel see Unit Universe.

Definition of Functions

The first task is to define a function $f : A \rightarrow B$ from a set $A$ into a set $B$ within the set-theoretic framework of the axiomatic of Zermelo and Fraenkel:

In the framework of Zermelo and Fraenkel every mathematical object is a set. So, we have to define a function $f : A \rightarrow B$ as a set. The solution is as follows:

A function $f : A \rightarrow B$ from a set $A$ into a set $B$ is defined to be a triple $(f, A, B)$ where $f$ is a subset of the direct product $A \times B$ such that for each element $x$ of the set $A$ there exists exactly one element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$. We write

$$
f(x) := y \mbox{ or } f : x \mapsto y.
$$

See Definition [#nst-def-function].

This definition is a very good model for our intuitive understanding of a function sending an element $x$ to an element $y = f(x)$. In particular, given two functions $f : A \rightarrow B$ and $g : A \rightarrow B$, we have

$$
f = g \mbox{ if and only if } f(x) = g(x) \mbox{ for all } x \in A.
$$

See Theorem [#nst-th-function-identical].

Given a function $f : A \rightarrow B$, the set $A$ is called the domain, and the set $B$ is called the codomain of the function $f$. The set

$$
\{f(x) \mid x \in A\}
$$

is called the range or the image of the function $f$ (Definition [#nst-def-domain]).

Injective, Surjective and Bijective Functions

Important properties of a function $f : A \rightarrow B$ are expressed by the notions injective, surjective and bijective: Injective means that we have $f(x) \neq f(x’)$ whenever $x \neq x’$. Surjective means that the range $\{f(x) \mid x \in A\}$ of the function $f$ is the whole set $B$, and bijective means injective and surjective (Definition [#nst-def-function-bijective]).

As an example, let

$$
\mathbb{R}^{\geq 0} := \{ x \in \mathbb{R} \mid x \geq 0 \}
$$

be the set of the non-negative real numbers, and consider the following functions:

$$
\begin{array}{lclcllcl}
f_1 & : & \mathbb{R} & \rightarrow & \mathbb{R}, & f_1 & : & x \mapsto x^2 \\
f_2 & : & \mathbb{R} & \rightarrow & \mathbb{R}^{\geq 0}, & f_2 & : & x \mapsto x^2 \\
f_3 & : & \mathbb{R}^{\geq 0} & \rightarrow & \mathbb{R}, & f_3 & : & x \mapsto x^2 \\
f_4 & : & \mathbb{R}^{\geq 0} & \rightarrow & \mathbb{R}^{\geq 0}, & f_4 & : & x \mapsto x^2
\end{array}
$$

The function $f_1 : \mathbb{R} \rightarrow \mathbb{R}$ is not injective (we have $f_1(-1) = 1 = f_1(1)$) and not surjective (we have $f_1(x) \neq -1$ for all real numbers $x$).

The function $f_2 : \mathbb{R} \rightarrow \mathbb{R}^{\geq 0}$ is not injective (we have $f_2(-1) = 1 = f_2(1)$), but surjective (we have $f_2(\sqrt{x}) = x$ for all real numbers $x \geq 0$).

The function $f_3 : \mathbb{R}^{\geq 0} \rightarrow \mathbb{R}$ is injective ($x^2 = y^2$ and $x, y \geq 0$ imply $x = y$), but not surjective (we have $f_1(x) \neq -1$ for all real numbers $x$).

Finally, the function $f_4 : \mathbb{R}^{\geq 0} \rightarrow \mathbb{R}^{\geq 0}$ is injective and surjective, that is, bijective.

The Composition of Functions

Given two functions $f : A \rightarrow B$ and $g : B \rightarrow C$ from a set $A$ into a set $B$ and from the set $B$ into a set $C$, respectively, one defines the composite function $g \circ f$ by

$$
(g \circ f)(x) := g \big( f(x) \big) \mbox{ for all } x \in A.
$$

The function $g \circ f : A \rightarrow C$ is a function from the set $A$ into the set $C$.

The composition of two functions has the following nice properties:

The composition is associative, that is, we have $h \circ (g \circ f) = (h \circ g) \circ f$ (see Proposition [#nst-prop-function-composite-associative]).

If the functions $f :A \rightarrow B$ and $g : B \rightarrow C$ are injective (respectively surjective, respectively bijective), then the composite $g \circ f : A \rightarrow C$ is also injective (respectively surjective, respectively bijective) (see Proposition [#nst-prop-f-circ-g-bijective]).

Of particular interest is the case where $A = B = C$: The set of the bijective function from a set $A$ into itself forms a so-called group. For more details see Theorem [#nst-th-bijective-functions-group].

Restrictions and Extensions of Functions

Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $A’$ and $B’$ be two subsets of the sets $A$ and $B$, respectively. The question is: Does there exist a function $g : A’ \rightarrow B’$ such that

$$
g(x) = f(x) \mbox{ for all } x \in A’ ?
$$

Obviously, a necessary condition for the existence of the function $g : A’ \rightarrow B’$ is the relation

$$
f(A’) \subseteq B’.
$$

This condition is also sufficient (see Theorem [#nst-th-restriction-function]).

The function $g : A’ \rightarrow B’$ is called the restriction of the function $f : A \rightarrow B$. Extension means the inverse question: Let $f: A \rightarrow B$ be a fuction from a set $A$ into a set $B$, and let $A’$ and $B’$ be two sets such that

$$
A \subseteq A’ \mbox{ and } B \subseteq B’.
$$

Does there exist a function $h : A’ \rightarrow B’$ from the set $A’$ into the set $B’$ such that

$$
f(x) = h(x) \mbox{ for all } x \in A ?
$$

The answer is obviously yes. However, this question is a central topic in analysis when we consider functions with additional properties such that continuous functions, differentiable functions or holomorphic functions. As a simple example for a question about extensions of continuous functions consider the two functions

$$
\begin{array}{lclcllcl}
f_1 & : & \mathbb{R} \setminus \{ 0 \} & \rightarrow & \mathbb{R}, & f_1 & : & x \mapsto \frac{1}{x} \mbox{ and} \\
f_2 & : & \mathbb{R} \setminus \{ 0 \} & \rightarrow & \mathbb{R}, & f_2 & : & x \mapsto \frac{\sin(x)}{x}.
\end{array}
$$

Do there exist continuous functions $h_1 : \mathbb{R} \rightarrow \mathbb{R}$ and $h_2 : \mathbb{R} \rightarrow \mathbb{R}$ such that

$$
f_1(x) = h_1(x) \mbox{ and } f_2(x) = h_2(x) \mbox{ for all } x \in \mathbb{R} \setminus \{ 0 \} ?
$$

The function $h_1 : \mathbb{R} \rightarrow \mathbb{R}$ does not exist. The function $h_2 : \mathbb{R} \rightarrow \mathbb{R}$ exists if we set $h_2(0) := 0$. We won’t go into details in this unit.

Another important question about functions is whether two different functions can be combined: Given two functions $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$, there exists exactly one function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ such that

$$
f(x) = f_1(x) \mbox{ for all } x \in A_1 \mbox{ and } f(x) = f_2(x) \mbox{ for all } x \in A_2
$$

provided that we have

$$
f_1(x) = f_2(x) \mbox{ for all } x \in A_1 \cap A_2.
$$

See Proposition [#nst-prop-union-two-functions] and Proposition [#nst-prop-union-two-disjoint-functions].

Functions and Equivalence Relations

In the unit Direct Products equivalence relations are introduced (see also Definition [#nst-def-equivalence-relation]). Let $\sim$ be an equivalence relation on a set $A$. For each element $x$ of the set $A$ let

$$
\bar{x} := \{ z \in A \mid z \sim x \}
$$

be the equivalence class of the element $x$, and let

$$
\bar{A} := \{ \bar{x} \mid x \in A \}
$$

be the set of the equivalence classes with respect to the equivalence relation $\sim$. Let $f : A \rightarrow B$ be a function from the set $A$ into a set $B$. An important question about functions and equivalence relations is the question under which condition a function $F : \bar{A} \rightarrow B$ exists such that

$$
F(\bar{x}) = f(x) \mbox{ for all } x \in A ?
$$

Such a function $F : \bar{A} \rightarrow B$ exists if and only if we have

$$
f(x) = f(y) \mbox{ for all } x, y \in A \mbox{ s. t. } x \sim y.
$$

See Remark [#nst-rem-function-X-equivalence-classes-surjective].

The existence of such a function $F : \bar{A} \rightarrow B$ often reduces complexity since the set $\bar{A}$ is (often) much smaller than the set $A$.

The function $F : \bar{A} \rightarrow B$ is called well-defined if the function $f : A \rightarrow B$ fulfills the above condition (see Definition [#nst-def-function-well-defined]).

Equivalent Sets

Counting the elements of a set $A$ means that we choose a first element that we call No. 1, then choose a second element that we call No. 2, and so on.

For a set of three elements we obtain the following mapping between the elements of the set $A$ and the numbers 1, 2 and 3.

More formally, we define a bijective function $f : A \rightarrow B := \{ 1, 2, 3\}$ from the set $A$ onto the set $B = \{ 1, 2, 3 \}$.

Hence, counting is one example for the application of bijective functions between two sets. Counting and, more generally, cardinalities are explained in Units Natural Numbers and the Principle of Induction and [Cardinal Numbers – in preparation].

Two sets $A$ and $B$ are called equivalent if there exists a bijective mapping $f: A \rightarrow B$ from the set $A$ onto the set $B$ (Definition [#nst-def-equivalent-sets]).

Often it is very helpful to replace one set by another equivalent set: An example in this direction is Proposition [#nst-prop-making-sets-disjoint] stating that two arbitrary set $A$ and $B$ always are equivalent to two sets $A’$ and $B’$ with the additional property that $A’ \cap B’ = \emptyset$. Even stronger is Proposition [#nst-prop-making-one-set-disjoint] stating that for each two sets $A$ and $B$ one can find a set $B’$ equivalent to the set $B$ such that $A \cap B’ = \emptyset$.

Functions

Definition of a Function:

The definition of a function will be based on the notion of the direct product of two sets which is defined as follows:

Definition. Let $A$ be a set. Then the set of the subsets of the set $A$ is called the power set of the set $A$. It is denoted by

$$
{\cal P}(A) := \{ X \mid X \subseteq A \}.
$$

(b) Let $a$ and $b$ be two sets. The ordered pair $(a, b)$ is defined by $(a, b) := \big\{ \{a\}, \{a, b\} \big\}$.

(c) Let $A$ and $B$ be two sets. Set

$$
A \times B := \{ x \in {\cal P} \big( {\cal P} (A \cup B) \big) \mid \exists \: a \in A \: \exists \: b \in B \mbox{ s.t. } x = (a, b) \}.
$$

The set $A \times B$ is called the direct product of the sets $A$ and $B$ or, equivalently, the Cartesian product of the sets $A$ and $B$.

We write $A \times B := \{ (a, b) \mid a \in A \mbox{ and } b \in B \}$ for short.

Fore more details about ordered pairs and the direct product of two sets see Unit Direct Products.

Definition. Let $A$ and $B$ be two sets.

(a) A function $f : A \rightarrow B$ from the set $A$ into the set $B$ is a triple $(f, A, B)$ where the set $f$ is a subset of the direct product $A \times B$ with the following property:

For each element $x$ of the set $A$, there is exactly one element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$.

A function $f : A \rightarrow B$ from the set $A$ into the set $B$ is also called a mapping from the set $A$ into the set $B$ or a transformation from the set $A$ into the set $B$.

(b) Let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$, and let $x$ be an element of the set $A$. The unique element $y$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$ is denoted by $y = f(x)$. We also write $f : x \mapsto y$ or, equivalently, $f : x \mapsto f(x)$.

(c) Let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$. Then the set

$$
G_f := \{ \big(x, f(x) \big) \in A \times B \mid x \in A \}
$$

is called the graph of the function $f$.

French / German. Function = Fonction = Funktion. Mapping = Application = Abbildung. Graph = Graphe = Graph.

Note that the word function is often reserved for mappings from a set $X$ into the field of the real or the field of the complex numbers. The word mapping is used in the general case.

Example. The following figures illustrate a function and the graph of this function:

Proposition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and suppose that the set $B$ is a proper subset of a set $B’$.

Then the triple $(f, A, B’)$ is a function $f : A \rightarrow B’$.

Remarks. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$.

(a) Note that the set $f$ is a relation on the direct product $A \times B$. (A relation is a subset of the direct product $A \times B$. For details see Unit Direct Products).

(b) We will sometimes speak of a function $f$ instead of a function $f : A \rightarrow B$ if there is no danger of confusion concerning the sets $A$ and $B$ (see Proposition [#nst-prop-function-extension-of-Y]).

(c) It may occur that the sets $A$ and $B$ are both empty. In this case we have $f = \emptyset$. However, if the set $A$ is non-empty, the set $B$ is also non-empty since for each element $x$ of the set $A$, there exists exactly one element $y = y_x$ of the set $B$ such that the pair $(x, y)$ is contained in the set $f$.

(d) Usually, we think of a function from the set $A$ into the set $B$ as an object mapping each element $x$ of the set $A$ to an element $y$ of the set $B$.

In other words, the elements $x$ and $y$ of the sets $A$ and $B$, respectively are related with respect to the relation (function) $f$ if and only if $f(x) = y$.

(e) The graph $G_f$ is in fact the same set as the set $f$ of the triple $(f, A, B)$. If the set $B$ is a proper subset of a set $B’$ and if $f’$ denotes the triple $(f, A, B’)$ of Proposition [#nst-prop-function-extension-of-Y], then we have $G_{f’} = G_f$.

Elementary Properties of a Function

Theorem. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ and $g : A \rightarrow B$ be two functions from the set $A$ into the set $B$.

Then we have $f = g$ if and only if $f(x) = g(x)$ for all elements $x$ of the set $A$.

In Proposition [#nst-prop-function-empty] we will consider functions $f : A \rightarrow B$ where $A = \emptyset$ is the empty set. For that purpose we need the following elementary result about direct products:

Proposition. Let $A$ and $B$ be two sets.

(a) We have $A = \emptyset \mbox{ or } B = \emptyset \mbox{ if and only if } A \times B = \emptyset$.

(b) We have $A \neq \emptyset \mbox{ and } B \neq \emptyset \mbox{ if and only if } A \times B \neq \emptyset$.

Proposition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$.

If $A = \emptyset$, then we have $f = \emptyset$.

Definition of the Domain and of the Range of a Function:

Definition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$.

(a) The set $A$ is called the domain of the function $f$, and the set $B$ is called the codomain of the function $f$.

(b) The set

$$
R := \{ f(x) \mid x \in A \} \subseteq B
$$

is called the range of the function $f$ or, equivalently, the image of the function $f$. We also write $R = f(A)$ or $R = \mbox{Image } f$. (Sometimes the word range is also used in the meaning of the codomain.)

(c) Let $X$ be a subset of the set $A$. Then the set

$$
Y := \{ f(x) \mid x \in X \} \subseteq B
$$

is called the image of the set $X$ under the function $f$. We also write $Y = f(X)$.

French / German. Domain = Domaine de définition = Definitionsbereich; Codomain = Codomaine = Wertebereich; Image (or range) = Imâge = Bild.

Remark. Note that the definition of

$$
f(X) := \{ f(x) \mid x \in X \}
$$

for a function $f : A \rightarrow B$ and a subset $X$ of the set $A$ in Definition [#nst-def-domain] may be ambiguous: If the set $X$ is also an element of the set $A$, then the value $f(X)$ has two meanings. For example, if $A := \big\{a, b, \{a, b\} \big\}$, $B := \{c, d\}$ and if the function $f : A \rightarrow B$ is given by $f : a \mapsto c, b \mapsto d$ and $\{a, b\} \mapsto c$, then we have

$$
f(\{a, b\}) = c \mbox{ and } f(\{a, b\}) = \{c, d\}
$$

which is obviously nonsense. In general, there is no danger of confusion.

Examples. Let $A := \{x, y, z \}$ and $B := \{a, b, c\}$ be two sets, and suppose that the elements $x$, $y$ and $z$ and the elements $a$, $b$ and $c$ are pairwise distinct.

(a) Let $f : A \rightarrow B$ be defined by $f(x) := a$, $f(y) := b$ and $f(z) := c$.

Then we have $f(A) = B$, that is, the range of the function $f$ is the set $B$. If $X := \{z\}$, then we have $f(X) = \{c\}$.

(b) Let $g : A \rightarrow B$ be defined by $g(x) := a$, $g(y) := b$ and $g(z) := b$.

Then we have $g(A) = \{a, b\} \neq B$, that is, the range of the function $g$ is a proper subset of the set $B$. If $X := \{z\}$, then we have $g(X) = \{b\}$.

Definition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $Y$ be a subset of the set $B$. We set

$$
f^{-1}(Y) := \{ x \in A \mid f(x) \in Y \} \subseteq A.
$$

The set $f^{-1}(Y)$ is called the inverse image of the set $Y$ under the function $f$ (see also Remark [#nst-rem-f-inverse-A]).

French / German. Inverse Image = Imâge réciproque = Urbild.

Proposition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$. Then we have $f(\emptyset) = \emptyset$ and $f^{-1}(\emptyset) = \emptyset$.

The Identity Function and the Inclusion Map:

Even though the identity function and the inclusion map are rather trivial, they play an important role in the theory of functions.

Definition. (a) Let $A$ be a set, and let $f : A \rightarrow A$ be the function defined by

$$
f(x) := x \mbox{ for all } x \in A
$$

or, equivalently, by

$$
f := \{ (x, y) \in A \times A \mid y = x \} = \{ (x, x) \in A \times A \mid x \in A \}.
$$

The function $f : A \rightarrow A$ is called the identity function on the set $A$.

It is denoted by $\mbox{id}_A : A \rightarrow A$ or, equivalently, by $\mbox{id} : A \rightarrow A$ if no confusion may arise.

Note that $\mbox{id} = \emptyset$ if $A = \emptyset$.

(b) Let $B$ be a set, let $A$ be a subset of the set $B$, and let $g : A \rightarrow B$ be the function defined by

$$
g(x) := x \mbox{ for all } x \in A
$$

or, equivalently, by

$$
g := \{ (x, y) \in A \times B \mid y = x \} = \{ (x, x) \in A \times B \mid x \in A \}.
$$

The function $g : A \rightarrow B$ is called the inclusion map or, equivalently, the inclusion function.

It is denoted by $\iota : A \rightarrow B$ or, equivalently, by $A \hookrightarrow B$.

French / German. Identity = Identité = Identität.

Proposition. (a) Let $\mbox{id} : A \rightarrow A$ be the identity function on a set $A$. Then the range of the function $\mbox{id} : A \rightarrow A$ equals the set $A$.

(b) Let $\iota : A \rightarrow B$ be the inclusion map for a subset $A$ of a set $B$. Then the range of the function $\iota : A \rightarrow B$ equals the set $A$.

Historical Notes:

The definition of a function in the set-theoretical way described in Definition [#nst-def-function] is due to Felix Hausdorff (see [Ebbinghaus-2010], p. 89, footnote 225):

Zuvor betrachten wir eine Menge $P$ solcher Paare, und zwar von der Beschaffenheit, dass jedes Element $a$ von $A$ in einem und nur einem Paare $p$ von $P$ als erstes Element auftritt. Jedes Element $a$ bestimmt auf diese Weise ein und nur ein Element $b$, nämlich dasjenige, mit dem es zu einem Paare $p = (a, b)$ verbunden auftritt; dieses durch $a$ bestimmte […] Element bezeichnen wir mit

$$
b = f(a)
$$

und sagen, dass hiermit in $A$ […] eine eindeutige Funktion von $A$ definiert sei.

See [Hausdorff-1914], p. 33.

We first consider a set $P$ of such pairs with the additional property that every element $a$ of $A$ is contained as a first element in one and only one pair $p$ of $P$. Each element $a$ determines in this way one and only one element $b$, namely the element $b$ contained in the pair $p = (a, b)$; we denote this element determined by $a$ […] by

$$
b = f(a)
$$

and say that this defines a unique function on the set $A$.

(Translation by the author.)

Note that Theorem [#nst-th-function-identical] is also mentioned by Hausdorff (see [Hausdorff-1914], p. 33).

Injective, Surjective and Bijective Functions

Definition of Injective, Surjective and Bijective Functions:

Definition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$.

(a) The function $f : A \rightarrow B$ is called injective if $f(x) \neq f(x’)$ for each two elements $x$, $x’$ of the set $A$ such that $x \neq x’$.

(b) The function $f : A \rightarrow B$ is called surjective if for each element $y$ of the set $B$ there exists an element $x$ of the set $A$ such that $f(x) = y$.

(c) The function $f : A \rightarrow B$ is called bijective if $f$ is injective and surjective.

French / German. Injective = Injective = Injektiv. Surjective = Surjective = Surjektiv. Bijective = Bijective = Bijektiv.

Examples. Suppose that the elements $x$, $y$, $z$ and $t$ and that the elements $a$, $b$, $c$ and $d$ are pairwise distinct. Let the functions

\begin{eqnarray*}
f & : & \{x, y, z \} \rightarrow \{a, b, c, d \} \\
g & : & \{x, y, z, t \} \rightarrow \{a, b, c, d \} \mbox{ and} \\
h & : & \{x, y, z, t \} \rightarrow \{a, b, c, d \}
\end{eqnarray*}

be defined as follows:

$$
\begin{array}{llll}
f(x) := a, & f(y) := b, & f(z) := c. & \\
g(x) := a, & g(y) := b, & g(z) := c, & g(t) := c. \\
h(x) := a, & h(y) := b, & h(z) := c, & h(t) := d.
\end{array}
$$

(a) The function $f : \{x, y, z \} \rightarrow \{a, b, c, d \}$ is injective, but not surjective.

(b) The function $g : \{x, y, z, t \} \rightarrow \{a, b, c, d \}$ is neither injective nor surjective.

(c) The function $h : \{x, y, z, t \} \rightarrow \{a, b, c, d \}$ is bijective.

Examples. (a) The identity function $\mbox{id} : A \rightarrow A$ (Definition [#nst-def-function-identity]) is bijective.

(b) The inclusion map $\iota : A \rightarrow B$ (Definition [#nst-def-function-identity]) is injective. It is bijective if and only if $B = A$. In this case the inclusion map is the identity function.

Elementary Properties of Injective, Surjective and Bijective Functions:

Proposition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$.

The function $f : A \rightarrow B$ is injective if and only if for all elements $x$ and $x’$ of the set $A$, the equation $f(x) = f(x’)$ implies that $x = x’$.

Proposition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $R$ be the range of the function $f$.

Then the triple $(f, A, R)$ is a surjective function $f : A \rightarrow R$ from the set $A$ onto the set $R$.

Injective Functions preserve the $\subseteq$-Relation:

Proposition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ be a function from the set $A$ into the set $B$. Let $X$ and $Y$ be two subsets of the set $A$.

(a) If the set $X$ is a subset of the set $Y$, then the set $f(X)$ is a subset of the set $f(Y)$.

(b) Suppose in addition that the function $f : A \rightarrow B$ is injective. Then we have

$$
X \subseteq Y \mbox{ if and only if } f(X) \subseteq f(Y).
$$

Historical Notes:

I could not find out who has introduced the notions injective, surjective and bijective, but I believe that I have read somewhere that these notions have been introduced by Bourbaki:

Définition 10. Soit $f$ une application de $A$ dans $B$. On dit que $f$ est une injection, ou que $f$ est une application injective, si deux éléments distincts de $A$ ont des images distinctes par $f$. On dit que $f$ est une surjection, ou que $f$ est une application surjective, si $f(A) = B$. On dit que $f$ est une bijection, ou que $f$ est une application bijective, si $f$ est à la fois injective et surjective.

See [Bourbaki-2006], pp. E II.16 – 17.

Definition 10. Let $f$ be a mapping from $A$ into $B$. One says that $f$ is an injective mapping if each two different elements of $A$ have different images via $f$. One says that $f$ is a surjective mapping if $f(A) = B$. One says that $f$ is a bijective mapping if $f$ is injective and surjective.

(Translation by the author.)

The Composition of Functions

Definition of the Composite of two Functions:

Definition. Let $A$, $B$ and $C$ be three sets, and let $f : A \rightarrow B$ and $g : B \rightarrow C$ be two functions from the set $A$ into the set $B$ and from the set $B$ into the set $C$, respectively.

Define the function $h : A \rightarrow C$ by $h(x) := g \big( f(x) \big)$ for all elements $x$ of the set $A$.

(a) The function $h : A \rightarrow C$ is called the composite of the two functions $f : A \rightarrow B$ and $g : B \rightarrow C$.

(b) The function $h : A \rightarrow C$ is denoted by $g \circ f : A \rightarrow C$.

French / German. Composition of two functions = Composition de deux fonctions = Verkettung / Hintereinanderausführung von zwei Funktionen.

Example. Let $A := \{x, y, z\}$, $B := \{a, b, c, d\}$, $C := \{x, y, z, t\}$, and let $f : A \rightarrow B$ and $g : B \rightarrow C$ be defined as follows:

$f : x \mapsto a, y \mapsto b, z \mapsto b$ and $g : a \mapsto x, b \mapsto x, c \mapsto z, d \mapsto z$.

Then the function $h := g \circ f : A \rightarrow C$ is defined by $h : x \mapsto x, y \mapsto x, z \mapsto x$.

Remarks. (a) Alternatively, we may define the composite $h = g \circ f$ of Definition [#nst-def-function-composite] as a subset of the direct product $A \times C$. To do so, set

$$
h := \{ (x, z) \in A \times C \mid z = g \big( f(x) \big) \}.
$$

For each element $x$ of the set $A$, there is exactly one element $z$ of the set $C$ such that the pair $(x, z)$ is an element of the set $h$, namely the element $z: = g \big( f(x) \big)$. Hence, the set $h$ is a function.

(b) Note that if $f = \emptyset$, then we have $g \circ f = \emptyset$.

Functional Composition is Associative:

Proposition. Let $A$, $B$, $C$ and $D$ be four sets, and let $f : A \rightarrow B$, $g : B \rightarrow C$ and $h : C \rightarrow D$ be three functions. Then we have

$$
(h \circ g) \circ f = h \circ ( g \circ f),
$$

that is, functional composition is associative.

Functional Composition is in general not Commutative:

Example. Let $A := \{a, b, c\}$ such that the elements $a$, $b$ and $c$ are pairwise distinct, and let $f : A \rightarrow A$ and $g : A \rightarrow A$ be two functions from the set $A$ into itself defined by:

$$
f : a \mapsto b, b \mapsto a, c \mapsto c \mbox{ and } g : a \mapsto a, b \mapsto c, c \mapsto b.
$$

Then we have

$$
\begin{array}{l}
(g \circ f)(a) = c \neq b = (f \circ g)(a) \\
(g \circ f)(b) = a \neq c = (f \circ g)(b) \\
(g \circ f)(c) = b \neq a = (f \circ g)(c)
\end{array}
$$

which implies that functional composition is in general not commutative.

Composition of Injective, Surjective and Bijective Functions:

Proposition. Let $A$, $B$ and $C$ be three sets, and let $f : A \rightarrow B$ and $g : B \rightarrow C$ be two functions from the set $A$ into the set $B$ and from the set $B$ into the set $C$, respectively.

(a) If the functions $f : A \rightarrow B$ and $g : B \rightarrow C$ are injective, then the function $g \circ f : A \rightarrow C$ is also injective.

(b) If the functions $f : A \rightarrow B$ and $g : B \rightarrow C$ are surjective, then the function $g \circ f : A \rightarrow C$ is also surjective.

(c) If the functions $f : A \rightarrow B$ and $g : B \rightarrow C$ are bijective, then the function $g \circ f : A \rightarrow C$ is also bijective.

Definition of the Inverse Function:

Definition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ be a bijective function. We define the function $g : B \rightarrow A$ as follows: For each element $y$ of the set $B$, let $x$ be the unique element of the set $A$ such that $f(x) = y$. Set $g(y) := x$.

The function $g : B \rightarrow A$ is called the inverse function of the function $f : A \rightarrow B$. It is denoted by $f^{-1} : B \rightarrow A$.

French / German. Inverse function = Fonction inverse = Inverse Funktion.

Remarks. (a) If $f : A \rightarrow B$ is a bijective function from a set $A$ onto a set $B$, then the function $f$ is a subset of the set $A \times B$. The inverse function $f^{-1} : B \rightarrow A$ from the set $B$ onto the set $A$ can also be defined as follows:

$$
f^{-1} := \{ (y, x) \in B \times A \mid (x, y) \in f \}.
$$

(b) Let $f : A \rightarrow B$ be a function, and let $Y$ be a subset of the set $B$. Note that the definition of $f^{-1}(Y)$ may be ambiguous:

If the function $f : A \rightarrow B$ is bijective and if the set $Y$ is also an element of the set $B$, then $f^{-1}(Y)$ denotes the element $x$ of the set $A$ such that $f(x) = Y$ and at the same time the subset

$$
\{ x \in A \mid f(x) \in Y \}
$$

of the set $A$ (see also Remark [#nst-rem-domain]). The correct interpretation will be explained whenever necessary.

Proposition. Let $A$ and $B$ be two sets, let $f : A \rightarrow B$ be a bijective function, and let $f^{-1} : B \rightarrow A$ be the inverse function of the function $f : A \rightarrow B$. Then we have

$$
f \circ f^{-1} = \mbox{id}_B : B \rightarrow B \mbox{ and } f^{-1} \circ f = \mbox{id}_A : A \rightarrow A.
$$

Proposition. Let $A$ and $B$ be two sets, and let $f : A \rightarrow B$ and $g : B \rightarrow A$ be two bijective functions. Then we have

$$
\big( g \circ f \big)^{-1} = f^{-1} \circ g^{-1}.
$$

The Bijective Functions $f : A \rightarrow A$ form a Group:

We recall the definition of a group:

Definition. {\rm (a) A pair $(G, *)$ consisting of a non-empty set $G$ and an operation

$$
* : G \times G \rightarrow G
$$

on the set $G$ is called a group if the following conditions are fulfilled:

(i) We have $x * y \in G \mbox{ for all } x, y \in G$ (closure).

(ii) We have $(x * y) * z = x * (y * z) \mbox{ for all } x, y, z \in G$ (associativity).

(iii) There exists an element $\mbox{id}$ of the group $G$ such that

$$
x * \mbox{id} = \mbox{id} * x = x \mbox{ for all } x \in G \mbox{ (existence of an identity element)}.
$$

(iv) For each element $x$ of the group $G$, there exists an element $y = y_x$ of the group $G$ such that

$$
x * y = \mbox{id} = y * x \mbox{ (existence of an inverse element)}.
$$

The element $y$ is denoted by $x^{-1}$.

(b) If the pair $(G, *)$ is a group, we often just say that $G$ is a group or that $G = (G, *)$ is a group.

(c) A group $G = (G, *)$ is called a commutative group or, equivalently, an abelian group if we have

$$
x * y = y * x\mbox{ for all } x, y \in G.
$$

French / German. Group = Groupe = Gruppe. Commutative = Commutatif = Kommutativ. Abelian = Abélien = Abelsch.

For more details see Unit [Groups and Subgroups – in preparation].

Theorem. Let $A$ be a set, and let

$$
{\cal B}(A) := \{ f : A \rightarrow A \mid f \mbox{ is bijective} \}
$$

be the set of the bijective functions from the set $A$ into itself.

Then the pair $\big( {\cal B}(A), \circ \big)$ is a group where $\circ$ denotes the composition of two functions of the set ${\cal B}(A)$. In general, this group is not abelian.

Historical Notes:

The definition of an inverse function in the set-theoretical framework is also due to Felix Hausdorff. It refers to the text of Hausdorff cited in the historical remarks at the end of Section Functions.

Ist die Menge $P$ aber so beschaffen, daß auch jedes Element $b$ in genau einem Paare als zweites Element auftritt, so bestimmt auch $b$ ein einziges mit ihm verbundenes Element

$$
a = \varphi(b),
$$

und wir haben eine zweite, in $B$ definierte eindeutige Funktion. Diese beiden Funktionen heißen zueinander invers.

See [Hausdorff-1914], p. 33.

If the set $P$ has the property that also each element $b$ is contained as a second element in exactly one pair, then $b$ also determines exactly one element

$$
a = \varphi(b)
$$

related to $b$, and we obtain a second function which is defined on $B$. These two functions are called inverse to each other.

(Translation by the author.)

Restrictions and Extensions of Functions

Restrictions and Extensions:

Definition. Let $f : A \rightarrow B$ and $g : A’ \rightarrow B’$ be two functions from a set $A$ into a set $B$ and from a set $A’$ into a set $B’$, respectively. Suppose that the sets $A’$ and $B’$ are subsets of the sets $A$ and $B$, respectively.

We say that the function $g : A’ \rightarrow B’$ is a restriction of the function $f : A \rightarrow B$ or, equivalently, that the function $f : A \rightarrow B$ is an extension of the function $g : A’ \rightarrow B’$ or, equivalently, that the function $g : A’ \rightarrow B’$ is induced by the function $f : A \rightarrow B$ if we have

$$
f(x) = g(x) \mbox{ for all } x \in A’.
$$

In this case we write $g = f|_{A’} : A’ \rightarrow B’$.\index{$f_A : A \rightarrow B$}

French / German. Restriction = Restriction = Einschränkung. Extension = Prolongement = Fortsetzung. Induced by = Induit par = Induziert von.

Theorem. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $A’$ and $B’$ be two subsets of the sets $A$ and $B$, respectively.

Then a restriction $g : A’ \rightarrow B’$ exists if and only if $f(A’) \subseteq B’$.

In this case the restriction $g : A’ \rightarrow B’$ of the function $f : A \rightarrow B$ is unique.

Proposition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $A’$ be a subset of the set $A$.

(a) If the function $f : A \rightarrow B$ is injective, then the restriction $f|_{A’} : A’ \rightarrow B$ is also injective.

(b) If the function $f : A \rightarrow B$ is injective, then the restriction $f|_{A’} : A’ \rightarrow f(A’)$ is bijective.

(c) The restriction $f|_A : A \rightarrow f(A)$ is surjective.

(d) The restriction $f|_{A’} : A’ \rightarrow f(A’)$ is surjective.

For the proof of Proposition [#nst-prop-union-two-functions] we will need the following elementary result about the direct product of sets:

Proposition. Let $A_1$, $A_2$, $B_1$ and $B_2$ be four sets. Then we have

$$
(A_1 \times B_1) \cup (A_2 \times B_2) = (A_1 \cup A_2) \times (B_1 \cup B_2).
$$

Proposition. Let $A_1$, $A_2$, $B_1$ and $B_2$ be four non-empty sets, and let $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$ be two functions of the sets $A_1$ and $A_2$ into the sets $B_1$ and $B_2$, respectively.

Suppose that $f_1(x) = f_2(x)$ for all elements $x$ of the set $A_1 \cap A_2$.\footnote{Note that this implies that $f_1(x) = f_2(x) \in B_1 \cap B_2$ for all $x \in A_1 \cap A_2$.}

(a) There exists exactly one function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ such that $f|_{A_1} = f_1$ and $f|_{A_2} = f_2$.

(b) If the functions $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$ are surjective, then the function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ is also surjective.

Proposition. Let $A_1$, $A_2$, $B_1$ and $B_2$ be four non-empty sets such that $A_1 \cap A_2 = \emptyset$ and $B_1 \cap B_2 =\emptyset$, and let $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$ be two functions of the sets $A_1$ and $A_2$ into the sets $B_1$ and $B_2$, respectively.

(a) There exists exactly one function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ such that $f|_{A_1} = f_1$ and $f|_{A_2} = f_2$.

(b) If the functions $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$ are injective, then the function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ is also injective.

(c) If the functions $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$ are surjective, then the function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ is also surjective.

(d) If the functions $f_1 : A_1 \rightarrow B_1$ and $f_2 : A_2 \rightarrow B_2$ are bijective, then the function $f : A_1 \cup A_2 \rightarrow B_1 \cup B_2$ is also bijective.

Functions and Equivalence Relations

In the present section we will explain the relation between functions and equivalence relations. We start by recalling some basic facts about equivalence relations. For more details see Unit Direct Products.

Definition. Let $A$ be a non-empty set, and let $\sim$ be a relation on the set $A$.

(a) The relation $\sim$\index{$\sim$} is called an equivalence relation if it is reflexive, symmetric and transitive.

(b) Let $\sim$ be an equivalence relation, and let $x$ be an element of the set $A$. The set

$$
A_x := \{ z \in A \mid z \sim x \}
$$

is called an equivalence class with respect to the equivalence relation $\sim$.

(c) The quotient of the set $A$ with respect to the equivalence relation $\sim$ is the set

$$
\bar{A} := \{ A_x \mid x \in A \}.
$$

It is denoted by $\bar{A}$ or by $A / \sim$. The elements $A_x$ of the set $\bar{A} = A / \sim$ often are denoted by $\bar{x} := A_x$.

Proposition. Let $A$ be a set, and let $\sim$ be an equivalence relation on the set $A$. Let $x$ and $y$ be two elements of the set $A$, and let $A_x$ and $A_y$ be the equivalence classes of the elements $x$ and $y$, respectively.

(a) The element $x$ is contained in the set $A_x$.

(b) We have

$$
x \sim y \mbox{ if and only if } A_x = A_y.
$$

(c) We have $A_x = A_y$ or $A_x \cap A_y = \emptyset$.

(d) We have $A = \bigcup_{x \in A} A_x$.

Proposition. Let $A$ be a set, and let $\sim$ be an equivalence relation on the set $A$. For each element $x$ of the set $A$, let

$$
\bar{x} := \{ z \in A \mid z \sim x \}
$$

be the equivalence class defined by the element $x$ (Definition [#nst-def-equivalence-relation]). Define the function $f : A \rightarrow \bar{A}$ from the set $A$ into the set $\bar{A}$ of the equivalence classes of the set $A$ by $f : x \mapsto \bar{x}$.

Then the function $f : A \rightarrow \bar{A}$ is surjective.

Remark. An equivalence class can be understood as the subset of all elements of a set $A$ sharing a specific property. For example, in a set $A$ of red, blue and green balls, the sets $R$, $B$ and $G$ of red, blue and green balls, respectively are the equivalence classes with respect to the equivalence relation “color”.

The function $f : A \rightarrow \bar{A}$ of Proposition [#nst-prop-function-X-equivalence-classes-surjective] does nothing else than attributing to each ball (element of the set $A$) its color (equivalence class).

Proposition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $\sim$ be an equivalence relation on the set $A$. Suppose that the function $f : A \rightarrow B$ fulfills the condition

$$
f(x) = f(x’) \mbox{ for all } x, x’ \in A \mbox{ with } x \sim x’.
$$

For an element $x$ of the set $A$, let $\bar{x} := \{ z \in A \mid z \sim x \}$ be the equivalence class defined by the element $x$.

Then we may define a function $\alpha : \bar{A} \: \rightarrow B$ from the set $\bar{A}$ of the equivalence classes of the set $A$ into the set $B$ by $\alpha : \bar{x} \mapsto f(x)$.

Definition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$, and let $\sim$ be an equivalence relation on the set $A$. For an element $x$ of the set $A$, let $\bar{x} := \{ z \in A \mid z \sim x \}$ be the equivalence class defined by the element $x$.

The function $\alpha : \bar{A} \: \rightarrow B$ from the set $\bar{A}$ of the equivalence classes of the set $A$ into the set $B$ defined by $\alpha : \bar{x} \mapsto f(x)$ is called well defined if we have

$$
f(x) = f(y) \mbox{ for all } x, y \in A \mbox{ with } x \sim y.
$$

French / German. Well defined = Bien défini = Wohldefiniert.

Proposition. Let $f : A \rightarrow B$ be a function from a set $A$ into a set $B$. For two elements $x$ and $y$ of the set $A$, set

$$
x \sim y \mbox{ if and only if } f(x) = f(y).
$$

(a) The relation $\sim$ is an equivalence relation on the set $A$.

(b) For an element $x$ of the set $A$, let $\bar{x} := \{ z \in A \mid z \sim x \}$ be the equivalence class defined by the element $x$.

Then the function $\alpha : \bar{A} \: \rightarrow B$ from the set $\bar{A}$ of the equivalence classes of the set $A$ into the set $B$ defined by $\alpha : \bar{x} \mapsto f(x)$ is well defined and injective.

Equivalent Sets

Definition of equivalent sets:

Definition. Two sets $A$ and $B$ are called equivalent if there exists a bijective function $f : A \rightarrow B$ from the set $A$ onto the set $B$. If the sets $A$ and $B$ are equivalent, we write $A \sim B$.

French / German. Equivalent = Équivalent = Äquivalent.

Proposition. Let $A$, $B$ and $C$ be three sets.

(a) We have $A \sim A$ (reflexivity).

(b) If $A \sim B$, then we have $B \sim A$ (symmetry).

(c) If $A \sim B$ and $B \sim C$, then we have $A \sim C$ (transitivity).

Remark. Note that $\sim$ has the properties of an equivalence relation insofar as it is reflexive, symmetric and transitive, but it is not an equivalence relation: It is not defined on a set, since the set of all sets does not exist (see Unit Universe). However, if we restrict $\sim$ on a set $A$, then $\sim$ is an equivalence relation on the set $A$.

How to Make two Sets Disjoint:

Proposition. Let $A$ and $B$ be two non-empty sets. Then there exist two sets $A’$ and $B’$ fulfilling the following conditions:

(i) The sets $A$ and $A’$ are equivalent.

(ii) The sets $B$ and $B’$ are equivalent.

(iii) We have $A’ \cap B’ = \emptyset$.

In the proof of Proposition [#nst-prop-making-one-set-disjoint] we will make use of the axiom of foundation:

Axiom. (ZFC-4: Axiom of Foundation) Every non-empty set $A$ contains an element $a$ which is element minimal with respect to the set $A$, that is, an element $a$ such that

$$
a \cap A = \emptyset.
$$

For more details see Unit Universe.

Proposition. Let $A$ and $B$ be two non-empty sets. Then there exists a set $B’$ fulfilling the following conditions:

(i) The sets $B$ and $B’$ are equivalent.

(ii) We have $A \cap B’ = \emptyset$.

Historical Notes:

Equivalent sets have been introduced by Georg Cantor:

Wenn zwei wohldefinirte Mannigfaltigkeiten $M$ und $N$ sich eindeutig und vollständig, Element für Element, einander zuordnen lassen […], so möge für das Folgende die Ausdrucksweise gestattet sein, dass diese Manningfaltigkeiten gleiche Mächtigkeit haben, oder auch, dass sie äquivalent sind.

See [Cantor-1878], p. 242.

If a well-defined set $M$ can be mapped element-wise onto another well-defined set $N$ and vice versa […], it may be allowed to say that these sets have the same cardinality or, equivalently, that they are equivalent.

(Translation by the author.)

Notes and References

One of the early books about set theory is Grundzüge der Mengenlehre by Felix Hausdorff [Hausdorff-1914]. It is still a good source of inspiration.

A list of textbooks about set theory is contained in Unit [Literature about Set Theory].

[Bourbaki-2006] Bourbaki, Nicolas (2006). Théorie des ensembles. Berlin, Heidelberg, and New York: Springer Verlag.

This book is a reprint of the edition of 1970. The four chapters of this book have been first published separately in the years 1954 (Description de la mathématique formelle), 1939 and 1954 (Théorie des ensembles), 1956 (Ensembles ordonnés, cardinaux, nombres entiers) and 1956 (Structures).

[Cantor-1878] Cantor, Georg (1878). “Ein Beitrag zur Mannigfaltigkeitslehre”. In: Journal für die reine und angewandte Mathematik 84, pp. 242–258.

[Ebbinghaus-2010] Ebbinghaus, Heinz-Dieter (2010). Ernst Zermelo. An Approach to His Life and Work. Berlin, Heidelberg, and New York: Springer Verlag.

[Hausdorff-1914] Hausdorff, Felix (1914). Grundzüge der Mengenlehre. Leipzig: Veit and Comp. For a new edition see [Hausdorff 2002].

[Hausdorff-CW-2] Hausdorff, Felix (2002). Gesammelte Werke. Vol. 2: Grundzüge der Mengenlehre. Ed. by Brieskorn E. et al. Berlin, Heidelberg, and New York: Springer Verlag.

For the first edition see [Hausdorff 1914].

Download

Functions and Equivalent Sets

The pdf document is the full text including the proofs.

Change History

VersionDateChanges
1.0.0April 2020Creation
1.0.1April 2020Minor Corrections
1.0.2August 2020Minor Corrections