DMPT

UNIT-2 Q & A For MSE-1

1 List the members of these sets.

a) {x | x is a real number such that x 2 = 1}
b) {x | x is a positive integer less than 12}
c) {x | x is the square of an integer and x < 100}
d) {x | x is an integer such that x 2 = 2}

Ans a) {−1,1}
b) {1,2,3,4,5,6,7,8,9,10,11}
c) {0,1,4, 9, 16, 25, 36, 49, 64, 81}
d) ∅

2 For each of these pairs of sets, determine whether the first is a subset of the second, the second is a
subset of the first, or neither is a subset of the other.
a) the set of airline flights from New York to New Delhi, the set of nonstop airline flights from New
York to New Delhi
b) the set of people who speak English, the set of people who speak Chinese
c) the set of flying squirrels, the set of living creatures that can fly

Ans a) The first is a subset of the second, but the second is not a subset of the first.
b) Neither is a subset of the other.
c) The first is a subset of the sec- ond, but the second is not a subset of the first.

3 Determine whether each of these pairs of sets are equal.

a) {1, 3, 3, 3, 5, 5, 5, 5, 5}, {5, 3, 1}
b) {{1}}, {1, {1}}
c) ∅, {∅}

Ans a) Yes b) No c) No

4 For each of the following sets, determine whether 2 is an element of that set.
a) {x ∈ R | x is an integer greater than 1}
b) {x ∈ R | x is the square of an integer}
c) {2,{2}}
d) {{2},{{2}}}
e) {{2},{2,{2}}}
f ) {{{2}}}

Ans a) Yes
b) No
c) Yes
d) No
e) No
f) No

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

 5 Determine whether each of these statements is true or false.
a) 0 ∈ ∅
b) ∅ ∈ {0}
c) {0} ⊂ ∅
d) ∅ ⊂ {0}
e) {0} ∈ {0}
f ) {0} ⊂ {0}
g) {∅} ⊆ {∅}

Ans a) False
b) False
c) False
d) True
e) False
f) False
g) True

6 Determine whether each of these statements is true or false.

a) x ∈ {x}
b) {x} ⊆ {x}
c) {x} ∈ {x}
d) {x} ∈ {{x}}
e) ∅ ⊆ {x}
f ) ∅ ∈ {x}

Ans a) True
b) True
c) False
d) True
e) True
f) False

7 Use a Venn diagram to illustrate the set of all months of the year whose names do not contain the
letter R in the set of all months of the year.

Ans

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

 8 Use a Venn diagram to illustrate the relationships A ⊂ B and B ⊂ C.

Ans The dots in certain regions indicate that those regions are not empty.

9 Suppose that A, B , and C are sets such that A ⊆ B and B ⊆ C. Show that A ⊆ C.

Ans Suppose that x ∈ A. Because A ⊆ B , this implies that x ∈ B .

Because B ⊆ C, we see that x ∈ C.
Because x ∈ A implies that x ∈ C, it follows that A ⊆ C.

10 What is the cardinality of each of these sets?

a) {a}
b) {{a}}
c) {a, {a}}
d) {a, {a}, {a, {a}}}

Ans a) 1
b) 1
c) 2
d) 3

11 Find the power set of each of these sets, where a and b are distinct elements.
a) {a}
b) {a, b}
c) {∅, {∅}}

Ans a) {∅, {a}}

b) {∅, {a}, {b}, {a, b}}
c) {∅, {∅}, {{∅}}, {∅, {∅}}}

12 How many elements does each of these sets have where a and b are distinct elements?
a) P ({a, b, {a, b}})
b) P ({∅, a, {a}, {{a}}})
c) P (P (∅))

Ans a) 8
b) 16
c) 2

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

13 Prove that P (A) ⊆ P (B ) if and only if A ⊆ B .

Ans For the “if” part, given A ⊆ B , we want to show that that P (A) ⊆ P (B ), i.e., if C ⊆ A then
C ⊆ B . But this follows directly from QUE. 9.
For the “only if” part, given that P (A) ⊆ P (B ), we want to show that A ⊆ B .
Suppose a ∈ A.
Then {a} ⊆ A, so {a} ∈ P (A).
Since P (A) ⊆ P (B ), it follows that {a} ∈ P (B ), which means that {a} ⊆ B .
But this implies a ∈ B , as desired.

