Simple theorems in the algebra of sets
From Wikipedia, the free encyclopedia
Elementary discrete mathematics courses sometimes leave students under an erroneous impression that the subject matter of set theory is the algebra of union, intersection, and complementation of sets. Those topics are treated below: they would typically be classified, as verification of properties of the Boolean algebra of subsets of a given universal set.
For an account of some elementary topics in set theory, see also set, naive set theory, 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, 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.
PROPOSITION 1: For any sets A, B, and C:
-
- A ∩ A = A;
- A ∪ A = A;
- A \ A = {};
- A ∩ B = B ∩ A;
- A ∪ B = 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);
- 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 = B;
- A ∩ B ⊆ A ⊆ A ∪ B;
- A ∩ {} = {};
- A ∪ {} = A;
- {} \ A = {};
- A \ {} = A.
PROPOSITION 2: For any universe U and subsets A, B, and C of U:
-
- A′′ = A;
- B \ A = A' ∩ B;
- (B \ A)' = A ∪ B';
- A ⊆ B if and only if B ⊆ A;
- A ∩ U = A;
- A ∪ U = U;
- U \ A = A′;
- A \ U = {}.
PROPOSITION 3: (distributive laws): For any sets A, B, and C:
-
- (a) A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C);
- (b) A ∪ (B ∩ C) = (A ∪ B) ∩ (A ∪ C).
The above propositions show that the power set P(U) is a Boolean lattice.
