Day 43 — Countability

Day 43 — Countability

Stage IV · concept day
Goal: Define countable sets; show \(\mathbb{Z}\) and \(\mathbb{Q}\) are countable (sketches); prove \((0,1)\) uncountable by Cantor diagonal; know continuum awareness; prove \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\).

Why this matters

“Countable” means listable in a sequence (possibly infinite). Computers enumerate \(\mathbb{N}\), finite strings, and programs—all countable. Real numbers and arbitrary function spaces are vastly larger: you cannot list all reals or all subsets of \(\mathbb{N}\). Diagonalization is the ancestor of undecidability and many impossibility proofs in CS theory.

Theory

Finite and infinite

\(A\) is finite if \(A=\emptyset\) or \(|A|=n\) for some \(n\in\mathbb{N}\) (bijection with \(\{1,\ldots,n\}\)).
Otherwise infinite.

Countably infinite and countable

\(A\) is countably infinite if there is a bijection \(\mathbb{N}\to A\) (or \(\mathbb{N}^+\to A\)).
\(A\) is countable if finite or countably infinite.
Equivalently: there exists an injection \(A\to\mathbb{N}\), or a surjection \(\mathbb{N}\to A\) (for nonempty \(A\)).

Enumerable: list \(a_0,a_1,a_2,\ldots\) possibly with repeats (surjection from \(\mathbb{N}\)).

Basic countable sets

• \(\mathbb{N}\), \(\mathbb{Z}\) (list \(0,1,-1,2,-2,\ldots\)).
  
• \(\mathbb{N}\times\mathbb{N}\) (diagonal enumeration).
  
• Finite products of countable sets.
  
• Finite strings \(\Sigma^*\) over finite \(\Sigma\) (union by length).
  
• \(\mathbb{Q}\) (list fractions in lowest terms by height \(|p|+|q|\)).

Theorems (tools)

1. Subset of countable is countable.
   
2. Image of countable under a function is countable.
   
3. Countable union of countable sets is countable.
   Sketch: arrange in a grid; diagonal walk; or map \(\bigcup_n A_n\) via pairs \((n,k)\) indexing \(A_n\).
   
4. Finite product of countable is countable.

\(\mathbb{Z}\) countable (sketch)

Define \(f:\mathbb{N}\to\mathbb{Z}\) by \(f(0)=0\), \(f(2k-1)=k\), \(f(2k)=-k\) for \(k\ge 1\). Bijective.

\(\mathbb{Q}\) countable (sketch)

Every rational \(p/q\) in lowest terms, \(q>0\). Enumerate by stages \(n=|p|+q\); each stage finite; countable union of finite sets. Discard duplicates. Hence injection \(\mathbb{Q}\to\mathbb{N}\) exists (or surjection from \(\mathbb{N}\)).

\(\mathbb{N}\times\mathbb{N}\) countable

Cantor pairing: list \((0,0),(0,1),(1,0),(0,2),(1,1),(2,0),\ldots\) by diagonals \(i+j=\mathrm{const}\).
Pairing function \(\pi(k,m)=\frac{(k+m)(k+m+1)}{2}+m\) (one common form)—bijection \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\).

Uncountable: Cantor diagonal on \((0,1)\)

Theorem. \((0,1)\) is uncountable.

Proof. Suppose for contradiction \((0,1)\) is countable: list all elements as infinite decimals
\(x_1 = 0.d_{11}d_{12}d_{13}\ldots\),
\(x_2 = 0.d_{21}d_{22}d_{23}\ldots\),
…
Define \(y = 0.e_1 e_2 e_3\ldots\) with \(e_n = 4\) if \(d_{nn}\neq 4\), and \(e_n=5\) if \(d_{nn}=4\) (avoid \(0\) and \(9\) to dodge dual representations).
Then \(y\in(0,1)\) but \(y\neq x_n\) for all \(n\) (differs in \(n\)-th place). Contradiction. \(\square\)

Hence \(\mathbb{R}\) uncountable (contains \((0,1)\)).

Continuum awareness

\(|\mathbb{R}| = 2^{\aleph_0} = \mathfrak{c}\) (continuum) under standard identification with \(\mathcal{P}(\mathbb{N})\) equinumerosity flavor (\(|\mathbb{R}|=|\mathcal{P}(\mathbb{N})|\)).
Continuum hypothesis (CH): no cardinality strictly between \(\mathbb{N}\) and \(\mathbb{R}\)—independent of standard ZFC (awareness only).

Power set strictly larger (Cantor)

Theorem. For any set \(A\), there is no surjection \(A\to\mathcal{P}(A)\). In particular \(|\mathcal{P}(A)| > |A|\) when infinite (and for finite already \(2^n > n\) for \(n\ge 0\) with care at \(0\)).

