Functions and Equivalent Sets

The present unit is part of the following walks

Introduction

In the following you will find a short summary of this unit. For detailed information please see the full text or download the pdf document at the end of this page.

The present unit is the fourth unit of the walk The Axioms of Zermelo and Fraenkel. Based on the relations introduced in Unit Direct Products and Relations we will introduce functions as specific relations:

We will explain the following terms:

You will learn the main results of this unit:

Functions

The definition of a function will be based on direct products and relations explained in Unit Direct Products and Relations:

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.

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$.

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.

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$.

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

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.

Injective, Surjective and Bijective Functions

The terms injective, surjective and bijective play an important role for the investigation of 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.

The Composition of Functions

The most important result of this sections is that the set of the bijective functions $f : A \rightarrow A$ from a set $A$ into itself forms a group with respect to the composition of 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.

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. 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.

Definition. (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 \mbox{ (closure)}.$$

(ii) We have

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

(iii) There exists an element $id$ of the group $G$ such that

$$x * id = 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 = id \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.

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.

Restrictions and Extensions of Functions

Given a function $f : A \rightarrow B$ from a set $A$ into a set $B$ it is often useful to restrict the function $f$ to a function $f : A_1 \rightarrow B$ with $A_1 \subseteq A$ or to extend the function $f$ to a function $f : A_2 \rightarrow B$ with $A \subseteq A_2$. In this unit we only look at the basic definition. This topic becomes more interesting when investigating functions with specific properties such as continuous or holomorphic functions.

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.

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$. 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. Equivalence relations have been explained in Unit Direct Products and Relations.

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

Equivalent sets play an important role for the definition of the cardinality of a set.

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).

Theorem. 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$.

Notes and References

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

Do you want to learn more? In Unit Families and the Axiom of Choice we will explain how to define families $(A_i)_{i \in I}$ in the context of the axioms of Zermelo and Fraenkel, and we will explain the famous axiom of choice.