Cardinal

File:Cardinal.jpg

In set theory, the cardinal numbers (or just cardinals) are equivalence classes defined by the relation "there exists a bijection from set \(A\) onto set \(B\)". Whereas ordinal numbers may be thought of as "structures" of certain kinds of sets, cardinals are best described as the "sizes" of sets.

Introduction

The intuitive idea of size works well enough for finite sets, but in the infinite realm it begins to break down. For an example, let's compare the sizes of four sets: the rational numbers, the natural numbers, the even natural numbers, and the real numbers. How do their sizes compare to each other? Most people will give one of two answers. One could argue the following: "The four sets all nest inside each other in this order: even natural numbers, natural numbers, rational numbers, real numbers. A set always has less elements than a superset, so their sizes are in this order from smallest to largest." Someone else would argue, "Since all the sets are infinite, they can't be different sizes — otherwise \(\infty < \infty\). So they're all the same size." These two arguments, seemingly both logical, give us contradictory answers, showing that we need something better than such intuitive reasoning.

Instead of asking when one set is smaller than another, we can ask a potentially easier question: when do two sets have the same size? The answer, agreed upon by set theorists, is in the idea of a bijection, also known as a one-to-one correspondence. The latter name suggests a nice visual description of a bijection — pairing up two sets of objects so that no object is left over and every object belongs to only one pair. If there exists  a bijection between two sets \(A\) and \(B\), then we say that they have the same cardinality, or that they are equipotent, equinumerous, or sometimes equicardinal. We then denote cardinality of a set \(A\) by \(|A|\). We can also speak of inequalities between sizes of two sets - since naturally we would expect all subsets \(B\) of a set \(A\) to have the size at most that of \(A\), it's natural to define notion "set \(C\) having the size at most the size of \(A\)" as "\(C\) is equinumerous to some subset of \(A\)".

Cardinality is simple for finite sets — it's just the number of elements in the set. The empty set has zero cardinality, the set of horns on your pet unicorn has cardinality 1, etc. The bijection definition also works intuitively. You can determine whether two groups of people are the same size by repeatedly removing two at a time, one from each group. This may seem roundabout when we can count all the elements, but what if we can't?

A simple example of an infinite set is the set of all nonnegative integers \(\{0,1,2,\ldots\}\). This has a cardinality we call aleph-zero or aleph-null or aleph-naught, notated \(\aleph_0\).

Let's try to answer a question comparing the cardinalities of two infinite sets, \(A = \{0,1,2,\ldots\}\) and \(B = \{1,2,3,\ldots\}\). To check for equicardinality, we look for a way to pair off elements with no leftovers or overlaps. Finding a bijection is easy: for each element in \(A\), add one to it and it matches up with an element in \(B\)! So \(A\) and \(B\) have the same cardinality, and \(\{1,2,3,\ldots\}\) has cardinality \(\aleph_0\). Since we took one element away to get from \(A\) to \(B\), this means that \(\aleph_0 - 1 = \aleph_0\), and the opposite argument shows that \(\aleph_0 + 1 = \aleph_0\). In fact, for all finite \(n\), adding or taking away \(n\) elements from an infinite set doesn't change its size.

What about \(A = \{0,1,2,\ldots\}\) and \(C = \{0,2,4,6,\ldots\}\)? We simply use the mapping \(x \mapsto 2x\), and that gives us a bijection from \(A\) onto \(C\). So the nonnegative integers have the same cardinality \(\aleph_0\) as just the even ones. So \(\aleph_0 = 2\aleph_0\). This may be a little surprising to people who thought that a set is always larger than each of its proper subsets! Same goes for the set of multiples of 3, multiples of 4, perfect squares, etc. The last of these is especially interesting, because perfect square numbers become more and more sparse when we go on, and their density among natural numbers is, in fact, 0.

A slightly more complicated mapping allows us to show that the integers \(\{\ldots,-3,-2,-1,0,1,2,3,\ldots\}\) also have cardinality \(\aleph_0\). One bijection involves alternating between the positive and negative integers: 0, 1, -1, 2, -2, ... and it works just like the argument for the even integers. The rational numbers are even trickier, but it is possible to show that they also have cardinality \(\aleph_0\), and that \(\aleph_0^2 = \aleph_0\).

