# 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 \bullet (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 \bullet f(a) = b$.

## Special Elements

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

**Identity**: The element $a$ is an identity element of $f$ if $f(\{ a, x \}) = x$**Absorbing**: The element $a$ is an absorbing element of $f$ if $f(\{ a, x \}) = a$**Inverse**: The element $a$ is an absorbing element of $f$ if $f(\{ a, x \})$ equals the identity element**Idempotent**: The element $a$ is an idempotent element of $f$ if $f(\{ a, a \}) = 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.

## Finiteness

- If the domain of a function is a finite set, then the function itself is finite

## 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 \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 : 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 \bullet 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 \bullet 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 f)(a) = g(f(a)) $.

- The composition of two one-to-one functions is one-to-one
- If $f : A \mapsto B$ is one-to-one, then there exists an onto function $g : B \mapsto A$ such that $\forall a \in A \bullet (g \circ f)(a) = a$, and conversely
- If $g : B \mapsto A$ is onto, then there exists a one-to-one function $f : A \mapsto B$ such that $\forall a \in A \bullet (g \circ f)(a) = a$

### Compatibility

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

## Operations

**Range**: given $f : A \mapsto B$, the range of $f$ is the set of all the results of the application of such function. $Range(f) = \{ f(a) \mid a \in A \}$**Restriction**: given $f : A \mapsto B$ and $C \subseteq A$, the set $f \cap (C \times B)$ is called*the restriction of $f$ to $C$*, since it limits the pairs included in the relation. This is usually denoted $f \restriction C$**Relational Override**: given functions $f$ and $g$, we can override certain pairs in $f$ with their $g$ corresponding pairs as $f \oplus g$. Notice we can’t simply do $f \cup g$ since it can result in pairs that map the same value to more than one result, violating the definition of a function. Formally, $f \oplus g = (dom(g) ⩤ f) \cup g$

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 \bullet f(x) = b \}$.

Then, given
$Y \subseteq B$,
the *inverse image of
$Y$
under
$f$*
is the set $ f^{-1}(Y) = { a A f(a) 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.