Understanding the fundamental building blocks of set theory
A set is a well-defined collection of distinct objects, called elements or members. The key properties of a set are:
For any object, we can definitively determine whether it is or is not a member of the set.
Each element appears at most once. Duplicates are ignored: {1, 1, 2} = {1, 2}.
Order does not matter: {1, 2, 3} = {3, 1, 2} = {2, 3, 1}.
The "well-defined" requirement is crucial. "The set of all tall people" is NOT a valid set because "tall" is subjective. However, "the set of all people over 6 feet" IS a valid set.
List all elements explicitly within curly braces:
(ellipsis for infinite sets with clear pattern)
Describe elements by a property they satisfy:
"The set of all real numbers x such that x² < 9" = (-3, 3)
"The set of all even integers" = {..., -4, -2, 0, 2, 4, ...}
| Notation | Meaning | Example |
|---|---|---|
| Element a belongs to set A | ||
| Element a does not belong to set A | ||
| A is a subset of B (A ⊆ B) | ||
| A is a proper subset of B (A ⊂ B, A ≠ B) | ||
| A equals B (same elements) | ||
| Empty set (contains no elements) | ||
| Cardinality (number of elements) of A |
Learn how to combine and manipulate sets using fundamental operations
Contains all elements that are in A or B (or both)
Contains all elements that are in both A and B
Contains elements in A but not in B
All elements in the universal set U that are not in A
Elements in A or B, but not in both
Essential algebraic properties for working with sets
Union:
Intersection:
Union:
Intersection:
Over Union:
Over Intersection:
Union:
Intersection:
Union:
Intersection:
Union Complement:
Intersection Complement:
De Morgan's Laws are essential for simplifying logical expressions and set operations. They show that complementation "distributes" over unions and intersections, but with a twist: unions become intersections and vice versa.
For any sets A and B in a universal set U:
We prove this by double inclusion:
Part 1: Show
Let .
Then by definition of complement.
This means AND (negation of OR).
So and .
Therefore . ✓
Part 2: Show
Let .
Then and .
This means and .
So (neither in A nor B).
Therefore . ✓
Understanding different sizes of infinity
A set S is countable if its elements can be put in one-to-one correspondence with the natural numbers (or a subset thereof).
Examples:
A set is uncountable if it cannot be put in one-to-one correspondence with the natural numbers. It has a "larger" infinity.
Examples:
| Symbol | Name | Description | Countable? |
|---|---|---|---|
| Natural Numbers | Yes | ||
| Integers | Yes | ||
| Rational Numbers | Yes | ||
| Real Numbers | No | ||
| Complex Numbers | No |
Cantor proved that (rational numbers) is countable, but (real numbers) is uncountable. This means there are "more" real numbers than rationals, even though both sets are infinite! This was a revolutionary idea that redefined our understanding of infinity.
Step-by-step solutions to reinforce your understanding
Problem:
Solution:
We prove this by showing both sets contain the same elements.
The reverse inclusion follows similarly, completing the proof. ∎
Problem:
Solution:
Apply De Morgan's law to the first pair:
Problem:
Solution:
We construct an explicit enumeration using Cantor's diagonal argument.
Arrange positive rationals in a grid: row i contains fractions with denominator i.
German mathematician Georg Cantor founded set theory in 1874 with his revolutionary work on infinite sets. His work established that there are different "sizes" of infinity, a concept that was controversial at the time but now forms the foundation of modern mathematics.
"A set is a Many that allows itself to be thought of as a One."
— Georg Cantor
Fundamental theorems that shaped modern set theory
For any set A, the power set P(A) has strictly greater cardinality than A: |P(A)| > |A|.
This theorem proves there is no 'largest' infinity and establishes a hierarchy of infinite cardinalities.
If there exist injections f: A → B and g: B → A, then there exists a bijection between A and B, so |A| = |B|.
This theorem allows us to prove set equality without explicitly constructing a bijection.
Every non-empty set can be well-ordered, meaning it can be given a total order where every non-empty subset has a least element.
Equivalent to the Axiom of Choice, this theorem is fundamental in transfinite induction and ordinal arithmetic.
There is no set whose cardinality is strictly between that of the integers and the real numbers: ℵ₁ = 2^ℵ₀.
Gödel and Cohen proved this is independent of ZFC set theory—it can neither be proved nor disproved from the standard axioms.
A set S can be partitioned into disjoint subsets whose union is S, with each element in exactly one part.
Partitions define equivalence relations and vice versa.
The 'set of all sets that don't contain themselves' leads to contradiction in naive set theory.
This paradox motivated the development of axiomatic set theories like ZFC.
A countable union of countable sets is countable.
Used to prove ℚ is countable: ℚ = ∪ₙ{rationals with denominator n}.
Essential methods for proving set-theoretic statements
Assume the hypothesis and derive the conclusion through logical steps.
Example: To prove A ⊆ B, let x ∈ A be arbitrary and show x ∈ B.
Assume the negation of what you want to prove and derive a contradiction.
Example: To prove a set is infinite, assume it's finite and show this leads to a contradiction.
Instead of proving P → Q, prove ¬Q → ¬P, which is logically equivalent.
Example: Instead of 'if x ∈ A ∩ B then x ∈ A', prove 'if x ∉ A then x ∉ A ∩ B'.
Prove a base case P(1), then prove P(n) → P(n+1) for all n.
Example: Prove |P(A)| = 2^n for finite sets A with n elements.
A ⊆ B (subset) means every element of A is in B, including the case A = B. A ⊂ B (proper subset) means A ⊆ B AND A ≠ B. For example, {1,2} ⊂ {1,2,3} but {1,2,3} ⊆ {1,2,3}.
By definition, A ⊆ B means 'for all x, if x ∈ A then x ∈ B'. For the empty set ∅, there are no elements, so the statement 'if x ∈ ∅ then x ∈ B' is vacuously true for any B.
Prove double inclusion: show A ⊆ B and B ⊆ A. This is called the 'element-chasing' method. Take an arbitrary element of one set and show it belongs to the other, then reverse.
Cantor's diagonal argument proves this. Any attempted list of reals can be 'diagonalized' to construct a new real not in the list, showing no enumeration can be complete.
The power set P(A) is the set of all subsets of A. For a set with n elements, |P(A)| = 2^n. Cantor's theorem proves |P(A)| > |A| for any set, even infinite ones.
The Cartesian product A × B is the set of all ordered pairs (a, b) where a ∈ A and b ∈ B. For example, {1,2} × {a,b} = {(1,a), (1,b), (2,a), (2,b)}. The cardinality |A × B| = |A| · |B|.
The symmetric difference A △ B = (A \ B) ∪ (B \ A) contains elements in exactly one of A or B, but not both. It can also be written as A △ B = (A ∪ B) \ (A ∩ B).
An indexed family {Aᵢ : i ∈ I} assigns a set Aᵢ to each index i in the index set I. The union ∪{Aᵢ : i ∈ I} contains all elements in at least one Aᵢ, and the intersection ∩{Aᵢ : i ∈ I} contains elements in all Aᵢ.
Test your understanding of set theory concepts