14 Let A = {a, b, c, d } and B = {y, z}. Find

a) A × B .
b) B × A.

Ans a) {(a, y), (b, y), (c, y), (d , y), (a, z), (b, z), (c, z), (d , z)}
b) {(y, a), (y, b), (y, c), (y, d ), (z, a), (z, b), (z, c), (z, d )}

15 What is the Cartesian product A × B × C, where A is the set of all airlines and B and C are both
the set of all cities in the United States? Give an example of how this Cartesian product can be used.

Ans The set of triples (a, b, c), where a is an airline and b and c are cities. A useful subset of this set
is the set of triples (a, b, c) for which a flies between b and c.

16 Let A be a set. Show that ∅ × A = A × ∅ = ∅.

Ans ∅ × A = {(x, y) | x ∈ ∅ and y ∈ A} = ∅ = {(x, y) | x ∈ A and y ∈ ∅} = A × ∅

17 Find A2 if
a) A = {0, 1, 3}.
b) A = {1, 2, a, b}.

Ans a) {(0, 0), (0, 1), (0, 3), (1, 0), (1, 1), (1, 3), (3, 0), (3, 1), (3, 3)}
b) {(1, 1), (1, 2), (1, a), (1, b), (2, 1), (2, 2), (2, a), (2, b), (a, 1), (a, 2), (a, a), (a, b), (b, 1), (b, 2),
(b, a), (b, b)}

18 How many different elements does A × B have if A has m elements and B has n elements?

Ans mn

19 How many different elements does An have when A has m elements and n is a positive integer?

Ans mn

20 Explain why A × B × C and (A × B) × C are not the same.

Ans The elements of A × B × C consist of 3-tuples (a, b, c), where a ∈ A, b ∈ B , and c ∈ C, whereas
the elements of (A × B) × C look like ((a, b), c)—ordered pairs, the first coordinate of which is
again an ordered pair.

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

21 Translate each of these quantifications into English and determine its truth value.
a) ∀x∈ R (x 2 = −1)
b) ∃x∈ Z (x 2 = 2)
c) ∀x∈ Z (x 2 > 0)
d) ∃x∈ R (x 2 = x)

Ans a) The square of a real number is never −1. True

b) There exists an integer whose square is 2. False
c) The square of every integer is positive. False
d) There is a real number equal to its own square. True

22 Let A be the set of students who live within one mile of school and let B be the set of students
who walk to classes. Describe the students in each of these sets.
a) A ∩ B
b) A ∪ B
c) A − B
d) B − A

Ans a) The set of students who live within one mile of school and walk to classes
b) The set of students who live within one mile of school or walk to classes (or do both)
c) The set of students who live within one mile of school but do not walk to classes
d) The set of students who walk to classes but live more than one mile away from school

23 Let A = {1, 2, 3, 4, 5} and B = {0, 3, 6}. Find

a) A ∪ B .
b) A ∩ B .
c) A − B .
d) B − A.

Ans a) {0,1,2,3,4,5,6}
b) {3}
c) {1, 2, 4,5}
d) {0, 6}

24 Assume that A is a subset of some underlying universal set U . Prove the domination laws
a) A ∪ U = U .
b) A ∩ ∅ = ∅.

Ans a) A ∪ U = {x | x ∈ A ∨ x ∈ U } = {x | x ∈ A ∨ T} = {x | T} = U
b) A ∩ ∅ = {x | x ∈ A ∧ x ∈ ∅} = {x | x ∈ A ∧ F} ={x | F} = ∅

25 Let A and B be sets. Prove the commutative laws

a) A ∪ B = B ∪ A.
b) A ∩ B = B ∩ A.

Ans a) A ∪ B = {x | x ∈ A ∨ x ∈ B } = {x | x ∈ B ∨ x ∈ A} = B ∪ A
b) A ∩ B = {x | x ∈ A ∧ x ∈ B } = {x | x ∈ B ∧ x ∈ A} = B ∩ A

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