Proof (diagonal). Suppose \(f: A\to\mathcal{P}(A)\). Let
\[D = \{ a\in A : a \notin f(a) \}.\]
If \(D=f(a_0)\), then \(a_0\in D \Leftrightarrow a_0\notin f(a_0)=D\), contradiction. So \(f\) not surjective. \(\square\)

Thus \(|\mathcal{P}(\mathbb{N})| > |\mathbb{N}|\): uncountably many subsets of \(\mathbb{N}\); uncountably many languages over \(\{0,1\}\); uncountably many functions \(\mathbb{N}\to\{0,1\}\).

Countable vs computable (awareness)

There are countably many programs (finite strings) but uncountably many languages/subsets of \(\mathbb{N}\)—most languages are not decidable / not even recognizable. Diagonalization appears again in undecidability proofs.

Worked examples

Example 1 — List \(\mathbb{Z}\)

\(0,1,-1,2,-2,3,-3,\ldots\)

Example 2 — Finite product

\(\mathbb{Z}^3\) countable: \((\mathbb{Z}\times\mathbb{Z})\times\mathbb{Z}\).

Example 3 — \(\Sigma^*\)

Binary strings: \(\varepsilon,0,1,00,01,10,11,\ldots\) by length then lex.

Example 4 — Union

\(\bigcup_{n=1}^\infty \{n\}\times\mathbb{Z}\) countable.

Example 5 — Diagonal y

If list starts \(0.1000\ldots\), \(0.1222\ldots\), … construct \(y\) differing on diagonal.

Example 6 — \(\mathcal{P}(\mathbb{N})\) injection from \(\mathbb{N}\)

\(n\mapsto \{n\}\) shows \(|\mathbb{N}| \le |\mathcal{P}(\mathbb{N})|\); Cantor shows not equal.

Example 7 — Functions \(\mathbb{N}\to\{0,1\}\)

Identified with characteristic sequences / subsets: uncountable.

Example 8 — Algebraic reals countable

Countable union over degrees of finite root sets of integer polynomials—countable. Hence transcendentals exist (reals uncountable).

Example 9 — Intervals

Any nonempty open interval equinumerous with \(\mathbb{R}\) (awareness: tan bijection).

Example 10 — No listing of all reals

Any purported list misses the diagonal real.

Example 11 — Countable union of finite

All finite subsets of \(\mathbb{N}\) is countable (union over size \(k\) of \(\binom{\mathbb{N}}{k}\) countable).
But \(\mathcal{P}(\mathbb{N})\) also has infinite subsets—uncountable.

Example 12 — Hilbert hotel

Full countable hotel can still accommodate one more: shift \(n\mapsto n+1\). Awareness anecdote for infinite bijections.

Example 13 — Surjection \(\mathbb{N}\to\mathbb{Q}^+\)

Enumerate; repeats OK.

Example 14 — Injection \(\mathbb{N}\to\mathbb{R}\)

\(n\mapsto n\); reals larger.

Exercises

1. Define countable and countably infinite.
   
2. Give an explicit bijection \(\mathbb{N}\to\mathbb{Z}\).
   
3. Explain diagonal enumeration of \(\mathbb{N}\times\mathbb{N}\).
   
4. Prove: subset of countable set is countable.
   
5. Prove: countable union of countable sets is countable (grid argument).
   
6. Sketch countability of \(\mathbb{Q}\).
   
7. Prove \((0,1)\) uncountable by diagonal (write carefully).
   
8. Conclude \(\mathbb{R}\) uncountable.
   
9. Prove no surjection \(A\to\mathcal{P}(A)\) for any \(A\).
   
10. Show the set of all infinite binary sequences is uncountable.
    
11. Show finite subsets of \(\mathbb{N}\) form a countable set.
    
12. Show \(\mathbb{Q}^n\) countable.
    
13. True/false: union of uncountably many countable sets is countable.
    
14. Show algebraic numbers are countable (outline).
    
15. Why does dual decimal \(0.1999\ldots=0.2000\ldots\) matter for diagonal proofs? How did we avoid it?
    
16. Prove \(|\mathbb{N}| < |\mathcal{P}(\mathbb{N})|\) using injection + Cantor.
    
17. CS: countability of all Python programs (finite text).
    
18. CS: uncountability of all functions \(\mathbb{N}\to\mathbb{N}\).
    
19. Give a countably infinite proper subset of \(\mathbb{Q}\).
    
20. Is \((0,1)\cup(2,3)\) countable?
    
21. Pairing: compute \(\pi(2,3)\) for the displayed formula if you use it.
    
22. Show there are countably many polynomials with rational coefficients.
    
