Ordinals

This is about the ordinal numbers, which (except for the finite ones) are less well known than the real numbers, although theoretically simpler.

The numbers of either kind compose a linear order: they can be arranged in a line, from less to greater. The orders have similarities and differences:

  • Of real numbers,

    • there is no greatest,

    • there is no least,

    • there is a countable dense set (namely the rational numbers),

    • every nonempty set with an upper bound has a least upper bound.

  • Of ordinal numbers,

    • there is no greatest,

    • every nonempty set has a least element,

    • those less than a given one compose a set,

    • every set has a least upper bound.

One can conclude in particular that the ordinals as a whole do not compose a set; they are a proper class. This is the Burali-Forti Paradox.

Diagram of reals as a solid line without endpoints; the ordinals as a sequence of dots, periodically coming to a limit

The descriptions above of the orders of numbers are characterizations: they determine each order up to isomorphism. The characterizations can be streamlined with some definitions:

  • A least upper bound is a supremum.

  • A linear order is

    • complete, if its every nonempty subset with an upper bound has a supremum;

    • well-ordered, if its every nonempty subset has a least element.

Thus both the real and the ordinal numbers are complete, but only the latter are also well-ordered.

There is no one canonical definition of a real number. Two possibilities are:

  1. a nonempty set of rational numbers with an upper bound, but no greatest element, in which every element is a lower bound for the set of non-elements;

  2. a series ∑k = m ek ⁄ 2k, namely em ⁄ 2m + em+1 ⁄ 2m+1 + em+2 ⁄ 2m+2 + …, where m is an integer (possibly negative), each ek is 0 or 1, and there is no upper bound on the integers k for which ek is 0 (since 1 ⁄ 2m + 1 ⁄ 2m+1 + 1 ⁄ 2m+2 + … can be written as 1 ⁄ 2m−1).

Either of these (incompatible) definitions determines the arithmetic of the real numbers, as well as their ordering. The ordering alone of the reals does not determine the arithmetic.

The ordering of the ordinals does determine their arithmetic. Moreover, an ordinal is canonically a set that

  1. is well-ordered by the relation ∈ of set-membership;

  2. includes, as a subset, its every element.

A set that includes its every element is called transitive. If one assumes the Axiom of Regularity, then an ordinal is simply a transitive set of transitive sets.

The origin of the sign ∈ in the Greek epsilon (ε) is discussed in “Boolean Arithmetic.”

Counting

Our first mathematical activities in life may be

  1. to recognize persistent discrete objects, and then

  2. to count them.

We count with numbers: one, two, three, and so on. These are ordinal numbers, because they put objects into a linear order, as above.

The ordinal numbers that we count with are also cardinal numbers, since the last number we reach is the cardinality—the purely numerical size—of the collection of objects that we have just counted.

Had we counted our collection in a different order, then we should have reached the same number in the end. I think nobody questions this, except perhaps the mathematician.

I recall sitting on an airplane, watching boxes of banknotes being loaded into the cargo hold. A man was counting the boxes as they passed along the loading ramp. He wrote a number on each box with a pen, so that he would not lose count. Had the order of the boxes mattered to the count, then the numbers would already have been on the boxes, and the man would have had to check those numbers off a list, or see them pass by in order, as they went into the plane.

Infinite Sets

The order of counting does not matter; but actually this is a theorem, and it fails for infinite sets. Not every infinite ordinal is a cardinal, but different ordinals can count the same infinite set.

You may deny that there are infinite sets. My father effectively did this, or at least did not recognize the possibility of their existence. When I learned from him the concept of infinity, which you could never count up to, I came up with the idea of infinity plus one, infinity plus two, and so on. My friend across the street was impressed: “You invented some new numbers!” he said. My father was not so impressed.

Those “new numbers” did not represent any new cardinalities; but they were indeed new ordinals, at least if “infinity” is understood more precisely as a particular ordinal number, such as the first ordinal after the finite ones: this is the ordinal that Georg Cantor denoted by ω (omega) in 1895. Here I am consulting Cantor’s Contributions to the Founding of the Theory of Transfinite Numbers, in the translation of Philip E.B. Jordain (New York: Cosimo Classics, 2007) that was originally published in 1915.

A Particular Infinite Ordinal

A recent paper (not by me) has a theorem involving the ordinal ωωω. The least ordinal is 0; then come the other finite ordinals, 1, 2, 3, and so on; then ω. The ordinals less than ωωω, other than 0, are those that can be written as sums

ωα0 + … + ωαm,

