Schaum's Outline of Discrete Mathematics, Third Edition (Schaum's Outlines)

14 SET THEORY [CHAP. 1

1.8 Prove Theorem 1.4. The following are equivalent:A⊆B,A∩B=A,A∪B=B.

SupposeA⊆Band letx∈A. Thenx∈B, hencex∈A∩BandA⊆A∩B. By Theorem 1.3,(A∩B)⊆A. Therefore

A∩B=A. On the other hand, supposeA∩B=Aand letx∈A. Thenx∈(A∩B); hencex∈Aandx∈B.

Therefore,A⊆B. Both results show thatA⊆Bis equivalent toA∩B=A.

Suppose again thatA⊆B. Letx∈(A∪B). Thenx∈Aorx∈B.Ifx∈A, thenx∈BbecauseA⊆B.Ineither

case,x∈B. ThereforeA∪B⊆B. By Theorem 1.3,B⊆A∪B. ThereforeA∪B=B. Now supposeA∪B=Band

letx∈A. Thenx∈A∪Bby definition of the union of sets. Hencex∈B=A∪B. ThereforeA⊆B. Both results

show thatA⊆Bis equivalent toA∪B=B.

ThusA⊆B,A∪B=AandA∪B=Bare equivalent.

VENN DIAGRAMS, ALGEBRA OF SETS, DUALITY

1.9 Illustrate DeMorgan’s Law(A∪B)C=AC∩BCusing Venn diagrams.

Shade the area outsideA∪Bin a Venn diagram of setsAandB. This is shown in Fig. 1-7(a); hence the shaded

area represents(A∪B)C. Now shade the area outsideAin a Venn diagram ofAandBwith strokes in one direction

(////), and then shade the area outsideBwith strokes in another direction (\\\\). This is shown in Fig. 1-7(b); hence the

cross-hatched area (area where both lines are present) representsAC∩BC. Both(A∪B)CandAC∩BCare 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∈Borx∈A, x∈C}=(A∩B)∪(A∩C)

Here we use the analogous logical lawp∧(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 alsoUand∅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 defineA⊕B.)

UsingX\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)