Polytropy

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.

The descriptions above of the orders of numbers are characterizations: they determine either 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}^∞ e_k ⁄ 2^k, namely e_m ⁄ 2^m + e_m+1 ⁄ 2^m+1 + e_m+2 ⁄ 2^m+2 + …, where m is an integer (possibly negative), each e_k is 0 or 1, and there is no upper bound on the integers k for which e_k is 0 (since 1 ⁄ 2^m + 1 ⁄ 2^m+1 + 1 ⁄ 2^m+2 + … can be written as 1 ⁄ 2^m−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 determines 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, every set that it contains as an element.

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

The origin of the sign ∈ in the minuscule 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.

Some Particular Infinite Ordinals

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

ω^α₀ + … + ω^α_m,

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

α₀ ≥ … ≥ α_m.

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

ω^b₀ + … + ω^b_n,

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

b₀ ≥ … ≥ b_n.

Now we have described all of the ordinals that are less than ω^ωω

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 ε₀. This is only the beginning. The ordinal ε₀ is only the least solution to the equation

ω^ξ = ξ.

Other solutions are ε₁, ε₂, ε₃, 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 ordinal 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,

ω⁰ = 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 they were 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 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, ε₀.

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, by reading 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 first number is a multiple, in the original sense, of the first. The quotients are ordered by the rule,

   a ⁄ b < c ⁄ d ⇔ ad < bc.

   Consequently,

   a ⁄ b = c ⁄ d ⇔ ad = bc.

   One must check that quotients that are equal to the same quotient, by this definition, are equal to one another; and then one must check that a quotient can be replaced by an equal without changing its place in the order.

   Today, in mathematics, we usually think of equals as being the same. If two different expressions a ⁄ b and c ⁄ d are equal by our rule and therefore 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 ⁄ d ⇒ a ⁄ 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:

   a − b < c − d ⇔ a + 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 = mⁿ e_k ⁄ 2^k, namely e_m ⁄ 2^m + e_m+1 ⁄ 2^m+1 + … + e_n ⁄ 2ⁿ, where again each e_k is 0 or 1, and m ≤ n.

Construction of the Ordinals

The ordinals result from a third way of filling out the counting numbers, other than taking quotients and negatives. Or let us fill out instead the natural numbers: the counting numbers with 0. Actually we can fill out 0 alone. We declare that, at any stage of this filling out, for the greatest number that we know so far, there is a successor, which is yet greater. It is the greatest known 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? Well, 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 = α & α ⋅ (β + 1) = (α ⋅ β) + α.

Using these rules, we can go on to 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 denoted by {x: x ∈ a}, 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: x ∉ x}, by the Russell Paradox; but the class of ordinals is another example.

Each of the ordinals described earlier is countable; thus its cardinality, if infinite, is ω, also called ω₀: 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}: x ∈ a}) of ℘(a), and not with the whole set: for if a_x ∈ ℘(a) for each element x of a, then the subset {x ∈ a: x ∉ a_x} of a cannot be a_x 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 even 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 α.

In the underlying html file of this post, the code

• for ℘ is

  ℘

• for ℵ is

  ℵ

—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 their status is unclear.

The ordinals are endless; blog articles, not.