Real numbers

At this point, it's tempting to conclude that all infinite sets have cardinality \(\aleph_0\). But German mathematician Georg Cantor proved that this is not the case. As it turns out, the set of real numbers is so large that there is no bijection from \(\mathbb{N}\) onto \(\mathbb{R}\), so they do not have cardinality \(\aleph_0\). In other words, there are different sizes of infinities!

First thing to note is, if we will show that some subset of real numbers has more elements than \(\mathbb{N}\), then the same will follow for all real numbers (because set of real numbers certainly doesn't have less elements than its subset). We will provide a basic outline of Cantor's famous diagonalization proof. We can encode all the real numbers in \((0, 1)\) using their binary expansions, such as 0.0110101101011... Using proof by contradiction, we assume that we can find a bijection from the natural numbers onto \((0,1)\). Then we can make a numbered list of all the real numbers in some order like this (this is, of course, just one example of such ordering, but it should get clear later that this works for any supposed ordering):

1. 0.010110101011110...

2. 0.101010011011100...

3. 0.011100101110101...

4. 0.010101101010000...

5. 0.011100100101011...

6. 0.111010101101000...

...

This list supposedly has all the real numbers, but it turns out we can always come up with a real number that isn't on the list! Just take all the bolded numbers:

1. 0.010110101011110...

2. 0.101010011011100...

3. 0.011100101110101...

4. 0.010101101010000...

5. 0.011100100101011...

6. 0.111010101101000...

...

and assemble them into a new real number 0.001100... Then flip all the bits in this number to form a new one, 0.110011... Since it has a different first bit than real number #1, it's not equal to the first. Since it has a different second bit than number #2, it's not equal to the second. Since it has a different third bit than #3, it's not equal to the third, and so on. So our real number isn't on the list at all, even though we assumed every real number is there! This is a contradiction, and therefore \((0,1)\) has a different cardinality than the natural numbers. We can show that there is at least as many reals as natural numbers, e.g. by noting that the set \(\{0.1,0.01,0.0001,...\}\) is fully contained in \((0,1)\), and has the same number of elements as \(\mathbb{N}\).

More detailed and rigorous statements of this proof can be found all over the Internet, so if you're concerned about details be sure to check those. (For example, we glossed over duplicate expansions such as 0.001011111... = 0.00110000... but these ultimately don't have any effect.)

