Informal Introduction to Cardinal Numbers

Cardinal numbers
We will now give an informal introduction to cardinal numbers. We will later formalize this by using ordinal numbers. Informally, cardinal numbers are “numbers” that measure the cardinality of a set. So for every set, we can introduce a cardinal number of this set. Let’s start with finite sets, cardinal numbers here are well known: they are exactly the natural numbers. For example the set {1,2,4,5} has cardinality 4 (because it contains 4 elements of course). We denote this by |{1,2,4,5}|=4.

Furthermore, the operations on natural numbers say something about the operations of finite sets. Take two disjoint sets and take their union. For example, take {1,2,5} and {3,6,7,8}, then their union is {1,2,3,5,6,7,8}. What we can immediately see is that the cardinality of the union is the sum of the cardinalities of the terms. Thus

[tex]|\{1,2,5\}|+|\{3,6,7,8\}|=|\{1,2,3,5,6,7,8\}|[/tex]

In fact, this holds for every disjoint sets. I.e. if A and B are finite and disjoint, then

[tex]|A|+|B|=|A\cup B|[/tex]

The cartesian product of two sets is defined as the set of couples of these sets. So

[tex]A\times B=\{(a,b)~\vert~a\in A,b\in B\}[/tex]

For example, [itex]\{1,2\}\times \{1,2,3\}=\{(1,1),(1,2),(1,3),(2,1),(2,2),(2,3)\}[/itex]. As we can see immediately, the cardinality of the cartesian product is the product of the cardinalities. This holds in general:

[tex]|A\times B|=|A|\cdot |B|[/tex]

All of this wasn’t very exciting, because we just worked with finite numbers. Can we generalize these things to infinite numbers? Yes! The idea is that we assign a cardinal number to an infinite set. Let’s begin with countable sets. Countable sets are in a way the smallest infinite sets. We assign to countable sets the number [itex]\aleph_0[/itex] (read: aleph nought, aleph is the first letter of the Hebrew alphabet).

Can we now define operations on this cardinal number? Well, we use the above results to define the operations. So [itex]\aleph_0+\aleph_0[/itex] is the cardinality of the union of two disjoint countable sets. But, as we can easily check, the union of two countable sets is countable, so

[tex]\aleph_0+\aleph_0=\aleph_0[/tex]

In the same fashion, we have that

[tex]n+\aleph_0=\aleph_0[/tex]

What about products, we define [itex]\aleph_0\cdot \aleph_0[/itex] to be the cardinality of the product of two countable sets. But our previous FAQ sais that this was countable again. So

[tex]\aleph_0\cdot \aleph_0=\aleph_0[/tex]

So we see that cardinal numbers don’t exactly behave like finite numbers. Can we also assign cardinal numbers to other infinite sets? Yes, but we will need to discuss ordinal numbers for this. So we will do this first. First, we take a little detour around well-ordered sets.

Well-ordered sets
An ordered set is just a set X equipped with an order [itex]\leq[/itex] that satisfies three criteria:
[itex]x\leq x[/itex],
If [itex]x\leq y[/itex] and [itex]y\leq x[/itex], then [itex]x=y[/itex],
If [itex]x\leq y[/itex] and [itex]y\leq z[/itex], then [itex]x\leq z[/itex].

A lot of familiar sets are ordered. The integers [itex]\mathbb{N}[/itex] are ordered by

[tex]0<1<2<3<4<5<…[/tex]

The reals [itex]\mathbb{R}[/itex] are also ordered.

