Discrete Mathematics - Functions

A Function assigns to each element of a set, exactly one element of a related set. Functions find their apppcation in various fields pke 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 highpghts the important aspects of functions.

Function - Definition

A function or mapping (Defined as $f: X ightarrow 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 ightarrow 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 e a_2$ imppes $f(a1) e f(a2)$.

Example

$f: N ightarrow N, f(x) = 5x$ is injective.

$f: N ightarrow N, f(x) = x^2$ is injective.

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

Surjective / Onto function

A function $f: A ightarrow 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 ightarrow N, f(x) = x + 2$ is surjective.

$f : R ightarrow 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 ightarrow 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 ightarrow 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 imppes 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 ightarrow B$, is the function $g : B ightarrow 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 ightarrow Z, f(x)=x+5$, is invertible since it has the inverse function $ g : Z ightarrow Z, g(x)= x-5$.

A Function $f : Z ightarrow 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 ightarrow B$ and $g: B ightarrow 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) eq (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.