Finite, countable and uncountable sets

Can you pair every entry without a leftover?

Match a to 0, b to 1 and c to 2. Each member of A = {a, b, c} has one partner in B = {0, 1, 2}; every partner is used once. You can compare the sets without their elements looking alike. Now try matching 0 to 1, 1 to 2, 2 to 3 and continuing by the same rule. Does leaving 0 out of the target make the second matching fail?

Useful preparation is reading functions with their declared input and output sets, equivalent fractions, decimal places, and the difference between checking examples and proving a general statement. The links below lead to published lessons on those topics. All set and mapping definitions used here are restated; you do not need to have read the later set lessons.

On a first reading, follow the matching, integer and pair sections, then the subset diagonal. The rational section uses reduced fractions; the real-number diagonal uses decimal place value. You can return to those two sections after the preparation lessons. The section on supplied families of lists extends the pair method and can be read after you can explain why every pair receives a finite position.

Say exactly what finite and countable mean

A set records distinct elements, with no repetition or order. The notation x ∈ A says that x is an element of A; A ⊆ B says that every element of A belongs to B. The empty set ∅ has no elements. In this lesson N₀ = {0, 1, 2, …}, N₊ = {1, 2, 3, …}, ℤ is the set of integers, ℚ the rational numbers, and ℝ the real numbers.

A function f: A → B assigns exactly one element of the declared target B to every element of the declared source A. It is injective if different inputs have different outputs, and surjective if every element of B is an output. A bijection has both properties. Two sets have equal cardinality, written |A| = |B|, when a bijection between them exists. The particular pairing is not required to preserve numerical order or distance.

A set is finite if it can be matched bijectively to {0, …, n−1} for some nonnegative integer n. For n = 0 this target is ∅, so |∅| = 0. A set is infinite if it is not finite. It is countably infinite if there is a bijection N₀ → A: a list a₀, a₁, a₂, … in which every element appears exactly once.

Here countable means finite or countably infinite; the phrase at most countable has the same meaning. In particular ∅ is countable, but not countably infinite. Uncountable means not countable. Some books use countable to mean only countably infinite, so check the convention rather than assuming that the word excludes finite sets.

A proper subset can have the same infinite cardinality

The shift f(n) = n+1 is a bijection N₀ → N₊. If f(m) = f(n), then m+1 = n+1, hence m = n: it is injective. Given any k ∈ N₊, the input k−1 belongs to N₀ and reaches k: it is surjective. Thus |N₀| = |N₊| even though N₊ is a proper subset of N₀ because it omits 0.

Likewise n ↦ 2n is a bijection N₀ → E, where E = {0, 2, 4, …}. Equality 2m = 2n forces m = n; every element of E has the form 2k and comes from k. The inverse on E is k ↦ k/2. This function is not a surjection onto all of N₀: odd numbers are outside the declared target E.

Removing an element from a finite set reduces its cardinality. That familiar finite rule cannot be applied to these infinite sets. The displayed arrows show only the first six matches; injectivity and the arbitrary-target reconstruction prove the claim for every element. There is no last arrow in the infinite matching.

Alternating signs reaches every integer once

An integer list must not spend all its positions on nonnegative values and promise to add negatives afterward: there is no position after infinitely many entries. Instead use 0, 1, −1, 2, −2, 3, −3, … . For k ≥ 1, define z(2k−1) = k and z(2k) = −k, with z(0) = 0.

The positive integer k occurs at index 2k−1, the negative integer −k at index 2k, and 0 only at index 0. These three disjoint cases account for every integer and give exactly one position each. Therefore z: N₀ → ℤ is a bijection and ℤ is countably infinite. The formula supplies the proof; a finite run of alternating signs merely illustrates it.

A diagonal sweep does not get stuck in one row

