Aleph-null, written , is the smallest infinite cardinal number. It is the cardinality of the set of natural numbers: a set has cardinality precisely when its elements can be placed in one-to-one correspondence with the natural numbers. Such a set is called countably infinite. Aleph-null provides a precise mathematical meaning for one size of infinity, distinct from larger infinite cardinalities such as that of the real numbers.
Definition and notation
Taking , the defining equation is
Here denotes the cardinality of a set . A set has cardinality if there exists a bijection
A bijection pairs every natural number with exactly one element of , using every element of exactly once. Equivalently, the elements of can be listed as
with neither omissions nor repetitions. Such a listing need not follow a set’s usual numerical or geometric order.
The symbol is the Hebrew letter aleph. Its subscript identifies the first member of the aleph sequence, which enumerates the infinite cardinal numbers associated with well-orderable sets.
A countable set is commonly defined to mean either a finite set or a countably infinite set. Under that convention, “countable” does not by itself imply cardinality ; “countably infinite” does.
Basic examples
Many sets that contain the natural numbers as a proper subset nevertheless have the same cardinality.
Even numbers and integers
The nonnegative even numbers have cardinality , because
is a bijection from to .
The set of integers also has cardinality . One enumeration is
These examples illustrate a characteristic property of infinite sets: a set can have the same cardinality as a proper subset. For finite sets, this is impossible.
Rational numbers
The rational numbers are countably infinite, even though between any two distinct rational numbers there is another rational number.
Every rational number has a representation , where and is a positive integer. The pairs can be listed in increasing order of . Reading their fractions and skipping repeated values yields an enumeration of all rational numbers. Consequently,
This shows that cardinality is different from density: being densely distributed along a line does not make a set uncountable.
Pairs and finite sequences
The Cartesian product is countably infinite. Its pairs can be listed by successive diagonals:
One explicit bijection is the pairing function
More generally, the set of finite sequences of natural numbers is countably infinite. Thus the set of finite strings over a finite or countably infinite alphabet is at most countable. If the alphabet is nonempty and strings of arbitrary finite length are allowed, that set is countably infinite.
Arithmetic of aleph-null
Cardinal arithmetic describes the sizes of sets constructed by disjoint union, Cartesian product, and function formation. It is not the same as ordinary arithmetic with a very large finite number.
Addition and multiplication
For every positive finite integer ,
Also,
The addition identity follows by interleaving two countably infinite lists. The multiplication identity follows from enumerating pairs of natural numbers.
For every positive finite ,
Accordingly, any fixed finite number of natural-number coordinates still gives only countably many possible tuples.
These identities do not support unrestricted cancellation. For example,
does not imply .
Infinite exponentiation
Allowing infinitely many coordinates changes the result. The set of infinite binary sequences has cardinality
which is strictly greater than . A binary sequence corresponds to a subset of : its -th entry records whether belongs to that subset. Thus
where is the power set of .
The set of all infinite sequences of natural numbers has the same cardinality:
There are therefore only countably many finite sequences of natural numbers, but uncountably many infinite ones.
Larger infinities and the continuum
Cantor’s theorem states that every set has strictly smaller cardinality than its power set. Applied to , it gives
The real numbers have cardinality
also called the cardinality of the continuum. They cannot be put into a complete list indexed by the natural numbers. Cantor’s diagonal argument establishes this by constructing, from any proposed list of infinite binary sequences, a sequence that differs from the -th listed sequence at its -th position.
The next aleph after is , the smallest uncountable cardinal. The continuum hypothesis asserts that
It is independent of the usual axioms of Zermelo–Fraenkel set theory with the axiom of choice, provided those axioms are consistent. Consequently, the strict inequality between countable infinity and the continuum does not, by itself, establish that the continuum is the next infinite cardinal.
Cardinality versus order type
Aleph-null measures size, not order. This distinguishes it from an ordinal number, which describes the order type of a well-ordered set.
The first infinite ordinal is , the order type of the natural numbers in their usual order. In the standard set-theoretic construction, cardinals are identified with initial ordinals, so and are represented by the same underlying set. Their notation nevertheless indicates different roles.
For example, ordinal addition gives
because appending a final element produces a different, larger order type. Cardinal addition instead gives
because that extra element does not change the set’s cardinality. Likewise, , , and are distinct ordinals but all have cardinality .
Foundational qualifications
Aleph-null exists in Zermelo–Fraenkel set theory without assuming the axiom of choice. The natural numbers can be explicitly well ordered, and every infinite well-orderable set has cardinality at least .
In the usual framework with choice, every infinite set contains a countably infinite subset, so is the least infinite cardinality among all sets.
Without choice, the situation requires care. It is possible for an infinite set to contain no countably infinite subset. Such a set is not finite, but it need not have cardinality comparable with . Also, the general assertion that a countable union of countable sets is countable is not provable in Zermelo–Fraenkel set theory alone. Explicitly supplied enumerations of the constituent sets are sufficient to construct an enumeration of their union.
History and mathematical significance
The theory of infinite cardinalities was developed by Georg Cantor in the late nineteenth century. His work distinguished the countability of the rational numbers from the uncountability of the real numbers and introduced systematic notation for transfinite cardinal numbers.
Aleph-null is fundamental to several areas of mathematics:
- In computer science, finite programs can be encoded as finite strings, so there are only countably many programs. Since there are uncountably many functions from to , not every such function can be computed by an algorithm.
- In topology, a separable space has a countable dense subset. The real line is an example: its rational points are countable and dense, although the full space is uncountable.
- In measure theory, every countable subset of the real line has Lebesgue measure zero. The converse fails: an uncountable set, such as the usual Cantor set, can also have measure zero.
Aleph-null is an exact cardinal number, not a real number or an ordinary numerical limit. A sequence increasing without bound does not converge to in real analysis, and the symbol used in limits does not generally denote . Cardinality, order, measure, and limiting behavior describe different mathematical properties.