# 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.

Contents

## Function – Definition

A function or mapping (Defined as f: 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 s.t for each x ∈ X, there exists a unique y ∈ Y such that (x,y) ∈ R. x is called pre-image and y is called image of function f.

A function can be one to one, many to one (not one to many). A function f: A→B is said to be invertible if there exists a function g: B→A

## Injective / One-to-one function

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

This means a function **f** is injective if a_{1} ≠ a_{2} implies f(a_{1}) ≠ f(a_{2}).

### Example

- f: N→N, f(x) = 5x is injective.
- f: Z
^{+}→Z^{+}, f(x) = x^{2}is injective. - f: N→N, f(x) = x
^{2}is not injective as (−x)^{2}= x^{2}

## Surjective / Onto function

A function f: A→B is surjective (onto) if the image of f equals its range. Equivalently, for every b ∈ B, there exists some a ∈ 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 : Z
^{+}→Z^{+}, f(x) = x^{2}is surjective. - f : N→N, f(x) = x
^{2}is not injective as (−x)^{2}= x^{2}

## Bijective / One-to-one Correspondent

A function f: 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→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**.

## Composition of Functions

Two functions f: A→B and g: B→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, find ( f o g)(x) and ( g o f)(x)

### Solution

(f o g)(x) = f (g(x)) = f(2x) = 2x+2

(g o f)(x) = g (f(x)) = g(x+2) = 2(x+2) = 2x+4

Hence, (f o g)(x) ≠ (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.