Simple theorems in the algebra of sets

This entry states, without proof, some of the elementary properties of the algebra of union (infix ∪), intersection (infix ∩), and complementation (postfix ') of sets. This algebra, called Boolean algebra, describes the properties of the subsets of a given universal set, denoted U. Let {} denote the empty set.

These properties can be visualized with Venn diagrams. They also follow from the fact that the power set of any U, denoted P(U), is a Boolean lattice. The properties marked with a "*" together form an interpretation of Huntington's (1904) postulates for Boolean algebra.

Elementary discrete mathematics courses sometimes leave students with the impression that the subject matter of set theory is no more than these properties. For more about elementary set theory, see set and naive set theory. For a more introduction to set theory at a higher level, see also axiomatic set theory, Cantor–Bernstein–Schroeder theorem, Cantor's diagonal argument, Cantor's first uncountability proof, Cantor's theorem, well-ordering theorem, axiom of choice, and Zorn's lemma.

Define the infix binary operation "\" as B \A = (A ∪B′)′ = A′ ∩B.

PROPOSITION 1. For any U and subsets A, B, and C of U:

{}′ = U;
U′ = {};
A ∩ {} = {};
A ∪ {} = A;
A \ {} = A;
{} \ A = {};
A ∩ U = A;
A ∪ U = U; *
A ′∪ A = U; *
A \ A = {};
U \ A = A′;
A \ U = {};
A ∩ B = {} if and only if B \ A = B;
A′′ = A.

PROPOSITION 2. For any sets A, B, and C:

A ∩ A = A;
A ∪ A = A;
A ∩ B = B ∩ A; *
A ∪ B = B ∪ A; *
(A ∪ B) \ A = B \ A;
(A ∩ B) ∩ C = A ∩ (B ∩ C);
(A ∪ B) ∪ C = A ∪ (B ∪ C);
C \ (A ∩ B) = (C \ A) ∪ (C \ B);
C \ (A ∪ B) = (C \ A) ∩ (C \ B);
C \ (B \ A) = (A ∩ C) ∪ (C \ B);
(B \ A) ∩ C = (B ∩ C) \ A = B ∩ (C \ A);
(B \ A) ∪ C = (B ∪ C) \ (A \ C).

PROPOSITION 3 (distributive laws): For any sets A, B, and C:

A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C); *
A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C). *

PROPOSITION 4. Some properties of ⊆:

A ⊆ B if and only if A ∩ B = A;
A ⊆ B if and only if A ∪ B = B;
A ⊆ B if and only if B' ⊆ A;
A ⊆ B if and only if A \ B = {};
A ∩ B ⊆ A ⊆ A ∪ B.

References

Edward Huntington (1904) "Sets of independent postulates for the algebra of logic," Transactions of the American Mathematical Society 5: 288-309.
Whitesitt, J. E. (1961) Boolean Algebra and Its Applications. Addison-Wesley. Dover reprint, 1999.