Sets

Builds on

Required prerequisites, all the way down: 1

You will learn to

• Use x ∈ A, A ⊆ B and brace notation to describe finite sets, including the empty set ∅.
• Compute unions, intersections and complements (relative to a stated universe) of finite sets and show them on Venn diagrams.
• Form ordered pairs and Cartesian products A × B, and explain why (a, b) differs from {a, b}.
• Count elements of finite sets, using |A × B| = |A|·|B| and |A ∪ B| = |A| + |B| − |A ∩ B|.

Definition

• A set is a collection of distinct objects, its elements; x ∈ A means x is an element of A.
• A ⊆ B (A is a subset of B) means every element of A is an element of B.
• A ∪ B = {x : x ∈ A or x ∈ B} and A ∩ B = {x : x ∈ A and x ∈ B}; the complement of A in a universe U is {x ∈ U : x ∉ A}.
• The empty set ∅ is the set with no elements.
• An ordered pair (a, b) has a first entry a and a second entry b, and (a, b) = (c, d) exactly when a = c and b = d. The Cartesian product A × B is the set of all ordered pairs (a, b) with a ∈ A and b ∈ B.
• The cardinality |A| of a finite set A is the number of its elements.

Theorem

• Two sets are equal exactly when they have the same elements (extensionality); order and repetition in a list do not matter.
• ∅ ⊆ A and A ⊆ A for every set A.
• |A ∪ B| = |A| + |B| − |A ∩ B| for finite sets A and B.
• |A × B| = |A|·|B| for finite sets A and B.
• A finite set with n elements has exactly 2ⁿ subsets.

Common misconceptions

• Thinking ∅ and {∅} are the same set: {∅} has exactly one element.
• Confusing ∈ with ⊆: 1 ∈ {1, 2} and {1} ⊆ {1, 2}, but {1} ∉ {1, 2}.
• Reading 'or' in a union as 'one but not both'; mathematical 'or' is inclusive.
• Assuming (a, b) = (b, a); this holds only when a = b.
• Taking a complement without saying which universe it is taken in.

Leads to

Optional discoveries

• Russell's paradox and why sets need axioms Sets can have sets as elements, and {∅} ≠ ∅. Allowing every property to define a set leads to Russell's paradox.Wonder Trail →
• ZFC: axiomatic set theory Nesting alone builds numbers: von Neumann's construction 0 = ∅, 1 = {∅}, 2 = {∅, {∅}}, … defines the natural numbers inside axiomatic set theory.Wonder Trail →
• Countability and Cantor's diagonal argument Matching elements one-to-one compares the sizes of finite sets; the same idea applied to infinite sets shows that some infinite sets are strictly larger than others.Wonder Trail →
• Ordinals and cardinals Cardinal numbers extend 'number of elements' from finite sets to all sets.Wonder Trail →
• Products by maps: a first universal property The Cartesian product, met here as a set of ordered pairs, can also be characterised by how functions into it behave.
• ← Shapes

Learning pathways

• Conventional K–12 progression
• Adult beginner pathway

Further reading

• Paul R. Halmos, Naive Set Theory (1960)