The Cartesian product N₀ × N₀ consists of ordered pairs (i, j) with i, j ∈ N₀. The first coordinate and second coordinate have different roles: (1, 2) and (2, 1) are different pairs. Reading the entire row (0, 0), (0, 1), (0, 2), … first would never reach row 1.

Instead visit pairs by increasing sum s = i+j. Within a sum, increase i from 0 to s and put j = s−i. This gives (0, 0); then (0, 1), (1, 0); then (0, 2), (1, 1), (2, 0); and so on. Every diagonal has the finite length s+1, so the sweep reaches the next diagonal.

There are Tₛ = s(s+1)/2 pairs on earlier diagonals. The zero-based rank of (i, j) is Tₛ+i, where s = i+j. This is a finite integer for any specified pair. Diagonal s occupies exactly the consecutive ranks Tₛ through Tₛ+s; the next begins at Tₛ+s+1. Thus the ranks cover N₀ once, and each pair receives exactly one rank. This proves that N₀ × N₀ is countably infinite.

For (2, 3), s = 5, T₅ = 15 and the rank is 17. The first fifteen points drawn below do not include it, but the same rule already tells you when it will occur. A point outside the displayed window is not an omitted member of the enumeration.

List fraction values, not repeated fraction expressions

Every positive rational number has a unique reduced representation p/q with positive integers p and q and greatest common divisor gcd(p, q) = 1. The greatest common divisor is the largest positive integer dividing both entries. For instance 2/4 = 1/2, but only 1/2 is reduced. Different expressions for the same number must not occupy different positions in a bijective list.

Sweep positive pairs (p, q) by increasing p+q, and within each sum increase p. Retain only pairs with gcd(p, q) = 1. The positive list begins 1, 1/2, 2, 1/3, 3, 1/4, 2/3, 3/2, 4, … . At sum 4, discard 2/2; it would repeat 1. Every reduced p/q appears on its finite diagonal p+q, and uniqueness of reduced representations prevents repeats.

To include all signs, start with 0, then place each positive value immediately before its negative: 0, 1, −1, 1/2, −1/2, 2, −2, 1/3, −1/3, … . Every nonzero rational has exactly one sign and one reduced positive magnitude, so it occurs exactly once. There are infinitely many retained positive entries, including p/1 for each p ≥ 1, so the signed list is an infinite bijective enumeration of ℚ.

Rational numbers lie between other rational numbers, but this density does not prevent enumeration. The list is not required to increase by numerical value. A grid cell represents the exact fraction p/q; retaining or skipping it is decided by integer divisibility, not by a rounded decimal display.

Filter one list, or sweep supplied lists together

Any subset A of a countable set is countable. For a finite parent set this follows by deleting unwanted elements. For a parent with list b₀, b₁, …, keep the positions whose entries belong to A. If only finitely many are kept, A is finite. Otherwise arrange the kept indices in increasing order. Each kept index has only finitely many smaller indices, so its entry eventually appears; no entry appears twice. This gives a bijective infinite list of A.

The union of a family is the set of elements belonging to at least one of its sets. Now suppose a family A₀, A₁, … is supplied with a particular finite or infinite list for each Aᵢ. Each list covers its set; repetitions are allowed, and an empty set has no slots. Sweep slot pairs (i, j) by the same diagonal order as N₀ × N₀, skip nonexistent finite-row slots, and keep a value only at its first occurrence. Every element in the union has a supplied slot with finite rank, so it is reached.

The ranks of first occurrences form a subset of N₀. Sorting those ranks gives either a finite list or a bijective infinite list of the union. Thus a countable family with these supplied lists has a countable union. This proof uses the lists as part of the data; it makes no assertion about choosing lists simultaneously from an arbitrary family without that data.

For example, supplied rows {a, b}, ∅ and {b, c} can be swept and deduplicated to give {a, b, c}. Infinite rows work by the same finite-rank argument. A finite experiment can check the ordering and duplicate rule, while the arbitrary supplied slot proves coverage of the whole union.

