1 Elementary Set Theory
Notation:
{} enclose a set.
{1, 2, 3} = {3, 2, 2, 1, 3} because a set is not defined by order or multiplicity.
{0, 2, 4, . . .} = x is an even natural number because two ways of writing
a set are equivalent.
∅ is the empty set.
x ∈ A denotes x is an element of A.
N = {0, 1, 2, . . .} are the natural numbers.
Z = {. . . , −2, −1, 0, 1, 2, . . .} are the integers.
Q = m, n ∈ Z and n 6= 0 are the rational numbers.
R are the real numbers.
Axiom 1.1. Axiom of Extensionality Let A, B be sets. If (∀x)x ∈ A iff x ∈ B
then A = B.
Definition 1.1 (Subset). Let A, B be sets. Then A is a subset of B, written
A ⊆ B iff (∀x) if x ∈ A then x ∈ B.
Theorem 1.1. If A ⊆ B and B ⊆ A then A = B.
Proof. Let x be arbitrary.
Because A ⊆ B if x ∈ A then x ∈ B
Because B ⊆ A if x ∈ B then x ∈ A
Hence, x ∈ A iff x ∈ B, thus A = B.
Definition 1.2 (Union). Let A, B be sets. The Union A ∪ B of A and B is
defined by x ∈ A ∪ B if x ∈ A or x ∈ B.
Theorem 1.2. A ∪ (B ∪ C) = (A ∪ B) ∪ C
Proof. Let x be arbitrary.
x ∈ A ∪ (B ∪ C) iff x ∈ A or x ∈ B ∪ C
iff x ∈ A or (x ∈ B or x ∈ C)
iff x ∈ A or x ∈ B or x ∈ C
iff (x ∈ A or x ∈ B) or x ∈ C
iff x ∈ A ∪ B or x ∈ C
iff x ∈ (A ∪ B) ∪ C
Definition 1.3 (Intersection). Let A, B be sets. The intersection A ∩ B of A
and B is defined by a ∈ A ∩ B iff x ∈ A and x ∈ B
Theorem 1.3. A ∩ (B ∪ C) = (A ∩ B) ∪ (A ∩ C)
Proof. Let x be arbitrary. Then x ∈ A ∩ (B ∪ C) iff x ∈ A and x ∈ B ∩ C
iff x ∈ A and (x ∈ B or x ∈ C)
iff (x ∈ A and x ∈ B) or (x ∈ A and x ∈ C)
iff x ∈ A ∩ B or x ∈ A ∩ C
iff x ∈ (A ∩ B) ∪ (A ∩ C)