FUNCTIONS-Discrete Mathematics

 

FUNCTIONS

DEFINITION

A relation f from a set X to another set Y is called a function if for every x∈X there is a unique  y∈Y such that (x,y)∈f.

In other words a function from X to Y is an assignment of exactly one element of Y to every element of X, which is represented as f : X→Y.

Sometimes the terms ‘transformation’, ‘mapping’ or ‘correspondence’ are also used in the place of function.

If y= f(x), x is called the domain of f denoted by D_f

                y is called the codomain of f.

The set of the images (y) of all elements of X is called the range of f, denoted by R_f.

  

TYPES OF FUNCTIONS

One-to-one Function

A function f : X→Y is called one-to-one or injective or injection, if distinct elements of X are mapped into distinct elements of Y.  In other words, f is one-to-one if and only if

f (x1)≠ f (x2) whenever x1≠x2 or equivalently

f (x1)= f (x2) whenever x1=x2

Example

The function represented by the first diagram is one-to-one

The function represented by the second diagram is not one-to-one, since f (-2)= f (2)=4, but 2≠-2

 

Onto Function

A function f : X→Y is called onto or surjective or surjection, if the range R_f=Y; otherwise it is called into.

In other words, a function f is onto, if and only if for every element y∈Y there is an element x∈X such that f(x)=y.

Example

The function represented by the first diagram is onto function

The function represented by the second diagram is not onto

One-to-one Onto Function

A function f : X→Y is called one-to-one onto or bijective or bijection or one-to-one correspondence, if it is both one-to-one and onto.

Obviously, if X and Y are finite such that f : X→Y is bijective, then X and Y have the same number of elements.

PERMUTATION FUNCTION

The set of all one-to-one onto functions from A to A called the set of permutation functions from A to A.

Example

If A={1,2,3} there are 3!=6 bijective functions from A to A, which are given below.

f₁={(1,1),(2,2),(3,3)}

f₂={(1,1),(2,3),(3,2)}

f₃={(1,2),(2,3),(3,1)}

f₄={(1,2),(2,1),(3,3)}

f₅={(1,3),(2,1),(3,2)}

f₆={(1,3),(2,2),(3,1)}

 

The images of {1,2,3} under the functions f₁,f₂,….f₆ are obtained by permutations of {1,2,3}.

The set of functions f₁,f₂,….f₆ denoted by F is the set of permutation functions from {1,2,3} to {1,2,3}.

The composition of the elements of F are given in the following composition table

.	f1	f2	f3	f4	f5	f6
f1	f1	f2	f3	f4	f5	f6
f2	f2	f1	f6	f5	f4	f3
f3	f3	f4	f5	f6	f1	f2
f4	f4	f3	f2	f1	f6	f5
f5	f5	f6	f1	f2	f3	f4
f6	f6	f5	f4	f3	f2	f1

Also we note that f₁^-1= f₁; f₂^-1= f₂; f₃^-1= f₅ ; f₄^-1= f₄;  f₅^-1= f₃;  f₆^-1= f_6.

If the set A has n elements, there are n!elements in the set of permutation functions from A to A.