The Size of Sets and the Length of Sets

Schematic diagram of ${\omega^2}$ . Each line corresponds to an ordinal ${\omega\cdot m + n}$ where ${m}$ and ${n}$ are natural numbers [image Wikimedia Commons].

Cardinals and Ordinals

The cardinal number of a set is an indicator of the size of the set. It depends only on the elements of the set. Sets with the same cardinal number — or cardinality — are said to be equinumerate or (with unfortunate terminology) to be the same size. For finite sets there are no problems. Two sets, each having the same number ${n}$ of elements, both have cardinality ${n}$ . But an infinite set has the definitive property that it can be put in one-to-one correspondence with a proper subset of itself.

An obvious example is the set of natural numbers ${\mathbb{N} = \{1, 2, 3, \dots \}}$ , which can be matched element for element with the set of even natural numbers ${\mathbb{E} = \{2, 4, 6, \dots \}}$ by the mapping ${n \longleftrightarrow 2n}$ .

According to the axiom of choice, every set can be well-ordered. A well-ordered set is an ordered set such that every subset has a least element. Clearly, ${\mathbb{N}}$ is well ordered, whereas ${\mathbb{Z}}$ is not.

Georg Cantor introduced the ordinal numbers to describe the lengths of infinite sets (strictly, we should say ordinality or order type, but length is simpler). In a sense, the cardinal number measures the “size” of a set while the ordinal measures its length. For finite sets there is essentially no difference between these: we can shuffle a finite set without changing either its size or its length.

The cardinal number of a finite set with ${n}$ elements is ${n}$ , and the ordinal number is also ${n}$ . Colloquially, the size and length of the set are both ${n}$ . While finite sets of the same size also have the same length, this is no longer true for infinite sets.

The ordinal number ${\omega}$ is the first infinite ordinal. It is the ordinal number of the set of natural numbers (with the usual ordering). Suppose we shuffle ${\mathbb{N}}$ by moving the first element to the end:

$\displaystyle \mathbb{N} \longrightarrow \mathbb{N}^\prime = \{1, 2, 4, \dots , 3 \} \,.$

Something crucial has changed: whereas ${\mathbb{N}}$ has no greratest element, the set ${\mathbb{N}^\prime}$ does have a greatest element, ${3}$ . The ordinal number of this set is ${\omega + 1}$ . But adding an element on the left does not change the ordinality: the set ${\{0, 1, 2, 3, \dots \}}$ has ordinal number ${\omega}$ . If we insist on indicating the additional element, we can write ${1 + \omega}$ , but we are forced to conclude that ${1 + \omega = \omega}$ .

Now let us move all the even numbers so that they follow all the odd numbers:

$\displaystyle \mathbb{OE} \equiv \{ 1, 3, 5, \dots , 2, 4, 6, \dots \} \,.$

The ordinal number of ${\mathbb{OE}}$ is ${\omega + \omega = \omega\,2}$ . With obvious notation, ${\mathbb{EO}}$ also has ordinality ${\omega\,2}$ .

The Hierarchy of Ordinals

The spiral of ordinal numbers up to ${\omega^\omega}$ [image Wikimedia Commons].

There is a whole hierarchy of ordinal numbers. The Figure shows them represented as a spiral from ${0}$ up to ${\omega^\omega}$ . Cantor continued the process, constructing a power tower of ${\omega}$ with height ${\omega}$ , which he denoted by ${\epsilon_0}$ . And he did not stop there. Indeed, there is no limit to the sequence of ordinals.

Cantor’s system was hugely controversial, and for good reasons. The non-commutative nature of the system was a cause of difficulty. Ordinals can be added, multiplied, and exponentiated. However, none of these operations is commutative. We have ${\omega + 1 > \omega}$ but ${1 + \omega = \omega}$ . One might be tempted to subtract ${\omega}$ from each side, but this would yield the nonsensical result ${1 = 0}$ .

The beautiful system of surreal numbers, invented by John Conway includes the ordinal numbers and the arithmetic operations are defined in a different way. That system forms a Field, respecting all the properties of commutativity, associativity, etc. (see reference below).

Sources

${\bullet}$ Darling, David and Agnijo Banerjee, 2022: The Biggest Number in the World: A Journey to the Edge of Mathematics. Oneworld Publications. ISBN: 9-780-8615-4305-2.

${\bullet}$ ThatsMaths: The Root of Infinity: It’s Surreal.

* * *

New Collection just Published

GREATLY REDUCED PRICE from Logic Press.

Now available also in hardback form

ThatsMaths