Exercises: Cardinality and Infinity

These build from mechanical warm-ups to full proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Every problem in this set turns on the same two moves — build a bijection to prove "same size," and walk the diagonal to prove "no list can contain everything" — so keep §10.2's sweep and §10.3's dodge straight as you go. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek. Throughout, $\mathbb{N} = \{0, 1, 2, \dots\}$ includes 0.

Part A — Warm-ups (⭐)

10.1 † State, in one sentence each, what you must produce to prove (a) $\lvert A\rvert = \lvert B\rvert$, and (b) $\lvert A\rvert \le \lvert B\rvert$. Name the one property the object in (a) has that the object in (b) need not.

10.2 The zig-zag bijection $f\colon \mathbb{N} \to \mathbb{Z}$ from §10.2 is $f(n) = n/2$ if $n$ is even and $-(n+1)/2$ if $n$ is odd. Compute $f(0), f(1), \dots, f(8)$, and find which $n$ maps to the integer $-5$.

10.3 † Classify each set as finite, countably infinite, or uncountable — no proof needed, just the answer: (a) $\{n \in \mathbb{N} : n < 10^{100}\}$; (b) the set of multiples of 7 in $\mathbb{N}$; (c) $\mathbb{R}$; (d) the set of all finite strings over $\{0, 1\}$; (e) the power set $\mathcal{P}(\mathbb{N})$; (f) $\mathbb{Q} \cap [0, 1]$.

10.4 Using the anti-diagonal grid sweep of §10.2, write out the first ten positive fractions in the order the sweep visits them (before discarding repeats), then cross out the ones that are not in lowest terms.

10.5 † In the diagonal proof that $[0,1)$ is uncountable, the digit rule is $x_k = 5$ if $d_{kk} \ne 5$, else $x_k = 4$. Given the partial table below, write the first four digits of the escaping number $x$.

        digit 0   digit 1   digit 2   digit 3
  r_0      3         1         4         1
  r_1      2         7         1         8
  r_2      0         0         5         0
  r_3      9         9         9         5

10.6 Fill in the blanks: a set $S$ is countable iff its elements can be arranged in a list $s_0, s_1, s_2, \dots$ with no \underline{\hphantom{xxxxx}} (the list is injective) and no \underline{\hphantom{xxxxx}} (the list is surjective). Equivalently, there is a \underline{\hphantom{xxxxx}} from $\mathbb{N}$ onto $S$.

10.6b Compute the Cantor pairing index $\pi(i,j) = \frac{(i+j)(i+j+1)}{2} + j$ for the cells $(0,0), (1,0), (0,1), (2,0), (3,2)$. Then, going the other way, find the grid cell $(i,j)$ whose index is $\pi(i,j) = 12$. (This is the bijection $\mathbb{N}\times\mathbb{N}\to\mathbb{N}$ by hand.)

Part B — Prove it (⭐⭐)

Every proof in this part is one of two shapes. To show "same size," produce a bijection and verify injectivity and surjectivity (§10.1–10.2). To show "countable," produce an explicit listing — a bijection with $\mathbb{N}$, or a sweep that gives every element a finite position (§10.2). Write the strategy in one line before the formal argument, exactly as the chapter does.

10.7 † (Scaffolded — fill in the missing steps.) Prove that the set of odd natural numbers $O = \{1, 3, 5, \dots\}$ is countably infinite by exhibiting a bijection $f\colon \mathbb{N} \to O$. - The map: define $f(n) = \underline{\hphantom{xxxx}}$ (a formula in $n$ producing the $n$-th odd number, starting from $f(0) = 1$). - Injective: suppose $f(m) = f(n)$. Then $\underline{\hphantom{xxxxxxxx}}$, which simplifies to $m = n$. - Surjective: take any odd $b \in O$. Then $b = 2k + 1$ for some $k \in \mathbb{N}$, and $f(\underline{\hphantom{xx}}) = b$. - Conclusion: $f$ is a bijection, so $\lvert O\rvert = \underline{\hphantom{xxxx}}$.

10.8 Prove that $\lvert \mathbb{N}\rvert = \lvert \mathbb{N} \setminus \{0, 1, 2\}\rvert$ by constructing an explicit bijection. (Remove finitely many elements from $\mathbb{N}$ — the result is still the same size. Explain in one sentence why this is the signature of an infinite set.)

10.9 † Prove that the union of two countably infinite sets is countably infinite. Strategy: given listings $a_0, a_1, a_2, \dots$ and $b_0, b_1, b_2, \dots$, build one list of the union by interleaving them, and explain why every element lands at a finite position. (Handle the case where the two sets overlap.)

10.10 Prove that $\mathbb{N} \times \mathbb{N}$ is countable by showing the Cantor pairing function $$\pi(i, j) = \frac{(i + j)(i + j + 1)}{2} + j$$ is injective. (You do not need to prove surjectivity for full credit, but state in words why the anti-diagonal picture makes it onto.) Hint: if $\pi(i,j) = \pi(i', j')$, first argue the two pairs lie on the same anti-diagonal, i.e. $i + j = i' + j'$.

