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 fis both injective and surjective.

Pigeon Hole

Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two
pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it, at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it.

 
Theorem –

I) If “A” is the average number of pigeons per hole, where A is not an integer then

• At least one pigeon hole contains ceil[A] (smallest integer greater than or equal to A) pigeons
• Remaining pigeon holes contains at most floor[A] (largest integer less than or equal to A) pigeons

Set - Definition

A set is an unordered collection of different elements. A set can be written explicitly by listing its elements using set bracket. If the order of the elements is changed or any element of a set is repeated, it does not make any changes in the set.

Some Example of Sets

• A set of all positive integers
• A set of all the planets in the solar system
• A set of all the states in India
• A set of all the lowercase letters of the alphabet

Representation of a Set

Sets can be represented in two ways −

• Roster or Tabular Form
• Set Builder Notation

Roster or Tabular Form

The set is represented by listing all the elements comprising it. The elements are enclosed within braces and separated by commas.

Example 1 − Set of vowels in English alphabet, A={a,e,i,o,u}A={a,e,i,o,u}

Example 2 − Set of odd numbers less than 10, B={1,3,5,7,9}B={1,3,5,7,9}

Set Builder Notation

The set is defined by specifying a property that elements of the set have in common. The set is described as A={x:p(x)}

Probability theory, a branch of mathematics concerned with the analysis of random phenomena. The outcome of a random event cannot be determined before it occurs, but it may be any one of several possible outcomes. The actual outcome is considered to be determined by chance.

The word probability has several meanings in ordinary conversation. Two of these are particularly important for the development and applications of the mathematical theory of probability. One is the interpretation of probabilities as relative frequencies, for which simple games involving coins, cards, dice, and roulette wheels provide examples. The distinctive feature of games of chance is that the outcome of a given trial cannot be predicted with certainty, although the collective results of a large number of trials display some regularity. For example, the statement that the probability of “heads” in tossing a coin equals one-half, according to the relative frequency interpretation, implies that in a large number of tosses the relative frequency with which “heads” actually occurs will be approximately one-half, although it contains no implication concerning the outcome of any given toss. There are many similar examples involving groups of people, molecules of a gas, genes, and so on. Actuarial statements about the life expectancy for persons of a certain age describe the collective experience of a large number of individuals but do not purport to say what will happen to any particular person. Similarly, predictions about the chance of a genetic disease occurring in a child of parents having a known genetic makeup are statements about relative frequencies of occurrence in a large number of cases but are not predictions about a given individual.