Module4 | unit 4 set relation function and counting techniques

Back to Study material

Module-4

Set, Relation, function, and Counting Techniques

Question-1: Define sets.

Sol.

Sets- A set is a collection of well-defined objects which are called the elements or members of the set.

We generally use capital letters to denote sets and lowercase letters for elements.

If any element which exists in the set is to be denoted as-

Suppose an element ‘a’ is from a set X, then it is represented as- aX

This means the element ‘a’ belongs to the set X.

If the element is not from the group then we use ‘not belongs to’.

Question-2: If A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8, 9} and C = {5, 6, 7, 8, 9, 10}

Sol.

Then-

A∪B = {1, 2, 3, 4, 5, 6,7, 8, 9}

A∪C = {1, 2, 3, 4, 5, 6,7, 8, 9,10}

B∪C = {4, 5, 6,7, 8, 9, 10}

A∩B = {4, 5, 6}

A∩C = {5, 6}

B∩C = {5, 6, 7, 8, 9}

Question-3: what do you understand by-product of sets.

Sol.

Product sets-

Suppose we have two sets X and Y. The set of all ordered pairs (x, y) where is called the Cartesian product of X and Y.

It is represented as follows-

And it is read as X cross Y.

Question-4: define the composition of relations.

Sol.

Composition of relations-

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

Question-5: 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.

Sol: 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)}

Question-6: If A = {1, 2, 3} and R = {(x, y): x<y}, then represent it as matrix.

Sol.

Here we have- R = {(1, 2), (1, 3), (2, 3)}

Then

Question-7: Find the relation from the following digraph-

Sol. The relation R of the digraph is

R = {(a, a), (a, c), (b, c), (c, b), (c, c), (d, c)}

Question-8:

Show that the inverse of an invertible mapping is unique.

Sol

Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

Are two different inverse mappings 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.

Question-9: Prove that is both one-one and onto then is both one-one and onto.

Sol.

Let f: X→Ybe both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f() = , and f () =

= () 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.

Question-10: Prove 1+2+...+n = n(n+1)/2 using a proof by induction

Sol.

Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,

Step-1: Assume n=k holds: 1+2+...+k = k(k+1)/2

Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2

Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.

Step-2: Now start with the left side of the equation

1+2+...+(k+1)=1+2+...+k+(k+1)

=k(k+1)/2 + (k+1)

=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition

=(k+2)(k+1)/2 by distribution of multiplication over addition

=(k+1)(k+2)/2 by commutativity of multiplication

Question-11: Find the minimum number of persons in a group that three of them are born in the same month.

Sol.

Here the n = 12 months are the pigeonholes, and k + 1 = 3 so k = 2. Hence among

Anykn+ 1 = 25 students (pigeons), three of them are born in the same month.

Module-4

Set, Relation, function, and Counting Techniques

Question-1: Define sets.

Sol.

Sets- A set is a collection of well-defined objects which are called the elements or members of the set.

We generally use capital letters to denote sets and lowercase letters for elements.

If any element which exists in the set is to be denoted as-

Suppose an element ‘a’ is from a set X, then it is represented as- aX

This means the element ‘a’ belongs to the set X.

If the element is not from the group then we use ‘not belongs to’.

Question-2: If A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8, 9} and C = {5, 6, 7, 8, 9, 10}

Sol.

Then-

A∪B = {1, 2, 3, 4, 5, 6,7, 8, 9}

A∪C = {1, 2, 3, 4, 5, 6,7, 8, 9,10}

B∪C = {4, 5, 6,7, 8, 9, 10}

A∩B = {4, 5, 6}

A∩C = {5, 6}

B∩C = {5, 6, 7, 8, 9}

Question-3: what do you understand by-product of sets.

Sol.

Product sets-

Suppose we have two sets X and Y. The set of all ordered pairs (x, y) where is called the Cartesian product of X and Y.

It is represented as follows-

And it is read as X cross Y.

Question-4: define the composition of relations.

Sol.

Composition of relations-

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

Question-5: 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.

Sol: 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)}

Question-6: If A = {1, 2, 3} and R = {(x, y): x<y}, then represent it as matrix.

Sol.

Here we have- R = {(1, 2), (1, 3), (2, 3)}

Then

Question-7: Find the relation from the following digraph-

Sol. The relation R of the digraph is

