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 


Last 50 Posts

Categories