26 Prove the second absorption law by showing that if A and B are sets, then A ∩ (A ∪ B) = A.

Ans Suppose x ∈ A ∩ (A ∪ B).

Then x ∈ A and x ∈ A ∪ B by the definition of intersection.
Because x ∈ A, we have proved that the left-hand side is a subset of the right- hand side.
Conversely, let x ∈ A.
Then by the definition of union, x ∈ A ∪ B as well.
Therefore x ∈ A ∩ (A ∪ B) by the definition of intersection, so the right-hand side is
a subset of the left-hand side.

27 Find the sets A and B if A − B = {1, 5, 7, 8}, B − A = {2, 10}, and A ∩ B = {3, 6, 9}.

Ans Since A = (A − B) ∪ (A ∩ B) ,
we conclude that A = {1, 5, 7, 8} ∪ {3, 6, 9} = {1, 3, 5, 6, 7, 8, 9} .
Similarly B = (B − A) ∪ (A ∩ B) = {2, 10} ∪ {3, 6, 9} = {2, 3, 6, 9, 10} .

28 Prove the second De Morgan law by showing that if A and B are sets, then

using a membership table.

Ans

29 Show that if A, B , and C are sets, then

a) by showing each side is a subset of the other side.

b) using a membership table.

Ans (a)

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

30 Let A, B , and C be sets. Show that
a) (A ∪ B) ⊆ (A ∪ B ∪ C).
b) (A ∩ B ∩ C) ⊆ (A ∩ B).
c) (A − B) − C ⊆ A − C.
d) (A − C) ∩ (C − B) = ∅.
e) (B − A) ∪ (C − A) = (B ∪ C) − A.

Ans a) Suppose that x ∈ A ∪ B .

Then either x ∈ A or x ∈ B .
In either case, certainly x ∈ A ∪ B ∪ C .
This establishes the desired inclusion.
b) Suppose that x ∈ A ∩ B ∩ C .
Then x is in all three of these sets.
In particular, it is in both A and B and therefore in A ∩ B , as desired.
c) Suppose that x ∈ (A − B) − C .
Then x is in A − B but not in C .
Since x ∈ A − B , we know that x ∈ A (we also know that x ∈/ B , but that won’t be used
here).
Since we have established that x ∈ A but x ∈/ C ,
we have proved that x ∈ A − C .
d) To show that the set given on the left-hand side is empty, it suffices to assume that x is
some element in that set and derive a contradiction, thereby showing that no such x exists.
So suppose that x ∈ (A − C ) ∩ (C − B) .
Then x ∈ A − C and x ∈ C − B .
The first of these statements implies by definition that x ∈/ C , while the second implies
that x ∈ C .
This is impossible, so our proof by contradiction is complete.
e) To establish the equality, we need to prove inclusion in both directions.
To prove that (B − A) ∪ (C − A) ⊆(B ∪ C ) − A ,
suppose that x ∈ (B − A) ∪ (C − A) .
Then either x ∈ (B − A) or x ∈ (C − A) .
Without loss of generality, assume the former (the proof in the latter case is exactly parallel.)
Then x ∈ B and x ∈/ A . From the first of these assertions, it follows that x ∈ B ∪ C .
Thus we can conclude that x ∈ (B ∪ C ) − A , as desired. For the converse, that is, to show
that (B ∪ C ) − A ⊆ (B − A) ∪ (C − A) , suppose that x ∈ (B ∪ C ) − A .
This means that x ∈ (B ∪ C ) and x ∈/ A .
The first of these assertions tells us that either x ∈ B or x ∈ C .
Thus either x ∈ B − A or x ∈ C − A . In either case, x ∈ (B − A) ∪ (C − A) .
(An alternative proof could be given by using Venn diagrams, showing that both sides
represent the same region.)

31 19. Show that if A and B are sets, then

Ans

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

32 Show that if A and B are sets with A ⊆ B , then
a) A ∪ B = B .
b) A ∩ B = A.

