solved problem1
SETS AND SUBSETS
1.1 Which of these sets are equal: {x, y , z}, {z, y, z, x }, {y , x , y, z}, {y, z, x, y }?
They are all equal. Order and repetition do not change a set.
1.2 List the elements of each set where N = {1, 2, 3, …}.
(a) A = {x ? N | 3 < x < 9}
(b) B = {x ? N | x is even, x < 11}
(c) C = {x ? N | 4 + x = 3}
(a) A consists of the positive integers between 3 and 9; hence A = {4, 5, 6, 7, 8}.
(b) B consists of the even positive integers less than 11; hence B = {2, 4, 6, 8, 10}.
(c) No positive integer satis?es 4 + x = 3; hence C = ?, the empty set.
1.3 Let A = {2, 3, 4, 5}.
(a ) Show that A is not a subset of B = {x ? N | x is even}.
(b) Show that A is a proper subset of C = {1, 2, 3, . . ., 8, 9}.
(a) It is necessary to show that at least one element in A does not belong to B. Now 3 ? A and, since B consists
of even numbers, 3 ?/ B; hence A is not a subset of B.
(b) Each element of A belongs to C so A ? C. On the other hand, 1 ? C but 1 ?/ A. Hence A = C. Therefore A
is a proper subset of C.
SET OPERATIONS
1.4 Let U = {1,2 , …, 9} be the universal set, and let
A = {1, 2, 3, 4, 5}, C = {5, 6, 7, 8, 9}, E = {2, 4, 6, 8},
B = {4, 5, 6, 7}, D = {1, 3, 5, 7, 9}, F = {1, 5, 9}.
Find: (a) A ? B and A ? B; (b) A ? C and A ? C ; (c) D ? F and D ? F .
Recall that the union X ? Y consists of those elements in either X or Y (or both), and that the intersection X ? Y consists
of those elements in both X and Y .
(a) A ? B = {1, 2, 3, 4, 5, 6, 7} and A ? B = {4, 5}
(b) A ? C = {1, 2, 3, 4, 5, 6, 7, 8, 9} = U and A ? C = {5}
(c) D ? F = {1, 3, 5, 7, 9} = D and D ? F = (1, 5, 9) = F
Observe that F ? D, so by Theorem 1.4 we must have D ? F = D and D ? F = F.
1.5 Consider the sets in the preceding Problem 1.4. Find:
(a ) AC, BC, DC, EC; (b) A\B, B\A, D\E; (c)A ? B, C ? D, E ? F .
Recall that:
(1) The complements XC consists of those elements in U which do not belong to X.
(2) The difference X\Y consists of the elements in X which do not belong to Y .
(3) The symmetric difference X ? Y consists of the elements in X or in Y but not in both.
Therefore:
(a) AC= {6, 7, 8, 9}; BC= {1, 2, 3, 8, 9}; DC= {2, 4, 6, 8} = E; EC= {1, 3, 5, 7, 9} = D.
(b) A\B = {1, 2, 3}; B\A = {6, 7}; D\E = {1, 3, 5, 7, 9} = D; F\D = ?.
(c) A ? B = {1, 2, 3, 6, 7}; C ? D = {1, 3, 6, 8}; E ? F = {2, 4, 6, 8, 1, 5, 9} = E ? F.
1.6 Show that we can have: (a) A ? B = A ? C without B = C; (b) A ? B = A ? C without B = C .
(a) Let A = {1, 2}, B = {2, 3}, C = {2, 4}. Then A ? B = {2} and A ? C = {2}; but B = C.
(b) Let A = {1, 2}, B = {1, 3}, C = {2, 3}. Then A ? B = {1, 2, 3} and A ? C = {1, 2, 3} but B = C.
1.7 Prove: B\A = B ? AC. Thus, the set operation of difference can be written in terms of the operations of
intersection and complement.
B\A = {x | x ? B, x /? A} = {x | x ? B, x ? AC} = B ? AC.
1.8 Prove Theorem 1.4. The following are equivalent: A ? B, A ? B = A, A ? B = B.
Suppose A ? B and let x ? A. Then x ? B , hence x ? A ? B and A ? A ? B. By Theorem 1.3, (A? B) ? A. Therefore
A ? B = A. On the other hand, suppose A ? B = A and let x ? A. Then x ? (A ? B); hence x ? A and x ? B.
Therefore, A ? B. Both results show that A ? B is equivalent to A ? B = A.
Suppose again that A ? B. Let x ? (A ? B). Then x ? A or x ? B. If x ? A, then x ? B because A ? B. In either
case, x ? B. Therefore A ? B ? B. By Theorem 1.3, B ? A ? B. Therefore A ? B = B. Now suppose A ? B = B and
let x ? A. Then x ? A ? B by de?nition of the union of sets. Hence x ? B = A ? B. Therefore A ? B. Both results
show that A ? B is equivalent to A ? B = B.
Thus A ? B, A ? B = A and A ? B = B are equivalent.
VENN DIAGRAMS, ALGEBRA OF SETS, DUALITY
1.9 Illustrate DeMorgan’s Law (A ? B)C= AC? BCusing Venn diagrams.
Shade the area outside A ? B in a Venn diagram of sets A and B. This is shown in Fig. 1-7(a); hence the shaded
area represents (A ? B)C. Now shade the area outside A in a Venn diagram of A and B with strokes in one direction
(////), and then shade the area outside B with strokes in another direction (\\\\). This is shown in Fig. 1-7(b); hence the
cross-hatched area (area where both lines are present) represents AC? BC. Both (A?B)CandAC ?BC are represented
by the same area; thus the Venn diagram indicates (A ? B)C= AC? BC. (We emphasize that a Venn diagram is not a
formal proof, but it can indicate relationships between sets.)
Fig. 1-7
1.10 Prove the Distributive Law: A ? (B ? C) = (A ? B) ? (A ? C).
A ? (B ? C) = {x | x ? A, x ? (B ? C)}
= {x | x ? A, x ? B or x ? A, x ? C} = (A ? B) ? (A ? C)
Here we use the analogous logical law p ? (q ? r) ? (p ? q) ? (p ? r) where ? denotes “and” and ? denotes “or.”
1.11 Write the dual of: (a) (U ? A) ? (B ? A) = A; (b) (A ? U) ? (? ? AC) = ?.
Interchange ? and ? and also U and ? in each set equation:
(a) (? ? A) ? (B ? A) = A; (b) (A ? ?) ? (U ? AC) = U.
1.12 Prove: (A ? B)\(A ? B) = (A\B) ? (B\A). (Thus either one may be used to de?ne A ? B.)
Using X\Y = X ? YCand the laws in Table 1.1, including DeMorgan’s Law, we obtain:
(A ? B)\(A ? B) = (A ? B) ? (A ? B)C= (A ? B) ? (AC? BC)
= (A ? AC) ? (A ? BC) ? (B ? AC) ? (B ? BC)
= ? ? (A ? BC) ? (B ? AC) ? ?
= (A ? BC) ? (B ? AC) = (A\B) ? (B\A)
1.13 Determine the validity of the following argument:
S1: All my friends are musicians.
S2: John is my friend.
S3: None of my neighbors are musicians.
S : John is not my neighbor.
The premises S1and S3lead to the Venn diagram in Fig. 1-8(a). By S2, John belongs to the set of friends which is
disjoint from the set of neighbors. Thus S is a valid conclusion and so the argument is valid.
Fig. 1-8
FINITE SETS AND THE COUNTING PRINCIPLE
1.14 Each student in Liberal Arts at some college has a mathematics requirement A and a science requirement B .
A poll of 140 sophomore students shows that:
60 completed A, 45 completed B , 20 completed both A and B.
Use a Venn diagram to ?nd the number of students who have completed:
(a) At least one of A and B; (b) exactly one of A or B ; (c) neither A nor B .
Translating the above data into set notation yields:
n(A) = 60, n(B) = 45, n(A ? B) = 20, n(U) = 140
Draw a Venn diagram of sets A and B as in Fig. 1-1(c). Then, as in Fig. 1-8(b), assign numbers to the four regions as
follows:
20 completed both A and B, so n(A ? B) = 20.
60 ? 20 = 40 completed A but not B, so n(A\B) = 40.
45 ? 20 = 25 completed B but not A, so n(B\A) = 25.
140 ? 20 ? 40 ? 25 = 55 completed neither A nor B.
By the Venn diagram:
(a) 20 + 40 + 25 = 85 completed A or B. Alternately, by the Inclusion–Exclusion Principle:
n(A ? B) = n(A) + n(B) ? n(A ? B) = 60 + 45 ? 20 = 85
(b) 40 + 25 = 65 completed exactly one requirement. That is, n(A ? B) = 65.
(c) 55 completed neither requirement, i.e. n(AC? BC) = n[(A ? B)C] = 140 ? 85 = 55.
1.15 In a survey of 120 people, it was found that:
65 read Newsweek magazine, 20 read both Newsweek and Time,
45 read Time,
42 read Fortune,
25 read both Newsweek and Fortune,
15 read both Time and Fortune,
8 read all three magazines.
(a) Find the number of people who read at least one of the three magazines.
(b) Fill in the correct number of people in each of the eight regions of the Venn diagram in Fig. 1-9(a) where
N , T , and F denote the set of people who read Newsweek, Time, and Fortune, respectively.
(c) Find the number of people who read exactly one magazine.
Fig. 1-9
(a) We want to ?nd n(N ? T ? F ). By Corollary 1.10 (Inclusion–Exclusion Principle),
n(N ? T ? F )= n(N ) + n(T ) + n(F ) ? n(N ? T ) ? n(N ? F ) ? n(T ? F ) + n(N ? T ? F )
= 65 + 45 + 42 ? 20 ? 25 ? 15 + 8 = 100
(b) The required Venn diagram in Fig. 1-9(b) is obtained as follows:
8 read all three magazines,
20 ? 8 = 12 read Newsweek and Time but not all three magazines,
25 ? 8 = 17 read Newsweek and Fortune but not all three magazines,
15 ? 8 = 7 read Time and Fortune but not all three magazines,
65 ? 12 ? 8 ? 17 = 28 read only Newsweek,
45 ? 12 ? 8 ? 7 = 18 read only Time,
42 ? 17 ? 8 ? 7 = 10 read only Fortune,
120 ? 100 = 20 read no magazine at all.
(c) 28 + 18 + 10 = 56 read exactly one of the magazines.
1.16 Prove Theorem 1.9. Suppose A and B are ?nite sets. Then A ? B and A ? B are ?nite and
n(A ? B) = n(A) + n(B) ? n(A ? B)
If A and B are ?nite then, clearly, A ? B and A ? B are ?nite.
Suppose we count the elements in A and then count the elements in B.
Then every element in A ? B would be counted twice, once in A and once in B. Thus
n(A ? B) = n(A) + n(B) ? n(A ? B)
1.17 Let A = [{1, 2, 3}, {4, 5}, {6, 7, 8}]. (a) List the elements of A; (b) Find n(A).
(a) A has three elements, the sets {1, 2, 3}, {4, 5}, and {6, 7, 8}.
(b) n(A) = 3.
1.18 Determine the power set P (A) of A = {a, b, c, d }.
The elements of P (A) are the subsets of A. Hence
P (A) = [A, {a, b, c}, {a, b, d}, {a, c, d}, {b, c, d}, {a, b}, {a, c}, {a, d}, {b, c}, {b, d},
{c, d}, {a}, {b}, {c}, {d}, ?]
As expected, P (A) has 24= 16 elements.
1.19 Let S = {a , b, c, d, e, f , g}. Determine which of the following are partitions of S:
(a) P1=[{a , c, e}, {b}, {d, g}],
(c) P3=[{a, b, e, g}, {c}, {d , f }],
(b) P2=[{a , e, g}, {c, d }, {b, e, f }], (d ) P4=[{a, b, c, d , e, f , g}].
(a) P1is not a partition of S since f ? S does not belong to any of the cells.
(b) P2is not a partition of S since e ? S belongs to two of the cells.
(c) P3is a partition of S since each element in S belongs to exactly one cell.
(d) P4 is a partition of S into one cell, S itself.
1.20 Find all partitions of S = {a, b, c, d }.
Note ?rst that each partition of S contains either 1, 2, 3, or 4 distinct cells. The partitions are as follows:
(1) [{a, b, c, d}]
(2) [{a}, {b, c, d}], [{b}, {a, c, d}], [{c}, {a, b, d}], [{d}, {a, b, c}],
[{a, b}, {c, d}], [{a, c}, {b, d}], [{a, d}, {b, c}]
(3) [{a}, {b}, {c, d}], [{a}, {c}, {b,d}], [{a}, {d}, {b, c}],
[{b}, {c}, {a, d}], [{b}, {d}, {a, c}], [{c}, {d}, {a, b}]
(4) [{a}, {b}, {c}, {d}]
There are 15 different partitions of S.
1.21 Let N = {1, 2, 3,…} and, for each n ? N, Let An={n, 2n, 3n,…}. Find:
(a ) A3? A5; (b) A4? A5; (c)i?QAiwhere Q = {2, 3, 5, 7, 11, …} is the set of prime numbers.
(a) Those numbers which are multiples of both 3 and 5 are the multiples of 15; hence A3? A5= A15.
(b) The multiples of 12 and no other numbers belong to both A4 and A6, hence A4 ? A6=A12 .
(c) Every positive integer except 1 is a multiple of at least one prime number; hence
Ai= {2, 3, 4, . . .} = N\{1}
i?Q
1.22 Let {Ai| i ? I } be an indexed class of sets and let i0? I . Prove
Let x ?i?IAi then x ? Aifor every i ? I. In particular, x ? Ai0 . Hencei?lAi ? Ai0 . Now let y ? Ai0 . Since
i0? I, y ?i?lAi. Hence Ai0 ?i?lAi.