Bridge to Abstract Mathematics: Mathematical Proof and Structures

34 SETS Chapter 1

To get further evidence, you should test this equation by using sets A, B,

and C of Example 2 and also by drawing Venn diagrams. The results of

this work should support (although of course not prove) the conjecture

that this equation, which asserts that "intersection distributes over union,"

holds for all sets X, Y, and 2. Can you write an analogous equation

representing the statement "union distributes over intersection?Write

this equation out, test it with sets A, B, and C of Example 2; then test it by

drawing Venn diagrams. After doing all this, you should be ready for Con-

jecture 3.

CONJECTURE 3

Let X, Y, and Z be any sets. Then:

(h) X n (Y u Z) = (X n Y) u (Xn Z)

(i) Xu(YnZ)=(XuY)n(XuZ)

These equations, when proved, will be known as the distributive laws of

set theory.

DE MORGAN'S LAWS

Thus far, we have not looked for any properties of sets that describe how

complementation interacts with union and intersection. We might hope to

find a property by which we could express the complement of the union

(X u Y)' of two sets X and Y in terms of the complements X' and Y' of

the individual sets, and similarly for (X n Y)'. The "obvious" guesses are:

(X u Y)' = X' u Y' and (X n Y)' = X' n Y'

As in previous situations, you should test these equations with some ex-

amples. Compute (X u Y)', X' u Y', (X n Y)', and X' n Y' for the pairs of

sets A and B of Example 2; do the same for sets A and C of the same ex-

ample. Next, construct Venn diagrams corresponding to each of the four

sets.

On the basis of your work, you should not only have rejected the pre-

ceding equations, but also should have discovered two replacement equa-

tions that seem, on the basis of this evidence, to be promising candidates

for theorems of set theory:

CONJECTURE 4

Let X and Y be sets. Then:

(j) (X u Y)' = X' n Y'

(k) (X n Y)' = X' u Y'

h These equations, when proved, will be referred to as De Morgan's laws of