Discrete Mathematics - Functions

---

---

A Function assigns to each element of a set, exactly one element of a related set. Functions find their application in various fields like representation of the computational complexity of algorithms, counting objects, study of sequences and strings, to name a few. The third and final chapter of this part highlights the important aspects of functions.

Function - Definition

A function or mapping (Defined as $f: X \rightarrow Y$) is a relationship from elements of one set X to elements of another set Y (X and Y are non-empty sets). X is called Domain and Y is called Codomain of function f.

Function f is a relation on X and Y such that for each $x \in X$, there exists a unique $y \in Y$ such that $(x,y) \in R$. x is called pre-image and y is called image of function f.

A function can be one to one or many to one but not one to many.

Injective / One-to-one function

A function $f: A \rightarrow B$ is injective or one-to-one function if for every $b \in B$, there exists at most one $a \in A$ such that $f(s) = t$.

This means a function f is injective if $a_1 \ne a_2$ implies $f(a1) \ne f(a2)$.

Example

• $f: N \rightarrow N, f(x) = 5x$ is injective.

• $f: N \rightarrow N, f(x) = x^2$ is injective.

• $f: R\rightarrow R, f(x) = x^2$ is not injective as $(-x)^2 = x^2$

Surjective / Onto function

A function $f: A \rightarrow B$ is surjective (onto) if the image of f equals its range. Equivalently, for every $b \in B$, there exists some $a \in A$ such that $f(a) = b$. This means that for any y in B, there exists some x in A such that $y = f(x)$.

Example

• $f : N \rightarrow N, f(x) = x + 2$ is surjective.

• $f : R \rightarrow R, f(x) = x^2$ is not surjective since we cannot find a real number whose square is negative.

Bijective / One-to-one Correspondent

A function $f: A \rightarrow B$ is bijective or one-to-one correspondent if and only if f is both injective and surjective.

Problem

Prove that a function $f: R \rightarrow R$ defined by $f(x) = 2x 3$ is a bijective function.

Explanation − We have to prove this function is both injective and surjective.

If $f(x_1) = f(x_2)$, then $2x_1 3 = 2x_2 3 $ and it implies that $x_1 = x_2$.

Hence, f is injective.

Here, $2x 3= y$

So, $x = (y+5)/3$ which belongs to R and $f(x) = y$.

Hence, f is surjective.

Since f is both surjective and injective, we can say f is bijective.

Inverse of a Function

The inverse of a one-to-one corresponding function $f : A \rightarrow B$, is the function $g : B \rightarrow A$, holding the following property −

$f(x) = y \Leftrightarrow g(y) = x$

The function f is called invertible, if its inverse function g exists.

Example

• A Function $f : Z \rightarrow Z, f(x)=x+5$, is invertible since it has the inverse function $ g : Z \rightarrow Z, g(x)= x-5$.

• A Function $f : Z \rightarrow Z, f(x)=x^2$ is not invertiable since this is not one-to-one as $(-x)^2=x^2$.

Composition of Functions

Two functions $f: A \rightarrow B$ and $g: B \rightarrow C$ can be composed to give a composition $g o f$. This is a function from A to C defined by $(gof)(x) = g(f(x))$

Example

Let $f(x) = x + 2$ and $g(x) = 2x + 1$, find $( f o g)(x)$ and $( g o f)(x)$.

Solution

$(f o g)(x) = f (g(x)) = f(2x + 1) = 2x + 1 + 2 = 2x + 3$

$(g o f)(x) = g (f(x)) = g(x + 2) = 2 (x+2) + 1 = 2x + 5$

Hence, $(f o g)(x) \neq (g o f)(x)$

Some Facts about Composition

• If f and g are one-to-one then the function $(g o f)$ is also one-to-one.

• If f and g are onto then the function $(g o f)$ is also onto.

• Composition always holds associative property but does not hold commutative property.