Images and Preimages

In mathematics, functions are a mean to assign each member of a set, exactly one member of another set. In Set theory they are defined as a set of key-value pairs, a binary relation, where each key appears only once.

Undoubtedly the most important concept in all of mathematics is that of a function — in almost every branch of modern mathematics functions turn out to be the central objects of investigation.

Definition: Let $A, B$ be sets, then the binary relation $f \subseteq A \times B$ is called a function or a mapping if for each $a \in A$ exists exactly one $b \in B$ such that $(a, b) \in f$, and is denoted by $f : A \rightarrow B$

Definition: Let $A, B$ be sets, let $f: A \rightarrow B$ be a function, let $a \in A$ and let $b \in B$ the only one such that $(a, b) \in f$, then $b$ is called the value of $f$ at $a$, and is denoted by $f(a)$ or $f_{a}$.

Notation Let $A, B$ be sets, then a fucntion $f: A \rightarrow B$ is sometimes denoted as $(f_{a})_{a \in A}$.

Corollary: Let $A, B$ be sets and let $f, g: A \rightarrow B$, then $f = g$ if and only if for each $a \in A$ holds that $f(a) = g(a)$.

Notation: Let $A, B$ be sets, let $f: A\rightarrow B$ be a function, and let $A_{0} \subseteq A$, then the class $\{b \in B : \text{exists } a \in A_{0} \text{ s.t. } f(a)=b\}$ is denoted by either $\{f(a) : a \in A_{0}\}$ or by $\{f(a)\}_{a \in A_{0}}$ or by $\{f_{a}\}_{a \in A_{0}}$ for short.

Definition: Let $A, B$ be sets, let $f: A\rightarrow B$ be a function, and let $A_{0} \subseteq A$, then the set $\{f(a) : a \in A_{0}\}$ is called the image of $A_{0}$ under $f$, and is denoted by $f(A_{0})$, if $A_{0}$ can also be a member of $A$ denote $F[A_{0}]$ to avoid confusion.

Corollary: Let $A, B$ be sets, and let $\{A_{0}, A_{1}\} \subseteq P(A)$ be subsets of $A$, then:

1. $f(A_{0})$ is a set, from the axiom schema of replacement.
2. $A_{0} \subseteq A_{1} \Longrightarrow f(A_{0}) \subseteq f(A_{1})$
Let $\{A_{\alpha}\}_{\alpha \in I} \subseteq P(A)$ subsets of $A$, then:
3. $f(\bigcup \limits_{\alpha \in I} A_{\alpha}) = \bigcup \limits _{\alpha \in I} f(A_{\alpha})$
4. $f(\bigcap \limits_{\alpha \in I} A_{\alpha}) = \bigcap \limits _{\alpha \in I} f(A_{\alpha})$

Definition: Let $A, B$ be sets, let $f: A \rightarrow B$ be a function, and let $B_{0} \subseteq B$, then the set $\{a \in A : f(a) \in B_{0}\}$ is called the preimage of $B_{0}$ under $f$ and is denoted by either $f^{-1}(B_{0})$ or $f^{-1}[B_{0}]$.

Corollary: Let $A, B$ be sets, let $f: A \rightarrow B$ be a function, and let $\{B_{0}, B_{1}\} \subseteq P(B)$ be subsets of $B$, then:

1. $f^{-1}(B_{0})$ is a set.
2. $f^{-1}(B_{0}\setminus B_{1})=f^{-1}(B_{0})\setminus f^{-1}(B_{1})$
3. $B_{0}\subseteq B_{1}\Longrightarrow f^{-1}(B_{0})\subseteq f^{-1}(B_{1})$
4. $f(f^{-1}(B_{0}))\subseteq B_{0}$
Let $A_{0} \subseteq A$ be a subset of $A$, then:
5. $f(A_{0})\subseteq B_{0}\Longleftrightarrow A_{0}\subseteq f^{-1}(B_{0})$
6. $A\subseteq f^{-1}(f(A_{0}))$
Let $\{B_{\beta}\}_{\beta\in J}\subseteq P(B)$ be subsets of $B$, then:
7. $f^{-1}(\bigcup\limits _{\beta\in J}B_{\beta})=\bigcup\limits _{\beta\in J}f^{-1}(B_{\beta})$
8. $f^{-1}(\bigcap\limits _{\beta\in J}B_{\beta})=\bigcap\limits _{\beta\in J}f^{-1}(B_{\beta})$