One thing that is worth pointing out is that the real numbers in the interval \((0, 1)\) have, in fact, the same cardinality as the entire set of real numbers — in set theory, a line segment has the same size as a line. There are quite a few bijections for this, one familiar one being the function \(\tan(x)\) which maps \((-\pi/2,\pi/2)\) onto \(\mathbb{R}\). (Don't worry about the fact that it's \((-\pi/2,\pi/2)\) and not \((0, 1)\), the scaling and translating doesn't affect the cardinality.)

How many real numbers are there then? One way to symbolize their cardinality is "\(2^{\aleph_0}\)" — each real number is defined by \(\aleph_0\) bits, and there are two choices for each bit. Another symbol is \(\mathfrak{c}\), which is the initial for the name of the cardinal: the cardinality of the continuum (or just continuum).

Another set with cardinality equal to \(2^{\aleph_0}\) is the power set of the natural numbers, which consists of all sets of natural numbers, finite and infinite. There is a very straightforward mapping from the real numbers onto these sets — a one a position n means that n is in the set. So 0.111 represents the set {1,2,3}, 0.01010101... the even numbers, etc.

Continuum hypothesis

So far we have a nice collection of cardinals going: in increasing order, we have the finite cardinalities 0, 1, 2, 3, ... and two infinite cardinalities \(\aleph_0\) and \(2^{\aleph_0}\).

Above we (sort of) showed that \(2^{\aleph_0} > \aleph_0\), but our argument doesn't tell us anything about whether there are cardinals between \(\aleph_0\) and \(2^{\aleph_0}\). Intuitively it seems odd that there would be any sets of cardinality between the natural numbers and real numbers, but intuition isn't an ideal way to argue about this. The continuum hypothesis asks the question

Are there any cardinals \(\alpha\) such that \(\aleph_0 < \alpha < 2^{\aleph_0}\)?

In a set-theoretic framework known as ZFC, we also know that there is a smallest cardinal greater than \(\aleph_0\). We call it \(\aleph_1\), or aleph-one. Thus in ZFC, the continuum hypothesis is equivalent to asking whether \(2^{\aleph_0} = \aleph_1\).

The resolution of continuum hypothesis is very interesting and weird. Kurt Gödel showed that it's not possible to disprove it in ZFC - which made many mathematicians of the time believe that it can be proven - but Paul Cohen later showed that it's not possible to prove it either. Thus it's independent of ZFC. In other words, it's neither true nor false, and ZFC just can't "make up its mind". If this is confusing to you, maybe check out our ZFC article for more details on formal theories and independence.

In spite of this undecided nature of the continuum, some poorly written introductions to set theory will explicitly or implicitly state that the real numbers have cardinality \(\aleph_1\) by definition. If you've learned this from such a tutorial, unlearn it! Even if you ever use the equality between these two cardinals, you should be aware that they are defined in significantly different way, and that this equality cannot be proven on the grounds of common set theory.

More cardinals

The power set of the real numbers has cardinality \(2^{2^{\aleph_0}}\), and the power set of that set has cardinality \(2^{2^{2^{\aleph_0}}}\). Starting to notice a pattern?

We already know from Cantor's diagonalization proof that \(2^{\aleph_0} > \aleph_0\). Similar arguments can be made to prove that \(2^{2^{\aleph_0}} > 2^{\aleph_0}\), and \(2^{2^{2^{\aleph_0}}} > 2^{2^{\aleph_0}}\), and so on. In general, Cantor's theorem tells us that for every cardinal \(\alpha\), \(2^\alpha > \alpha\). That is, every set is outnumbered by its power set. From this we see that there is no such thing as the largest cardinal number - for any supposed such cardinal, we could just take its power set, and we would know that it's larger.

By the way, there's a more concise standard notation for cardinals like \(2^{2^{\aleph_0}}\) and \(2^{2^{2^{\aleph_0}}}\), called the beth numbers. They are defined as \(\beth_0 = \aleph_0\), \(\beth_1 = 2^{\aleph_0}\), \(\beth_2 = 2^{2^{\aleph_0}}\), \(\beth_3 = 2^{2^{2^{\aleph_0}}}\), etc. Using the beth numbers, we can restate the continuum hypothesis as \(\aleph_1 = \beth_1\), assuming ZFC.

There are also the aleph numbers, one of which you're familiar with by now — \(\aleph_0\). Recall that \(\aleph_1\) is defined as the smallest cardinal greater than \(\aleph_0\). Similarly, \(\aleph_2\) is the smallest cardinal greater than \(\aleph_1\), and so forth. The difference between these two sequences is quite important: the beth numbers are created by repeated application of power sets, and the aleph numbers try to make themselves as close together as possible.

Oh, and here's some more terminology. \(\aleph_0\) is the smallest infinite cardinal, and as such we define an infinite cardinal as any cardinal at least \(\aleph_0\). Sets with cardinality \(\leq \aleph_0\) are called countable, and sets with cardinality \(> \aleph_0\) are called uncountable. Sets with cardinality \(\aleph_0\) are unsurprisingly called countably infinite.

Cardinal arithmetic and ordinals

Before we introduce even more cardinals, now's a good time to step back and discuss some theory.

• Cardinal ordering. Earlier on, we wrote \(2^{\alpha_0} > \alpha_0\) but we didn't define what \(>\) means. We say that \(\alpha \geq \beta\) iff there are sets \(|A| = \alpha,\, |B| = \beta\) and \(A \supseteq B\). We say that \(\alpha > \beta\) iff \(\alpha \geq \beta\) and \(\alpha \neq \beta\).
• Cardinal addition. \(\alpha + \beta\) means taking two disjoint sets \(A\) and \(B\), where \(A\) has cardinality \(\alpha\) and \(B\) has cardinality \(\beta\), and returning the cardinality of their union \(A \cup B\). It's worth noting that we get the same value of \(\alpha+\beta\) no matter what sets \(A\) and \(B\) we choose, as long as they have correct cardinalities. Also, some authors use an equivalent definition that constructively supplies such \(A\) and \(B\) from \(\alpha\) and \(\beta\).
•  Cardinal multiplication. If we take cardinals \(\alpha,\beta\) and sets \(A,B\) of these respective cardinalities, then we define \(\alpha\cdot\beta\) to be the cardinality of the Cartesian product \(A\times B\). Intuitively, this means that we take are taking \(|B|\) copies of \(A\) and we are taking their collective size.
• Cardinal exponentiation. To exponentiate cardinals, we first need a notion of "set exponentiation" (just like disjoint union and Cartesian product are "set addition" and "set multiplication"). This is achieved by, again given two sets \(A,B\), considering the set of all functions from \(B\) to \(A\). This set is denoted by \(A^B\) (or sometimes \(^BA\)). We then define cardinal exponentiation to be an operation taking cardinalities of sets \(A,B\) and returning the cardinality of set \(A^B\). A justification for this definition is as follows: when we are constructing a function from \(B\) to \(A\), then for every element of \(B\) we can independently choose any of \(|A|\) elements of \(A\), thus, to count how many functions from \(B\) to \(A\) there are, we would want to multiply \(|A|\) with itself \(|B|\) times.
• Suprema. Just like for ordinals, we can define the supremum of a set of cardinals as the least cardinal greater than or equal to all cardinals in the set. Formally, if \(A\) is a set of cardinals, \(\textrm{sup}A\ :=\ \textrm{min}\{\kappa\in\textrm{Card}:\forall(\lambda\in A)(\lambda\le\kappa)\}\). The supremum of a set of cardinals is always a cardinal.

Now that we have some fundamentals out of the way, let's talk about the relationship between cardinals and ordinals. Cardinals are closely related to the system of ordinal numbers, but they're not the same. Their arithmetic systems behave differently — for example, \(\omega + 1 \neq \omega\) while \(\aleph_0 + 1 = \aleph_0\).

From here on we use the Von Neumann definition of ordinals. \(\omega\), as we've established, is the smallest infinite ordinal. \(\omega_1\) is the name for the smallest uncountable ordinal, \(\omega_2\) for the smallest ordinal of cardinality \(\aleph_2\), and so forth.

It's convenient to "define" a cardinal number as equal to the smallest ordinal number with its own cardinality. So we'd say that \(\omega = \aleph_0\), \(\omega_1 = \aleph_1\), and so forth, which is nice because now the cardinal numbers are represented by actual sets. How can this be reasonable if \(\omega + 1\) and \(\aleph_0 + 1\) are different? That's because we're using different definitions of addition here, and ordinal addition is defined differently from cardinal addition. Distinguishing between the two is just a matter of context, and it's rarely if ever ambiguous.

With all this in mind, we have enough foundation to move on to larger cardinal numbers.

Higher cardinals

Using the infinite sum definition, we can create a new, larger cardinal \(\aleph_0 + \aleph_1 + \aleph_2 + \cdots\). This is necessarily larger than all of the summands, and we'll call it \(\aleph_\omega\). \(\aleph_{\omega + 1}\) doesn't require much explanation — it's the next cardinal after \(\aleph_\omega\).

More generally, we can consider the aleph hierarchy, which is a hierarchy of cardinal numbers indexed by all ordinal numbers. It is defined as follows: \(\aleph_0\) is, as before, cardinality of set \(\{0,1,2,...\}\). If we have cardinal \(\aleph_\alpha\) defined, then \(\aleph_{\alpha+1}\) is defined as the smallest cardinal greater than \(\aleph_\alpha\). Finally, if \(\alpha\) is a limit ordinal, then we have \(\aleph_\beta\) defined for all \(\beta<\alpha\), then we define \(\aleph_\alpha\) as the sum \(\sum_{\beta<\alpha}\aleph_\beta\).

Similarly we can define the beth hierarchy, as \(\beth_0=\aleph_0\), \(\beth_{\alpha+1}=2^{\beth_\alpha}\) and for limit \(\alpha\), \(\beth_\alpha=\sum_{\beta<\alpha}\aleph_\beta\). The generalized continuum hypothesis (GCH) asks whether, for all ordinals \(\alpha\), \(\beth_\alpha = \aleph_\alpha\). Like the continuum hypothesis, GCH is independent of ZFC.

Since \(\aleph_0 = \omega\), we can write \(\aleph_\omega = \aleph_{\aleph_0}\), and we can keep iterating the map \(\alpha \mapsto \aleph_\alpha\) to get \(\aleph_{\aleph_{\aleph_0}}, \aleph_{\aleph_{\aleph_{\aleph_0}}}, \ldots\). Just like how we used an infinite sum to reach \(\aleph_\omega\), we can sum these all together to get a cardinal visualized as \(\aleph_{\aleph_{\aleph_{._{._.}}}}\). As an ordinal, this looks like \(\omega_{\omega_{\omega_{._{._.}}}}\) and we call it the (first) omega fixed point. Similarly there is \(\beth_{\beth_{\beth_{._{._.}}}}\). This isn't the limit of cardinal notation, by the way — we can also consider sums such as \(\aleph_1 + \aleph_{\aleph_1} + \aleph_{\aleph_{\aleph_1}} + \cdots\), which is also an aleph fixed point.

From these hierarchies we can define some new terms. A successor cardinal is a cardinal that immediately follows another. \(1,2,3,4,\ldots\) are all successor cardinals, but the ones we care about are of the form \(\aleph_{\alpha + 1}\) for some ordinal \(\alpha\). It turns out that all infinite successor cardinals are regular. We've already seen that \(\aleph_1\) is regular, and so are \(\aleph_2\) and \(\aleph_3\) and \(\aleph_{\omega + 1}\).

The weak limit cardinals are the cardinals that are neither successor cardinals nor 0. Examples are \(\aleph_0\), \(\aleph_\omega\), and the first aleph fixed point. The strong limit cardinals are \(\beth_\alpha\) where \(\alpha\) is zero or a limit ordinal.

Cofinality

Main article: Cofinality

Notice how \(\aleph_\omega\) is expressible as a supremum of countably many smaller cardinals \(\textrm{sup}\{\aleph_0,\aleph_1,\aleph_2,\cdots\}\). The same goes for the familiar \(\aleph_0\) — it's equal to \(\textrm{sup}\{0,1,2,3,\cdots\}\). Same goes for the first aleph fixed point \(\aleph_{\aleph_{\aleph_{._{._.}}}} = \textrm{sup}\{\aleph_0,\aleph_{\aleph_0},\aleph_{\aleph_{\aleph_0}},\cdots\}\).

We define the cofinality of a cardinal \(\alpha\) as the least cardinality of a set of ordinals less than \(\alpha\) that has supremum \(\alpha\). Informally, it is the minimal number of "smaller parts" necessary to create \(\alpha\). So \(\aleph_0\), \(\aleph_\omega\), and the first aleph fixed point have cofinality \(\aleph_0\). \(\aleph_1\) has cofinality \(\aleph_1\). A cardinal is regular if it is equal to its own cofinality (i.e. it cannot be broken into a smaller number of smaller parts), or singular otherwise.

Let's classify some infinite cardinals as singular or regular:

• \(\aleph_0\) is regular. You can't take limits of finitely many natural numbers to get an infinite cardinal.
• \(\aleph_1\) is regular. You can't take limits of countably many countable cardinals to get an uncountable cardinal.
• \(\aleph_2\) is regular.
• \(\aleph_\omega\) is singular — just take the supremum of all the smaller cardinals, of which there are \(\aleph_0\).
• \(\aleph_{\omega + 1}\) is regular.
• \(\aleph_{\omega + 2}\) is regular.
• \(\aleph_{\omega 2}\) is singular.
• \(\aleph_{\omega 2 + 1}\) is regular.
• \(\aleph_{\aleph_0}\) is singular. (It's the limit of all previous aleph numbers, of which there are \(\aleph_0\).)
• The first aleph fixed point is singular. (Recall the supremum which we used to construct it, whose set has cardinality \(\aleph_0\).)

A pattern emerges — all the weak limit cardinals other than \(\aleph_0\) are singular, and all the successor cardinals are regular. Is this always true? Are there any uncountable regular weak limit cardinals?

Inaccessible cardinals

The answer is "maybe." The statement is actually independent of ZFC. Set theorists refer to uncountable regular weak limit cardinals as weakly inaccessible cardinals.

External links

• Cardinal number in wikipedia
• Aleph number in wikipedia

See also

Ordinals, ordinal analysis, and set theory

Basics: cardinal numbers · ordinal numbers · limit ordinals · fundamental sequence · normal form · transfinite induction · ordinal notation · Absolute infinity
Theories: Robinson arithmetic · Presburger arithmetic · Peano arithmetic · KP · second-order arithmetic · ZFC
Model Theoretic Concepts: structure · elementary embedding
Countable ordinals: \(\omega\) · \(\varepsilon_0\) · \(\zeta_0\) · \(\eta_0\) · \(\Gamma_0\) (Feferman–Schütte ordinal) · \(\varphi(1,0,0,0)\) (Ackermann ordinal) · \(\psi_0(\Omega^{\Omega^\omega})\) (small Veblen ordinal) · \(\psi_0(\Omega^{\Omega^\Omega})\) (large Veblen ordinal) · \(\psi_0(\varepsilon_{\Omega + 1}) = \psi_0(\Omega_2)\) (Bachmann-Howard ordinal) · \(\psi_0(\Omega_\omega)\) with respect to Buchholz's ψ · \(\psi_0(\varepsilon_{\Omega_\omega + 1})\) (Takeuti-Feferman-Buchholz ordinal) · \(\psi_0(\Omega_{\Omega_{\cdot_{\cdot_{\cdot}}}})\) (countable limit of Extended Buchholz's function)‎ · \(\omega_1^\mathfrak{Ch}\) (Omega one of chess) · \(\omega_1^{\text{CK}}\) (Church-Kleene ordinal) · \(\omega_\alpha^\text{CK}\) (admissible ordinal) · recursively inaccessible ordinal · recursively Mahlo ordinal · reflecting ordinal · stable ordinal · \(\lambda,\gamma,\zeta,\Sigma\) (Infinite time Turing machine ordinals) · gap ordinal · List of countable ordinals
Ordinal hierarchies: Fast-growing hierarchy · Hardy hierarchy · Slow-growing hierarchy · Middle-growing hierarchy · N-growing hierarchy
Ordinal functions: enumeration · normal function · derivative · Veblen function · ordinal collapsing function · Weak Buchholz's function · Bachmann's function · Madore's function · Feferman's theta function · Buchholz's function · Extended Weak Buchholz's function · Extended Buchholz's function · Jäger-Buchholz function · Jäger's function · Rathjen's psi function · Rathjen's Psi function · Stegert's Psi function · Arai's psi function
Uncountable cardinals: \(\omega_1\) · omega fixed point · inaccessible cardinal \(I\) · Mahlo cardinal \(M\) · weakly compact cardinal \(K\) · indescribable cardinal · rank-into-rank cardinal
Classes: \(\textrm{Card}\) · \(\textrm{On}\) · \(V\) · \(L\) · \(\textrm{Lim}\) · \(\textrm{AP}\) · Class (set theory)

Googology overview

Concepts: googology · large number · eventual domination · ordinal · cardinal · recursion · infinity
Important numbers and functions: googol · googolplex · -illions · hyper operators · Graham's number · Extensible-E System · Bowers' Exploding Array Function · Bird's array notation · TREE sequence · Busy beaver function · fast-growing hierarchy · Rayo's number
People: Chris Bird · Jonathan Bowers · Harvey Friedman · Lawrence Hollom · André Joyce · Leo Moser · Robert Munafo · Sbiis Saibian · Aarex Tiaokhiao