There some identities which hold for sets. Some branches of mathematics—e.g. analysis—use them frequently in proofs. Knowing their names helps one read proofs.
Union and Intersection
Two operators in set algebra are union and intersection. Like addition and multiplication they are commutative and associative.
However, as we shall see, set algebra matches more closely with Boolean algebra (aka Boolean logic). That is, union and intersection are analogous to logical ∨ (or) and ∧ (and).
Addition and multiplication usually form a ring, and maybe even a field. The precise algebraic structure depends upon the set of numbers. Sets under union and intersection, and propositions under logical or and and form Boolean algebras, which are a type of lattice.
commutative laws
- A ⋃ B = B ⋃ A
- A ⋂ B = B ⋂ A
associative laws
- (A ⋃ B) ⋃ C = A ⋃ (B ⋃ C)
- (A ⋂ B) ⋂ C = A ⋂ (B ⋂ C)
distributive laws
The analogy of union and intersection with addition and multiplication breaks down when we come to the distributive laws:
- A ⋃ (B ⋂ C) = (A ⋃ B) ⋂ (A ⋃ C)
- A ⋂ (B ⋃ C) = (A ⋂ B) ⋃ (A ⋂ C)
The difference is whereas multiplication distributes over addition, addition does not distribute over multiplication.
idempotent laws
- A ⋃ A = A
- A ⋂ A = A
absorption laws
- A ⋃ (A ⋂ B) = A
- A ⋂ (A ⋃ B) = A
Empty Set and Universal Set
The empty set contains nothing. The universal set contains "everything".
If we have any sets, then we also have an empty set.
The universal set depends on context. Usually we assume the existence of a set X and all sets under consideration are subsets of X or equivalently elements of the power set of X.
identity laws
The empty set and the universal set are the identities of union and intersection, respectively.
- A ⋃ ∅ = A
- A ⋂ U = A
domination laws
- A ⋃ U = U
- A ⋂ ∅ = ∅
Duality
All of the above identities come in pairs. Moreover, we can derive one identity in the pair from the other by a simple substitution: replace unions with intersections and intersections with unions. Also, replace the empty set with the universal set and the universal set with the empty set.
Inclusion
In the correspondence of sets to logical operators, inclusion corresponds to implication, i.e. A ⊆ B corresponds to if A then B.
The dual of the subset relation is the superset relation, i.e. the dual of ⊆ is ⊇.
- reflexivity: A ⊆ A
- antisymmetry: A ⊆ B and B ⊆ A iff A = B
- transitivity: if A ⊆ B and B ⊆ C then A ⊆ C
- least and greatest set: ∅ ⊆ A ⊆ U
- existence of join: A ⊆ A ⋃ B
- existence of join: if A ⊆ C and B ⊆ C, then A ⋃ B ⊆ C
- existence of meet: A ⋂ B ⊆ A
- existence of meet: if C ⊆ A and C ⊆ B, the C ⊆ A ⋂ B
These five statements are all equivalent:
- A ⊆ B
- A ⋂ B = A
- A ⋃ B = B
- A ∖ B = ∅
- BC ⊆ AC
Proofs
The above statements hold for all sets A, B, and C.
To prove the above statements, we use the definitions of union and intersection:
- A ⋃ B = {x: x ∈ A ∨ x ∈ B }
- A ⋂ B = {x: x ∈ A ∧ x ∈ B }
The definitions suggest why the union and intersection operators obey the same laws as the ∨ (or) and ∧ (and) operators of logic.
To prove that two sets are equal, i.e. A = B, we usually show that A ⊆ B and B ⊆ A.
To show that A ⊆ B, we choose arbitrary x ∈ A and show that x ∈ B.
Complement
The complement operator requires the existence of a universal set.
In the correspondence with logic, complement corresponds to logical negation.
The complement operator is self-dual, meaning that it is its own dual.
complement laws
- A ⋃ AC = U
- A ⋂ AC = ∅
de morgan's laws
- (A ⋃ B)C = AC ⋂ BC
- (A ⋂ B)C = AC ⋃ BC
involution law
- (AC)C = A
complement of universal and empty sets
- UC = ∅
- ∅C = U
uniqueness of complement
- if A ⋃ B = U and A ⋂ B = ∅, then B = AC
Set Difference
The set difference operator is not commutative or associative.
todo: counterexamples
Set difference operator can be expressed using intersection and complement:
- B ∖ A = B ⋂ AC
On the other hand, intersection and complement can be expressed as set difference and the universal set:
- A ⋂ B = A ∖ (A ∖ B)
- AC = U ∖ A
Set difference distributes over union and intersection from the right:
- (A ⋃ B) ∖ C = (A ∖ C) ⋃ (B ∖ C)
- (A ⋂ B) ∖ C = (A ∖ C) ⋂ (B ∖ C)
Set difference does not distribute over union and intersection from the left, but we have these identities:
- A ∖ (B ⋃ C) = (A ∖ B) ⋂ (A ∖ C)
- A ∖ (B ⋂ C) = (A ∖ B) ⋃ (A ∖ C)
Union and intersection do not distribute over set difference, but we have these identities:
- A ⋃ (B ∖ C) = (A ⋃ B) ∖ (C ∖ A)
- A ⋂ (B ∖ C) = (B ⋂ A) ∖ C = B ⋂ (A ∖ C)
Set Theory
Whereas set algebra concerns the laws observed by the operators on sets, set theory concerns which sets exist.
Axioms for the existence of sets were introduced when it was realized that not all properties can define sets. For example the Russell paradox, which considers the set of all items which do not contain themselves.
- axiom extensionality
- axiom regularity
- axiom schema of specification
- axiom of pairing
- axiom of union
- axiom schema of replacement
- axiom of infinity
- axiom of power set
- well-ordering theorem
Indexed Unions and Intersections
If A1, ..., An are sets, we can use index notation to write the union and intersection:
(1)countable unions and intersections
uncountable unions and intersections
Closure
An algebra is a nonempty family 𝒜 of sets of X which is closed under the complement operator and finite unions.
X ∈ 𝒜 since there exists A ∈ 𝒜 and A ⋃ AC ∈ 𝒜. Thus ∅ = XC ∈ 𝒜.
A ⋂ B = (AC ⋃ BC)C ∈ 𝒜. Thus algebras are closed under finite intersections.
A ring is a family ℛ of sets of X which is closed under the difference operator and finite unions.
If A, B ∈ ℛ, then A ⋂ B = A ∖ (A ∖ B) ∈ ℛ so rings are closed under finite intersections.
σ-algebra
σ-ring