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

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.

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.