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→Y$f:X\to 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∈X$x\in X$, there exists a unique y∈Y$y\in Y$ such that (x,y)∈R$(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→B$f:A\to B$ is injective or one-to-one function if for every b∈B$b\in B$, there exists at most one a∈A$a\in A$ such that f(s)=t$f(s)=t$.

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

Example

• f:N→N,f(x)=5x$f:N\to N,f(x)=5x$ is injective.
• f:N→N,f(x)=x2$f:N\to N,f(x)=x^2$ is injective.
• f:R→R,f(x)=x2$f:R\to R,f(x)=x^2$ is not injective as (−x)2=x2$(-x{)}^2=x^2$

Surjective / Onto function

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

Example

• f:N→N,f(x)=x+2$f:N\to N,f(x)=x+2$ is surjective.
• f:R→R,f(x)=x2$f:R\to 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→B$f:A\to 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→R$f:R\to R$ defined by f(x)=2x–3$f(x)=2x–3$ is a bijective function.

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

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

Hence, f is injective.

Here, 2x–3=y$2x–3=y$

So, x=(y+5)/3$x=(y+5)/3$ which belongs to R and f(x)=y$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→B$f:A\to B$, is the function g:B→A$g:B\to A$, holding the following property −

f(x)=y⇔g(y)=x$f(x)=y\iff g(y)=x$

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

Example

• A Function f:Z→Z,f(x)=x+5$f:Z\to Z,f(x)=x+5$, is invertible since it has the inverse function g:Z→Z,g(x)=x−5$g:Z\to Z,g(x)=x-5$.
• A Function f:Z→Z,f(x)=x2$f:Z\to Z,f(x)=x^2$ is not invertiable since this is not one-to-one as (−x)2=x2$(-x{)}^2=x^2$.

Composition of Functions

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

Example

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

Solution

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

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

Hence, (fog)(x)≠(gof)(x)$(fog)(x)\ne (gof)(x)$

Some Facts about Composition

• If f and g are one-to-one then the function (gof)$(gof)$ is also one-to-one.
• If f and g are onto then the function (gof)$(gof)$ is also onto.
• Composition always holds associative property but does not hold commutative property.