10.11 † Prove that any subset of a countable set is countable. Strategy: if $S$ is countable it has a listing $s_0, s_1, s_2, \dots$; given $T \subseteq S$, describe how to extract a listing of $T$ from it. Why does this immediately tell you the primes are countable?

10.12 Prove that the open interval $(0, 1)$ and the whole real line $\mathbb{R}$ are equinumerous by exhibiting a bijection between them. Hint: a function from trigonometry or a rational function such as $g(x) = \frac{2x - 1}{x(1 - x)}$ works; pick one and argue it is a bijection $(0,1) \to \mathbb{R}$. What does this prove about $\lvert (0,1)\rvert$?

Part C — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Keep each solution under 30 lines. Remember the chapter's division of labor (theme four): code demonstrates the mechanism on a finite window; it never proves the infinite claim. Your # Expected output: is evidence, and you should be able to say in one sentence why it is not a proof.

10.13 † Write a generator rationals_positive() that yields positive fractions (p, q) (as pairs in lowest terms, p/q) by sweeping the anti-diagonals of the grid from §10.2, skipping any fraction whose value already appeared. Show the first 8 pairs it yields in an # Expected output: comment. (This is "$\mathbb{Q}$ is countable" as a running program.)

10.14 Implement cantor_pair(i, j) and its inverse cantor_unpair(n) (the Toolkit's cardinality.py functions). Then write a loop that checks cantor_unpair(cantor_pair(i, j)) == (i, j) for all i, j in range(20). What single output value confirms the round-trip held on every pair, and why is that evidence rather than proof?

10.15 † Write diagonal_escape(rows) that, given a list of equal-length rows of decimal digits, returns a new row of digits differing from row k at position k (use the 4/5 rule from §10.3). Run it (by hand) on the table [[1,1,1],[2,2,2],[3,3,3]] and confirm in code that the result differs from every row's diagonal entry. Put the result and the boolean check in your # Expected output:.

10.16 Write a function is_in_evens_image(e) returning True iff the integer e is in the image of the bijection $f(n) = 2n$ from $\mathbb{N}$ to the even naturals, and recover(e) returning the unique n with $f(n) = e$ when it exists. Demonstrate on e = 0, 7, 8, 100.

Part D — Find the error (⭐⭐)

Each "proof" below is wrong. State precisely which part fails and why. The skill is surgical: name the exact sentence that does not follow, say why it fails, and — where you can — give the smallest concrete witness to the failure. Vague objections ("infinity is weird") earn nothing; the chapter's own "🐛 Find the Error" callouts in §10.1 and §10.3 are the model.

10.17 † Claim: "$\mathbb{R}$ is countable." "Proof": "By §10.2, $\mathbb{Q}$ is countable. Every real number is the limit of a sequence of rationals (rationals are dense in $\mathbb{R}$). A limit of elements drawn from a countable list is itself reachable from that list, so $\mathbb{R}$ is countable too." ∎ — Find the flaw. (Relate it to the chapter's "🐛 Find the Error" callout in §10.3.)

10.18 Claim: "Cantor's argument is bogus, because once it produces the missing number $x$, we can just insert $x$ at the front of the list, and now the list is complete." Explain in two or three sentences exactly why this objection fails — what does re-running the construction on the patched list produce?

10.19 † Claim: "The set of all functions $\mathbb{N} \to \{0, 1\}$ is countable." "Proof": "Each such function is determined by finitely much information — for any input $n$ you only need to know the value $f(n)$ — and a thing determined by finite information is describable by a finite string. Finite strings are countable (§10.4, Step 1), so the functions are countable." ∎ — Pinpoint the fallacy. (What is the difference between "$f(n)$ is finite for each $n$" and "$f$ has a finite description"?)

10.20 Claim: "$\lvert \mathbb{N}\rvert < \lvert E\rvert$ where $E$ is the even naturals, because $E \subset \mathbb{N}$ and a proper subset is strictly smaller." Identify the false premise and cite the exact result from §10.1 that contradicts it.

Part E — Model it & Conjecture and test (⭐⭐⭐)

10.21 † (Model it.) A startup claims its new file format can losslessly compress every infinite bit-stream (every function $\mathbb{N} \to \{0,1\}$) down to a finite file, with a decompressor that perfectly reconstructs the original stream. Translate this claim into a statement about cardinalities of two sets, then use a result from §10.4 to prove the claim is impossible. (This is the counting argument behind "no universal lossless compressor exists.")

10.22 (Model it.) You are designing the ID scheme for a logging system that will, over infinite runtime, emit log records, where each record is tagged by a pair (stream_id, sequence_number) with both drawn from $\mathbb{N}$. Your colleague says "we'll run out of 64-bit IDs because there are infinitely many pairs." Model the set of records as a discrete-math object, state precisely which cardinality it has, and explain — using §10.2 — why a single countable ID space suffices in principle (ignoring the finite 64-bit limit). Which Toolkit function realizes the ID assignment?

10.23 † (Conjecture and test, then prove.) Let $T$ be the set of real numbers in $[0,1)$ whose decimal expansion uses only the digits 0 and 1. Write code that lists, in the diagonal order of §10.2, the first several such numbers that have a terminating expansion (finitely many nonzero digits), and conjecture whether $T$ — the full set, including non-terminating expansions — is countable or uncountable. Then prove your conjecture. Hint: try the diagonal argument restricted to $T$; what digit rule stays inside $\{0,1\}$?

10.24 (Conjecture and test, then prove.) Define $g\colon \mathbb{N} \times \mathbb{N} \to \mathbb{N}$ by $g(i, j) = 2^i (2j + 1) - 1$. Write code that computes $g(i,j)$ for all $i, j < 6$, collect the outputs in a set, and check for collisions and for which values in range(40) are hit. Conjecture whether $g$ is a bijection $\mathbb{N} \times \mathbb{N} \to \mathbb{N}$, then prove your conjecture. (This gives a second, independent proof that $\mathbb{N} \times \mathbb{N}$ is countable — compare it to the Cantor pairing.)

10.25 (Model it + prove.) Argue that the set of all programs in your favorite language that halt on all inputs (the "total" programs) is countable. Then explain, in one paragraph, why this does not by itself name an uncomputable problem — what extra ingredient does Chapter 36 supply to turn "uncomputable problems exist" into "here is one"?

Part F — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

10.26 † (Ch. 9 + 10.) In §10.1 we used that a bijection $f\colon A \to B$ has an inverse $f^{-1}\colon B \to A$. Using only the Chapter 9 definitions of injective and surjective, prove that if $f$ is a bijection then $f^{-1}$ is also a bijection. Conclude in one sentence why "equinumerous" is a symmetric relation.

10.27 (Ch. 8 + 10.) A decision problem was identified in §10.4 with a function $\mathbb{N} \to \{0,1\}$, which corresponds to a subset of $\mathbb{N}$ (its "yes" inputs). Make the correspondence explicit: describe the bijection between $\mathcal{P}(\mathbb{N})$ and the set of functions $\mathbb{N} \to \{0,1\}$, naming the indicator function. Then state what $\lvert \mathcal{P}(\mathbb{N})\rvert > \lvert \mathbb{N}\rvert$ says about decision problems.

10.28 † (Ch. 5 + 10.) Cantor's theorem is itself a proof by contradiction. Reconstruct it: let $S$ be any set and suppose, for contradiction, that there is a surjection $f\colon S \to \mathcal{P}(S)$. Consider the "diagonal" set $D = {x \in S : x \notin f(x)}$. Derive a contradiction by asking whether the element $s$ with $f(s) = D$ belongs to $D$. (This is the master diagonal argument; §10.4's bit-flip is the special case $S = \mathbb{N}$.)

10.29 (Ch. 6 + 10.) Prove by induction on $n$ that for every $n \ge 0$, the set of finite strings of length exactly $n$ over a fixed alphabet of size $a \ge 1$ is finite, with exactly $a^n$ elements. Then explain in one sentence how this feeds the §10.4 argument that all finite strings form a countable set. (You proved the $2^n$ special case in Exercise 6.23 / §6 for truth tables — this is the same counting idea.)

10.30 (Deep Dive.) Prove Cantor's theorem in full: for every set $S$, $\lvert S\rvert < \lvert \mathcal{P}(S)\rvert$. You must show two things: (i) there is an injection $S \to \mathcal{P}(S)$ (easy — map $x$ to $\{x\}$); and (ii) there is no surjection $S \to \mathcal{P}(S)$ (the diagonal argument of 10.28). Conclude that there is no largest infinity.

10.31 (Deep Dive.) Use Cantor's theorem to build an explicit infinite strictly increasing tower of cardinalities starting from $\mathbb{N}$: $$\lvert \mathbb{N}\rvert < \lvert \mathcal{P}(\mathbb{N})\rvert < \lvert \mathcal{P}(\mathcal{P}(\mathbb{N}))\rvert < \cdots$$ Explain why each "$<$" is strict and why the tower never terminates. Which two named cardinalities are the first two rungs?

10.32 (Deep Dive — preview of Chapter 36.) Sketch how the diagonal bit-flip of §10.4 becomes the proof that the halting problem is undecidable. Set it up: suppose a program $H(p, x)$ decides whether program $p$ halts on input $x$; build a program $D$ that, on input $p$, "does the opposite" of $H(p, p)$. Ask what $D$ does on input $D$, and locate the contradiction. (You are not expected to write the formal proof — just identify where the diagonal flip lives and why it forces a contradiction. Chapter 36 completes it.)

10.33 (Deep Dive — synthesis.) The chapter draws four consequences for programmers in §10.6: limits of computation, floating point as a countable net, most reals being unnameable, and no language being universal over all functions. Pick two of the four and, for each, write a precise two-sentence argument naming (a) which set is countable, (b) which set is uncountable, and (c) the resulting impossibility. Then state in one sentence the single pattern all four share.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: a clearly stated bijection or diagonal construction, an explicit injectivity / surjectivity (or "differs at digit $n$") check, correct handling of the 0-in-$\mathbb{N}$ convention, and a clean conclusion stating which cardinality comparison you have established.