Cardinality and countability

How to say two sets have the same size without counting them: a set is finite if some n = {1, …, n} is in bijection with it, and two sets have the same cardinality when a bijection exists. The subject the last chapter of baker-algebra-number-theory teaches, in about ten pages.

What the chapter proves

• The pigeonhole principle in its two versions, as a statement about injections between finite sets.
• Infinite and countable sets. The chapter defines countable sets by a bijection with ℕ₀ (or finiteness) and lists the standard consequences, such as the real algebraic numbers (roots of monic polynomials over ℚ) being countable.
• No set surjects onto its power set (Theorem 4.14, called Russell's Paradox in the notes), so power sets always have strictly larger cardinality.
• ℝ is uncountable (Cantor). The proof lists (0, 1] as non-terminating decimals and builds a number that differs from the kth entry in the kth place, using only the digits 1 and 2 so it stays non-terminating. This is the diagonalization argument.

Where it sits

lal-algebra-1 gives logic and set theory two full chapters before any algebra, with Russell's and Cantor's paradoxes as the motivation. Baker gives the topic one chapter and puts it last, after number-theory and group-theory, with no motivation beyond counting. klazar-elementary-real-analysis builds the number systems from set theory and is the other source here touching the same ground. This page records the elementary treatment; the foundations-level one lives in those sources.