Countable Sets

Set Theory · Axiom Academy

Understanding sets that can be enumerated with natural numbers A set A is called countable if its cardinality is less than or equal to that of the natural numbers. When the cardinality equals exactly that of the natural numbers, we say the set is countably infinite . At first glance, the integers seem "twice as large" as the natural numbers since they extend infinitely in both directions. However, we can prove they're countable using a clever zigzag enumeration . We arrange the integers in the sequence: 0, 1, -1, 2, -2, 3, -3, 4, -4, ... This establishes a bijection with the natural numbers, proving that the integers have the same cardinality as the naturals. 3. The Rationals are Countable Perhaps the most surprising result is that the rational numbers are countable. Using Cantor's diagonal argument , we arrange all positive rationals in an infinite grid and traverse them diagonally, skipping duplicates. Each row n contains all fractions with denominator n . By following diagonal paths and eliminating reduced fractions we've already counted, we create a sequence that lists every positive rational exactly once. An important theorem states that the countable union of countable sets is countable . If we have countably many sets, each of which is countable, their union is also countable. This is proven using a diagonal enumeration similar to the rationals. Arrange the elements of each set in rows, then traverse diagonally to create a single sequence listing all elements.

This is the written version of the interactive lesson above. See the full Set Theory course.