80 Chapter^2
law, has no counterpart in a number field, and both equalities in (3) are
false in a number field, i.e., a+ a f a (excepting a = 0), and aa f a
(excepting a = 0 or 1 ). The cancellation laws do not hold in the calculus
of sets, i.e., from AU B = AU C, or from An B = An C, it does not
follow B = C necessarily.
The calculus of sets presents a remarkable duality: if in any property the
symbols U and n, 0 and U, and/or C and::) are everywhere interchanged,
the resulting property is also valid in the calculus. The calculus of sets is an
example of a Boolean algebra, which is abstractly defined as a mathematical
system with the operations U, n, and' satisfying (1), (2), (4), (5), (6), and
(10) (these axioms are redundant). However, M. H. Stone [17] has shown
that given any Boolean algebra there exists a universal set such that an
algebra of its subsets is isomorphic to the given Boolean algebra.
We should note that the inclusion relation A C B may be defined to
mean A= An B, or B =AU B. Then property (7) may be expressed in
terms of equalities as follows: A= An (AU B) and A= AU (An B).
The difference A - B may be defined as A n B'.
The equalities in (3) are called idempotent laws.
The equalities in (11) are called De Morgan's laws, and show that com-
plementation has the property of interchanging U and n. De Morgan's laws
are valid for arbitrary unions and inters"ections, i.e.,
EXERCISES 2.1
- Prove that the set Q of the rational numbers is denumerable.
- Prove that the set R of the real numbers is uncountable.
- Prove that the set of complex numbers with rational components is
denumerable. · - Prove that a countable union of countable sets is countable.
- Prove that every subset of a countable set is countable.
- Show that if X is·a finite set with n elements, then P(X) has 2n
elements. - Prove each of the following.
(a) (A-B)'=BUA' (b) An(B-C)=AnB-AnC
(c) (A-C)U(B-C) = (AUB)-C
- The symmetric difference of two sets A and B is defined by A 6 B =
(A - B) U (B - A). Prove the following.
(a) A 6 B = B 6 A