Countability and Cantor's diagonal argument

前置知识

14 项必需的前置知识（一直追溯到底）

你将学会

• Show that ℤ and ℚ are countable by constructing explicit enumerations or bijections.
• Define the power set P(A) and prove Cantor's theorem that no function A → P(A) is surjective.
• Reproduce Cantor's diagonal argument that [0, 1) is uncountable, handling numbers with two decimal expansions.

定义

• Sets A and B have the same cardinality if there is a bijection A → B.
• A set is countable if it is finite or has the same cardinality as ℕ; otherwise it is uncountable.
• The power set P(A) is the set of all subsets of A.

定理

• ℤ, ℚ and ℕ × ℕ are countable.
• A countable union of countable sets is countable (the general statement uses the axiom of countable choice).
• Cantor's theorem: for every set A there is no surjection from A onto P(A).
• ℝ is uncountable; in fact ℝ and P(ℕ) have the same cardinality.

常见误解

• Thinking a proper subset of an infinite set must be smaller: ℕ and the even numbers have the same cardinality.
• Objecting that the diagonal number 'can just be added to the list'; the argument shows that every list misses some number.
• Forgetting that 0.4999… = 0.5, which a careful diagonal argument must avoid (for example by never changing a digit to 0 or 9).

通向

可选发现

• Forcing and independence Is there a set strictly larger than ℕ but smaller than ℝ? This is the continuum hypothesis; Gödel (1940) and Cohen (1963) showed that, if ZFC is consistent, it can be neither proved nor refuted in ZFC.探奇小径 →
• Gödel's incompleteness theorems A diagonal idea reappears in Gödel's proof through a self-referential sentence; the resemblance is genuine in spirit, but Gödel's diagonal lemma is a different construction.
• ← Counting
• ← Sets
• ← Set-builder notation, quantifiers and infinite sets
• ← Rational numbers

学习路径

• Accelerated secondary progression
• Undergraduate mathematics major

延伸阅读

• Paul R. Halmos, Naive Set Theory (1960)
• Martin Aigner and Günter M. Ziegler, Proofs from THE BOOK (1998)