32 SETS Chapter 1CONJECTURE 2
Let X, Y, and Z be any sets. Then:
(f) Xn(YnZ)=(XnY)nZ and Xu(YuZ)=(XuY)uZ
(g) XnY=YnX and XuY=YuXDeveloping the analogy between the algebra of sets and the algebra of
numbers, we are led to view the equations in (f), once they've been proved,
as associative laws for intersection and union of sets and those in (g) as
commutative laws for intersection and union. An associative law involves
one binary operation and is the basis for our ability to apply such an op-
eration to three or more sets, rather than just to two. Specifically, the law
tells us to apply the operation to the objects two at a time, starting at either
end of the expression; the result will be the same whether we work left to
right or right to left. The upshot of the associative laws for union and in-
tersection is that the union of three or more sets consists of all the objects
in any of the sets, grouped together within one set, while the intersection of
three or more sets consists of the objects common to all the sets. Com-
mutativity says that, in computing unions and intersections of two sets, the
order in which the two sets are listed is irrelevant.
DISTRIBUTIVITY
Distributivity, familiar as a property of the real numbers, has its analogy
in set theory. Unlike commutativity and associativity, distributivity in-
volves two operations at a time within one equation. Over the real num-
bers, the property that a(b + c) = ab + ac for all a, b, c E R is distributivity
of multiplication over addition. By inquiring whether intersection distrib-
utes over union, we would be asking whether there is a general equivalent
way of expressing A n (B u C). Motivated by the associative law (in which
a "shift" of parentheses leads to an identity), we could be tempted to con-
jecture (wrongly, we will soon see) that A n (B u C) = (A n B) u C for
any three sets A, B, and C. The following example explores this possibility.
EXAMPLE 3 With U = (1, 2, 3,... , 9, 10)' let A = (2, 3, 5, 81, B = (1, 2,
5,6,7, lo), and D = (8). Compute (A n B) u D and A n (B u D).
Solution A n B = (2, 5) so that (A n B) u D = (2, 5,8), while B u D =
{1,2,5,6,7,8,10) so that A n (B u D) = {2,5,8). In this example
(A n B) u D and A n (B u D) are equal.The result of Example 3 supports our conjecture. Do you think that
(X n Y) u Z = X n (Y u Z) holds for any three sets X, Y, and Z? Test
this conjecture further by using the three sets A, B and C of Example 2.
Also note the comparison of the Venn diagrams in Figure 1.8. In this case
the regions in the two Venn diagrams do not correspond. This should