where m is a finite ordinal, and each exponent αi is an ordinal less than ωω, and

α0 ≥ … ≥ αm.

The ordinals less than ωω, other than 0, are those that can be written as sums

ωb0 + … + ωbn,

where n is a finite ordinal, and each exponent bj is a finite ordinal, and

b0 ≥ … ≥ bn.

We can likewise write nonzero ordinals less than ωωωω as finite sums of powers of ω whose exponents form a descending sequence of ordinals less than ωωω; then we can write ordinals less than ωωωωω; and so on.

The least ordinal greater than all of the powers ω, ωω, ωωω, and so on is called ε0.

This is only the beginning. The ordinal ε0 is only the least solution to the equation

ωξ = ξ.

Other solutions are ε1, ε2, ε3, and so on; then εω. There is a solution εα for each ordinal α. In particular, there are εωω, and εωωω, and so on; then εε0; also εεε0, and εεεε0, and so on. Again, this is only the beginning.

With ordinals, we are always only at the beginning, because of the property that for every set of them, there is another that is greater than each of them.

The ordering of the ordinals described above as sums can be understood from the rules that, for all ordinals α and β,

α + βα,

ωα ≥ ωβαβ,

α < β ⇒ ωα + ωβ = ωβ;

also,

ω0 = 1.

Even among mathematicians, perhaps not many will have learned such things.

Measuring

When young, we may learn about negative numbers through measuring temperatures. I don’t know if that was so for me: using the Fahrenheit scale in a temperate zone, I never saw temperatures below zero, though I must have learned that this was theoretically possible. I do remember learning in school that to add a positive and a negative number, you take a difference, then use the sign of the larger number.

When we learn to measure, be it with a thermometer or a ruler or a bathroom scale, we are using real numbers. Strictly we are using rational approximations to real numbers; however, somebody may teach us that numbers like the square root of two exist, but are irrational.

Completeness

If we learn calculus, this relies on the property of the real numbers that I recall being introduced to by Daviette Stansbury. I suppose this was in Geometry, though it could have been Algebra II; Mrs Stansbury taught both of them. If you break a geometrical line in two, she said, then exactly one of the pieces must have an endpoint.

That is precisely the property of the real numbers that distinguishes them from the rational numbers. If you divide the rationals into two classes, each member of the first being greater than each member of the second, then there may be neither a least member of the first class nor a greatest member of the second. This is what happens when one class consists of the positive rationals whose squares exceed two; the other, the other rationals. It is possible in every such case to fill the gap with an irrational real number: in the example, the positive square root of two.

In a word, the linear order of real numbers is complete. If one learns nothing else from calculus, one ought to learn that completeness makes it all possible. Of course this will not mean much unless one also learns what completeness makes possible; and that is hard. I may not be the only mathematician for whom learning calculus rigorously was the hardest thing they ever did, at least in mathematics.

In another post, revisiting the first chapter of Collingwood’s New Leviathan and in particular its concept of scientific persecution, I had reason to bring up the notion of Donald Knuth that he could make learning calculus a pleasure by means of “several notational improvements that advanced mathematicians have been using for more than a hundred years.” This was backed up by no evidence; it was a fantasy. Many of us think we could solve the problems of the world, if only everybody else would listen. But then we have not even solved the problem of how to get people to listen.

Like the real numbers, the ordinal numbers are also complete: there are sets of ordinals with no greatest element, but with an upper bound, and then there is a least upper bound, a supremum. The supremum

  • of the set of finite ordinals is ω;

  • of the powers ω, ωω, ωωω, and so on, ε0.

I cannot say that learning the ordinals would be an aid in learning calculus. I called it a theorem that all ordinalities of a finite set are the same. Proving the theorem is not so easy, if only because we have implicitly accepted the theorem since childhood. Or perhaps proving the theorem is not hard, once one has defined the technical machinery involved; but this is hard. Likewise, though defining the real numbers is harder or at least more complicated than defining the ordinals, still the existence of the reals, as a complete linear order, may be easier to accept than the existence of the complete linear order of ordinals.

Axiomatizations

The main difference between the two orders is,

  • the reals are dense: between any two of them lies a third;

  • the ordinals are well-ordered: any nonempty set of them has a least element.

The properties of being dense and being well-ordered are mutually exclusive (provided an order is understood to have at least two elements).

Not only are the reals dense, but the rationals are dense in them: between any two reals lies a rational.

