Function #

A function $f\colon X \to Y$ maps each element $x$ of its domain $X$ to an element $f(x)$ of its codomain $Y$.

Terminology. A function is also called a map.

Examples.

• $\ $the function $f\colon \mathbb{Z} \to \mathbb{N}$ defined by

$\qquad f(x) = x^2$

$\qquad$maps each integer to its squared value.
$\qquad$For instance,

$\qquad f(3) = 9$

• $\ $the function $g\colon \mathbb{N} \to \mathcal{P}(\mathbb{N})$ defined by

$\qquad g(x) = \{y \mid y \in \mathbb{N},\ y < x\}$

$\qquad$maps each natural number to the set of natural numbers that precede it.
$\qquad$For instance,

$\qquad g(3) = \{0,1,2\}$

Injection, bijection, surjection #

Definition. A function $f\colon X \to Y$ is:

• injective (or an injection) is no two elements in its domain have the same image, i.e. if for all $ x_1, x_2 \in X$,

$\qquad \qquad x_1 \neq x_2$ implies $f(x_1) \neq f(x_2)$

• surjective (or a surjection) if every element in its codomain has a preimage, i.e. if

$\qquad \qquad$ for each $y \in Y$, there is a $x \in X$ such that $y = f(x)$.

• bijective (or a bijection) if it is injective and surjective.

Anonymous function #

Example. Consider the function

$\qquad f\colon \mathbb{Z} \to \mathbb{N} \text{ defined by } f(x) = x^2$

This is (arguably) the same function as

$\qquad g\colon \mathbb{Z} \to \mathbb{N} \text{ defined by } g(x) = x^2$

So the name of these function ($f$ or $g$) is in a certain sense irrelevant.
They can be both described as

$\qquad$“the function that maps an integer $x$ to $x^2$”.

Notation (borrowed from lambda calculus).

Let $f(x) = D$ be a function definition (for instance, $D$ could be $x^2$).

Then $\lambda x.D$ is an alternative notation for $f$.

In other words, $f$ can be viewed as an alias for $\lambda x.D$.

Example (continued).

$\lambda x.x^2 \colon \mathbb{Z} \to \mathbb{N}$ is the function that maps an integer $x$ to $x^2$.

It is equivalent to the functions $f$ and $g$ above.
For instance,

$\qquad (\lambda x.x^2)(3) = f(3) = g(3) = 9$

Terminology. An anonymous function is also called a lambda abstraction.

Higher-order function #

The domain of a function may consist of functions.

Example. We can define a function $\textit{isInjective}$ that maps a function $\mathbb{Z} \to \mathbb{N}$ to $1$ if it is injective, and to $0$ otherwise.
For instance:

• $\textit{isInjective}(\lambda x.x+1) = 1$
• $\textit{isInjective}(\lambda x.x^2) = 0$

The co-domain of a function may also consist of functions.

Examples. Consider the function $f\colon \mathbb{N} \to (\mathbb{N} \to \mathbb{N})$ defined by

$\qquad f(x) = \lambda y. x^y$

Then:

• $f(2)$ is the function $\lambda y.2^y$, or equivalently $g(y) = 2^y$,
• $f(3)$ is the function $\lambda y.3^y$, or equivalently $h(y) = 3^y$,
• etc.

Currying #

Intuition. Consider a function $f\colon X \times Y \to Z$.

This function takes as argument a pair of elements.
For instance, this function could be $f\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$, defined by

$\qquad f(x,y) = x + y$

If we know the values of $x$ and $y$, then we can evaluate $f(x,y)$.
For instance, if $x$ is $2$ and $y$ is $3$, then

$\qquad f(x,y) = 2 + 3 = 5$

Now what if we only know the value of $x$?
In this case, we cannot evaluate $f(x,y)$.
Instead, the best approximation of $f(x,y)$ that we can produce is a function that already knows the value of $x$ and is “waiting” for the value of $y$.

In our example, this function is:

$\qquad f_2(y) = 2 + y$

More generally, if we only know the value $a$ of $x$, then the best approximation of $f(x,y)$ that we can produce is the function

$\qquad f_a(y) = a + y$

Now the function $\bar{f} \colon X \to (Y \to Z)$ defined by

$\qquad \bar{f}(x) = f_x$

is called $f$ in curried form.

Intuitively, $\bar{f}$:

• takes a value for the first argument of $f$, and
• returns a function that expects a value for the second argument of $f$.

So in our example, $f$ in curried form is

$\qquad \bar{f} = \lambda x.(\lambda y.x + y)$

or equivalently

$\qquad \bar{f}(x) = \lambda y.x + y$

or equivalently

$\qquad \bar{f}(x)(y) = x + y$

Definition. If $f\colon X \times Y \to Z$ is a function, then $f$ in curried form is the function

$\qquad \bar{f}\colon X \to (Y \to Z)$

defined by

$\qquad \bar{f} = \lambda x.(\lambda y. f(x,y))$

or equivalently

$\qquad \bar{f}(x) = \lambda y. f(x,y)$

or equivalently

$\qquad \bar{f}(x)(y) = f(x,y)$

Generalization. Currying is not limited to functions over pairs: this extends to functions over arbitrary tuples. Let us define it for triples (the case of quadruples, quintuples, etc. is analogous).

If

$\qquad f\colon W \times X \times Y \to Z$

is a function, then $f$ in curried form is the function

$\qquad \bar{f} \colon W \to (X \to (Y \to Z))$

defined by

$\qquad \bar{f}(w)(x)(y) = f(w,x,y)$

Composition #

Definition. The composition of two functions

$\qquad f\colon X \to Y\qquad$ and $\qquad g\colon Y \to Z$

is the function

$\qquad g \circ f\colon X \to Z$

defined by

$\qquad(g \circ f)(x) = g(f(x))$

For instance, if

$\qquad f(x) = x - 2$

and

$\qquad g(y) = 3y,$

then

$\qquad(g \circ f)(x) = 3(x - 2)$

Identity function #

Definition. For a set $X$, the identity function $\text{id}_X \colon X \to X$ is defined by

$\qquad \text{id}_{X}(x) = x$

Note. If $f \colon X \to Y$, then

$\qquad f \circ \text{id}_X = \text{id}_Y \circ f = f$