Unit - 2

Relations and Functions

Q1) Explain relation.

A1) Let X and Y are two sets, A relation from X to Y is a subset of .

Now suppose R is a relation form X to Y, then R is a set of ordered pairs where each first element comes from X and each second element comes from Y.

For each pair , one the following rule is true-

1.

2.

The domain of a relation R is the set of all first elements of the ordered pairs which belongs to R, and range is the second element.

Q2) Define composition of relations.

A2) Let X, Y and Z are three sets and R be a relation from X to Y and S is a relation from Y to Z.

So that R is a subset of  and S is a subset of .

Then R and S give a relation form X to Z which is denoted by RoS,

And can be defined as follows-

The relation RoS is called the composition of R and S.

Note- If R is a relation on a set A, that is, R is a relation from a set A to itself. Then the composition of R is RoR. Denoted by .

Q3) A = {2, 3}, B = {3, 4, 5, 6} and R is a relation from A to B defined as follows-

(a, b) ∈R if “a divides b” write the solution set of R.

A3) 2 divides 4 and 2 divides 6

⇒ (2, 4) ∈R and (2, 6) ∈R

3 divides 3, 3 divides 6

⇒ (3, 3) ∈R and (3, 6) ∈R

4 divides 4 ⇒ (4, 4) ∈R

Thus R = {(2, 4), (2, 6), (3, 3), (3, 6), (4, 4)}

Q4) Z denote the set of integers and the relation R in Z be defined by “aRb” iff a – b is an even integer”. Then show that R is an equivalence relation.

A4) 1. R is reflexive; since

∅ = a −a is even, hence aRa for every a∈Z.

2. R is symmetric:

If a – b is even then b – a = – (a – b) is also even hence aRb⇒bRa

3. R is transitive: for if aRb and bRc then both a – b and b – c are even.

Consequently, a – c = (a – b) + (b – c) is also even.

∴aRb and bRc⇒aR c

Thus, R is an equivalence relation.

Q5) Let Z denote the set of integers and the relation R in Z be defined by “aRb” iff a – b is an even integer”. Then show that R is an equivalence relation.

A5)  1. R is reflexive; since

∅ = a −a is even, hence aRa for every a∈Z.

2. R is symmetric:

If a – b is even then b – a = – (a – b) is also even hence aRb⇒bRa

3. R is transitive: for if aRb and bRc then both a – b and b – c are even.

Consequently, a – c = (a – b) + (b – c) is also even.

∴aRb and bRc⇒aR c

Thus, R is an equivalence relation.

Q6) Define partial ordering.

A6) A relation R on a set Sis called a partial order relation in Sif R is, Reflexive Anti-symmetric and transitive.

A set S together with a partial ordering R is called a partially ordered set.

We denote a partial order relation by the symbol ≤.

Q7) Find the number of ways to partition of 10 peoples into four groups

So that two teams contain 3 persons and two teams contain 2 persons.

A7) By using above theorem, we get-

ordered partitions

Here the group form an unordered partition so that we divide m’ by Because of the two cells with three elements each and Because of the two cells with two elements each.

 So that-

Q8) There are 12 employees in a company. Find the number of ways that the 12 employees do three different tasks if four employees are to take each task.

A8) Here we find the number of ordered partitions of twelve employees into cells containing 4 employees each.

There are total - partitions

Hence the required number of ways, the employees can do the task is 34,650.

Q9) Draw the Hasse diagram of positive division of 36.

A9) We have

Suppose R is the partial order relation on

The Hasse diagram will be-

Q10) Define lattices.

A10) A lattice is a partially ordered set in which every pair of elements a, b has a greatest lower bound and a least upper bound

For example- 

Suppose S be a non-empty set and L = P(S); that means ( is partially ordered.

If X and Y are two elements of L, then-

Hence ( is a Lattice.

Q11) What do you understand by axiomatic definition of lattice?

A11) Axiomatic definition of Lattice-

Let L be a non-empty set closed under two binary operations denoted by ∧ and ∨.

Then L is said to be a Lattice if it follows the axioms given below, here a, b and c are the elements of L.

1. Commutative law-

(i) a∧b = b∧a                                         (ii) a∨b = b∨a

2. Associative law-

(i) (a∧b)∧ c = a∧(b∧c)                          (ii) (a∨b) ∨ c = a∨ (b∨c)