23. Explain Hilbert hotel check-in of one guest.
    
24. Prove: if \(A\) infinite countable and \(a\in A\), then \(A\setminus\{a\}\) still countably infinite.
    
25. One paragraph: how diagonalization foreshadows undecidability.

CS connection

• Programs countable; behaviors often uncountable ⇒ noncomputable functions exist.
  
• Languages: \(|\mathcal{P}(\Sigma^*)|=|\mathcal{P}(\mathbb{N})|\) uncountable; only countably many TMs.
  
• Floating point is finite (hence countable)—not \(\mathbb{R}\).
  
• Databases store finite subsets; theory still uses \(\mathbb{Q},\mathbb{Z}\).
  
• Hashing infinite domains cannot be injective into finite tables.
  
• Diagonal arguments in proof of undecidability of halting (later courses).

Common pitfalls

Pitfall	What to do instead
“Infinite = countable”	\(\mathbb{R}\) counterexample
Diagonal with \(0/9\) ambiguity	Avoid those digits
Assuming \(\mathbb{Q}\) uncountable because dense	Density ≠ cardinality
Confusing finite strings vs infinite sequences	\(\Sigma^*\) countable; \(\Sigma^{\mathbb{N}}\) not
Claiming all subsets of \(\mathbb{N}\) finite	Infinite subsets exist
Bijection required for “list”	Surjection enough for countability

Checkpoint

• Define countable
  
• Sketch \(\mathbb{Z}\), \(\mathbb{N}\times\mathbb{N}\), \(\mathbb{Q}\) countable
  
• Full diagonal proof for \((0,1)\)
  
• Cantor power set theorem
  
• Continuum / CH awareness one sentence
  
• CS link: more languages than programs
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — hierarchy of sizes (awareness)

\[ |\mathbb{N}| = \aleph_0 < 2^{\aleph_0} = |\mathbb{R}| = |\mathcal{P}(\mathbb{N})| < |\mathcal{P}(\mathcal{P}(\mathbb{N}))| < \cdots \]

Each power set strictly increases cardinality (Cantor’s theorem iterated).
No “largest” infinite set in this hierarchy.

Computability link (one page in a course)

• Programs ⊆ finite strings ⊆ countable.
  
• Each program decides at most one language (subset of \(\Sigma^*\)).
  
• Only countably many decidable languages.
  
• Uncountably many languages ⇒ almost all undecidable.

Diagonalization in the halting problem is a computable cousin of Cantor’s argument.

Careful with “listing”

A listing \(a_0,a_1,\ldots\) may have duplicates (surjection \(\mathbb{N}\to A\)) and still prove countability. Bijection is cleaner when you can write one.

More worked examples

Example 15 — \(\mathbb{N}^{<\omega}\)
Finite sequences of naturals: countable union over length of \(\mathbb{N}^k\), each countable.

Example 16 — \(\mathbb{R}\times\mathbb{R}\)
\(|\mathbb{R}\times\mathbb{R}|=|\mathbb{R}|\) (interleave decimals awareness)—continuum squared is continuum.

Example 17 — Missing diagonal
Any list of reals in \((0,1)\) misses at least the constructed \(y\).

Example 18 — Finite \(\Rightarrow\) countable
\(\{1,2,3\}\) injects into \(\mathbb{N}\).

Additional exercises

26. Prove \(\mathbb{Z}\times\mathbb{Z}\) countable two ways (product; zigzag).
    
27. Show the set of polynomials with integer coefficients is countable.
    
28. Prove \((0,1)\) and \((0,1)\times(0,1)\) equinumerous (outline).
    
29. Why does “\(\mathbb{Q}\) dense” not imply “\(\mathbb{Q}\) uncountable”?
    
30. Write the diagonal set \(D\) for a supposed enumeration of all subsets of \(\mathbb{N}\).

Extended practice workshop

Prove countable

1. \(\mathbb{N}\)
   
2. \(\mathbb{Z}\) (explicit bijection)
   
3. \(\mathbb{N}\times\mathbb{N}\) (diagonal)
   
4. \(\mathbb{Q}\) (outline by height)
   
5. \(\Sigma^*\) for \(\Sigma=\{0,1\}\)
   
6. Finite subsets of \(\mathbb{N}\)
   
7. \(\mathbb{Z}[x]\) polynomials with integer coeffs (outline)

Prove uncountable

8. \((0,1)\) diagonal full write-up
   
9. \(\mathbb{R}\)
   
10. \(\{0,1\}^{\mathbb{N}}\) infinite binary sequences
    
11. \(\mathcal{P}(\mathbb{N})\) via Cantor theorem
    
12. Functions \(\mathbb{N}\to\mathbb{N}\)

Tools

13. Subset of countable is countable.
    
