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)\)