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, $\text{dom}F=A$, and $\text{ran}F\subseteq B$.

A function is said to be elementary if it cannot be obtained from polynomials, exponentials, logarithms, or (inverse) trigonometric functions in a finite number of steps using addition, subtraction, multiplication, division, or composition.

A function $F:A\to B$ is said to be total if every element of $A$ maps to an element of $B$. If $F$ is only defined on a subset $S\subseteq A$, then $F$ is said to be partial with domain of definition $S$, denoted $F:A\rightharpoonup B$.

An implicit function is a function defined by an implicit equation that relates one of the variables (considered the value of the function) with the others (considered as the arguments).

A function $f$ is periodic with period $p$ if $f(t+p)=f(t)$ for all $t$ in the domain of $f$ and $p$ is the smallest positive number that has this property.

A function $f$ is cofunction of function $g$ if $f(A)=g(B)$ whenever $A$ and $B$ are complementary angles. For example, sine and cosine are cofunctions.

A function $f$ is said to be odd if $-f(x)=f(-x)$ for all $x$ in $f$'s domain. A function $f$ is said to be even if $f(x)=f(-x)$ for all $x$ in $f$'s domain.

Bijectivity

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.

A function $f$ is invertible if and only if it is bijective. Such a function has an inverse, denoted $f^{-1}$ such that $f\circ f^{-1}$ and $f^{-1}\circ f$ is the identity function.

Let $f:B\to C$ and $g:A\to B$. If $f\circ g$ is bijective, then $f$ is surjective and $g$ is injective.

Injectivity

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.

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.

If $A$ and $B$ are finite sets such that $|A|=|B|$, the pigeonhole principle shows an injection $F:A\to B$ is also surjective.

Surjectivity

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, $\text{dom}A$, and $\text{ran}F=B$.

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

If $A$ and $B$ are finite sets such that $|A|=|B|$, the pigeonhole principle shows a surjection $F:A\to B$ is also injective.

Monotonicity

A function $f$ is said to be increasing on a set $S$ if $f(x)\le f(y)$ for every pair of points $x$ and $y$ in $S$ with $x<y$. If the strict inequality $f(x)<f(y)$ holds for all $x<y$ in $S$, the function is said to be strictly increasing on $S$.

Similarly, $f$ is called decreasing on $S$ if $f(x)\ge f(y)$ for all $x<y$ and strictly decreasing if $f(x)>f(y)$.

A function is monotonic on $S$ if it is increasing on $S$ or decreasing on $S$. It is strictly monotonic if it is either strictly increasing on $S$ or strictly decreasing on $S$.

Finite Differences

Let $f$ be a function. The forward difference and backward difference of $f$, denoted as ${\mathrm{\Delta }}_h[f](x)$ and ${\mathrm{\nabla }}_h[f](x)$ respectively, are defined as

If $h$ is unspecified, it is usually assumed to take on value $1$.

Closures

If $S$ is a function and $A$ is a subset of $\text{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$.

Top-down Approach

Let $f$ be a function from $B$ into $B$ and assume $A\subseteq B$. The top-down approach for constructing the closure $C$ of $A$ under $f$ defines $C^{\ast }=C$ to be the intersection of all closed supersets of $A$:

Bottom-Up Approach

Let $f$ be a function from $B$ into $B$ and assume $A\subseteq B$. The bottom-up approach for constructing the closure $C$ of $A$ under $f$ defines $C_{\ast }=C$ to be

where $h:\omega \to \mathcal{P}(B)$ is recursively defined as:

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

Currying

Currying is the technique of translating a function of multiple arguments into a sequence of functions, each taking a single argument. The reverse process is called uncurrying.