R = {(a, a), (a, c), (b, c), (c, b), (c, c), (d, c)}

Question-8:

Show that the inverse of an invertible mapping is unique.

Sol

Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

Are two different inverse mappings 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.

Question-9: Prove that is both one-one and onto then is both one-one and onto.

Sol.

Let f: X→Ybe both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f() = , and f () =

= () 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.

Question-10: Prove 1+2+...+n = n(n+1)/2 using a proof by induction

Sol.

Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,

Step-1: Assume n=k holds: 1+2+...+k = k(k+1)/2

Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2

Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.

Step-2: Now start with the left side of the equation

1+2+...+(k+1)=1+2+...+k+(k+1)

=k(k+1)/2 + (k+1)

=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition

=(k+2)(k+1)/2 by distribution of multiplication over addition

=(k+1)(k+2)/2 by commutativity of multiplication

Question-11: Find the minimum number of persons in a group that three of them are born in the same month.

Sol.

Here the n = 12 months are the pigeonholes, and k + 1 = 3 so k = 2. Hence among

Anykn+ 1 = 25 students (pigeons), three of them are born in the same month.

Module-4

Set, Relation, function, and Counting Techniques

Question-1: Define sets.

Sol.

Sets- A set is a collection of well-defined objects which are called the elements or members of the set.

We generally use capital letters to denote sets and lowercase letters for elements.

If any element which exists in the set is to be denoted as-

Suppose an element ‘a’ is from a set X, then it is represented as- aX

This means the element ‘a’ belongs to the set X.

If the element is not from the group then we use ‘not belongs to’.

Question-2: If A = {1, 2, 3, 4, 5, 6}, B = {4, 5, 6, 7, 8, 9} and C = {5, 6, 7, 8, 9, 10}

Sol.

Then-

A∪B = {1, 2, 3, 4, 5, 6,7, 8, 9}

A∪C = {1, 2, 3, 4, 5, 6,7, 8, 9,10}

B∪C = {4, 5, 6,7, 8, 9, 10}

A∩B = {4, 5, 6}

A∩C = {5, 6}

B∩C = {5, 6, 7, 8, 9}

Question-3: what do you understand by-product of sets.

Sol.

Product sets-

Suppose we have two sets X and Y. The set of all ordered pairs (x, y) where is called the Cartesian product of X and Y.

It is represented as follows-

And it is read as X cross Y.

Question-4: define the composition of relations.

Sol.

Composition of relations-

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

Question-5: 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.

Sol: 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)}

Question-6: If A = {1, 2, 3} and R = {(x, y): x<y}, then represent it as matrix.

Sol.

Here we have- R = {(1, 2), (1, 3), (2, 3)}

Then

Question-7: Find the relation from the following digraph-

Sol. The relation R of the digraph is

R = {(a, a), (a, c), (b, c), (c, b), (c, c), (d, c)}

Question-8:

Show that the inverse of an invertible mapping is unique.

Sol

Let

By any invertible mapping,

Let,

g: Y→X

h: Y→X

Are two different inverse mappings 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.

Question-9: Prove that is both one-one and onto then is both one-one and onto.

Sol.

Let f: X→Ybe both one-one and onto.

Then there exist elements ∈X, and elements∈Y

Such that

f() = , and f () =

= () 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.

Question-10: Prove 1+2+...+n = n(n+1)/2 using a proof by induction

Sol.

Let n=1: 1 = 1(1+1)/2 = 1(2)/2 = 1 is true,

Step-1: Assume n=k holds: 1+2+...+k = k(k+1)/2

Show n=k+1 holds: 1+2+...+k+(k+1)=(k+1)((k+1)+1)/2

Substitute k with k+1 in the formula to get these lines. Notice that I write out what I want to prove.

Step-2: Now start with the left side of the equation

1+2+...+(k+1)=1+2+...+k+(k+1)

=k(k+1)/2 + (k+1)

=(k(k+1)+2(k+1))/2 by 2/2=1 and distridution of division over addition

=(k+2)(k+1)/2 by distribution of multiplication over addition

=(k+1)(k+2)/2 by commutativity of multiplication

Question-11: Find the minimum number of persons in a group that three of them are born in the same month.

Sol.

Here the n = 12 months are the pigeonholes, and k + 1 = 3 so k = 2. Hence among

Anykn+ 1 = 25 students (pigeons), three of them are born in the same month.

Sign Up