Definition: Let $A, B$ be sets, let $f: A \rightarrow B$ be a a function and let $A_{0} \subseteq A$, then the function $f \cap (A_{0} \times B)$ is called the restriction of $f$ to $A_{0}$ and is denoted either by $f \Bigl|_{A_{0}}$ or by $f \restriction A_{0}$.

Corollary: Let $A, B$ be sets, let $f: A\rightarrow B$ be a function, and let $A_{0} \subseteq A, B_{0} \subseteq B$, then: $(f \Bigl|_{A_{0}})^{-1}(B_{0}) = A_{0} \cap f^{-1}(B_{0})$.

Inverse Function

We now move on to talk about the most important types of functions: injective and surjective functions, that when combined together are called bijective functions. These properties are the basis upon which the study of different sizes of infinity is built.

Definition: Let $A, B$ be sets, and let $f: A \rightarrow B$ be a function, if for each $\{x, y\} \subseteq A$ such that $f(x) = f(y)$ holds that $x = y$, $f$ is called a injective function, or a one-to-one function.

Definition: Let $A, B$ be sets, and let $f:A \rightarrow B$, if for each $b \in B$ exists $a \in A$ such that $f(a)=b$ then $f$ is called a surjective fucntion or a function onto $B$.

Definition: Let $A, B$ be sets, and let $f:A \rightarrow B$, if $f$ is both injective and surjective it is called a bijection.

Claim: Let $A, B$ be sets, and let $f: A \rightarrow B$ be an injective function, then exists a surjective function $g: B \rightarrow A$.

Proof: Let $a_{0} \in A$ and deonte $g := \{(b, a) : (a, b) \in f\} \cup \left(\left(B\setminus f(A)\right)\times\{a_{0}\}\right)$. Let $b_{1} \in B$ and solve by case, if $b \in f(A)$ then from inectiveness of $f$ exists exactly one $a_{1}$ such that $(b_{1}, a_{1}) \in g$, otherwise $(b_{1}, a_{0}) \in g$ and therefore $g$ is a function. Let $a_{1} \in A$, then $(f(A_{1}), a_{1}) \in g$ and therefore $g$ is surjective.

Definition: Let $A, B, C$ be sets, and let $f: A\rightarrow B, g: B \rightarrow C$ be functions, then the function $h: A \rightarrow C$ which maps each element of $A$ to $g(f(a))$ is called the composition of $f$ and $g$, and is denoted by $f \circ g$.

Claim: Let $A, B, C$ be sets, and let $f: A\rightarrow B, g: B \rightarrow C$ be injective functions, then $f \circ g$ is injective.

Proof: Let $\{x, y\} \subseteq A$ be such that $(f \circ g)(x) = (f \circ g)(y)$, then from injectiveness of $g$ holds that $f(x) = g(y)$, and from the injectivess of $f$ we get that $x = y$.

Claim: Let $A, B, C$ be sets, and let $f: A\rightarrow B, g: B \rightarrow C$ be surjective functions, then $f \circ g$ is surjective.

Proof: Let $c \in C$ from surjectiveness of $g$ exists $b \in B$ such that $g(b)=c$, and from the surjectiveness of $f$ exists $a \in A$ such that $f(a)=b$, and therefore $(f \circ g)(a) = c$.

Definition: Let $A, B$ be sets and let $f: A \rightarrow B$ be a function, then $g: B\rightarrow A$ is called the inverse of $f$ if for each $a \in A$ holds that $(g \circ f)(a) = a$ and for each $b \in B$ holds that $(g \circ f)(b) = b$.

Definition: Let $A, B$ be sets, and let $f: A \rightarrow B$ be a function, then if exists $f$ had an inverse function, $f$ is called invertible.

Claim: Let $A, B$ be sets, and let $f: A \rightarrow B$ be a function, then $f$ is invertible if and only if it is a bijection.

