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

This means a function **f** is injective if a1≠a2a1≠a2 implies f(a1)≠f(a2)f(a1)≠f(a2).

### Example

- f:N→N,f(x)=5xf:N→N,f(x)=5x is injective.
- f:N→N,f(x)=x2f:N→N,f(x)=x2 is injective.
- f:R→R,f(x)=x2f:R→R,f(x)=x2 is not injective as (−x)2=x2(−x)2=x2

## Surjective / Onto function

A function f:A→Bf:A→B is surjective (onto) if the image of f equals its range. Equivalently, for every b∈Bb∈B, there exists some a∈Aa∈A such that f(a)=bf(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+2f:N→N,f(x)=x+2 is surjective.
- f:R→R,f(x)=x2f:R→R,f(x)=x2 is not surjective since we cannot find a real number whose square is negative.

## Bijective / One-to-one Correspondent

A function f:A→Bf:A→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→Rf:R→R defined by f(x)=2x–3f(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(x1)=f(x2), then 2x1–3=2x2–32×1–3=2×2–3 and it implies that x1=x2x1=x2.

Hence, f is **injective**.

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

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

f(x)=y⇔g(y)=xf(x)=y⇔g(y)=x

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

### Example

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