Abstract Algebra/Functions

Definition

A function $\operatorname{f}$ is a triplet (A,B,G) such that:

• A is a set, called the domain of $\operatorname{f}$
• B is a set, called the codomain of $\operatorname{f}$
• G is a subset of $A \times B$, called the graph of $\operatorname{f}$

In addition the following two properties hold:

1. $\forall x \in A, \exists y \in B \mid (x,y) \in G$.
2. $\forall x \in A, y \in B, y' \in B\mbox{, then } (x,y) \in G \mbox{ and } (x,y') \in G \Rightarrow y=y'$.

$\forall x \in A$ we write $\operatorname{f}(x)$ for the unique $y \in B$ such that $(x,y) \in G$.

We say that $\operatorname{f}$ is a function from A to B, which we write:

$\operatorname{f}:A \rightarrow B$

Example

Let's consider the function from the real to the real which squares its argument. We could define it like this:

$\operatorname{f}:\mathbb{R} \rightarrow \mathbb{R}$

$\operatorname{f}:x \mapsto x^2$

Remark

As you see in the definition of a function above, the domain and codomain are an integral part of the definition. In other words, even if the values of $\operatorname{f}(x)$ don't change, changing the domain or codomain changes the function.

Let's look at the following four functions.

The function:

$\operatorname{f_1}:\mathbb{R} \rightarrow \mathbb{R}$

$\operatorname{f_1}:x \mapsto x^2$

is neither injective nor surjective (these terms will be defined later).

The function:

$\operatorname{f_2}:\mathbb{R} \rightarrow \mathbb{R}_{\geq 0}$

$\operatorname{f_2}:x \mapsto x^2$

is not injective but surjective.

The function:

$\operatorname{f_3}:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}$

$\operatorname{f_3}:x \mapsto x^2$

is injective but not surjective.

The function:

$\operatorname{f_4}:\mathbb{R}_{\geq 0} \rightarrow \mathbb{R}_{\geq 0}$

$\operatorname{f_4}:x \mapsto x^2$

is injective and surjective

As you see, all four functions have the same mapping but all four are different. That's why just giving the mapping is insufficient; a function is only defined if its domain and codomain are known.

Image and preimage

For a set E, we write $\mathcal{P}(E)$ for the set of subsets of E.

Let $\operatorname{f}:A \rightarrow B$. We will now define two related functions.

The image function:

$\operatorname{f}:\mathcal{P}(A) \rightarrow \mathcal{P}(B),S \subseteq A \mapsto \{\operatorname{f}(x) \mid x \in S\}$

The preimage function:

$\operatorname{f^{-1}}:\mathcal{P}(B) \rightarrow \mathcal{P}(A),T \subseteq B \mapsto \{x \in A \mid \operatorname{f}(x) \in T\}$

Note that the image and preimage are written respectively like $\operatorname{f}$ and its inverse (if it exists). There is however no ambiguity because the domains are different. Note also that the image and preimage are not necessarily inverse of one another. (See the section on bijective functions below).

We define $\operatorname{Im}_{\operatorname{f}}:=\operatorname{f}(A)$, which we call the image of $\operatorname{f}$.

For any $y \in B$, we call $\operatorname{f^{-1}}(\{y\})$ the support of y.

Example

Let's take again the function:

$\operatorname{f}:\mathbb{R} \rightarrow \mathbb{R}$

$\operatorname{f}:x \mapsto x^2$

Let's consider the following examples:

$\operatorname{f^{-1}}(\{4\})=\{-2,2\}$

$\operatorname{f^{-1}}(\mathbb{R}_{< 0}) = \emptyset$

$\operatorname{f}(\mathbb{R}_{\geq 0}) = \mathbb{R}_{\geq 0}$

Further definitions

Let $\operatorname{f}:B \rightarrow C$ and $\operatorname{g}:A \rightarrow B$. We define $\operatorname{f} \circ \operatorname{g}:A \rightarrow C$ by $(\operatorname{f} \circ \operatorname{g})(x) := \operatorname{f}(\operatorname{g}(x))$, which we call the composition of $\operatorname{f}$ and $\operatorname{g}$.

Let A be a set. We define the identity function on A as

$\operatorname{id_A}:A \rightarrow A, x \mapsto x$

Properties

Definition: A function $\operatorname{f}:A \rightarrow B$ is injective if

$\forall x \in A, x' \in A, \operatorname{f}(x) = \operatorname{f}(x') \Rightarrow x = x'$

Lemma: Consider a function $\operatorname{f}:A \rightarrow B$ and suppose $A \neq \emptyset$. Then $\operatorname{f}$ is injective if and only if there exists a function $\operatorname{g}:B \rightarrow A$ with $\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}$.
Proof:
$'\Rightarrow'$:
Suppose $\operatorname{f}$ is injective. As $A \neq \emptyset$ let's define m as an arbitrary element of A. We can then define a suitable function $\operatorname{g}:B \rightarrow A$ as follows:

$\operatorname{g}(y):= \left\{ \begin{array}{ll} \mbox{the unique } x \in A \mid \operatorname{f}(x) = y & \text{, if } y \in \operatorname{Im}_{\operatorname{f}}\\ m & \text{, else}\\ \end{array} \right.$

It is now easy to verify that $\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}$.
$'\Leftarrow'$:
Suppose there is a function $\operatorname{g}:B \rightarrow A$ with $\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}$. Then $\forall x,x' \in A, \operatorname{f}(x) = \operatorname{f}(x') \Rightarrow \operatorname{g}(\operatorname{f}(x)) = \operatorname{g}(\operatorname{f}(x')) \Rightarrow x = x'$. $\operatorname{f}$ is thus injective.
Q.E.D.

Definition: A function $\operatorname{f}:A \rightarrow B$ is surjective if

$\forall y \in B, \exists x \in A \mid \operatorname{f}(x) = y$

Lemma: Consider a function $\operatorname{f}:A \rightarrow B$. Then $\operatorname{f}$ is surjective if and only if there exists a function $\operatorname{g}:B \rightarrow A$ with $\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}$.
Proof:
$'\Rightarrow'$:
Suppose $\operatorname{f}$ is surjective. We can define a suitable function $\operatorname{g}:B \rightarrow A$ as follows:

$\operatorname{g}(y):= \mbox{an } x \in A \mid \operatorname{f}(x) = y$

It is now easy to verify that $\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}$.
$'\Leftarrow'$:
Suppose there is a function $\operatorname{g}:B \rightarrow A$ with $\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}$. Then $\forall y \in B \mbox{, let } x := \operatorname{g}(y)$. Then $\operatorname{f}(x) = \operatorname{f}(\operatorname{g}(y)) = y$. $\operatorname{f}$ is thus surjective.
Q.E.D.

Definition: A function $\operatorname{f}:A \rightarrow B$ is bijective if it is both injective and surjective.

Lemma: A function $\operatorname{f}:A \rightarrow B$ is bijective if and only if there exists a function $\operatorname{g}:B \rightarrow A$ with $\operatorname{g} \circ \operatorname{f} = \operatorname{id_A}$ and $\operatorname{f} \circ \operatorname{g} = \operatorname{id_B}$. Furthermore it can be shown that such a $\operatorname{g}$ is unique. We write it $\operatorname{f^{-1}}:B \rightarrow A$ and call it the inverse of $\operatorname{f}$.
Proof:
Left as an exercise.

The text in its current form is incomplete.