Homepage

Functions

A function is a relation between a set of inputs and a set of outputs

A binary relation \(F\) from \(A\) to \(B\) is a considered a function from \(A\) to \(B\) if \(\forall a \in A \exists ! b \in B ((x, y) \in F)\). This is denoted \(F : A \mapsto B\). In fact, \(A \mapsto B\) is an alternate notation for \((A, B)\), which makes the relationship between relations and functions even clearer.

Note that a relation from \(A\) to \(B\) is not considered a function if it doesn’t contain one single pair for every element of \(A\).

Lambda Notation

This notation allows to easily express functions \(f : A \mapsto B\) whose domain is the subset of \(A\) that satisfies a certain constraint.

For example, we may express division as \((\lambda x \in \mathbb{N}; y \in \mathbb{N} \mid y \neq 0 \circ \frac{x}{y})\). Notice the function takes two arguments, where the divisor can’t equal 0. Without lambda notation, we might have expressed this using the following set comprehension: \(\{ x \in \mathbb{N}, y \in \mathbb{N} \mid y \neq 0 \circ (x, y) \mapsto \frac{x}{y}\}\).

The contraint part is optional. We can define \(double = (\lambda x \in \mathbb{N} \circ x + x)\).

Special Functions

Identity Function

The identity function of \(A\) is defined as: \(i_{A} = \{ (a, a) \mid a \in A \}\).

The identity function is the only relation on \(A\) that is both an equivalence relation on \(A\) and also a function from \(A\) to \(A\).

Assuming a function \(f\) from \(A\) to \(B\) that is a one-to-one correspondence, \(f^{-1} \circ f = i_{A}\) and \(f \circ f^{-1} = i_{B}\).

Also, given \(g : B \mapsto A\), if \(g \circ f = i_{A}\) and \(f \circ g = i_{B}\), then \(g = f^{-1}\).

Constant Function

A constant function is a function that returns the same value given any input. \(f : A \mapsto B\) is a constant function if \(\exists b \in B \forall a \in A (f(a) = b)\).

Special Elements

Given a function \(f : (A \times A) \mapsto A\), and elements \(a \in A\) and \(x \in A\):

In the case of multiplication, 1 is the identity and idempotent element, 0 is the absorbing element, and \(x^{-1}\) is the inverse element of \(x\). In the case of addition, 0 is the identity and idempotent element, and \(-x\) is the inverse element of \(x\). There is no absorbing element in this case.

Properties

One-to-one (injection)

A function is one-to-one if no two arguments point to the same result. Given \(f : A \mapsto B\), \(f\) is one-to-one if \(\forall a_{1} \in A \forall a_{2} \in A (f(a_{1}) = f(a_{2}) \implies a_{1} = a_{2})\).

If two functions are one-to-one, the composition of those two functions is also one-to-one.

Given a function \(f : A \mapsto B\), if there is a function \(g : B \mapsto A\) such that \(g \circ f\ = i_{A}\), then \(f\) is one-to-one.

Onto (surjection)

A function \(f : A \mapsto B\) is onto if every element of \(B\) is returned by the function, which basically means that \(Range(f) = B\) or more generally, that \(\forall b \in B \exists a \in A (f(a) = b)\).

If two functions are onto, the composition of those two functions is also onto.

Given a function \(f : A \mapsto B\), if there is a function \(g : B \mapsto A\) such that \(f \circ g\ = i_{B}\), then \(f\) is onto.

One-to-one Correspondence (bijection)

A function is a one-to-one correspondence if its both one-to-one and onto. If a function \(f : A \mapsto B\) is a one-to-one correspondence, then \(f^{-1} : B \mapsto A\).

Giving a bijection between two sets is often a good way to show they have the same size.

Permutation

A function \(f : A \mapsto B\) is a permutation if \(A = B\), and \(f\) is a bijection.

Types

Total

A function \(f : A \mapsto B\) is a total function if its defined for every value of \(A\). A function is assumed to be total unless explicitly told otherwise.

Partial

A function \(f : A \mapsto B\) is a partial function if its only defined for a subset of \(A\). This is denoted as \(f : A \mapsto_{p} B\) or as \(f : A ⇸ B\). Notice that counter-intuitively, a partial function not necessarily a function.

We can think of a partial function from \(A\) to \(B\) as a total function from \(A\) to \(B \cup \{ \perp \}\), and instead of saying a function \(f\) is undefined for some \(a \in A\), we say that \(f(a) = { \perp }\).

The set of partial functions is a proper superset of the set of total functions, since a partial function is allowed to be defined on all its input elements.

Relationships

Equality

Two functions \(f\) and \(g\) from \(A\) to \(B\) are considered equal if \(\forall a \in A (f(a) = g(a))\).

Composition

Since functions are binary relations, they can be composed. Given \(f : A \mapsto B\) and \(g : B \mapsto C\), \((g \circ f)(a) = g(f(a)) \).

Compatibility

Given \(f : A \mapsto B\) and an equivalence relation \(R\) on \(A\), \(f\) is compatible with \(R\) if \(\forall x \in A \forall y \in A ((x, y) \in R \implies f(x) = f(y))\).

Operations

Note that if \(dom(f) \cap dom(g) = \emptyset\), then \(f \oplus g = f \cup g\), and \(f \oplus g = g \oplus f\).

Images

Given \(f : A \mapsto B\) and \(X \subseteq A\), then \(f(X)\) is called the image of \(X\) under \(f\), which is the set of values returned by \(f\) for every element in \(X\), which can be expressed as \(f(X) = \{ f(x) \mid x \in X \} = \{ b \in B \mid \exists x \in X (f(x) = b) \}\).

Then, given \(Y \subseteq B\), the inverse image of \(Y\) under \(f\) is the set \( f^{-1}(Y) = \{ a \in A \mid f(a) \in Y\} \).

Note that \(f^{-1}(Y)\) is defined as a set, and thus its not necessary for \(f^{-1}\) to be a function, which would imply that \(f\) is a one-to-one correspondence.