Countable Infinity
The smallest type of infinity, representing sets whose elements can be listed in a sequence and matched one-to-one with the natural numbers.
Also known as: Aleph-Null, Aleph-Naught, Countable Set, Denumerable Set
Category: Concepts
Tags: mathematics, set-theory, infinity, abstraction
Explanation
Countable Infinity (denoted aleph-null or aleph-naught) is the cardinality (size) of the set of natural numbers {1, 2, 3, ...}. A set is countably infinite if its elements can be arranged in a sequence — even if that sequence is infinite, every element eventually gets a turn.
**Formally**:
A set S is countably infinite if there exists a bijection (one-to-one correspondence) between S and the natural numbers. This means every element in S can be 'counted' — assigned a unique natural number.
**Surprisingly countable sets**:
- **Integers**: {..., -2, -1, 0, 1, 2, ...} — despite extending in both directions, they can be listed: 0, 1, -1, 2, -2, 3, -3, ...
- **Rational numbers**: All fractions p/q — despite being dense (between any two rationals lies another), they can be enumerated using Cantor's zigzag argument
- **Algebraic numbers**: All roots of polynomial equations with integer coefficients
- **Pairs of natural numbers**: All (m, n) pairs — countable via Cantor's pairing function
**Properties**:
- The union of countably many countable sets is countable
- Any subset of a countable set is countable (or finite)
- Countable infinity plus countable infinity equals countable infinity
- Countable infinity times countable infinity equals countable infinity
**The boundary**:
Countable infinity is the smallest infinity. Cantor proved that the real numbers are uncountably infinite — strictly larger. This was a revolutionary discovery: not all infinities are the same size.
**Connection to computability**:
Countable infinity appears throughout computer science. The set of all possible programs is countably infinite, but the set of all possible functions is uncountably infinite. This means most functions cannot be computed — a fundamental result in the theory of computation.
Related Concepts
← Back to all concepts