S. Lang Solution Key to Assignment #2 (40 pts.) Feb.
11, 2000
1.
(12 pts.) Prove each of the following
statements in Parts (a) - (f), assuming the symbols A, B, and C represent (arbitrary) sets. Your proof must be based on the appropriate
definitions and the laws and theorems listed below (but only these). Be sure to
explain each step of your proof.
(Commutative Law) A
È B = B È A,
A Ç B = B Ç A.
(Associative
Law) (A È B)
È C = A È (B
È C), (A Ç B) Ç C = A Ç (B Ç C).
(Distributive
Law) A È (B
Ç C) = (A È B) Ç (A
È C) , A Ç (B È C) = (A Ç B) È (A
Ç C)
.
(Idempotent Property) A È A
= A, A Ç A = A.
(De Morgan’s Law) Ø(A
È B) = ØA
Ç ØB, Ø(A Ç B)
= ØA È ØB.
(Double
Negation) Ø(ØA) = A.
(Complementary
Property) A Ç ØA = Æ, A
È ØA = U, where U denotes the universe.
Theorem: (a) A Ç B Ì A.
(b) A Ì A
È B. (c) A Ç Æ = Æ. (d) A È Æ = A.
(e) A Ì B
iff ØB Ì ØA
(f) A Ì B iff A Ç ØB = Æ. (g) A - B = A Ç ØB. (h) (A Ì B and B Ì C) implies A Ì C. (i) A Ì B implies A È C Ì B È C. (j) A Ì B implies A Ç C Ì B Ç C.
(a)
If
A Ç B = C, then C Ì A and C Ì B.
Since C = A Ç B
---- (1) by assumption, and A Ç B Ì A ---- (2) by the above theorem (a), so substituting (1) into (2) proves C Ì A. Similarly, since A Ç B = B Ç A Ì B ---- (3) by the commutative law and by
the above theorem (a), substituting (1) into (3) yields C Ì B.
(b)
Ø(A Ç ØB) = ØA È B.
Ø(A Ç ØB) = ØA È Ø(ØB) by De Morgan’s law
= ØA È B
because ØØB =
B by Double Negation.
(c)
(A - B) Ç B = Æ.
(Solution one) We prove (A
- B)
Ç B =
Æ by
contradiction; that is, we assume there exists x Î (A - B) Ç B ---- (1), then we prove this leads to a contradiction.
From (1), x Î (A - B) ---- (2) and x Î B ----
(3), by the definition of Ç. From (2) and the definition of set difference, x Î A and x Ï B, but x Ï B contradicts (3). Thus, we proved (A - B) Ç B = Æ.
(Solution two) (A - B)
Ç B =
(A Ç ØB) Ç B
by the above theorem (g)
= A Ç (ØB Ç B)
by the associative law
= A Ç Æ because ØB Ç B =Æ by the definition of ØB
= Æ by the above theorem (c).
(d)
A Ì A È B È C.
= A È B È C by the associative law.
(e)
If
B Ì C, then A ´ B Ì A ´ C.
Let (x, y) Î A ´ B ---- (1), we need to prove (x, y) Î A ´ C ---- (2).
From
(1), x Î A ---- (3) and y Î B ----
(4), by the definition of A ´ B.
Since B Ì C
by assumption, so (4) implies y Î C ----
(5). Thus, combining (3) and (5) proves
(x, y) Î A ´ C by the definition of A ´ C, so (2) is proved.
(f)
(A È B) Ç A = (A Ç B)
È A.
(A È B)
Ç A =
(A Ç A) È (B Ç A) by the associative law
= A È (B
Ç A)
by the idempotent law A Ç A =
A
= (A Ç B)
È A
by the commutative law.
2.
(4 pts.) Disprove
each of the following statements by using a "small" counter- example,
where symbols A, B, and C represent sets.
(a)
If
A Ç B = Æ, then B = Æ.
Let (i.e., choose) A = {1}, B = {2}. Then A
Ç B
= Æ, but B
¹ Æ.
(b)
If
A Ì B È C, then A Ì B or
A Ì C.
Let A =
{1, 2}, B = {1}, and C = {2}. Then, B È C
= {1, 2} = A, so A Ì B È C is true. However, both A Ì B and A Ì C
are false.
3.
(12
pts.) Prove each of the following statements by using the same instructions as
in Question 1.
(a)
If
B Ì C, then A - C Ì A - B.
Let x Î A - C ----
(1), we need to prove x Î A - B ----
(2).
From (1), we have x Î A ---- (3) and x Ï C ---- (4), by the definition
of A - C.
Since B Ì C
by assumption, so (4) implies x Ï B ---- (5). Combining (3) and (5) yields x Î A - B
by the definition of A - B,
which proves (2).
(b)
If
A ´ B =
Æ, then A
= Æ or B = Æ.
We proves the contrapositive statement; that is, we
prove if A ¹ Æ and B ¹ Æ ---- (1), then A ´ B ¹ Æ ---- (2).
From (1), there exists x Î A
and there exists y Î B ----
(3). Thus, (3) implies (x, y)
Î A ´ B, by the definition of A ´ B.
Thus, A ´ B ¹ Æ, which proves (2).
(c)
A - (B È C)
= (A - B) - C.
A - (B È C)
= A Ç Ø(B È C)
by the above theorem (g)
= A Ç (ØB Ç ØC)
by De Morgan’s law
= (A Ç ØB) Ç ØC by the associative law
= (A - B)
Ç ØC by
the above theorem (g)
= (A - B)
- C by
the above theorem (g).
(d)
If
Power(A) Ì Power(B),
then A Ì B.
Since A Î Power(A)
---- (1) by the definition of Power(A),
and Power(A) Ì Power(B)
---- (2) by assumption, so combining (1) and (2) yields A Î Power(B) ---- (3). Since Power(B) contains all the subsets of B as its elements (by definition), so
(3) implies A is a subset of B. i.e., A Ì B.
4.
(6 pts.) Suppose the symbols A, B,
and C represent three arbitrary finite sets. Answer the following two questions:
(a)
If
|A Ç B| = 3 and |A - B|
= 5, determine |A| and explain your
answer.
Since A =
(A - B) È (A Ç B), and (A - B)
Ç (A
Ç B)
= Æ (this is proved in the course notes), so the
Sum Principle implies |A| = |A - B| + |A Ç B|
= 3 + 5 = 8.
(b)
Suppose
|A Ç B| = 3, |B Ç C|
= 2, |A Ç C|
= 1, |A Ç B Ç C|
= 0, |A - B|
= 5, |B - C|
= 8, and |C - B|
= 4. Determine |A È B È C| and explain your answer.
Using the same argument as in Part (a), we have
|B| = |B - C| + |B Ç C|
= 8 + 2 = 10; and
|C| = |C - B| + |C Ç B|
= 4 + 2 = 6.
Therefore, using the formula proved in the course
notes, |A È B È C|
= |A| + |B| + |C| - |A
Ç B|
- |B
Ç C|
- |A
Ç C|
+ |A Ç B Ç C| = 8 + 10 + 6 – 3 – 2 – 1 + 0 = 18.
5.
(6
pts.) Let A denote a non-empty set of
symbols (i.e., an alphabet), and let W,
X, and Y denote sets of strings over A,
i.e., W Ì A*,
X Ì A*, and Y Ì A*.
(a)
Prove
that if WY Ç XY =
Æ, then W
Ç X
= Æ or Y = Æ.
We prove the contrapositive
statement; that is, we prove if W Ç X ¹ Æ ---- (1) and Y ¹ Æ ---- (2), then WY Ç XY ¹ Æ ---- (3).
From (1), there exists u Î W and u Î X ----
(4), by the definition of W Ç X. From (2), there exists v Î Y ---- (5). From (4) and
(5), we have uw Î WY
and uw Î XY, by the definition of WY and
XY.
Thus, uw Î WY
Ç XY,
which proves (3).
(b)
If
W Ì Y, then prove W* È Y*
= Y*.
We need to prove Y* Ì W* È Y* ---- (1) and W* È Y*
Ì Y*
---- (2), by the definition of set equality for W* È Y* = Y*.
Note that (1) is true
because of the above theorem (b).
To prove (2), let u Î W* È Y* ---- (3), we need to prove u
Î Y*
---- (4). From (3), u Î W* or u Î Y*,
by the definition of W* È Y*. There are now two cases:
(Case 1) Suppose u Î W*. Since W Ì Y by assumption, so W* Ì Y*,
which proves u Î Y*,
so (4) is proved in this case.
(Case 2) Suppose u Î Y*. In this case, (4) is
already true.
Thus, we proved (4) in both
cases, so (2) is proved.