14. Countable union of countable is countable.
    
15. Image of countable is countable.
    
16. No surjection \(A\to\mathcal{P}(A)\).

CS links

17. Programs countable.
    
18. Languages uncountable.
    
19. Therefore noncomputable languages exist—one paragraph.
    
20. Floating-point sets are finite—not \(\mathbb{R}\).

Careful points

21. Avoid \(0.999=1.000\) in diagonal—how?
    
22. Listing may have duplicates—still OK for countability.
    
23. Density of \(\mathbb{Q}\) ≠ uncountability.

Cardinality postcard

\[|\mathbb{N}| < |\mathcal{P}(\mathbb{N})| = |\mathbb{R}| < |\mathcal{P}(\mathbb{R})| < \cdots\]
(CH: nothing between \(|\mathbb{N}|\) and \(|\mathbb{R}|\)?—independent.)

Synthesis

Countability is bijection-with-\(\mathbb{N}\) thinking (or injection into \(\mathbb{N}\)). Countable sets are listable—possibly with repeats. Uncountable sets are not: Cantor’s diagonal and \(|\mathcal{P}(A)|>|A|\) are the standard hammers. CS punchline: there are countably many programs and uncountably many languages/functions on \(\mathbb{N}\), so most behaviors are noncomputable.

Hierarchy (working picture)

Set	Countable?	Why (sketch)
\(\mathbb{N}\)	yes	identity
\(\mathbb{Z}\)	yes	\(0,1,-1,2,-2,\ldots\)
\(\mathbb{N}\times\mathbb{N}\)	yes	diagonal / Cantor pairing
\(\mathbb{Q}\)	yes	enumerate reduced fractions
\(\Sigma^*\) finite strings	yes	length then lex
\((0,1)\), \(\mathbb{R}\)	no	diagonal
\(\{0,1\}^{\mathbb{N}}\)	no	diagonal / \(\sim\mathcal{P}(\mathbb{N})\)
\(\mathcal{P}(\mathbb{N})\)	no	Cantor theorem

More worked examples

Example — \(\mathbb{Z}\) bijection.
\(f:\mathbb{N}\to\mathbb{Z}\), \(f(0)=0\), \(f(2k-1)=k\), \(f(2k)=-k\) for \(k\ge 1\). Check bijective.

Example — Countable union of countable sets is countable.
List each \(A_i=\{a_{i0},a_{i1},\ldots\}\); zigzag over the grid \((i,j)\) same as \(\mathbb{N}\times\mathbb{N}\). (Careful: needs countable choice in full generality—awareness only.)

Example — Diagonal on \((0,1)\).
Given supposed list \(0.d_{n1}d_{n2}\ldots\), define \(e_n=4\) if \(d_{nn}\neq 4\), else \(e_n=5\) (avoid \(0/9\) terminal issues). Then \(0.e_1e_2\ldots\) differs from every listed expansion.

Example — Cantor theorem.
No surjection \(f:A\to\mathcal{P}(A)\): diagonal set \(D=\{a\in A: a\notin f(a)\}\) cannot be \(f(a_0)\) for any \(a_0\).

Example — Programs vs languages.
Fix finite alphabet; programs \(\subseteq\Sigma^*\) countable. Languages \(\mathcal{P}(\Sigma^*)\) uncountable. Hence some languages have no decider.

Extra exercises (synthesis)

31. Give an explicit injection \(\mathbb{N}\times\mathbb{N}\to\mathbb{N}\) (e.g. \(2^a(2b+1)-1\)).
    
32. Prove any subset of a countable set is countable (finite or countably infinite).
    
33. Prove the set of finite subsets of \(\mathbb{N}\) is countable.
    
34. Prove functions \(\mathbb{N}\to\{0,1\}\) are uncountable.
    
35. Show \((0,1)\) and \((0,2)\) equinumerous via an explicit bijection.
    
36. Explain why density of \(\mathbb{Q}\) in \(\mathbb{R}\) does not make \(\mathbb{Q}\) uncountable.

Proof-tool checklist

Goal	Tool
Show countable	Exhibit injection into \(\mathbb{N}\) or bijection with \(\mathbb{N}\) / known countable
Show uncountable	Diagonal, or reduce from \(\mathcal{P}(\mathbb{N})\) / \((0,1)\)
Compare sizes	Injection both ways (Cantor–Bernstein) awareness
CS noncomputability	Countable programs, uncountable problems

Floating-point sets are finite—do not confuse machine scalars with \(\mathbb{R}\). Continuum hypothesis is optional culture, not a drill target.

Tomorrow

Day 44 — Types/sets analogy. Types as sets of values; sum/product types; option/maybe; predicates as subsets; specs vs implementation—no coding labs.