When I learned calculus from Donald J. Brown, we students were given the real numbers axiomatically, as a complete ordered field. From algebra with Mrs Stansbury, we knew about ordered fields, though not by that term. The rational numbers alone compose an ordered field, which just means that two of them can be

  • compared, to see which one is greater, if they are different;

  • added, to form a sum;

  • multiplied, to form a product;

and the ordering relation and the operations of addition and multiplication interact in the ways that one learns in algebra. (For example, every nonzero rational or its negative is positive, and sums and products of positive numbers are positive.)

Mr Brown observed that one could construct the real numbers, but we would not be doing this. I quote his own words, as having been important for my own understanding; they are from the typed and photocopied notes that he gave out at the beginning of his two-year course (the first year being nominally Precalculus, the second Calculus).

There are many ways to approach a study of the real numbers. One way, called the constructive approach, is, as the name suggests, to construct the entire system of real numbers from basic building blocks called the natural numbers. It is a technical and involved method requiring fine attention to detail and completeness, but in the end one obtains the real numbers and all of their properties.

A second approach, appropriately called nonconstructive, takes the opposite direction. That is, one assumes the existence of the real numbers and then looks for a set of characteristic properties (axioms) which are sufficient to describe completely the real numbers as a mathematical system. This is the approach which we will take.

The real numbers as a mathematical system are technically what is known as a complete ordered field. The three terms of this expression, in fact, give the kinds of axioms which characterize the real numbers in just this way. First, the real numbers are a field because they are a set upon which two binary operations, addition and multiplication, have been defined and which satisfy field axioms. Second, they are ordered because there is a way in which we can talk about a property called “positiveness” which satisfies order axioms. Lastly, they satisfy the completeness axiom, which intuitively means that there are no “gaps” in the real number line.

It is time to make these ideas precise …

I skip the precision of the axioms.

Construction of the Reals

I worked through the construction of the real numbers for myself, in the Epilogue of Spivak’s Calculus (second edition, 1980), which was an official reference for Mr Brown’s course. I review the construction now, to back up my claim that it is more complicated than that of the ordinals.

Leaving off 0, I start with the counting numbers, 1, 2, 3, … There are two ways of filling out their order.

  1. For any two counting numbers, there is a quotient of the first by the second. This quotient is a new number, unless the second of the two counting numbers was unity. The quotients are ordered by the rule,

    a ⁄ b < c ⁄ dad < bc.

    Consequently,

    a ⁄ b = c ⁄ dad = bc.

    If two different expressions a ⁄ b and c ⁄ d stand for the same quotient, what is it? We may say it is precisely the set

    {(x, y): ay = bx}

    of ordered pairs of counting numbers. Perhaps children do not raise the question and are not given such an answer. In any case, the order of the quotients is dense:

    a ⁄ b < c ⁄ da ⁄ b < (a+c) ⁄ (b+d) < c ⁄ d.

  2. For any two counting numbers, there is a difference of the first from the second, nominally resulting from subtracting the second from the first. If the first number is not greater than the second, the difference is a new number: either 0 or a negative number. Each of these is less than each of the counting numbers. Thus the ordering of the differences is not dense, though it is defined as for quotients:

    ab < cda + d < b + c.

The quotients just defined are the positive rational numbers; the differences, the integers. Taking differences of all of the positive rationals yields the rationals, simply.

As noted, the order of rational numbers is dense. It also has no greatest or least element, but let us express this in a positive way: there are rational numbers both greater and less than any given rational.

The order of the rational numbers is still incomplete. There are gaps in the sense described earlier. However, we can fill each gap with—itself. That is, if we define a gap in the rationals as precisely a division of them into two classes, each member of the first being greater than each member of the second, but where there is neither a least member of the first class nor a greatest member of the second, then we can define the real numbers to consist of

  1. the rational numbers, and

  2. the gaps.

Perhaps one is taken aback by the thought that we are “allowed” to do this. In any case, one still has to show how the rationals are an ordered field, and that this property carries over to the reals.

By our definition, it is immediate that the rationals are dense in the reals, which are complete. The rationals are also countable, because they can be listed so as to be counted by the counting numbers. Such a list might be 0, 1, −1, 2, −2, 3, −3, 1 ⁄ 3, −1 ⁄ 3, 1 ⁄ 4, −1 ⁄ 4, 2 ⁄ 3, −2 ⁄ 3, 3 ⁄ 2, …

If one wants only to construct a complete linear order with no endpoints, but with a countable dense subset, one may let that subset consist of finite sums ∑k = mn ek ⁄ 2k, namely em ⁄ 2m + em+1 ⁄ 2m+1 + … + en ⁄ 2n, where again each ek is 0 or 1, and mn.