Change the membership decision at each row’s own index

The power set P(A) is the set of all subsets of A, including ∅ and A itself. For A = {0, 1}, P(A) = {∅, {0}, {1}, {0, 1}}. A subset of N₀ can be recorded as membership decisions: at position n, write 1 if n belongs and 0 if it does not.

Take any proposed list S₀, S₁, S₂, … of subsets of N₀. Define a new subset D = {n ∈ N₀ : n ∉ Sₙ}. At row n, D makes the opposite decision about n from Sₙ. If n belongs to Sₙ, it does not belong to D; if it does not belong to Sₙ, it belongs to D. Hence D ≠ Sₙ for every n.

No proposed N₀-indexed list covers P(N₀), even if repetitions are allowed. This is stronger than showing that one particular list fails. P(N₀) is infinite because the singleton sets {0}, {1}, {2}, … are all distinct; it is therefore uncountable. The diagonal rule defeats an arbitrary supposed complete list.

The finite grid flips only its three, four or five shown diagonal entries. Its new row differs from each shown row at the corresponding position, but might agree with an unseen later row on this finite window. The proof constructs the whole subset D, making a decision at every index, rather than extrapolating a finite pattern.

The same argument applies to every set

Let A be any set and let f: A → P(A) be any function. Define D = {a ∈ A : a ∉ f(a)}. This is a subset of A, so D ∈ P(A). If f(c) = D for some c ∈ A, then the defining condition says c ∈ D exactly when c ∉ D, which is impossible. Consequently f is not surjective; no bijection A → P(A) exists. This is Cantor’s theorem.

There is an injection A → P(A), given by a ↦ {a}: equal singleton sets force equal elements. We write |A| < |P(A)| to mean that such an injection exists but no bijection exists. For A = ∅, the power set is {∅}, not ∅; the empty function misses its only target element. The theorem includes this case.

For a finite set of n elements, each element has two membership choices, giving 2ⁿ subsets. Cantor’s argument also works for infinite A without treating an infinite cardinality as an ordinary integer exponent. It gives a larger cardinality each time a power set is taken; it does not claim that every uncountable set has one common size.

Different digit strings can name the same real number

The interval (0, 1) consists of real numbers x with 0 < x < 1. Write their fractional decimal places from left to right. A terminating decimal is extended with zeros, as 0.5 = 0.5000… . The same real also has the expansion 0.4999… . Thus simply changing a digit in an arbitrary expansion is not enough to prove that its real value changed.

The only ambiguity is a terminating expansion with trailing zeros versus its alternative with trailing nines. To see why, suppose two decimal strings first differ at fractional place k. The gap contributed there is at least 10⁻ᵏ; the whole later tail can compensate by at most 10⁻ᵏ. Equality is possible only when that gap is exactly one unit at place k, the smaller string continues entirely with nines, and the larger continues entirely with zeros.

Choose the canonical expansion which is not eventually all nines. In particular, terminating values use trailing zeros. This removes the ambiguity. Every real in (0, 1) has such a chosen expansion; decimal places express the exact real, not a calculator’s rounded finite display. The infinite tail bound used above is the positional-value fact 9×10⁻⁽ᵏ⁺¹⁾ + 9×10⁻⁽ᵏ⁺²⁾ + … = 10⁻ᵏ.

Construct a real number missing from every proposed list

Suppose x₀, x₁, x₂, … were a list of every real number in (0, 1). Write each in its canonical decimal expansion. Let aₙ be the digit of xₙ at fractional place n+1; zero-based row 0 uses the first fractional place, row 1 the second, and so on.

At place n+1 choose dₙ = 2 if aₙ = 1, and dₙ = 1 otherwise. Define y = 0.d₀d₁d₂… using this rule at every place. Its digits are only 1 or 2, so 1/9 ≤ y ≤ 2/9 and y ∈ (0, 1). It is neither eventually all zeros nor eventually all nines, so its expansion has no alternative terminating representation.