Now, a well-ordered set is a set in which every subset has a minimum. For example, if we take [itex]\mathbb{N}[/itex], then this is well-ordered. Take [itex]\{1,2,4,5,7\}[/itex], then this has minimum 1. The entire set [itex]\mathbb{N}[/itex] has minimum 0. The reals are not well-ordered, for example ]0,1[ does not have a minimum (as 0 does not belong to ]0,1[).

A well-ordered set X always has the smallest element: indeed the entire set X has a minimum [itex]x_0[/itex], this is the smallest element. It also has a second smallest element [itex]x_1[/itex]: indeed, the set [itex]X\setminus \{x_0\}[/itex]has a minimum and this is exactly the second smallest element. It also has a third-smallest element, etc…

Another crucial example of a well-ordered set is if we take the naturals [itex]\mathbb{N}[/itex] and we adjoin one element [itex]\omega[/itex]. We order it such that [itex]n<\omega[/itex] for all naturals n. So [itex]\omega[/itex] is an upper bound of all of the naturals. This is another well-ordered set, as we can clearly check. Furthermore, it is an infinite well-ordered set that is essentially different from [itex]\mathbb{N}[/itex], indeed: the latter doesn’t have a maximum.

Ordinal numbers
The idea of ordinals is to assign to every well-ordered set a certain “ordinal number” that completely describes the structure of the well-ordered set in question. For example, to the finite well-ordered set

[tex]0<1<2[/tex]

we assign the number 3 (since it has 3 elements). There are other sets with ordinal number 3, for example

[tex]1<4<1000[/tex]

also has ordinal number 3. But in a way, the structure of these sets is the same.

Let’s do this in general. First, we define the “segment” of a well-ordered set. Take X a well-ordered set and take an element of X. Then we define

[tex]X_a=\{x\in X~\vert~x<a\}[/tex]

the segment of a. This is every element that is strictly smaller than a. In [itex]\mathbb{N}[/itex], for example, the segment of 6 is {0,1,2,3,4,5}.

Now comes a difficult definition, so bear with me. An ordinal number is a well-ordered set such that every element equals its segment. Thus for every a in X must hold that [itex]a=X_a[/itex].

Wait, the previous definition doesn’t make sense!! How on earth can something equal its own segment???? Let’s give some examples to clarify.

The empty set is ordinal. Indeed every element in the empty set equals its own segment. So this is vacuously true. A bit boring, but it’s essential.
The set [itex]\{\emptyset\}[/itex] (with the trivial ordering) is an ordinal. Indeed, the only element in here is [itex]a=\emptyset[/itex]. The segment of a is everything smaller than a, but there is nothing smaller than a! So The segment of a is empty. So we see that the segment of a equals a!
The set [itex]\{\emptyset,\{\emptyset\}\}[/itex] with the ordering [itex]\emptyset<\{\emptyset\}[/itex] is an ordinal. Indeed, there is nothing smaller than [itex]\emptyset[/itex], so the segment of this element is empty. The only element smaller than [itex]\{\emptyset\}[/itex] is [itex]\emptyset[/itex]. So the segment of [itex]\{\emptyset\}[/itex] is [itex]\{\emptyset\}[/itex].

Let’s introduce some notation here to see what we’re doing. Define

[itex]0:=\emptyset[/itex] (this is the definition of the number 0!!!!)
1:={0}
2:={0,1}
3:={0,1,2}
In general: n:={0,1,…,n-1}

With this definition, every natural number is an ordinal number. However, with this definition, also [itex]\mathbb{N}[/itex] is an ordinal. Indeed, the segement of n is {0,1,…,n-1}, which equals n! We denote this ordinal by [itex]\omega[/itex]. Now we can continue:

[itex]\omega+1:=\omega\cup \{\omega\}[/itex]
[itex]\omega+2:=\omega\cup \{\omega,\omega+1\}[/itex]
In general [itex]\omega+n:=\omega\cup \{\omega+1,…,\omega+n-1\}[/itex]

Now, we can even put

[tex]\omega\cdot 2:=\{0,1,2,3,…,\omega,\omega+1,\omega+2,\omega+3,…\}[/tex]

as an ordinal, and we can continue by defining

[tex]\omega\cdot 2+n=\omega\cdot 2 \cup\{\omega\cdot 2+1,…,\omega\cdot 2+n-1\}[/tex]

As you see, this process continues indefinitely!!

The crucial thing about ordinal numbers is that every well-ordered set has the exact same structure as one of the ordinal numbers. So the ordinal numbers describe the well-ordered sets perfectly.

Back to cardinal numbers
We will now define cardinal numbers as a special kind of ordinal number. Take a set X, a famous theorem (of Zermelo) says that X can be well-ordered, i.e. there exists a well-order on X. But this can happen in many ways. For example, [itex]\mathbb{N}[/itex] has a lot of well-orderings on it:

0<1<2<3<… (the usual well-ordering), this well-ordering has [itex]\omega[/itex] as its associated ordinal.
1<0<2<3<… This again has [itex]\omega[/itex] as its associated ordinal.
1<2<3<4<…<0 This has [itex]\omega+1[/itex] as its associated ordinal.
4<5<6<7<…<0<1<2<3 This has [itex]\omega+4[/itex] as its associated ordinal.

So we can assign a lot of well-orderings to a set X, and we can assign a lot of ordinals to a set X. The cardinality of X, however, is the smallest ordinal assigned to X. For example, [itex]\mathbb{N}[/itex] has cardinality [itex]\omega[/itex]. But, to avoid confusion with [itex]\omega[/itex] as ordinal, we define [itex]\aleph_0=\omega[/itex] when speaking about cardinal numbers.

So, we have

[tex]0,1,2,3,4,…,\aleph_0[/tex]

as cardinals. The smallest cardinal number bigger than [itex]\aleph_0[/itex] is called [itex]\aleph_1[/itex]. Then we can have [itex]\aleph_2[/itex]. We have [itex]\aleph_\alpha[/itex] for every ordinal [itex]\alpha[/itex]. So we can even have the cardinal number [itex]\aleph_\omega[/itex] (which is huge!).

So every set can be assigned a cardinality. For example, we know that [itex]\mathbb{Q}[/itex] is countable, so the cardinality of [itex]\mathbb{Q}[/itex] is [itex]\aleph_0[/itex]. What about [itex]\mathbb{R}[/itex]? This certainly has cardinality [itex]\aleph_\alpha[/itex] for an ordinal [itex]\alpha[/itex], but we don’t know which one. Indeed, in previous FAQ we have talked a bit about the continuum hypothesis and how it was impossible to know if there were infinite sets C such that

[tex]|\mathbb{N}|<C<|\mathbb{R}|[/tex]

Likewise, it’s impossible to know which cardinality [itex]\mathbb{R}[/itex] has. We know it has one, but we don’t know which one. :frown:

Further reading
The text “Introduction to set theory” by Hrbacek and Jech offers an excellent and elementary introduction to the topic.

Click For Forum Comments