1
Bijection is the definition of same size
For finite sets it agrees with counting. For infinite ones it is the only definition available, and it must be accepted before anything here parses.
Lesson · Sets, Relations, and Functions · Counting
Cardinality and Countability
Two sets have the same size when a bijection pairs them. That definition makes ℤ and ℚ the same size as ℕ, and Cantor's diagonal argument shows ℝ is strictly larger.
|A| = |B| ⟺ a bijection A → B exists
countable = finite, or in bijection with ℕ
|ℕ| = |ℤ| = |ℚ| all countably infinite
|ℝ| > |ℕ| Cantor's diagonal argument
Size, defined by pairing
Core ideas
What this lesson establishes
Counting stops working at infinity, so size is redefined by pairing. The consequences are strange and they are forced.
2
An infinite set can match a proper subset
ℕ and the even naturals are the same size, via n ↦ 2n. For finite sets that is impossible; for infinite ones it is the definition of infinite.
3
Not all infinities are equal
ℝ cannot be listed. Cantor's diagonal argument constructs, from any proposed list, a real number missing from it.
The material
Countable and uncountable
The definition, two sets that can be listed, one that cannot, and the theorem behind the one that cannot.
Definition · Same cardinality
|A| = |B| means there is a bijection A → B. |A| ≤ |B| means there is an injection A → B.
Definition · Countable
A set is countably infinite if it is in bijection with ℕ, and countable if it is finite or countably infinite. Otherwise it is uncountable.
Countably infinite means listable: a bijection with ℕ is exactly an enumeration a₀, a₁, a₂, … in which every element appears exactly once. Proving countability means producing such a list.
Theorem · ℤ is countable
The integers can be listed: 0, 1, −1, 2, −2, 3, −3, …
Define f : ℕ → ℤ by f(n) = n/2 for even n and f(n) = −(n+1)/2 for odd n. The even inputs produce 0, 1, 2, 3, … and the odd ones produce −1, −2, −3, …, so every integer appears exactly once. That is a bijection, so |ℤ| = |ℕ|.
□
Listing them in their natural order …, −2, −1, 0, 1, 2, … does not work: it has no first element, so it is not an enumeration by ℕ. Reordering is allowed and is exactly what the alternating list does.
Theorem · ℚ is countable
The rational numbers can be listed.
Arrange the positive rationals a/b in a grid with a as the row and b as the column, and walk it along diagonals: 1/1, then 1/2, 2/1, then 1/3, 2/2, 3/1, and so on. Every positive rational appears; skip any fraction not in lowest terms so each appears once.
Each diagonal is finite, so the walk reaches every cell in finitely many steps. Interleave the negatives and 0 as in the previous theorem to get all of ℚ.
□
This is genuinely surprising: the rationals are dense — between any two there is another — and there are still no more of them than there are counting numbers. Density and cardinality are unrelated properties.
Theorem · Cantor: ℝ is uncountable
There is no surjection ℕ → ℝ; in particular no bijection.
It is enough to show the interval (0,1) cannot be listed. Suppose r₁, r₂, r₃, … is any list of reals in (0,1), each written as a decimal expansion rₙ = 0.dₙ₁dₙ₂dₙ₃… (a list indexed from 0 is reindexed from 1 without loss).
Build a new number x = 0.x₁x₂x₃… by choosing xₖ = 5 if dₖₖ ≠ 5, and xₖ = 4 otherwise. (Restricting to 4 and 5 avoids the ambiguity of expansions ending in all 9s.)
Then x differs from r₁ in the first decimal place, from r₂ in the second, and from rₙ in the nth — so x is on no line of the list, yet lies in (0,1).
Every proposed list therefore misses something, so no list of all the reals exists.
□
The argument is constructive in a useful sense: hand it a list and it hands back a specific missing number. It does not rely on the list being defined by any rule, which is why it defeats all lists at once.
Theorem · Cantor's theorem
For every set A, there is no surjection A → P(A); so |A| < |P(A)|. There is no largest cardinality.
Let f : A → P(A) be any function and set D = {a ∈ A : a ∉ f(a)}, a subset of A. If D = f(d) for some d ∈ A, then d ∈ D exactly when d ∉ f(d) = D — a contradiction either way. So D is not in the image of f, and f is not a surjection.
a ↦ {a} is an injection A → P(A), so |A| ≤ |P(A)|, and with no surjection the inequality is strict. This is the diagonal argument again: D is built to disagree with f(a) at the element a, for every a at once.
□
Interactive
Injective, surjective, bijective
Built by hand, classified by counting
Method
Proving a set countable or uncountable
Produce a list, or defeat every list.
1
To prove countable, produce an explicit enumeration
A rule that reaches every element in finitely many steps, with no repeats. The diagonal walk is the standard device for a two-dimensional family.
2
Check the list covers everything
A list that never reaches some element is not an enumeration. The finiteness of each diagonal is what makes the rational walk work.
3
To prove uncountable, take an arbitrary list
Not a specific one. The argument must defeat every list, which is why it starts with an unspecified enumeration.
4
Construct the missing element by diagonalising
Differ from the nth entry in the nth position. The element you build is in the set and on no line of the list.
Countability
Score 0 / 0Choose the answer you can justify.
The evens are the same size as ℕ
Which is impossible for finite sets and routine for infinite ones.
f : ℕ → E, f(n) = 2n, where E = {0, 2, 4, 6, …}
injective? 2m = 2n ⟹ m = n yes
surjective? any even e = 2k, and f(k) = e yes
So |ℕ| = |E|, even though E ⊊ ℕ and E omits every odd number.
0 1 2 3 4 5 …
↓ ↓ ↓ ↓ ↓ ↓
0 2 4 6 8 10 …
This is Hilbert's hotel in arithmetic form, and it is the property that defines an infinite set: a set is infinite exactly when it is in bijection with a proper subset of itself. For a finite set that is impossible, by “Injective, Surjective, Bijective”'s theorem.
Common mistakes
1
Thinking a proper subset must be smallerTrue for finite sets and false for infinite ones. n ↦ 2n pairs ℕ with the evens, and no element is left over.
2
Confusing dense with uncountableℚ is dense in ℝ and still countable. Having something between any two elements says nothing about cardinality.
3
Diagonalising against one specific listThe argument must begin with an arbitrary list. Defeating one enumeration shows only that that enumeration was incomplete.
Check your understanding
✓
Finish when you can run the diagonal argument from memory.
Write out Cantor's proof for (0,1), including why the digits 4 and 5 are chosen rather than any two. If you can state the reason — avoiding the 0.4999… = 0.5000… ambiguity — you have the argument rather than its outline.
Note: Whether any cardinality lies strictly between |ℕ| and |ℝ| is the continuum hypothesis. It was shown independent of the standard axioms of set theory: it can be neither proved nor disproved from them. That is a fact about the axioms, not about our ignorance.