Simple theorems in the algebra of sets

Elementary discrete mathematics courses sometimes leave students with the impression that the subject matter of set theory is no more than 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.

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.

We list without proof several simple properties of the operations of union, intersection, and complementation of sets. These properties can be visualized with Venn diagrams.

Let {} denote the empty set. Then the properties below all follow from the fact that the power set P(U) is a Boolean lattice. The properties marked with a "*" together form an interpretation of Huntington's (1904) postulates for Boolean algebra.

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

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

A ∩ A = A;
A ∪ A = A;
A \ A = {};
A ∩ {} = {};
A ∪ {} = A;
{} \ A = {};
A \ {} = A;
A ∩ B = B ∩ A; *
A ∪ B = B ∪ A; *
A ∩ B = {} if and only if B \ A = B;
(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 2. For any U and subsets A, B, and C of U:

{}′ = U;
U′ = {};
A ∩ U = A;
A ∪ U = U; *
A ′∪ A = U; *
A \ A = {};
U \ A = A′;
A \ U = {};
A′′ = A.

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.