Overview
This lecture introduces the foundations of set theory, covering sets, elements, subsets, unions, intersections, complements, and related properties, as well as key notation and paradoxes.
Introduction to Sets
- A set is a collection of distinct objects, called elements, grouped by shared properties.
- Sets provide a clear rule to determine if an object is an element or not (no ambiguity).
- Sets are often denoted with curly brackets: e.g., {1, 2, 3}.
Set Notation and Membership
- Assign names to sets, e.g., A = {1, 2, 3}.
- Use "∈" for "is an element of" and "∉" for "is not an element of".
- Set builder notation describes sets by property: {p ∈ ℕ | p is prime}.
Equality and Cardinality of Sets
- Two sets are equal if they contain exactly the same elements (order and repetition don’t matter).
- The cardinality (|A|) of a set is the number of its elements; use ∞ for infinite sets.
Subsets and Proper Subsets
- A is a subset of B (A ⊆ B) if every element of A is also in B.
- A proper subset (A ⊂ B) means A ⊆ B but A ≠ B.
- All sets are subsets of themselves; the empty set is a subset of every set.
- If A ⊆ B and B ⊆ C, then A ⊆ C (transitivity of subsets).
The Empty Set
- The empty set (∅) contains no elements and is unique.
- ∅ is a subset of every set.
Union and Intersection
- Union (A ∪ B): all elements in A or B.
- Intersection (A ∩ B): all elements common to both A and B.
- Order and grouping don’t affect the outcome (associativity, commutativity).
- Key identities: |A ∪ B| = |A| + |B| – |A ∩ B|.
Set Difference and Complement
- Set difference (A \ B): elements in A not in B.
- Complement (Bᶜ): all elements not in B, relative to a universal set U.
- The complement of U is ∅; the complement of ∅ is U.
De Morgan’s Laws and Duality
- (A ∪ B)ᶜ = Aᶜ ∩ Bᶜ
- (A ∩ B)ᶜ = Aᶜ ∪ Bᶜ
- Switching unions and intersections in identities yields valid dual identities.
Power Sets and Indexed Families
- The power set P(A) contains all subsets of A, including ∅ and A itself.
- Indexed families: sets labeled by indices, e.g., {A₁, A₂, A₃}.
Russell’s Paradox and Set Theory Foundations
- Russell’s paradox: considering the set of all sets that do not contain themselves leads to a contradiction.
- Axiomatic set theory uses axioms to rigorously define sets and avoid such paradoxes.
Key Terms & Definitions
- Set — a collection of distinct elements.
- Element — an object within a set.
- Subset (⊆) — a set whose elements are all in another set.
- Proper Subset (⊂) — a subset that is not equal to the original set.
- Empty Set (∅) — the unique set with no elements.
- Union (∪) — set of all elements in either set.
- Intersection (∩) — set of all elements common to both sets.
- Cardinality (|A|) — number of elements in a set.
- Complement (Aᶜ) — all elements not in set A, with respect to a given universal set.
- Power Set (P(A)) — the set of all subsets of A.
- Universal Set (U) — the set of all elements under consideration.
Action Items / Next Steps
- Practice identifying subsets, unions, intersections, and complements with example sets.
- Review set builder notation and properties of power sets.
- Read about Russell’s paradox and differences between naive and axiomatic set theory.