3. Absorption law-

(i) a∧ (a∨b) = a                                      (ii) a∨(a∧b) = a

To show that which operation is involved we denote the Lattice by (L, ∧, ∨)

Q12) Let (L, ≤) be a lattice in which ‘⋅’ And ‘+’ denote the operations of meet and join respectively.

Then a≤b⇔a ⋅b = a ⇔a + b = b          ∀a, b, c ∈L

A12) Proof: Suppose a ≤b

As we know that a ≤a so that a ≤a. b but according to definition a. b≤a

So that- a ≤b ⇒a ⋅b = a

Let a ⋅b = a

But this is possible only if a ≤b which means a ⋅b = a ⇒a ≤b

∴a≤b⇒a⋅b = a and a ⋅b = a ⇒a ≤b

Combine these two, we get

a≤b⇔a ⋅b = a

Now let,

a⋅b= a,

Then we have

b + (a ⋅b) = b + a + a + b

But,

b + (a ⋅b) = b

Hence a + b = b

Similarly, by assuming a + b = b

We can show that a ⋅b = a

Hence a ≤b ⇔a ⋅b = a ⇔a + b = b = a

Q13) Define direct product.

A13) Let (L1, *, +) and 2 (L, ∧, ∨) be two lattices. The algebraic system (L1 × L2..., +)

In which the binary operation + and ‘’ ⋅are on L1 × L2 defined as

(a1, b1) ⋅ (a2, b2) = (a1 ∗a2, b1 ∧b2)

(a1, b1) + (a2, b2) = (a1 ⊕a2, b1 ∨b2)

For all (a1, b1) and (a2, b2) (a2, b2) ∈L1 × L2

Is called the direct product of the lattices L1 and L2.

Q14) Explain surjective and injective functions.

A14) Surjective function (Onto-Mapping)-

A mapping is said to be onto-mapping if the range set

If is onto then each element of B if f-image of at least one element of X.

That means.

A mapping is said to be into if it is not onto.

Injective function (One-To-One Mapping)-

A mapping is said to be one-to-one mapping if distinct elements of X are mapped into distinct elements of Y.

That means if f is a one-to-one mapping, then-

Or

Q15) Prove that is both one-one and onto then is both one-one and onto.

A15) Let f: X→Y be both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f () = , and f () =

Or

= () and = ()

Now,

Let () = (), then

() = ()

⇒ =

⇒f () = f ()

⇒ =

Thus is one-one

Since f is onto, for y∈Y, there is some element x∈X, such that f (x) = y.

Now

f(x) = y

⇒x=

So that is onto.

Hence is both one-one and onto.

Q16) Show that the inverse of an invertible mapping is unique.

A16) Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

are two different inverse mapping of f.

Let y ∈ Y and

Now-

And

so that-

and

Now-

Which shows that g(y) = h(y)∀ y ∈ Y

So that the inverse of f is unique.

Q17) Prove that is both one-one and onto then is both one-one and onto.

A17) Let f: X→Y be both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f () = , and f () =

Or

= () and = ()

Now,

Let () = (), then

() = ()

⇒ =

⇒f () = f ()

⇒ =

Thus is one-one

Since f is onto, for y∈Y, there is some element x∈X, such that f (x) = y.

Now

f(x) = y

⇒x=

So that is onto.

Hence is both one-one and onto.

Q18) Show that the inverse of an invertible mapping is unique.

A18) Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

are two different inverse mapping of f.

Let y ∈ Y and

Now-

And

so that-

and

Now-

Which shows that g(y) = h(y)∀ y ∈ Y

So that the inverse of f is unique.

Q19) Show that addition is primitive recursive.

A19)

Addition is defined by a + 0 = a, a + (b + 1) = (a + b) + 1 for all-natural numbers a, b.

We define f (a, b) = a + b such that

f (a, b + 1) = a + b + 1 = (a + b) + 1

= f (a, b) + 1

= S (f (a, b))

Also, f (a, 0) = a

We define f (a, b) as

If follows that f comes from primitive recursion from and so that f is primitive recursive.

Q20) Find the minimum number of persons in a group that three of them are born in the same month.

A20)

Here the n = 12 months are the pigeonholes, and k + 1 = 3 so k = 2. Hence among any kn+ 1 = 25 students (pigeons), three of them are born in the same month.