Function and its Properties

A function is a relation between input X and output Y with the property that there is at most one element in Y corresponding to each element in X. For example, relation {(1, 2), (1, 3)} is not a function since 1 has two corresponding elements 2 and 3.

If $f: X \to Y$, X is called the domain of function $f$, and Y codomain or range

If $A \subseteq X$, then $f(A)$ is called the image of $A$ under $f$. Refer to the below diagram, the yellow area is image.

If $B \subseteq Y$, then $f^{-1}(B)$ is called the preimage of $B$ under $f$.

From Wikipedia

Identity function
$$id: X \to X \land \forall x: X \bullet id(x)=x$$

Injective function, or one-to-one function
$$\forall a,b:X \bullet f(a)=f(b) \implies a=b$$
For example,

• identity function
• inclusion function
• $f(x)=2x+1$
• $f(x)=e^x$

Inclusion function
$$\forall a:X, b:Y \bullet X \subset Y \implies f(a)=a$$

Surjective function (Onto)
$$\forall y:Y \bullet \exists x:X \bullet f(x)=y$$

From Wikipedia

For example,

• identity function
• $f(x)=2x+1$
• $f: \mathbb{R} \to \mathbb{R}, f(x)=e^x$ is not surjective since there is no x such that f(x) is negative
• $f: \mathbb{R} \to \mathbb{R}, f(x)=x^2$ is not surjective since there is no x such that f(x) is negative
• $f: \mathbb{R} \to \mathbb{R}^{nn}, f(x)=x^2$ is surjective since for each y there is a x that $x^2=y$

Partial Function
A function f from X to Y is partial if it doesn't map every element in X to Y. Formally,
$$\exists x:X \bullet f(x) \text{ is undefined}$$
For example,

• $f: \mathbb{N} \to \mathbb{N}$, and $f(x)=\sqrt{x}$

Total Function
Every element in X is defined.
$$\forall x:X \bullet \exists y:Y \bullet f(x)=y$$
For example,

• $f: \mathbb{N} \to \mathbb{N}$, f(x)=x

Monotonic
$$\forall x_1,x_2:X \bullet x_1 < x_2 \implies f(x_1) < f(x_2)$$

Idempotent
$$\overbrace{f(f(...f}^n(x))=f(x)$$

Associative
$$f(f(x,y), z) = f(x, f(y, z))$$

Distributive
$$f(g(x,y), z) = g(f(x, z), f(y, z))$$
f is distributive in g.
For example,

• $f(x, y) = x \times y, g(x,y)=x+y$, $x \times (y+z)=(x \times y + x \times z)$