Ans a) It is always the case that B ⊆ A ∪ B , so it remains to show that A ∪ B ⊆ B .

But this is clear because if x ∈ A ∪ B , then either x ∈ A , in which case x ∈ B (because
we are given A ⊆ B ) or x ∈ B ; in either case x ∈ B .
b) It is always the case that A ∩ B ⊆ A , so it remains to show that A ⊆ A ∩ B .
But this is clear because if x ∈ A , then x ∈ B as well (because we are given A ⊆ B ), so x
∈ A∩B.

33 Prove the first associative law from by showing that if A, B , and C are sets, then
A ∪ (B ∪ C) = (A ∪ B) ∪ C.

Ans x ∈ A ∪ (B ∪ C) ≡ (x ∈ A) ∨ (x ∈ (B ∪ C)) ≡ (x ∈ A) ∨ (x ∈ B ∨ x ∈ C) ≡ (x ∈ A ∨
x ∈ B) ∨ (x ∈ C) ≡ x ∈ (A ∪ B) ∪ C

34 Prove the second associative law from by showing that if A, B , and C are sets, then
A ∩ (B ∩ C) = (A ∩ B) ∩ C.

Ans First we show that every element of the left-hand side must be in the right-hand side as well.
If x ∈ A∩(B ∩C ) , then x must be in A and also in B ∩ C .
Hence x must be in A and also in B and in C .
Since x is in both A and B , we conclude that x ∈ A ∩ B .
This, together with the fact that x ∈ C tells us that x ∈ (A ∩ B) ∩ C , as desired.
The argument in the other direction (if x ∈ (A ∩ B) ∩ C then x must be in A ∩ (B ∩ C ) )
is nearly identical.

35 Prove the first distributive law from by showing that if A, B , and C are sets, then
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).

Ans x ∈ A ∪ (B ∩ C) ≡ (x ∈ A) ∨ (x ∈ (B ∩ C)) ≡ (x ∈ A) ∨ (x ∈ B ∧ x ∈ C) ≡
(x ∈ A ∨ x ∈ B) ∧ (x ∈ A ∨ x ∈ C) ≡ x ∈ (A ∪ B) ∩ (A ∪ C)

36 Let A, B , and C be sets. Show that (A − B) − C = (A − C) − (B − C).

Ans First suppose x is in the left-hand side.

Then x must be in A but in neither B nor C .
Thus x ∈ A − C , but x ∈/ B − C , so x is in the right-hand side.
Next suppose that x is in the right-hand side.
Thus x must be in A − C and not in B − C .
The first of these implies that x ∈ A and x ∈/ C .
But now it must also be the case that x ∈/ B , since otherwise we would have x ∈ B − C .
Thus we have shown that x is in A but in neither B nor C , which implies that x is in the
left-hand side.

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

37 Let A = {0, 2, 4, 6, 8, 10}, B = {0, 1, 2, 3, 4, 5, 6}, and C = {4, 5, 6, 7, 8, 9, 10}. Find
a) A ∩ B ∩ C.
b) A ∪ B ∪ C.
c) (A ∪ B) ∩ C.
d) (A ∩ B) ∪ C.

Ans a) {4,6}
b) {0,1,2,3,4,5,6,7,8,9,10}
c) {4, 5, 6, 8, 10}
d) {0,2,4, 5,6,7,8,9,10}

38 Determine whether f is a function from the set of all bit strings to the set of integers if
a) f (S) is the position of a 0 bit in S.
b) f (S) is the number of 1 bits in S.
c) f (S) is the smallest integer i such that the ith bit of S is 1 and f (S) = 0 when S is the empty string,
the string with no bits.

Ans a) Not a function

b) A function
c) Not a function

39 Find the domain and range of these functions. Note that in each case, to find the domain, determine
the set of elements assigned values by the function.
a) the function that assigns to each bit string the number of ones in the string minus the number of
zeros in the string
b) the function that assigns to each bit string twice the number of zeros in that string
c) the function that assigns the number of bits left over when a bit string is split into bytes (which
are blocks of 8 bits)
d) the function that assigns to each positive integer the largest perfect square not exceeding this
integer