For every n, the chosen digit dₙ differs from the corresponding digit aₙ of xₙ. Both are canonical expansions, so uniqueness gives y ≠ xₙ. The supposed complete list misses y, a contradiction. This defeats any list; therefore (0, 1) is uncountable. If ℝ were countable, its subset (0, 1) would be countable too, so ℝ is uncountable.

A finite grid shows only an initial segment of y. It does not identify all its digits, prove that a particular finite decimal is irrational, or exclude an unseen row by itself. The proof is the rule for every n and the differing digit chosen against every row n. It does not assume that an uncountable set must be the next cardinality after N₀.

Predict the next match, rank or changed digit

In the matching scene, predict the input that reaches 6 under the shift, 10 under the even-number map, and −2 under the integer list. Reveal the exact pairs and compare them with the formulas: the inputs are 5, 5 and 4. The empty case shows a genuine empty pairing rather than a single element named ∅.

In the pair scene, change the last included diagonal. Predict when (1, 2) appears: its sum is 3 and its rank is 7. In the fraction scene, predict which cells are skipped at sum 6. The unreduced fractions 2/4, 3/3 and 4/2 are skipped; 1/5 and 5/1 are retained. The tables give every displayed retained value and its signed-list index.

In the subset and decimal scenes, identify the diagonal entries before revealing the changed row. Each new entry must oppose the entry in its own row, not every entry in its column. Finish by explaining what the finite construction proves and what the infinite definition adds. Return to the union section to reuse the finite-rank coverage argument, and to the decimal section to explain why the real-number conclusion needs canonical expansions.

Worked examples

Try it yourself

1. Under this lesson’s convention, classify ∅, {∅}, {0, 1, 2} and N₀ as finite, countable or countably infinite. Is ∅ = {∅}?

   Show the answer and reasoning

   The first three are finite and countable, with sizes 0, 1 and 3. N₀ is countably infinite. ∅ and {∅} are different sets.

   The empty set has no member; {∅} has one member, namely the empty set. Countable includes finite sets, while countably infinite requires a bijection from N₀. A finite set cannot provide distinct outputs for every index in N₀.

2. Is f(n) = n+3 a bijection N₀ → {3, 4, 5, …}? Is it a bijection N₀ → N₀? Give the inverse where it exists.

   Show the answer and reasoning

   It is a bijection onto {3, 4, 5, …}, with inverse k ↦ k−3. It is not a bijection onto N₀ because 0, 1 and 2 are missed.

   Adding 3 preserves distinctness. Every declared target element k ≥ 3 gives a valid nonnegative input k−3. If the target changes to all N₀, those three additional target elements have no preimage; the rule remains injective but ceases to be surjective.

3. At which zero-based indices do 7 and −7 appear in 0, 1, −1, 2, −2, …? What integer occurs at index 18?

   Show the answer and reasoning

   7 is at index 13; −7 is at index 14. Index 18 contains −9.

   A positive k has index 2k−1 and a negative −k has index 2k. Since 18 = 2×9 is a positive even index, its output is −9. Index 0 is treated separately and gives 0.

4. Find the ranks of (1, 2) and (0, 4). Recover the pair at rank 8. Why does finishing row 0 before row 1 fail?

   Show the answer and reasoning

   The ranks are 7 and 10. Rank 8 contains (2, 1). Finishing the infinite row 0 would leave no later starting position for row 1.

   For sum 3, T₃ = 6, so (1, 2) has rank 6+1 = 7 and rank 8 has first entry 2, second entry 1. For (0, 4), T₄ = 10. A sum diagonal is finite, whereas an entire row is infinite; only the diagonal sweep guarantees that other rows are reached.