Construction of the Ordinals

The ordinals result from a third way of filling out the counting numbers, beyond taking quotients and negatives. Or let us now say that we start with the natural numbers: the counting numbers with 0. Actually we can start with 0 alone. Then we declare that, at any stage, for the greatest number that we know so far, there is a successor, which is yet greater. It is the number, “plus one.” This process gives us all of the natural numbers. We get the ordinals by declaring further that, for every set of numbers that we have so far, there is a greater. This gives us ω, for example, as the number greater than all of the natural numbers; then there are ω + 1, ω + 2, ω + 3, and so on; then ω + ω or ω ⋅ 2, ω ⋅ 2 + 1, ω ⋅ 2 + 2, and so on.

How can we just declare a number into existence? Whenever α is a set of ordinals that contains, for its every element, every ordinal that is less than that element, we declare α itself to be a new ordinal, greater than all of its elements. By this construction, 0 is the empty set, and every ordinal is the set of ordinals that are less than it is.

The construction is von Neumann’s, depicted in an early post of this blog.

Arithmetic

The arithmetic of the counting numbers is determined by the rules

(1)

α + (β + 1) = (α + β) + 1,

(2)

α ⋅ 1 = α & α ⋅ (β + 1) = (α ⋅ β) + α.

Using these, we define the operations of addition and multiplication of rationals as in school. Depending on how one has defined the reals, one can extend the operations to them, then prove that they make the reals into an ordered field, as in Spivak; but the process is tedious. One can also argue from completeness that since the operations on the rationals are uniformly continuous on closed bounded intervals, they extend uniquely to the reals, which also then become an ordered field.

On the ordinals, rules (1) and (2) continue to hold; also α + 0 = α and α ⋅ 0 = 0. It remains to define α + γ and α ⋅ γ when γ is a limit: neither 0 nor the successor of any ordinal. We make the definitions to ensure continuity, and there is only one way to do it:

α + γ = sup {α + ξ: ξγ},

α ⋅ γ = sup {α ⋅ ξ: ξγ}.

Now the operations ξα + ξ and ξα ⋅ ξ are continuous. However, ξξ + α and ξξ ⋅ α are not continuous (unless trivially so, when α is 0 in the former, 0 or 1 in the latter). For example,

1 + ω = ω < ω + 1,

2 ⋅ ω = ω < ω ⋅ 2.

Sets and Classes

The construction of the ordinal numbers would seem to be a lot simpler than constructing the reals.

However, the construction entails that the ordinals themselves do not compose a set. They form a proper class. Every set a is the class {x: xa}, consisting of the members of a. We assume that those members are always themselves sets. Every set is thus a class.

Not every class is a set. The simplest example is {x: xx}, by the Russell Paradox; but the class of ordinals is another example.

All of the ordinals described earlier are countable; thus their cardinality is ω, also called ω0: the least infinite ordinal. There are uncountable sets, such as ℘(ω), the set of subsets of ω. For any set a, the set ℘(a) of its subsets has greater cardinality, in the sense that a is in one-to-one correspondence only with proper subsets (such as {{x}: xa}) of ℘(a), and not with the whole set: for if ax ∈ ℘(a) for each element x of a, then the subset {xa: xax} of a cannot be ax for any x in a.

One form of the Axiom of Choice is that every set can be counted: this means being well-ordered, and thus being put in one-to-one correspondence with some ordinal. Even without this axiom, the class of all ordinals that can be put in one-to-one correspondence with subsets of a given set A is a set, and in particular an ordinal, which therefore cannot be put in one-to-one correspondence with a subset of A. This is Hartogs’s Lemma. It means that, for every ordinal, there is not only a greater ordinal, but one of greater cardinality. This gives us the function

ξ ↦ ℵξ,

assigning to each ordinal α an infinite ordinal ℵα (“aleph-alpha”), which is the least ordinal of its own cardinality. The function is strictly increasing: the greater the α, the greater the ℵα. For every infinite ordinal β, the least ordinal of its cardinality is ℵα for some α.

The code for ℘ is

&weierp;

and ℵ is

&alefsym;

—that is, “weierp” and “alefsym” respectively between ampersand and semicolon. Using “wp” and “aleph” worked when I checked my drafts directly on a browser (Opera) without uploading to the blog; but these were not official character entity references in HTML4. Also on the site of the World Wide Web Consortium is a chart with a lot more entity references for HTML5 (including “wp” and “aleph”) but the status is unclear.

The ordinals are endless; blog articles, not.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.

%d bloggers like this: