Cardinality of important sets

The aleph numbers are a sequence of numbers used to represent the cardinality (or size) of infinite sets that can be well-ordered. They were introduced by the mathematician Georg Cantor and are named after the symbol he used to denote them, the Hebrew letter aleph ($\,\aleph \,$).

The cardinality of the natural numbers is $\,\aleph _{0}\,$ (read aleph-nought or aleph-zero; the term aleph-null is also sometimes used), the next larger cardinality of a well-orderable set is aleph-one $\,\aleph _{1}\;,$ then $\,\aleph _{2}\,$ and so on. Continuing in this manner, it is possible to define a cardinal number $\,\aleph _{\alpha }\,$ for every ordinal number $\,\alpha \;,$ as described below.

The concept and notation are due to Georg Cantor, who defined the notion of cardinality and realized that infinite sets can have different cardinalities.

The aleph numbers differ from the infinity ($\,\infty \,$) commonly found in algebra and calculus, in that the alephs measure the sizes of sets, while infinity is commonly defined either as an extreme limit of the real number line (applied to a function or sequence that "diverges to infinity" or "increases without bound"), or as an extreme point of the extended real number line.

Aleph-nought

$\,\aleph _{0}\,$ (aleph-nought, also aleph-zero or aleph-null) is the cardinality of the set of all natural numbers, and is an infinite cardinal. The set of all finite ordinals, called $\,\omega \,$ or $\,\omega _{0}\,$ (where $\,\omega \,$ is the lowercase Greek letter omega), has cardinality $\,\aleph _{0}\;.$ A set has cardinality $\,\aleph _{0}\,$ if and only if it is countably infinite, that is, there is a bijection (one-to-one correspondence) between it and the natural numbers. Examples of such sets are

• the set of all integers,
• any infinite subset of the integers, such as the set of all square numbers or the set of all prime numbers,
• the set of all rational numbers,
• the set of all constructible numbers (in the geometric sense),
• the set of all algebraic numbers,
• the set of all computable numbers,
• the set of all binary strings of finite length, and
• the set of all finite subsets of any given countably infinite set.

These infinite ordinals: $\,\omega \;,$ $\,\omega +1\;,$ $\,\omega \,\cdot 2\,,\,$ $\,\omega ^{2}\,,$ $\,\omega ^{\omega }\,$ and $\,\varepsilon _{0}\,$ are among the countably infinite sets. For example, the sequence (with ordinality ω·2) of all positive odd integers followed by all positive even integers

$\,\{\,1,3,5,7,9,...,2,4,6,8,10,...\,\}\,$

is an ordering of the set (with cardinality $\aleph _{0}$) of positive integers.

If the axiom of countable choice (a weaker version of the axiom of choice) holds, then $\,\aleph _{0}\,$ is smaller than any other infinite cardinal.

Cardinality of $\mathbb {N}$

Two important generalizations of natural numbers arise from the two uses of counting and ordering: cardinal numbers and ordinal numbers.

• A natural number can be used to express the size of a finite set; more precisely, a cardinal number is a measure for the size of a set, which is even suitable for infinite sets. This concept of "size" relies on maps between sets, such that two sets have the same size, exactly if there exists a bijection between them. The set of natural numbers itself, and any bijective image of it, is said to be countably infinite and to have cardinality aleph-null (ℵ₀).
• Natural numbers are also used as linguistic ordinal numbers: "first", "second", "third", and so forth. This way they can be assigned to the elements of a totally ordered finite set, and also to the elements of any well-ordered countably infinite set. This assignment can be generalized to general well-orderings with a cardinality beyond countability, to yield the ordinal numbers. An ordinal number may also be used to describe the notion of "size" for a well-ordered set, in a sense different from cardinality: if there is an order isomorphism (more than a bijection!) between two well-ordered sets, they have the same ordinal number. The first ordinal number that is not a natural number is expressed as ω; this is also the ordinal number of the set of natural numbers itself.

The least ordinal of cardinality ℵ₀ (that is, the initial ordinal of ℵ₀) is ω but many well-ordered sets with cardinal number ℵ₀ have an ordinal number greater than ω.

For finite well-ordered sets, there is a one-to-one correspondence between ordinal and cardinal numbers; therefore they can both be expressed by the same natural number, the number of elements of the set. This number can also be used to describe the position of an element in a larger finite, or an infinite, sequence.

A countable non-standard model of arithmetic satisfying the Peano Arithmetic (that is, the first-order Peano axioms) was developed by Skolem in 1933. The hypernatural numbers are an uncountable model that can be constructed from the ordinary natural numbers via the ultrapower construction.

Georges Reeb used to claim provocatively that The naïve integers don't fill up ℕ. Other generalizations are discussed in the article on numbers.

Cardinality of $\mathbb {Z}$

The cardinality of the set of integers is equal to ℵ_0 (aleph-null). This is readily demonstrated by the construction of a bijection, that is, a function that is injective and surjective from $\mathbb {Z}$ to $\mathbb {N}$. If $\mathbb {N} _{0}\equiv \{0,1,2,...\}$ then consider the function:

$f(x)={\begin{cases}2|x|,&{\mbox{if }}x\leq 0\\2x-1,&{\mbox{if }}x>0.\end{cases}}$

{... (−4,8) (−3,6) (−2,4) (−1,2) (0,0) (1,1) (2,3) (3,5) ...}

If $\mathbb {N} \equiv \{0,1,2,3,...\}$ then consider the function:

$g(x)={\begin{cases}2|x|,&{\mbox{if }}x<0\\2x+1,&{\mbox{if }}x\geq 0.\end{cases}}$

{... (−4,8) (−3,6) (−2,4) (−1,2) (0,1) (1,3) (2,5) (3,7) ...}

If the domain is restricted to $\mathbb {Z}$ then each and every member of $\mathbb {Z}$ has one and only one corresponding member of $\mathbb {N}$ and by the definition of cardinal equality the two sets have equal cardinality.

Cardinality of $\mathbb {Q}$

The set of all rational numbers $\mathbb {Q}$ is countably infinite and has the same cardinality as the set of all natural numbers ℵ_0.

The rational numbers are arranged thus:

${\dfrac {0}{1}},{\dfrac {1}{1}},{\dfrac {-1}{1}},{\dfrac {1}{2}},{\dfrac {-1}{2}},{\dfrac {2}{1}},{\dfrac {-2}{1}},{\dfrac {1}{3}},{\dfrac {2}{3}},{\dfrac {-1}{3}},{\dfrac {-2}{3}},{\dfrac {3}{1}},{\dfrac {3}{2}},{\dfrac {-3}{1}},{\dfrac {-3}{2}},{\dfrac {1}{4}},{\dfrac {3}{4}},{\dfrac {-1}{4}},{\dfrac {-3}{4}},{\dfrac {4}{1}},{\dfrac {4}{3}},{\dfrac {-4}{1}},{\dfrac {-4}{3}}\ldots$

It is clear that every rational number will appear somewhere in this list.

Thus it is possible to set up a bijection between each rational number and its position in the list, which is an element of $\mathbb {N}$. Note that this is NOT true for the irrational numbers, which have the same cardinality as the real numbers (see below).

Cardinality of $\mathbb {R}$

The cardinality of the continuum is the cardinality or "size" of the set of real numbers $\mathbb {R}$, sometimes called the continuum. It is an infinite cardinal number and is denoted by ${\mathfrak {c}}$ (lowercase fraktur "c") or $|\mathbb {R} |$. The irrational numbers ($\mathbb {R} \setminus \mathbb {Q}$) is also of this cardinality.

The real numbers $\mathbb {R}$ are more numerous than the natural numbers $\mathbb {N}$. Moreover, $\mathbb {R}$ has the same number of elements as the power set of $\mathbb {N} .$ Symbolically, if the cardinality of $\mathbb {N}$ is denoted as $\aleph _{0}$, the cardinality of the continuum is ${\mathfrak {c}}=2^{\aleph _{0}}>\aleph _{0}\,.$ This was proven by Georg Cantor in his uncountability proof of 1874, part of his groundbreaking study of different infinities. The inequality was later stated more simply in his diagonal argument in 1891. Cantor defined cardinality in terms of bijective functions: two sets have the same cardinality if, and only if, there exists a bijective function between them.

Between any two real numbers a < b, no matter how close they are to each other, there are always infinitely many other real numbers, and Cantor showed that they are as many as those contained in the whole set of real numbers. In other words, the open interval (a,b) is equinumerous with $\mathbb {R} .$ This is also true for several other infinite sets, such as any n-dimensional Euclidean space $\mathbb {R} ^{n}$ (see space filling curve). That is, $|(a,b)|=|\mathbb {R} |=|\mathbb {R} ^{n}|.$

The smallest infinite cardinal number is $\aleph _{0}$ (aleph-null). The second smallest is $\aleph _{1}$ (aleph-one). The continuum hypothesis, which asserts that there are no sets whose cardinality is strictly between $\aleph _{0}$ and ${\mathfrak {c}}$, means that ${\mathfrak {c}}=\aleph _{1}$. The truth or falsity of this hypothesis is undecidable and cannot be proven within the widely used Zermelo–Fraenkel set theory with axiom of choice (ZFC).

Licensing

Content obtained and/or adapted from:

• Natural number, Wikipedia under a CC BY-SA license
• Rational numbers are countably infinite, ProofWiki.org under a CC BY-SA license