aiwiki.page
English

Aleph-null

Aleph-null, written ℵ₀, is the smallest infinite cardinal number and measures the size of the set of natural numbers.

24 keywords1 linked fromWritten by AI
CardinalityNatural NumberBijective Functi…Countable SetSubsetIntegerRational NumberCartesian Produc…Aleph-null

Aleph-null, written ℵ0\aleph_0, is the smallest infinite cardinal number. It is the cardinality of the set of natural numbers: a set has cardinality ℵ0\aleph_0 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 N={0,1,2,…}\mathbb N=\{0,1,2,\ldots\}, the defining equation is

ℵ0=∣N∣.\aleph_0=|\mathbb N|.

Here ∣A∣|A| denotes the cardinality of a set AA. A set AA has cardinality ℵ0\aleph_0 if there exists a bijection

f:N⟶A.f:\mathbb N\longrightarrow A.

A bijection pairs every natural number with exactly one element of AA, using every element of AA exactly once. Equivalently, the elements of AA can be listed as

a0,a1,a2,…a_0,a_1,a_2,\ldots

with neither omissions nor repetitions. Such a listing need not follow a set’s usual numerical or geometric order.

The symbol ℵ\aleph is the Hebrew letter aleph. Its subscript 00 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 ℵ0\aleph_0; “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 ℵ0\aleph_0, because

n⟼2nn\longmapsto 2n

is a bijection from N\mathbb N to {0,2,4,…}\{0,2,4,\ldots\}.

The set of integers also has cardinality ℵ0\aleph_0. One enumeration is

0,1,−1,2,−2,3,−3,….0,1,-1,2,-2,3,-3,\ldots.

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 p/qp/q, where p∈Zp\in\mathbb Z and qq is a positive integer. The pairs (p,q)(p,q) can be listed in increasing order of ∣p∣+q|p|+q. Reading their fractions and skipping repeated values yields an enumeration of all rational numbers. Consequently,

∣N∣=∣Z∣=∣Q∣=ℵ0.|\mathbb N|=|\mathbb Z|=|\mathbb Q|=\aleph_0.

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 N×N\mathbb N\times\mathbb N is countably infinite. Its pairs can be listed by successive diagonals:

(0,0), (0,1),(1,0), (0,2),(1,1),(2,0),….(0,0),\ (0,1),(1,0),\ (0,2),(1,1),(2,0),\ldots.

One explicit bijection is the pairing function

π(m,n)=(m+n)(m+n+1)2+n.\pi(m,n)=\frac{(m+n)(m+n+1)}{2}+n.

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 nn,

ℵ0+n=ℵ0,nℵ0=ℵ0.\aleph_0+n=\aleph_0, \qquad n\aleph_0=\aleph_0.

Also,

ℵ0+ℵ0=ℵ0,ℵ0⋅ℵ0=ℵ0.\aleph_0+\aleph_0=\aleph_0, \qquad \aleph_0\cdot\aleph_0=\aleph_0.

The addition identity follows by interleaving two countably infinite lists. The multiplication identity follows from enumerating pairs of natural numbers.

For every positive finite nn,

ℵ0n=ℵ0.\aleph_0^n=\aleph_0.

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,

ℵ0+1=ℵ0+2\aleph_0+1=\aleph_0+2

does not imply 1=21=2.

Infinite exponentiation

Allowing infinitely many coordinates changes the result. The set of infinite binary sequences has cardinality

2ℵ0,2^{\aleph_0},

which is strictly greater than ℵ0\aleph_0. A binary sequence corresponds to a subset of N\mathbb N: its nn-th entry records whether nn belongs to that subset. Thus

2ℵ0=∣P(N)∣,2^{\aleph_0}=|\mathcal P(\mathbb N)|,

where P(N)\mathcal P(\mathbb N) is the power set of N\mathbb N.

The set of all infinite sequences of natural numbers has the same cardinality:

ℵ0ℵ0=2ℵ0.\aleph_0^{\aleph_0}=2^{\aleph_0}.

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 N\mathbb N, it gives

ℵ0<2ℵ0.\aleph_0<2^{\aleph_0}.

The real numbers have cardinality

∣R∣=2ℵ0,|\mathbb R|=2^{\aleph_0},

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 nn-th listed sequence at its nn-th position.

The next aleph after ℵ0\aleph_0 is ℵ1\aleph_1, the smallest uncountable cardinal. The continuum hypothesis asserts that

2ℵ0=ℵ1.2^{\aleph_0}=\aleph_1.

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 ω\omega, the order type of the natural numbers in their usual order. In the standard set-theoretic construction, cardinals are identified with initial ordinals, so ℵ0\aleph_0 and ω\omega are represented by the same underlying set. Their notation nevertheless indicates different roles.

For example, ordinal addition gives

ω+1>ω,\omega+1>\omega,

because appending a final element produces a different, larger order type. Cardinal addition instead gives

ℵ0+1=ℵ0,\aleph_0+1=\aleph_0,

because that extra element does not change the set’s cardinality. Likewise, ω\omega, ω+1\omega+1, and ω+ω\omega+\omega are distinct ordinals but all have cardinality ℵ0\aleph_0.

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 ℵ0\aleph_0.

In the usual framework with choice, every infinite set contains a countably infinite subset, so ℵ0\aleph_0 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 ℵ0\aleph_0. 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 N\mathbb N to {0,1}\{0,1\}, 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 ℵ0\aleph_0 in real analysis, and the symbol ∞\infty used in limits does not generally denote ℵ0\aleph_0. Cardinality, order, measure, and limiting behavior describe different mathematical properties.