TEST BANK FOR Topology 2nd Edition by James Munkres

Chapter 1 Set Theory and Logic
x1 Fundamental Concepts
Exercise 1.1
Check the distributive laws for [ and \ and DeMorgan's laws.
Solution:
Suppose that A, B, and C are sets. First we show that A \ (B [ C) = (A \ B) [ (A \ C).
Proof. We show this as a series of logical equivalences:
x 2 A \ (B [ C) , x 2 A ^ x 2 B [ C
, x 2 A ^ (x 2 B _ x 2 C)
, (x 2 A ^ x 2 B) _ (x 2 A ^ x 2 C)
, x 2 A \ B _ x 2 A \ C
, x 2 (A \ B) [ (A \ C) ;
which of course shows the desired result.
Next we show that A [ (B \ C) = (A [ B) \ (A [ C).
Proof. We show this in the same way:
x 2 A [ (B \ C) , x 2 A _ x 2 B \ C
, x 2 A _ (x 2 B ^ x 2 C)
, (x 2 A _ x 2 B) ^ (x 2 A _ x 2 C)
, x 2 A [ B ^ x 2 A [ C
, x 2 (A [ B) \ (A [ C) ;
which of course shows the desired result.
Now we show the rst DeMorgan's law that A 􀀀 (B [ C) = (A 􀀀 B) \ (A 􀀀 C).
Proof. We show this in the same way:
x 2 A 􀀀 (B [ C) , x 2 A ^ x =2 B [ C
, x 2 A ^ :(x 2 B _ x 2 C)
, x 2 A ^ (x =2 B ^ x =2 C)
, (x 2 A ^ x =2 B) ^ (x 2 A ^ x =2 C)
, x 2 A 􀀀 B ^ x 2 A 􀀀 C
, x 2 (A 􀀀 B) \ (A 􀀀 C) ;
which is the desired result.
Lastly we show that A 􀀀 (B \ C) = (A 􀀀 B) [ (A 􀀀 C).
Page 1
Proof. Again we use a sequence of logical equivalences:
x 2 A 􀀀 (B \ C) , x 2 A ^ x =2 B \ C
, x 2 A ^ :(x 2 B ^ x 2 C)
, x 2 A ^ (x =2 B _ x =2 C)
, (x 2 A ^ x =2 B) _ (x 2 A ^ x =2 C)
, x 2 A 􀀀 B _ x 2 A 􀀀 C
, x 2 (A 􀀀 B) [ (A 􀀀 C) ;
as desired.
Exercise 1.2
Determine which of the following statements are true for all sets A, B, C, and D. If a double implication
fails, determine whether one or the other of the possible implications holds. If an equality fails, determine
whether the statement becomes true if the \equals" symbol is replaced by one or the other of the inclusion
symbols or .
(a) A B and A C , A (B [ C).
(b) A B or A C , A (B [ C).
(c) A B and A C , A (B \ C).
(d) A B or A C , A (B \ C).
(e) A 􀀀 (A 􀀀 B) = B.
(f) A 􀀀 (B 􀀀 A) = A 􀀀 B.
(g) A \ (B 􀀀 C) = (A \ B) 􀀀 (A \ C).
(h) A [ (B 􀀀 C) = (A [ B) 􀀀 (A [ C).
(i) (A \ B) [ (A 􀀀 B) = A.
(j) A C and B D ) (A B) (C D).
(k) The converse of (j).
(l) The converse of (j), assuming that A and B
are nonempty.
(m) (A B) [ (C D) = (A [ C) (B [ D).
(n) (A B) \ (C D) = (A \ C) (B \ D).
(o) A (B 􀀀 C) = (A B) 􀀀 (A C).
(p) (A􀀀B)(C􀀀D) = (AC􀀀BC)􀀀AD.
(q) (A B) 􀀀 (C D) = (A 􀀀 C) (B 􀀀 D).
Solution:
(a) We claim that A B and A C ) A (B [ C) but that the converse is not generally true.
Proof. Suppose that A B and A C and consider any x 2 A. Then clearly also x 2 B since
A B so that x 2 B [ C. Since x was arbitrary, this shows that A (B [ C) as desired.
To show that the converse is not true, suppose that A = f1; 2; 3g, B = f1; 2g, and C = f3; 4g. Then
clearly A f1; 2; 3; 4g = B [ C but it neither true that A B (since 3 2 A but 3 =2 B) nor A C
(since 1 2 A but 1 =2 C).
(b) We claim that A B or A C ) A (B [ C) but that the converse is not generally true.
Proof. Suppose that A B or A C and consider any x 2 A. If A B then clearly x 2 B so that
x 2 B [ C. If A C then clearly x 2 C so that again x 2 B [ C. Since x was arbitrary, this shows
that A (B [ C) as desired.
The counterexample that disproves the converse of part (a), also serves as a counterexample to the
converse here. Again this is because A B [ C but neither A B nor A C, which is to say that
A 6 B and A 6 C. Hence it is not true that A B or A C.
Page 2
(c) We claim that this biconditional is true.
Proof. ()) Suppose that A B and A C and consider any x 2 A. Then clearly also x 2 B and
x 2 C since both A B and A C. Hence x 2 B \ C, which proves that A B \ C since x was
arbitrary.
(() Now suppose that A B \ C and consider any x 2 A. Then x 2 B \ C as well so that x 2 B
and x 2 C. Since x was an arbitrary element of A, this of course shows that both A B and A C
as desired.
(d) We claim that only the converse is true here.
Proof. To show the converse, suppose that A B \ C. It was shown in part (c) that this implies
that both A B and A C. Thus it is clearly true that A B or A C.
As a counterexample to the forward implication, let A = f1g, B = f1; 2g, and C = f3; 4g so that
clearly A B and hence A B or A C is true. However we have that B and C are disjoint so
that B \ C = ?, therefore A 6 ? = B \ C since A 6= ?.
(e) We claim that A 􀀀 (A 􀀀 B) B but that the other direction is not generally true.
Proof. First consider any x 2 A 􀀀 (A 􀀀 B) so that x 2 A but x =2 A 􀀀 B. Hence it is not true that
x 2 A and x =2 B. So it must be that x =2 A or x 2 B. However, since we know that x 2 A, it has
to be that x 2 B. Thus A 􀀀 (A 􀀀 B) B since x was arbitrary.
Now let A = f1; 2g and B = f2; 3g. Then we clearly have A􀀀B = f1g, and thus A􀀀(A􀀀B) = f2g.
So clearly B is not a subset of A 􀀀 (A 􀀀 B) since 3 2 B but 3 =2 A 􀀀 (A 􀀀 B).
(f) Here we claim that A 􀀀 (B 􀀀 A) A 􀀀 B but that the other direction is not generally true.
Proof. First suppose that x 2 A 􀀀 B so that x 2 A but x =2 B. Then it is certainly true that x =2 B
or x 2 A so that, by logical equivalence, it is not true that x 2 B and x =2 A. That is, it is not true
that x 2 B 􀀀 A, which is to say that x =2 B 􀀀 A. Since also x 2 A, it follows that x 2 A 􀀀 (B 􀀀 A),
which shows the desired result since x was arbitrary.
To show that the other direction does not hold consider the counterexample A = f1; 2g and B =
f2; 3g. Then B 􀀀 A = f3g so that A 􀀀 (B 􀀀 A) = f1; 2g = A. We also have that A 􀀀 B = f1g so
that 2 2 A 􀀀 (B 􀀀 A) but 2 =2 A 􀀀 B. This suces to show that A 􀀀 (B 􀀀 A) 6 A 􀀀 B.
(g) We claim that equality holds here, i.e. that A \ (B 􀀀 C) = (A \ B) 􀀀 (A \ C).
Proof. () Suppose that x 2 A \ (B 􀀀 C) so that x 2 A and x 2 B 􀀀 C. Thus x 2 B but x =2 C.
Since both x 2 A and x 2 B we have that x 2 A \ B. Also since x =2 C it clearly must be that
x =2 A \ C. Hence x 2 (A \ B) 􀀀 (A \ C), which shows the forward direction since x was arbitrary.
() Now suppose that x 2 (A \ B) 􀀀 (A \ C). Hence x 2 A \ B but x =2 A \ C. From the former
of these we have that x 2 A and x 2 B, and from the latter it follows that either x =2 A or x =2 C.
Since we know that x 2 A, it must therefore be that x =2 C. Hence x 2 B 􀀀 C since x 2 B but
x =2 C. Since also x 2 A we have that x 2 A \ (B 􀀀 C), which shows the desired result since x was
arbitrary.
(h) Here we claim that A [ (B 􀀀 C) (A [ B) 􀀀 (A [ C) but that the forward direction is not
generally true.
Page 3
Proof. First consider any