5. At positive sum p+q = 6, which fractions are retained, and which are skipped? Explain why the skipped fractions do not represent new rational values.

   Show the answer and reasoning

   Retain 1/5 and 5/1. Skip 2/4 = 1/2, 3/3 = 1 and 4/2 = 2.

   The retained numerator-denominator pairs have gcd 1; the skipped pairs have gcd 2, 3 and 2 respectively. Their reduced values appeared on earlier diagonals. The enumeration must count rational numbers once, rather than count multiple expressions for the same value.

6. Sweep supplied rows A₀ = (a, b), A₁ = (), A₂ = (b, c) by increasing i+j, increasing i within a diagonal. Skip empty slots and duplicate values. What distinct-value list results, and why is the analogous supplied infinite family countable?

   Show the answer and reasoning

   The result is a, b, c. For a supplied infinite family, each element has a finite-rank slot, and its first occurrence can be indexed by a subset of N₀.

   The first two nonempty slots are (0, 0) and (0, 1). Slot (2, 0) repeats b, and (2, 1) contributes c. For infinitely many supplied rows the same sweep reaches any specified slot on its finite sum diagonal. Sorting the first-occurrence ranks yields a finite or bijective infinite list without needing to choose unspecified row lists.

7. Given subset rows (0, 1, 0), (1, 1, 0) and (0, 0, 0) on columns 0, 1, 2, find the complement diagonal. Also find P(∅).

   Show the answer and reasoning

   The new row is (1, 0, 1), the visible subset {0, 2}. P(∅) = {∅} has one element.

   The diagonal is (0, 1, 0); flip it entry by entry. The result differs from each shown row at that row’s own column. The empty set has exactly one subset, itself; the power set contains that subset as one element rather than being empty.

8. For f: A → P(A), define D = {a ∈ A : a ∉ f(a)}. If f(c) = D, what happens when c ∈ D? What happens when c ∉ D?

   Show the answer and reasoning

   The first case forces c ∉ D; the second forces c ∈ D. Both are contradictions, so D is not an output of f.

   Membership in D is defined to oppose membership in f(c) at c. Substituting f(c) = D makes each assumption reverse itself. Since f was arbitrary, every such function misses a subset and no surjection, hence no bijection, from A to P(A) exists.

9. A proposed canonical real list has diagonal digits 0, 1, 9, 2, 1. Find the first five replacement digits. Why would arbitrary different decimal strings be insufficient?

   Show the answer and reasoning

   The replacement digits are 1, 2, 1, 1, 2. Arbitrary strings may still denote one value, such as 0.5000… = 0.4999… .

   Use 2 only when the original diagonal digit is 1, and 1 otherwise. Canonical expansions exclude tails of all nines; the constructed all-1-or-2 expansion has no ambiguity. Its difference from each canonical row at the selected place therefore establishes a difference of real values.

10. A five-row grid produces a new five-digit prefix. Does this prove that the new real is irrational, that an unseen row differs, or that all uncountable sets have the same cardinality? What does the complete diagonal argument prove?

    Show the answer and reasoning

    None of those three claims follows from the finite grid. The complete rule proves that no N₀-indexed list contains every real in (0, 1).

    A finite prefix allows many possible tails and could agree with an unseen row. The infinite diagonal chooses a differing digit against every row and uses canonical expansions, proving uncountability. It neither decides the new number’s rationality from a prefix nor compares all uncountable cardinalities with one another.

What to carry forward

• Equal cardinality means a bijection with the declared whole target, even when one infinite set is a proper subset of the other.
• Countable includes finite sets and ∅ here; countably infinite means a repetition-free complete list indexed by N₀.
• A sum-diagonal sweep assigns every pair a finite rank. Reduced fractions, signs and first-occurrence filtering turn it into other complete lists.
• Diagonalisation opposes an arbitrary list at every row’s own index. A finite window illustrates that rule but does not replace its general proof.
• P(N₀) and (0, 1) are uncountable. The decimal proof needs unique chosen expansions; Cantor’s power-set theorem applies to every set.