Simple theorems in the algebra of sets
The simple theorems in the algebra of sets are some of the elementary properties of the algebra of union (infix ∪), intersection (infix ∩), and complementation (postfix ') of sets.
These properties assume the existence of at least two sets: some universal set, denoted U, and the empty set, denoted {}. This algebra, called Boolean algebra, describes the properties of all possible subsets of U. The operations of union, intersection, and complementation are assumed closed under U.
The properties below are stated without proof, but can be derived from a small number of properties taken as axioms. The properties marked with a "*" make up an interpretation of Huntington's (1904) classic postulate set for Boolean algebra. 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 followed by "L" characterize a lattice.
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.
The properties below include a third binary operation, relative complement, denoted by infix "\". Define the relative complement of A in B as B \A = (A ∪B′)′ = A′ ∩B.
PROPOSITION 1. For any U and any subset A of U:
- {}′ = U;
- U′ = {};
- A \ {} = A;
- {} \ A = {};
- A ∩ {} = {};
- A ∪ {} = A; *
- A ∩ U = A; *
- A ∪ U = U;
- A′ ∪ A = U; *
- A′ ∩ A = {}; *
- A \ A = {};
- U \ A = A′;
- A \ U = {};
- A′′ = A;
- A ∩ A = A;
- A ∪ A = A.
PROPOSITION 2. For any sets A, B, and C:
- A ∩ B = B ∩ A; * L
- A ∪ B = B ∪ A; * L
- A ∪ (A ∩ B) = A; L
- A ∩ (A ∪ B) = A; L
- (A ∪ B) \ A = B \ A;
- A ∩ B = {} if and only if B \ A = B;
- (A′ ∪ B)′ ∪ (A′ ∪ B′)′ = A;
- (A ∩ B) ∩ C = A ∩ (B ∩ C); L
- (A ∪ B) ∪ C = A ∪ (B ∪ C); L
- 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 A′ ∪ 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.