From sets to infinity
Set theory
Build the language of modern mathematics: sets, relations, functions, proof, and the surprising sizes of infinity.
01 / Membership & operations
Two sets. Four places to belong.
Our universe is U = {1, 2, 3, 4, 5, 6, 7, 8}. Every number is in A only, B only, both, or neither. Change the checkboxes and choose an operation.
Solid dot = included in the result. Positions show membership; areas do not show set size.
Choose who belongs
The notation
3 ∈ A means “3 is an element of A.” 3 ∉ A means it is not. Braces list a set’s elements: {1, 2, 3}.
Order and repetition do not matter: {1, 2, 2} = {2, 1}. The empty set, ∅ = {}, has no elements.
Count each element once
The cardinality |A| is the number of elements in A. Adding |A| + |B| counts the overlap twice, so subtract it once.
|A ∪ B| = |A| + |B| − |A ∩ B|
Why does a complement need a universe?
Aᶜ = U ∖ A contains everything in U that is not in A. If A is {2, 4} and U is {1, 2, 3, 4}, then Aᶜ is {1, 3}. With U = {1, 2, 3, 4, 5}, it is {1, 3, 5}. Always specify the universe.
One rule, two descriptions
Change A or B above to test this identity. Examples illustrate the rule; the explanation in terms of membership is why it holds for every pair of sets.
02 / Containment
An element belongs. A subset fits.
A ⊆ B means every element of A is also in B. Equality is allowed. A proper subset, A ⊊ B, leaves at least one element of B out.
This result uses the sets you edited above.
∈ and ⊆ ask different questions
2 ∈ {1, 2} is true: 2 is an element.
{2} ⊆ {1, 2} is true: every element of {2} is there.
{2} ∈ {1, 2} is false: neither listed element is the set {2}.
The empty set fits everywhere
∅ ⊆ B for every set B. There is no element of ∅ that could fail to belong to B.
But ∅ ≠ {∅}: the first has zero elements, while the second has one element, which is itself a set.
03 / All possible subsets
A set of sets.
The power set 𝒫(S) contains every subset of S, including ∅ and S itself. Choose the elements of S and watch its power set grow.
For each of n elements, a subset makes one of two choices: include it or leave it out. That gives |𝒫(S)| = 2ⁿ. Even when S is empty, it has one subset: ∅.
04 / Ordered pairs
Pair every choice with every other.
The Cartesian product X × Y consists of all ordered pairs (x, y) with x ∈ X and y ∈ Y. Unlike a set’s listing order, a pair’s order matters.
For finite sets, |X × Y| = |X| · |Y|. If either set is empty, there are no pairs. In general, X × Y ≠ Y × X: (1, a) and (a, 1) are different ordered pairs.
05 / Sets as predicates
Membership turns algebra into logic.
Set-builder notation describes a set by a condition rather than a list. The ambient set tells us what objects we are considering.
This reads: E is the set of integers n for which some integer k satisfies n = 2k. The symbol means “for every”; means “there exists.” Their order matters.
Subset and equality
To prove a subset relation, choose an arbitrary element of A and show it belongs to B. To disprove it, find one counterexample.
Negating a statement
“Not every element works” means “at least one element fails.” It does not mean that every element fails.
This is true: choose y = x + 1. Reversing the two quantifiers would demand one integer larger than every integer, which is impossible.
Proof: intersection distributes over union
Choose any x. Translate membership into logic, distribute “and” over “or,” then translate back.
Both sets have exactly the same elements, so they are equal. This is an elementwise proof, not a conclusion drawn only from a diagram.
Indexed families
Unions correspond to existence; intersections correspond to universality. Relative to a fixed universe U, an empty indexed union is ∅, while an empty indexed intersection is U.
06 / Relations
A relation is a set of pairs.
A binary relation on X is a subset of . Here . Select a cell to include or exclude its ordered pair. Read from the row to the column.
A missing pair is a false statement, not missing data. A failed property is accompanied by a concrete witness.
Equivalence relations classify
Reflexive, symmetric and transitive relations group objects that are equivalent in some chosen sense. Every equivalence relation determines a partition into disjoint, nonempty classes.
Partial orders compare
Reflexive, antisymmetric and transitive relations are partial orders. Antisymmetric does not mean “never symmetric”: two-way related elements must be equal. A total order also compares every pair of elements.
07 / Equivalence classes & quotients
Forget the object. Keep its class.
Integers are congruent modulo m when their difference is divisible by m. The relation remembers only the remainder.
The display shows only integers 0 through 11. Each actual class includes infinitely many positive and negative integers with the same remainder.
Why the classes form a partition
Reflexivity puts every element in its own class. If two classes share an element, symmetry and transitivity force all their elements into both classes; the classes are equal. Thus distinct classes cannot overlap.
The quotient set is the collection of classes, not a choice of representatives:
08 / Functions, images & preimages
Exactly one output for every input.
A function is a relation with a special constraint: every domain element occurs in exactly one ordered pair as the first coordinate. Choose the outputs of , with and a codomain Y that you can resize.
Image: push a subset forward
For the fixed subset :
Repeated outputs appear only once in an image set.
Preimage: pull a subset back
A preimage is defined for every function; it does not require an inverse function.
Composition, inverses and a useful distinction
If f maps X to Y and g maps Y to Z, their composition maps X to Z. Composition is associative; it need not be commutative. A function has a two-sided inverse exactly when it is bijective.
Preimages preserve intersections. Images only satisfy an inclusion in general:
For a counterexample to equality, map both 1 and 2 to a, and take the disjoint subsets {1} and {2}. The left image is empty; the intersection of the two images is {a}.
09 / Beyond finite sets
Can a part be as big as the whole?
For infinite sets, yes. Two sets have the same cardinality when a one-to-one correspondence pairs every element of one with exactly one element of the other.
Pair n with 2n
The even positive integers form a proper subset of the positive integers, yet this pairing misses nothing on either side. Both sets are countably infinite. The real numbers are uncountable: no list can contain them all. The next experiment explains why. Infinite does not mean “all the same size.”
The rationals can be listed
Every positive rational has the form p/q for positive integers p and q. Visit pairs in increasing order of p + q, skipping fractions not in lowest terms. Every pair has a finite sum, so every positive rational is eventually reached. Interleave zero and the negative rationals to enumerate all of the rationals.
“Dense” is different from “uncountable”: there is a rational between any two distinct reals, yet the rationals are countable.
Comparing sizes by injections
An injection from A to B shows that A is no larger than B. The Cantor–Schröder–Bernstein theorem says that injections in both directions guarantee a bijection. The infinite case is a theorem; it cannot be justified merely by subtracting finite counts.
10 / Cantor’s diagonal argument
Construct the thing the list missed.
Suppose someone claims to list every infinite binary sequence. Construct a new sequence by changing the nth bit of the nth row. It differs from every listed row at a known position.
Click any bit below. The diagonal cells are outlined; the constructed row always flips them.
This is a six-row, six-column window onto the construction, not an experimental proof about infinity. The proof below applies to every index n in a hypothetical infinite list.
Why no infinite list can succeed
Given any proposed list of infinite binary sequences, define the new sequence by the displayed rule for every positive integer n. If it appeared at position k in the list, its kth bit would both equal and differ from the kth bit of row k. That is impossible. Therefore the set of infinite binary sequences is uncountable.
To connect this to real numbers without ambiguous binary expansions, send each binary sequence to a ternary expansion using only digits 0 and 2:
If two sequences first differ at position k, that term contributes a difference of , and all later terms can cancel at most . Their real numbers are distinct. Hence there are uncountably many reals even inside [0, 1].
The more general theorem
No set can be put in bijection with its power set. Singletons give an injection from A into its power set. To rule out a surjection from A onto its power set, take any proposed function and form its diagonal subset:
If D were f(d) for some d, then:
The contradiction shows D is missing from the image of f. This works for finite and infinite A.
11 / Foundations
Not every description defines a set.
Unrestricted comprehension—allowing a set for every condition—leads to Russell’s paradox. Imagine “the set of all sets that do not contain themselves.”
Modern axiomatic set theory avoids this construction. The separation schema selects elements from an already existing set, rather than forming an unrestricted collection:
Zermelo–Fraenkel set theory with the axiom of choice (ZFC) is a standard foundation. Its axioms govern operations such as pairing, unions and power sets; assert an infinite set; and control how new sets are formed. There is no set of all sets in ZFC.
Choice
The axiom of choice says that for any set of nonempty sets, there is a function choosing an element from each. For finitely many sets this can be proved without the axiom; the general infinite assertion is an additional principle.
Cardinals and ordinals
Cardinals describe size. Ordinals describe the order types of well-ordered sets. A well-order gives every nonempty subset a least element. Two infinite well-orders can have the same cardinality but different order types.
The natural-number order has no last element; adding one at the end changes its order type, but not its countable size.
Where a first course ends
Cantor’s theorem proves that the real numbers have larger cardinality than the natural numbers. It does not settle whether some cardinality lies strictly between them. The continuum hypothesis asserts there is none; assuming ZFC is consistent, it is neither provable nor refutable in ZFC.
Further study develops well-orders, transfinite induction, ordinal arithmetic, and models of set theory. These require more than extending finite diagrams.
12 / Check your understanding
Make a prediction.
These questions use their own sets, independently of the experiments above.
Proof exercises
Prove that the composition of two injections is injective
Assume g(f(x)) = g(f(y)). Injectivity of g gives f(x) = f(y), then injectivity of f gives x = y. This is exactly what injectivity of the composition requires.
Prove that equivalence classes sharing an element are equal
If z belongs to both [a] and [b], then a is related to z and z to b, using symmetry as needed. Transitivity gives a related to b. Any element related to a is then related to b, and conversely. The classes are equal.
Continue reading
Richard Hammack · Book of Proof
Chapters on sets, relations, functions, and cardinality, with exercises.
Open Logic Project · Set Theory: An Open Introduction
A fuller treatment of the foundations and infinite sets.