Functions


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

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

Note that a relation from AA to BB is not considered a function if it doesn’t contain one single pair for every element of AA.

Lambda Notation

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

For example, we may express division as (λx;yy0xy)(\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,yy0(x,y)xy}\{ 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=(λxx+x)double = (\lambda x \in \mathbb{N} \circ x + x).

Special Functions

Identity Function

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

The identity function is the only relation on AA that is both an equivalence relation on AA and also a function from AA to AA.

Assuming a function ff from AA to BB that is a one-to-one correspondence, f1f=iAf^{-1} \circ f = i_{A} and ff1=iBf \circ f^{-1} = i_{B}.

Also, given g:BAg : B \mapsto A, if gf=iAg \circ f = i_{A} and fg=iBf \circ g = i_{B}, then g=f1g = f^{-1}.

Constant Function

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

Special Elements

Given a function f:(A×A)Af : (A \times A) \mapsto A, and elements aAa \in A and xAx \in A:

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

Finiteness

Properties

One-to-one (injection)

A function is one-to-one if no two arguments point to the same result. Given f:ABf : A \mapsto B, ff is one-to-one if a1Aa2Af(a1)=f(a2)a1=a2\forall a_{1} \in A \forall a_{2} \in A \bullet 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:ABf : A \mapsto B, if there is a function g:BAg : B \mapsto A such that gf=iAg \circ f = i_{A}, then ff is one-to-one.

Onto (surjection)

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

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

Given a function f:ABf : A \mapsto B, if there is a function g:BAg : B \mapsto A such that fg=iBf \circ g = i_{B}, then ff 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:ABf : A \mapsto B is a one-to-one correspondence, then f1:BAf^{-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:ABf : A \mapsto B is a permutation if A=BA = B, and ff is a bijection.

Types

Total

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

Partial

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

We can think of a partial function from AA to BB as a total function from AA to B{}B \cup \{ \perp \}, and instead of saying a function ff is undefined for some aAa \in A, we say that f(a)=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 ff and gg from AA to BB are considered equal if aAf(a)=g(a)\forall a \in A \bullet f(a) = g(a).

Composition

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

Compatibility

Given f:ABf : A \mapsto B and an equivalence relation RR on AA, ff is compatible with RR if x,yA(x,y)Rf(x)=f(y)\forall x, y \in A \bullet (x, y) \in R \implies f(x) = f(y).

Operations

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

Images

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

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

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