Functions

Overview

A function $F$ is a single-valued relation. We say $F$ maps $A$ into $B$, denoted $F:A\to B$, if and only if $F$ is a function, $\mathrm{dom}F=A$, and $\mathrm{ran}F\subseteq B$.

An operation on some set (say) $S$ is a function with “signature” $S\times \cdots \times S\to S$. More precisely, an $n$-ary operation on $S$ is a function $S^n\to S$ where $n\ge 0$.

Injections

A function is injective or one-to-one if each element of the codomain is mapped to by at most one element of the domain.

Left Inverses

Assume that $F:A\to B$ is a function and $A\ne \varnothing$. Then there exists a function $G:B\to A$ (a left inverse) such that $G\circ F=I_A$ if and only if $F$ is one-to-one.

Surjections

A function is surjective or onto if each element of the codomain is mapped to by at least one element of the domain. That is, $F$ maps $A$ onto $B$ if and only if $F$ is a function, $\mathrm{dom}A$, and $\mathrm{ran}F=B$.

Right Inverses

Assume that $F:A\to B$ is a function and $A\ne \varnothing$. Then there exists a function $G:B\to A$ (a right inverse) such that $F\circ G=I_B$ if and only if $F$ maps $A$ onto $B$.

Bijections

A function is bijective or a one-to-one correspondence if each element of the codomain is mapped to by exactly one element of the domain.

Inverses

Let $F$ be an arbitrary set. The inverse of $F$ is the set $F^{-1}=\{⟨u,v⟩\mid vFu\}$

Compositions

Let $F$ and $G$ be arbitrary sets. The composition of $F$ and $G$ is the set $F\circ G=\{⟨u,v⟩\mid \exists t,uGt\wedge tFv\}$

Restrictions

Let $F$ and $A$ be arbitrary sets. The restriction of $F$ to $A$ is the set $F\upharpoonright A=\{⟨u,v⟩\mid uFv\wedge u\in A\}$

Images

Let $F$ and $A$ be sets. Then the image of $F$ under $A$ is $F[[A]]=\{v\mid \exists u\in A,uFv\}$

The following holds for any sets $F$, $A$, $B$, and $\mathcal{A}$:

• The image of unions is the union of the images:
  • $F[[\bigcup \mathcal{A}]]=\bigcup \{F[[A]]\mid A\in \mathcal{A}\}$
• The image of intersections is a subset of the intersection of images:
  • $F[[\bigcap \mathcal{A}]]\subseteq \bigcap \{F[[A]]\mid A\in \mathcal{A}\}$ for $\mathcal{A}\ne \varnothing$
  • Equality holds if $F$ is single-rooted.
• The image of a difference includes the difference of the images:
  • $F[[A]]-F[[B]]\subseteq F[[A-B]]$
  • Equality holds if $F$ is single-rooted.

Closures

If $S$ is a function and $A$ is a subset of $\mathrm{dom}S$, then $A$ is said to be closed under $S$ if and only if whenever $x\in A$, then $S(x)\in A$. This is equivalently expressed as $S[[A]]\subseteq A$.

Let $f$ be a function from $B$ into $B$ and assume $A\subseteq B$. There are two possible methods for constructing the closure $C$ of $A$ under $f$. The top-down approach defines $C^{\ast }$ to be the intersection of all closed supersets of $A$: $C^{\ast }=\bigcap \{X\mid A\subseteq X\subseteq B\wedge f[[X]]\subseteq X\}$

The bottom-up approach defines $C_{\ast }$ to be $C_{\ast }={\bigcup }_{i\in \omega }h(i)$ where $h:\omega \to \mathcal{P}(B)$ is recursively defined as: \begin{align*} h(0) & = A, \\ h(n^+) &= h(n) \cup f[\![h(n)]\!]. \end{align*}

Note that the recursion theorem proves $h$ is indeed a function.

Kernels

Let $F:A\to B$. Define equivalence relation $\sim$ as $x\sim y\iff f(x)=f(y)$ Relation $\sim$ is called the (equivalence) kernel of $f$. The partition induced by $\sim$ on $A$ is called the coimage of $f$ (denoted $\mathrm{coim}f$). The fiber of an element $y$ under $F$ is $F^{-1}[[\{y\}]]$, i.e. the preimage of singleton set $\{y\}$. Therefore the equivalence classes of $\sim$ are also known as the fibers of $f$.

Bibliography

• “Bijection, Injection and Surjection,” in Wikipedia, May 2, 2024, https://en.wikipedia.org/w/index.php?title=Bijection_injection_and_surjection.
• “Fiber (Mathematics),” in Wikipedia, April 10, 2024, https://en.wikipedia.org/w/index.php?title=Fiber_(mathematics)&oldid=1218193490.
• Herbert B. Enderton, Elements of Set Theory (New York: Academic Press, 1977).
• “Kernel (Set Theory),” in Wikipedia, May 22, 2024, https://en.wikipedia.org/w/index.php?title=Kernel_(set_theory)&oldid=1225189560.
• “Operation (Mathematics).” In Wikipedia, October 10, 2024. https://en.wikipedia.org/w/index.php?title=Operation_(mathematics).