Ans a) Domain the set of bit strings; range the set of integers
b) Domain the set of bit strings; range the set of even nonnegative integers
c) Domain the set of bit strings; range the set of nonnegative integers not exceeding 7
d) Domain the set of positive integers; range the set of squares of positive integers = {1, 4, 9, 16,...}

40 Find the domain and range of these functions.

a) the function that assigns to each pair of positive integers the maximum of these two integers
b) the function that assigns to each positive integer the number of the digits 0, 1, 2, 3, 4, 5, 6, 7, 8,
9 that do not appear as decimal digits of the integer
c) the function that assigns to a bit string the number of times the block 11 appears
d) the function that assigns to a bit string the numerical position of the first 1 in the string and that
assigns the value 0 to a bit string consisting of all 0s

Ans a) Domain Z+×Z+; range Z+

b) Domain Z+; range {0, 1, 2, 3, 4, 5, 6, 7, 8, 9}
c) Domain the set of bit strings; range N
d) Domain the set of bit strings; range N

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

41 Determine whether each of these functions from {a, b, c, d } to itself is one-to-one and onto
a) f (a) = b, f (b) = a, f (c) = c, f (d ) = d
b) f (a) = b, f (b) = b, f (c) = d , f (d ) = c
c) f (a) = d , f (b) = b, f (c) = c, f (d ) = d

Ans (a) Onto

(b) One-to-one
(c) One-to-one

42 Determine whether f : Z × Z → Z is onto if

a) f (m, n) = 2m − n.
b) f (m, n) = m2 − n2 .
c) f (m, n) = m + n + 1.
d) f (m, n) = |m| − |n|.
e) f (m, n) = m2 − 4.

Ans a) This is clearly onto, since f (0, −n) = n for every integer n .
b) This is not onto, since, for example, 2 is not in the range. To see this, if m2 − n2 =
(m − n)(m + n) = 2 , then m and n must have same parity (both even or both odd). In
either case, both m − n and m + n are then even, so this expression is divisible by 4 and
hence cannot equal 2 .
c) This is clearly onto, since f (0, n − 1) = n for every integer n .
d) This is onto. To achieve negative values we set m = 0 , and to achieve nonnegative values
we set n = 0 . e) This is not onto, for the same reason as in part (b). In fact, the range here
is clearly a subset of the range in that part.

43 Determine whether the function f: Z × Z → Z is onto if

a) f(m, n) = m + n.
b) f(m, n) = m2 + n2 .
c) f(m, n) = m.
d) f(m, n) = |n|.
e) f(m, n) = m − n.

Ans a) Onto
b) Not onto
c) Onto
d) Not onto
e) Onto

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu

44 Consider these functions from the set of teachers in a school. Under what conditions is the function
one-to-one if it assigns to a teacher his or her
a) office.
b) assigned bus to chaperone in a group of buses taking students on a field trip.
c) salary.
d) social security number

Ans a) Depends on whether teachers share offices

b) One to-one assuming only one teacher per bus
c) Most likely not one-to-one, especially if salary is set by a collective bargaining agreement
d) One-to-one

45 Give an explicit formula for a function from the set of integers to the set of positive integers that
is
a) one-to-one, but not onto.
b) onto, but not one-to-one.
c) one-to-one and onto.
d) neither one-to-one nor onto

Ans a) The function f (x) with f (x) = 3x + 1 when x ≥ 0 and f (x) = −3x + 2 when x < 0
b) f (x) = |x| + 1
c) The function f (x) with f (x) = 2x + 1 when x ≥ 0 and f (x) = −2x when x < 0
d) f (x) = x2 + 1

46 Determine whether each of these functions is a bijection from R to R.

a) f (x) = 2x + 1
b) f (x) = x 2 + 1
c) f (x) = x 3
d) f (x) = (x 2 + 1)/(x 2 + 2)

Ans a) Yes
b) No
c) Yes
d) No

DMPT-III SEM CT- Nileshsingh V. Thakur & Akshay Kadu