Proof: Assume $f$ is invertible, and let $g$ be its inverse, let $b \in B$ and denote $a := g(b) \in A$, then $(f \circ g)(b) = b$, and $f(a) = b$ and therefore $f$ is surjective. Let $\{x, y\} \subseteq A$ such that $f(x) = f(y)$, then $x = (g \circ f)(x) = (g \circ f)(y) = y$, and therefore $f$ is injective. Assume now that $f$ is bijective, and denote $g := \{(b, a) : (a, b) \in f\}$, then from surjectiveness of $f$ holds that for all $b \in B$ exists $a \in A$ such that $(b, a) \in g$ and from injectiveness of $f$ we have that it is unique and therefore $g$ is a function. Let $a \in A$ then exists exactly one $b \in B$ such that $(a, b) \in f$ and therefore $(b, a) \in g$, and therefore $(g \circ f)(a) = a$ and $(f \circ g)(b) = b$.

Corollary: Let $A, B$ be sets and let $f: A \rightarrow B$ a bijection, then:

1. Exists exactly one inverse of $f$, it is denoted by $f^{-1}$.
2. $f^{-1}$ is ivertible and $f$ is its inverse.
3. The image of $f$ is the preimage of $f^{-1}$.

Recursion Theorem

Some function are defined recursively, by defining the first value, and then for each value defining its successor, we now prove that such definition is valid.

Claim: Let $A$ be non-empty set, and let $a_{0} \in A$, let $n \in \mathbb{N}$ be natural, and let $g:A \times \mathbb{N} \rightarrow A$ be a function, then exists $f_{n} : S(n) \rightarrow A$, such that $f_{n}(0) = a_{0}$ and for all natural $n_{0} \le n$ holds that $f_{n}(S(n_{0})=g(f_{n}(n_{0}),n_{0})$.

Proof: If $n = 0$ then $f_{n} = \{(0, a_{0}\}$ and we are done, otherwise let $m \in \mathbb{N}$ be natural such that $f_{m}(0) = a_{0}$, and for all natural $n_{0} \le m$ holds that $f_{m}(S(n_{0}))=g(f_{m}(n_{0}),n_{0})$, then $f_{S(m)} := f_{m}\cup\{(S(m),g(f_{m}(S(m)),S(m)))\}$ is a function such that $f_{S(m)}(0)=a$ and for all natural $n_{0} \le S(m)$ holds that $f_{S(m)}(S(n_{0}))=g(f_{S(m)}(n_{0}),n_{0})$, and therefore from the principle of induction the claim holds for all $n \in \mathbb{N}$.

Claim (Recursion Theorem): Let $A$ be non-empty, let $a_{0} \in A$ and let $g: A \times \mathbb{N} \rightarrow A$ be a function, then exists $f: \mathbb{N} \rightarrow A$ function such that $f(0) = a_{0}$ and that for all natural $n \in \mathbb{N}$ holds that $f(S(n))=g(f(n),n)$.

Proof: For all $k \in \mathbb{N}$ exists $f_{k}:(S(k))\rightarrow A$ function such that $f_{k}(0)=a$ and for all $n_{0} \le k$ holds that $f_{k}(S(n_{0}))=g(f_{k}(n_{0}),n_{0})$, denote $f := \bigcup\limits _{n\in\mathbb{N}}f_{n}$. Let $k_{0}$ such that for all $n \le k_{0} \le k_{1}$ natural holds that $f_{k_{0}}(n)=f_{k_{1}}(n)$. Denote $a_{k_{0}} := f_{k_{0}}(k_{0})$. Therefore for all $S(k_{0})\le k_{1}$ holds that $f_{k_{1}}(S(k_{0}))=g(a_{k_{0}},k_{0})$, and therefore from the principle of induction we get that for all $k_0 \in \mathbb{N}$ and for all natural $n \le k_{0} \le k_{1}$ holds that $f_{k_{0}}(n)=f_{k_{1}}(n)$, and so $f$ holds that for all $n \in \mathbb{N}$ there is exactly one $a \in A$ such that $(n, a) \in f$ and $f$ is a function, and for all $n \in \mathbb{N}$ holds that $f(S(n))=g(f(n),n)$.