Fri, 21 Aug 2026
The road to epsilon-zero: Shortlex order also orders sequences of numbers
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- Nim always ends, even with infinite ordinals
- Infinite Nim as a coin-moving game
- Coin-moving games with no coins
- Productive programs and well-founded orders
In part 4, Infinite Nim as a coin-moving game, we saw how to reinterpret infinite Nim into an equivalent game: instead of heaps of beans and various special tokens, we interpreted it as a game about moving coins first on a track, then on a grid, and then in a rather difficult-to-visualize infinite-dimensional space.
In part 5, Coin-moving games with no coins, we stopped thinking about the coins and their locations in space, and just wrote down the coordinates of each coin. Each coin has an infinite sequence of coordinates, each of which is a non-negative number. But crucially, only a finite number of the coordinates are greater than zero, so every coin's list of coordinates can be written down as a finite sequence, with the infinite tail of zeroes left implicit.
The rule for the original game of Nim was: take as many beans as you want from any one pile.
The rule for the reinterpreted form is: reduce any one sequence of coordinates, as follows:
- Pick any nonzero coordinate
- Reduce it by at least 1
- Replace any coordinates to the left of that one with any numbers at all
For example, we can move from !!⟨2, 3⟩!! to !!⟨17, 2⟩!! (the !!3!! has decreased), or to !!⟨1, 3⟩!! (the !!2!! has decreased). We can move from !!⟨9, 3, 7⟩!! to !!⟨1000, 23, 5⟩!! (the !!7!! has decreased), or to !!⟨86, 19, 0⟩!!, which we can also write as !!⟨86, 19⟩!!.
Now that we've learned about shortlex order, we can state the game rule more simply:
Replace any one sequence of coordinates with one that is earlier in shortlex order.
There's one minor wrinkle. We had defined shortlex order as:
- If the sequences are different lengths, the shorter one comes first.
- If they're the same length, compare them lexicographically.
None of that has changed, but we need to be a bit careful about “lexicographically”.
When we write ordinary numerals, like 239, we write the most
significant part on the left. In this case it's the !!2!!, which represents
!!200!!. And when we compare numerals of the same length
lexicographically, we compare these most significant parts first,
moving rightward only if the leftmost parts are tied.
To lexicographically compare sequences of coordinates or the same length, we still need to begin with the most significant part as before. But because of how we are writing the sequences, the most significant part is the rightmost component. A sequence like !!⟨9, 3, 2⟩!! represents a nim-heap of !!9 + ω·3 +ω^2·2!! beans, and the !!2!! is the most significant component, because !!ω^2·2!! is vastly more than !!9+ω·3!! beans.
I said at some point that !!ω^ω!! was where the ordinals start to get scary. But !!ω^ω!! is now not scary at all. It's just the family of of nim-heaps where:
- Instead of beans, we think of a heap as a finite sequence of finite numbers
- Instead of imagining the player removing beans from a heap, we imagine them replacing the sequence with a sequence that is earlier in shortlex order
And to play Nim with ⸢heaps⸣ of this sort, the winning rule is, as always, that the winner is the player who reduces the last ⸢heap⸣ to to zero.
We can completely forget about beans, about infinite piles, about infinite varieties of colored tokens, about coins moving around in infinite-dimensional spaces, and so on. !!ω^ω!!-Nim is just finite sequences of ordinary numbers, and you can move from one sequence to any earlier one.
I think !!ε_0!! is going to arrive in the next article.
[Other articles in category /math/ordinals] permanent link
Thu, 13 Aug 2026
The road to epsilon-zero: Productive programs and well-founded orders
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- Nim always ends, even with infinite ordinals
- Infinite Nim as a coin-moving game
- Coin-moving games without the coins
Previously we saw how to interpret the difficult-seeming ordinal !!ω^ω!! as a particular ordering of the set of finite sequences of numbers, revealing what seemed like a scary monster as gentle and straightforward.
Now we're going to take a sidetrack into one of my favorite topics, computation with infinite lists. I wrote about this for The Perl Journal in 1997 and then it turned into chapter 6 of Higher-Order Perl and here we are again. Gosh! it just keeps coming back. Like John the Baptist.
Infinite lists
Suppose you have an infinite set of strings — we'll call this set !!S!! for the rest of the article — and you want a program to print them all out. Of course the program can't exactly print them all out, because it will only run for a finite amount of time. But there are more and less useful ways for the program to try.
For each string that the program is supposed to print, we should at least be able to guarantee that the the program will print it, eventually, if we just wait long enough. If this is true then we'll say that the program is “productive”.
Here's a productive program to print the base-10 numerals for all the positive integers:
# Python
i = 1
while True:
print(i)
i += 1
What would a non-productive program look like? Here's an example of a non-productive program to print the base-10 numerals for all the positive integers:
# Python, silly
i = 1
while True: # print all the odd numbers
print(i)
i += 2
i = 2
while True: # then print all the even numbers
print(i)
i += 2
This one tries to print all the odd numbers first, and then all the even numbers. Obviously that doesn't work because it never finishes with the odd numbers. If you were to sit around waiting for the number !!14!!, you'd wait forever. Whereas with the first program, whatever number you are waiting for, even if it is very very big, it will come out eventually.
That's what I meant when I said there are more and less useful ways for a program to try to print an infinite set. The first one never finishes, true, but the way in which it never finishes is much more useful than the way in which the second one never finishes.
Okay, that was a silly example. But there are less silly examples.
Printing strings in sorted order
A productive program is always semidecidable: if a user wants to know if some particular string !!s!! is in !!S!!, and they wait long enough, !!s!! will come out and they have the answer. But if !!s!! isn't in !!S!!, they never find that out! They just wait and wait, wondering if it will come out, and never getting a definitive answer.
If we can get a productive program to produce its strings in sorted order, we can make a better guarantee. The program will be decidable: the user will eventually get an answer, one way or the other. If !!s\in S!! the productive program will eventually produce !!s!!, and the user can stop watching. But if !!s\notin S!!, the program must eventually produce a string that comes after !!s!! in sorted order, and they can quit then. And the program must eventually produce some string that comes after !!s!!, because, being productive, it eventually produces every string in !!S!!.
(What if there is no string in !!S!! that comes after !!s!! in sorted order? Then the productive program will first produce all the strings that precede !!s!!, then it will produce !!s!!, and then it will halt. When it does that user has their answer, whatever it is.)
Not every program is productive
The non-productive program I showed above is silly, but productivity isn't something you can always guarantee, if you want the data in sorted order. Some orders work, and some don't.
The conventional order for strings, implemented by Python's
< operator or C's strcmp, is called lexicographic, which means
“dictionary-style”. There are some sets of strings for which
no productive program can print all the strings in lexicographic order.
For example, consider the set of all strings that are made up of
either all as or all bs:
a
b
aa
bb
aaa
bbb
aaaa
bbbb
…
Notice that this list is not in lexicographic order, because in
lexicographic order, the string aa should come out before b.
There is no productive program to print this set in lexicographic order. Why not? Because in lexicographic order the list begins like this:
a
aa
aaa
aaaa
aaaaa
…
and the program never gets around to printing any of the strings with
bs. This is analogous to how the non-productive example earlier waited to
print even numbers until after it was finished with the odd numbers.
To print these strings in lexicographic order would meansto print the
strings beginning with b after printing the strings
beginning with a. But the program never does finish with the strings
beginning with a. The program is supposed to produce bbb, but it
never does, no matter how the user waits. And it's supposed to reach
a point where the user can be sure that banana will not come out,
but it never does that either, it keeps printing as and never prints
a string like bbb that comes after banana in lexicographic order.
The problems with lexicographic order are even worse than this example shows. Consider this set of strings:
b
ab
aab
aaab
aaaab
aaaaab
…
Notice again: not lexicographic order, because b should come out last, not first.
But what should come first? A program to print these strings in lexicographic order
can't even get started, because in lexicographic order, this list of strings doesn't have
a first element! The program can't print out b first because all
the a strings were supposed to come out before that. And it can't
print out ab first because aab was supposed to come out before
that. And it can't print out aaaaaaaaab because aaaaaaaaaaaaaaab
was supposed to come out before that. Whatever string the program
tries to print out first, it will have made a mistake!
If you're trying to print out an ordered, infinite list of strings, lexicographic order just won't do.
Lexicographic order isn't well-founded
In an earlier article in this series we talked about “well-founded” orders. In a well-founded order, every set of items has a first item, if it has any at all. Writing a productive program for a well-founded order is easy:
- Repeat forever:
Question: Are there any items left to print?
No: Halt
Yes:- Let !!P!! be the set of unprinted items
- Let !!s!! be the first item in !!P!!
(There must be one, because we're printing the items in a well-founded order) - Print !!s!!
As we saw, the conventional lexicographic order is not well-founded for strings. Some sets simply don't have a lexicographically first element.
So in circumstances where we might be handling infinite data streams, we often prefer a different string ordering, almost as simple and considerably better-behaved.
Shortlex order
You already know this one, although perhaps not by that name. It's
nothing more than the order we use for regular numerals like 723.
It's not lexicographic, because as you've probably noticed, in
lexicographic order, 10 comes before 2. Here's the track listing
of my copy of Quadrophenia, as listed by the Unix ls program:
1 I am the sea.mp3
10 I've had enough.mp3
11 515.mp3
12 Sea And Sand.mp3
13 Drowned.mp3
14 Bell Boy.mp3
15 Doctor Jimmy.mp3
16 The Rock.mp3
17 Love Reign O'er Me.mp3
2 The real me.mp3
3 Quadrophenia.mp3
4 Cut my hair.mp3
5 The punk and the godfather.mp3
6 I'm one.mp3
7 The dirty jobs.mp3
8 Helpless dancer.mp3
9 Is it in my head.mp3
Hey, wait, why did ls put track 17 ahead of track 2? Because ls
lists files in lexicographic order, and in lexicographic order, 17 comes
ahead of 2 for the same reason that agony and the other ag-
words come before bony and the other b- words in the dictionary:
1 comes before 2 just as a comes before b.
If you name your files after numbers, then when the computer lists them in lexicographic order, they won't be in numeric order. Numeric order isn't lexicographic. But numerals, in shortlex order are in numeric order, and of course it's trivial to print all possible numerals in numeric order.
The rule to compare two strings in shortlex order is:
- If the strings are different lengths, the shorter one comes first.
- If they're the same length, compare them lexicographically.
Compare the shortness first, and use lexicographic comparison as a tiebreaker. Hence “short” + “lex”.
Consider what this means for numerals. Here's a list of binary numerals from !!0!! to !!15!!:
0
1
10
100
1000
1001
101
1010
1011
11
110
1100
1101
111
1110
1111
It looks strange because it's in lexicographic order — all the numerals that begin with 10
appear before all those beginning with 11, which means that 1000
comes before 11, even though (checking my notes) !!3 \lt 8!!.
If we want to print all binary numerals in lexicographic order, we're out of luck. The list starts like this:
0
1
10
100
1000
…
and we never get to printing any of the numerals starting with 11,
including 11 itself.
In shortlex order, it's what we expect. We get the numeral for every number, and in numeric order:
0
1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111
…
Unlike lexicographic order, the shortlex order is well-founded. Remember that “well-founded” means that every set of strings has a first element. But in lexicographic order, this set of binary numerals has no first element:
11
101
1001
10001
100001
…
In shortlex order there's no problem. There can't be, because shortlex order is numeric order, and if numeric order wasn't well-founded there wouldn't be a productive program to print all the numerals in order, which of course there is.
The infinite lists that we couldn't put into lexicographic order before give us no trouble in shortlex order. In fact, I listed both in shortlex order already:
a b
b ab
aa aab
bb aaab
aaa aaaab
bbb aaaaab
… …
For strings, shortlex order is well-founded, which means that every set of strings contains a first element. Here's why: Consider some set !!S!! and some string !!s\in S!!. The string !!s!! has a length !!\ell!!. Consider the set !!E!! of strings that come before !!s!!. The set !!E!! must be finite because every string that comes before !!s!! in shortlex order has length less than or equal to !!\ell!!, and there are only a finite number of such strings.
If !!E!! is empty, then !!s!! itself is the first string in !!S!!. If !!E!! is not empty, then, being finite, it must have a first element. (Just sort !!E!!.) This first element is the first string in !!S!!. Done.
Wait, why are there are only a finite number of strings with length less than or equal to !!\ell!!? Well, there are only a finite number of strings of length !!0!!. (There's only one.) And there are only a finite number of strings of length !!1!!: If the character set contains !!n!! symbols, there are only !!n!! with length !!1!!. Similarly there are only !!n^2!! strings of length !!2!!, and so on. Since there are only a finite number with each length up to !!\ell!!, we just add up this finite list of finite numbers and the sum is finite. And since every string in !!E!! has length no more than !!\ell!!, the number of strings in !!E!! is at most this finite number.
Coming next: Shortlex order also orders sequences of numbers.
[Other articles in category /math/ordinals] permanent link
Tue, 11 Aug 2026
There are two kinds of theorems
In mathematical study there are two kinds of theorems, which serve very different purposes. Math instruction follows the same pattern. Students are often very puzzled by this, and rightly so, because it's never explained, or at least I've never seen it explained. There is this crucial, critical piece of mathematical methodology which is never made explicit, students just have to figure it out on their own, and many of them never do.
When we do mathematics, we construct a simplified model of some phenomenon. For example, Euclidean geometry is a simplified model of how shapes and lines actually work.
In formal geometry, things are simple: lines have no thickness, and three or more lines might all intersect at the exact same point. There are perfect circles, where every point is the exact same distance from the center, and there are perfect rectangles with perfectly straight sides and perfectly equal angles.
Real shapes aren't like this. Nobody can draw an infinitely thin line. Nobody has ever seen a geometrically perfect circle or rectangle. Three lines, however carefully drawn, will always intersect in three different places. That's okay! The point of geometry is to construct a simplified model that is easier to deal with.
When we're setting up a mathematical model, we start by describing its basic objects, like points and lines, and with axioms and postulates, what properties we intend the objects to have. For example, Euclid has:
- A line is breadthless length.
- A circle is a plane figure contained by one (curved) line with a point inside, the center, so that the segments from the center to the boundary of the circle are always of equal length
- All right angles are equal.
Having done that, we state and prove the theorems of the first kind. We're not studying the actual phenomenon yet. We're not yet trying to learn anything new about shapes and circles. Instead, we're investigating the model itself:
Is the model accurate? Does it seem to lead to wrong conclusions? What happens if we try to prove things that we know are are false? The proofs should fail! If they don't, something is wrong with the model, and we need to fix it.
Is the model powerful enough to prove at least simple things about the actual phenomenon? If it can't encompass the simple aspects of the phenomenon, we haven't much hope of using it to understand more complex aspects.
So for example Euclid starts by proving extremely simple theorems. For example, propositions 4 and 5:
- Proposition 4: If in triangles !!ABC!! and !!A'B'C'!! we have !!AT=A'B'!! and !!AC=A'C'!! and !!\angle A = \angle A'!!, then the two triangles are congruent.
Proposition 5: If two straight lines cut one another, then they make the vertical angles equal to one another.
(That is, !!\angle CEB = \angle AED!! and !!\angle CEA = \angle BED!!.)
Obviously, yes, anyone can see that! We didn't need to develop a whole mathematical theory in order to discover that vertical angles were equal. Everyone already knew that, long before Euclid. The point of proving this theorem, the real discovery, is: our simple model is strong enough to demonstrate that vertical angles are equal. The theory didn't explicitly include anything about vertical angles, but the vertical angle theorem was latent in the model anyway.
Consider the opposite situation, where we couldn't prove that vertical angles were equal. Or worse, what if the model allowed us to construct a pair of unequal vertical angles? Would this tell us something about vertical angles? Obviously not. Vertical angles are equal, regardless of what the theory does or doesn't prove. It would, though, tell us something about the theory, namely that it wasn't fit for purpose, and we'd better try a different model.
This is a common pattern in all mathematics education and indeed in all mathematics, but I've rarely seen it called out as such, not even with a passing remark like “here's why we're doing this”. In nearly every undergraduate class I've ever been in, someone was puzzled about why we were doing this. Why is Euclid proving all these theorems that are obvious?
In Euclid the mode goes back and forth: Euclid will do some model-verifying theorems, then move on to interesting-result theorems, then back for a while to introduce something new to the model, then forward again to prove interesting theorems about the thing he introduced. The first transition happens around proposition 32 or 36 or so. Up until that point there were a lot of proposition like this:
Proposition 20 In any triangle the sum of any two sides is greater than the remaining one.
and this:
Proposition 25 If two triangles have two sides equal to two sides respectively, but have the base greater than the base, then they also have the one of the angles contained by the equal straight lines greater than the other.
But then very soon after, the theorems start to have a different flavor:
Proposition 36: Parallelograms which are on equal bases and in the same parallels equal one another.
That is:
This is actually an interesting fact about parallelograms, and not intuitively obvious. Even though the two parallelograms are not at all the same shape, they have equal areas, since they lie between the same parallels and !!AB=CD!!. (Interactive version)
The same issue comes up in many different contexts. We develop the theory of the Peano numbers, define addition, and prove that addition is commutative, Was that because we didn't know how to do addition? No. We already knew that addition was commutative. The point of the theorem is to show that Peano arithmetic knows that addition is commutative. But I have more than once seen instructors demonstrate the proof, via a double induction, and then finish with a remark like “therefore, addition is commutative!” The students, to their credit, were suspicious of this. They knew something wasn't quite right, even if they weren't sure what. The right announcement would have been something like “therefore, the Peano axioms aren't complete rubbish!”
Or: We explore Dedekind cuts, we define a model for the real numbers as cuts of rationals, and a construction that we claim characterizes addition. And then we prove a batch of theorems that are intended to show things we already know about addition, not because we want to know whether addition is commutative (news flash: it is) but to show that it's plausible that our construction really does characterize addition. One of these, that the addition operation we defined on cuts, which looks nothing like the addition we defined on rational numbers, actually agrees with it when the cuts themselves correspond to rationals. Another, that if !!a < b!! then !!a+c < b+c!!.
Taking a look at Rudin Principles of Mathematical Analysis, I see that the first fifteen or so pages are like this, theorems like !!\lvert z\rvert = \lvert \bar z \rvert!!, which is a basic property of the fundamental notions !!\lvert z\rvert!! and !!\bar z!!. And then the mode starts to shift, first a little bit, with
Let !!z!! and !!w!! be complex numbers. Then !!\lvert z+w\rvert ≤ \lvert z\rvert + \lvert w\rvert !!
Okay, that's a triangle inequality again… and suddenly, seemingly out of nowhere, something not at all obvious: Theorem 1.35, the Cauchy-Schwartz inequality for !!\Bbb C^1!!:
$$ \left\lvert\sum_{j=1}^n a_j\bar b_j\right\rvert ^2 ≤ \sum_{j=1}^n\lvert a_j\rvert^2 \sum_{j=1}^n\lvert b_j\rvert^2 $$
A completely different kind of theorem, not a basic property of anything.
Remember the whole point of the process: We wanted to model some object of study, we built a model, we proved a lot of theorems to lend plausibility to our model, to verify that the model wasn't broken, to confirm that the model captures the properties of interest. And then came time to use the model, and we started to prove theorems that told us new things about the original object of study.
Does Rudin announce this shift? Of course not, Rudin never announces anything. (Usually he mutters, and sometimes if you are especially unlucky he fixes you with a glare that dares you to question the remark he throws away in an undertone.) But Rudin is Rudin, and nobody else seems to announce this shift either. Almost always, it's passed over, usually without remark, even in gentler textbooks that give more attention to pedagogical matters. Sometimes the shift is sudden, sometimes gradual, but it's almost never pointed out.
In advanced study, that's okay, because advanced students should be expected to recognize the pattern. But why do we expect high schoolers and undergraduates to understand this without explanation?
In summary:
- There are two kinds of theorems.
- The purpose of the first kind is to validate the model we've built, to check it for power and correctness.
- But the second kind is the kind we're really after, to apply the model to the problem we want to study.
- This pattern, of building a model, validating it, and then using it, is a fundamental and universal methodology in all mathematical study.
- Secondary and tertiary mathematical education should explain this methodology, but rarely acknowledges it at all.
[Other articles in category /math] permanent link
Wed, 05 Aug 2026
The road to epsilon-zero: Coin-moving games with no coins
Previously:
- Ordinal numbers and basic set theory
- Ordinals as nim-heaps
- Nim always ends, even with infinite ordinals
- Infinite Nim as a coin-moving game
In the previous article we saw how to interpret Nim heaps of up to !!ω^2!! beans as coins on a quarter-infinite array:
The coin here represents a heap of !!ω·3 + 2!! beans. The heap can be reduced to any smaller number of beans. In the coin version of the game, this corresponds to moving the coin to any square to the left in the same row, or to any square in any lower row.
To extend this past !!ω^2!!, though, was a little clumsy. We had to pile up an infinite stack of these grids, and that got us only to !!ω^3!!. Then to go further we had to move into the fourth dimension, and to get all the way to !!ω^ω!! we had to imagine a sort of discrete Hilbert space with an infinite number of dimensions, not easy. I personally have trouble imagining anything with more than about !!17!! dimensions, and an infinite number of dimensions is a couple more than I can handle comfortably.
We can do better. Instead of imagining a grid of squares with coins on the squares, just write the coordinates of the coin! The one above, representing a pile of !!ω·3+2!! beans, is simply $$⟨2, 3⟩.$$
A game of infinite Nim is now simply a list of these pairs, one for each coin. A legal move is to pick one of the pairs and:
- reduce the first coordinate, which corresponds to moving the coin to the left in the same row, or
- reduce the second coordinate (which moves it to a lower row) and replace the first coordinate with any number at all, even a larger one (any square in the lower row is allowed)
Moving from !!ω·3+2!! to !!ω·3+1!! uses the first rule to reduce the first coordinate from !!⟨2, 3⟩!! to !!⟨1, 3⟩!!. Moving from !!ω·3+2!! to !!ω·2+17!! uses the second rule to reduce the second coordinate from !!⟨2, 3⟩!! to !!⟨2, 2⟩!! and simultaneously replace the first coordinate with !!17!!, leaving the coin on !!⟨17, 2⟩!!.
Removing the entire pile uses the second rule to reduce the second coordinate from !!⟨2, 3⟩!! to !!⟨2, 0⟩!! and simultaneously replace the first coordinate with !!0!!, yielding !!⟨0, 0⟩!!.
To stack up multiple grids no longer requires third dimension, just a third coordinate. To make it compatible with the two-coordinate notation, we just agree to understand !!⟨a, b⟩!! as an abbreviation for !!⟨a, b, 0⟩!!. The move rule generalizes to:
- Pick any nonzero coordinate
- Reduce it by at least 1
- Replace any coordinates to the left of that one with any numbers at all
For example, we can move from !!⟨2, 3, 0⟩!! to !!⟨17, 2, 0⟩!! (the !!3!! has decreased), or from !!⟨2, 3, 9⟩!! to !!⟨1000, 0, 7⟩!! (the !!9!! has decreased).
To go into the fourth dimension and beyond is similarly easy: just allow a list of coordinates of any finite length, and use the same rule as above: reduce any single coordinate, and simultaneopusly replace any or all of the coordinates to its left.
For example, !!ω^7 + ω^3·12 + ω^2 + ω + 83!! is now represented as !!⟨83, 1, 1, 12, 0, 0, 0, 1⟩!!. We can also imagine there is a trailing sequence of zeroes, of either finite or infinite length, but they don't affect the game.
Maybe it's easier to see now why this enormous nim-heap must eventually be removed. On the first move, someone must either reduce that !!83!! or else one of the numbers to the right of it. But the players can't indefinitely put off reducing one of the other numbers; if they work only on the !!83!!, then after at most !!83!! they will have arrived at !!⟨{\bf 0}, 1, 1, 12, 0, 0, 0, 1⟩!!, and then someone must reduce one of the other numbers, since moves from !!0!! aren't allowed.
The !!83!! can be increased, but only at the cost of reducing a farther-right number. But that's true of every number except the final !!1!!. And however long the players avoid reducing that final !!1!!, by reducing numbers farther left — and it might be a very, very, very long time — eventually they will get to !!⟨0, 0, 0, 0, 0, 0, 0, 1⟩!! and won't be able to put it off any longer.
To get ordinals up to !!ω^ω!! is straightforward: they correspond directly to finite sequences of numbers, with the moving rule described above: sequence !!A!! represents an ordinal less than sequence !!B!! if one of !!A!!'s elements is less than the corresponding one of !!B!!'s, and the elements to the right are the same.
I hd said at one point that !!ω^ω!! was where the ordinals started to get scary. And perhaps it does seem scary, if you try to think of it as cells in an infinite-dimensional array. But when you think of !!ω^ω!! as just the set of finite sequences of numbers, it's not scary at all!
That was my first big step on the road to !! \epsilon_0 !!, but !! \epsilon_0 !! seems much more daunting. It's not merely !!ω^ω!!, it's actually more like
$$ω^{ω^{ω^{ω^⋰}}}$$
because it's by definition the smallest ordinal !!x!! with the property that !!x = ω^x!!. But the next couple of articles will take us the rest of the way there!
Coming next:
- You can write a program to print an infinite list of strings, but you can't always write one to print them in alphabetic order: Productive programs and well-founded orders
- Shortlex order also orders sequences of numbers
[Other articles in category /math/ordinals] permanent link
Sun, 02 Aug 2026
Seven books I keep close because I love them
The bookshelf by my elbow, the one that I can reach without getting up, has seven books on it, not necessarily the ones I look in the most, but the ones whose emanations I most hope will infuse me as I write.
Roget's Thesaurus (4th edition)
The one I actually refer to most often is the Harper and Row Roget's Thesaurus. I thought I had acquired this in my teens, but the note on the flyleaf says 1989.
This is the fourth edition. I was very excited to get the eighth edition, which I thought I might like better, and for some time I kept them next to each other so that I could look up the same things in both, and compare. My conclusion was that while the eighth edition had more stuff in it, it wasn't stuff I needed. And it is really fat. So I have retired it to a farther shelf and will eventually get rid of it.
The thesaurus is a book that is widely misunderstood. It is not, as many people mockingly imagine, just a compendium of synonyms, and its correct and intended use is not to replace common words with more impressive-sounding ones. just as the correct use of a screwdriver is not to scrape the veneer off of an expensive cabinet.
“Thesaurus” means “storehouse" or “treasure room”. Roget's idea, similar to that of John Wilkins before him, was to classify everything in the world into a hierarchy, in this case a hierarchy with a thousand divisions. At the top level the divisions are grouped into "Abstract concepts", "Space”, “Physics”, “Matter”, “Sensation” and so on. Then under “abstract concepts” there are subclasses, of which subclass VI is “Time”, subdivided into five smaller sections:
A. Absolute time
B. Relative time
C. Time with reference to age
D. Time with reference to season
E. Recurrent time
At the next level down, section (1)(VI)(B) is divided into:
§116. Priority
§117. Posteriority
§118. Simultaneity
§119. The Past
§120. The Present
§121. The Future
Roget's idea is that if you are thinking or writing about time, and specifically about how it goes by, you will leaf through those sections for inspiration, not to find a more pompous way of expressing something you have already written, but to refine your own idea of what it is you wanted to express.
Perhaps you are trying to say that one event followed immediately after another. You might look at “§117 posteriority (later time)” which mentions “ensue”, “consequence”, “aftermath”, and “subsequent” — not synonyms, but related aspects of similar concepts, worth more or less consideration depending on what you are trying to emphasize. §117 will also suggest common phrases like “step into the shoes of” — not a synonym by any means, but a related idea. This is probably not what you wanted in this case, but it in another it might be just the thing, and in any case it might give you a bright idea.
If nothing in section 117 seems suitable, it is right next to “§116 priority”, and you might discover that instead of saying that the second event followed immediately after the first, you would rather say that the first immediately preceded the second. Or perhaps you realize, looking at “§118 Simultaneity”, that what you really want to say is that the two events were not quite simultaneous. Or perhaps, finding your way to “§131 Earliness” and “§132 Lateness” you realize that your meaning would be more clearly expressed if you said that the second event was a little tardy, or that the first event was premature.
Looking through the index for “immediately” you will see that the index distinguishes several senses of “immediate”: are you trying to suggest instantaneity, or continuity, or haste, or promptness, or punctuality? And in this way the book helps you refine your understanding of what you were trying to say.
One can use the thesaurus for more concrete tasks. Perhaps I am trying to remember a word, but I can't quite put my finger on it. I know it it is not “coexisting”, but is something like it. I can look up “coexisting” in the index, and it will take me to “§118 Simultaneity” where I find “contemporaneous”… aha, that's what I was looking for! The really important thing about the thesaurus is this large-scale organizing principle, which puts related ideas near one another.
Note that none of this works for someone who doesn't know what the words actually mean. All that person can do with the thesaurus is to replace one wrong word with another one, more or less at random. Effective tool use requires skill and training, and careful thought.
An online version would be more convenient, but again, it wouldn't have the same stuff and I am very attached to the one I have.
My banishment of the 8th edition left a lot of space on the shelf, some of which I have filled with an anthology of the prose of Sir Thomas Browne. I think this will be healthful and inspiring for me, especially if I remember to take it up and thumb through it from time to time.
The Prose of Sir Thomas Browne
One recurring theme on this blog since the very earliest days has been the writers of the English Baroque period. In 2008 I wrote:
[Browne] is witty, and learned, and wise, and humane, and to read his books is to feel that you are in the company of this witty, learned, wise, humane man, one of the best men that the English Renaissance has to offer, and that you are profiting thereby.
His work was also a favorite of Jorge Luis Borges', in case you consider that a recommendation.
Browne has shown up here a number of times, although not so much as he should have, because I started the blog the year after I was on my big Thomas Browne kick. One reason I have put this book next to my elbow is that I hope it will spark a new Browne kick. (I wrote in 2006 “I'm sure I will return someday”, and it is long past time for that return.)
My favorite book by Browne is his Pseudodoxia Epidemica, which is a compilation of stuff that people in 1646 believed that Browne thought was probably wrong. I wrote about that in some detail in 2008 although I didn't get around to publishing it until 2020. And somehow the other three articles I was writing about this have never seen the light of day. One is about his discussion of whether John the Baptist actually ate locusts or whether they were locust beans or something else. Browne is firmly on the side of it being actual locusts, as am I. My unpublished article says:
Chester Brown's version of the gospels makes it clear that John was a crazy old bug-gobbler.
Panels from Yummy Fur #17, page 15, by Chester Brown.
Also Sir Thomas comes up in connection with whether snails have eyes in their horns — a rare example where he was wrong, and for a dumb reason:
If we concede they have two eyes, we must alse grant, they have no lesse than four… And therefore if they have two eyes, they have also four, which will be monstrous, and beyond the affirmation of any.
Browne seems to be noping out of the very idea of four-eyed snails, and therefore that they must have none at all. In a later edition of the book, he changed his mind, which is to his credit.
He had a thoughtful and well-informed opinion about whether Pythagoras forbade his followers from eating beans, supposedly because he thought they contained the souls of the dead. (Browne says the former is true, but not the latter.)
I have trouble connecting with the thinkers of the Middle Ages. Their thinking seems to me to be frightened, so overcautious, so cramped and circumscribed, I can't read it without sadness for the way that medieval Christianity strangled the human spirit for so long. But in the early Renaissance there is a flowering of a joyfully brave willingness to try to understand the world, and to follow any inquiry, no matter how extravagant or ridiculous. The whole idea of God has transformed, changed from something constricting to something empowering. The world before belonged to God, and humans were in it only grudgingly and on promise of good behavior. But when the Renaissance started, the world became a beautiful gift, in which humans had been placed to honor God by admiring and marveling at his creation.
This admiration and marvel, the willingness to follow any path to understanding, is how I want to be about knowledge and how I hope I am. Reading Browne, I always feel like he and I would have gotten along well, and that that is one of the best parts of myself.
Boccaccio's Decameron
The story of the Decameron is this: It is 1348, and Florence is devastated by Black Plague. Nothing can be done, despair is everywhere, and there are not enough left living to bury the dead. So ten young people, still healthy, decide to turn their backs on suffering and quit town. They take provisions and servants, retire to the country, and try to forget the horrors they have seen. There they spend the time feasting, walking in the gardens, playing chess, and, once a day, for ten days, they meet, choose a theme, and then each of them tells a story on the theme.
I explained this once to a friend who said “That sounds cool, when was it written?” I said “In 1348!” It is one of the two great works of classical Italian literature, the other of course being Dante. Dante is solidly medieval, hierarchical, doctrinaire, and obsessed with a God who is supposedly loving but doesn't seem to know how to show it. That was in 1308 or so, and then, only a few decades later, we have the Decameron which could not be more different. It is about people, doing people things in the real world, eating, drinking, singing, arguing, and making love. God is present, but not oppressive. He has sent a terrible plague for who knows what reason, but rather than submit to it the characters of the Decameron try to take practical steps to make the best of it.
There is a story in the Decameron for every mood, usually more than one. Some are sad, some romantic, some funny and salacious. Dioneo is exempt from following the daily theme and usually has a story that is more or less dirty.
My favorite story is probably the one about the cross-dressing English princess, or perhaps the one about how young Caterina wanted to sleep on the balcony so that she could hear the nightingale, which I find very sweet. But the funniest one is about the abbess who is called out of her cell one night to berate a nun for having her lover stay over, and who doesn't realize that in her hurry she has put her own lover's trousers on her head instead of her wimple.
I have several different Decamerons, but this copy is the Cormac Ó Cuilleanáin translation, which has made several previous appearances here:
- On the word “squillions”. Following up a chance encounter in the Oxford English Dictionary is what led me to discover the Decameron in the first place
- The phrase “two-bit huckster”
- “soup-guzzling pie-muncher”
- “soup-guzzling pie-muncher” again
There's also an unpublished blog article inviting me to look into this passage:
Messer Lotto Gualandi gave him a daughter of his, Bartolomea by name, one of the fairest and handsomest young ladies of Pisa — although most of the females from that benighted town look like tarantulas.
The J.M. Rigg translation says “spotted lizards”. This is closer to the original Italian, which is lucertole verminare, literally small wormy lizards.
I have my doubts about the desirability of living to be a thousand years old, but if I do decide to do it, one reason will certainly be that I will need the time to learn Medieval Italian and translate the Decameron.
From Frege to Gödel, edited by van Heijenoort
This is a collection of the most important papers in mathematical logic from the time of Frege (who, I have written before, was responsible for kicking the field of logic out of its medieval period into the modern world) to Gödel (who spoiled everything).
In between these van Heijenoort hits all the most important ideas, starting with Frege's explanation of Begriffsschrift, which is wacky and weird and which didn't catch on except it kind of did and it still underlies half of mathematical logic and which is the prototype for many of the symbols we still use. After this there is Russell's tragic correspondence with Frege in which he pointed out, too late, that Frege's foundational theory didn't work.
The book reprints Peano's original description of the Peano numbers, perhaps the most successful single mathematical theory of all time.
The book includes Zermelo's proof of Zermelo's theorem that every set can be well-ordered, and Ackermann's discovery of Ackermann's function, which demonstrated the not every computable function is primitive recursive.
The book has Russell on type theory and early work by Kolmogorov and Brouwer on the origin of intuitionism. (Heyting is missing.)
Van Heijenoort has come up here when I wanted to quote from Schönfinkel's paper about the SKI-calculus, Wiener's paper inventing the ordered pair, and implicitly in probably a dozen other math and logic articles here over the years.
The book is on my shelf because I refer to it pretty often, but also because I can usually find something interesting just by thumbing through it. For example, these remarks by Thoralf Skolem about the futility of deriving induction from set-theoretic foundations.
Bonus trivia: Van Heijenoort was the personal secretary of Leon Trotsky, and while he was accompanying Trotsky during the latter's exile in Mexico, he was one of Frida Kahlo's lovers.
Orbis Sensualium Pictis (English edition), Johannes Comenius
I adore this book. My heart swells with love when I think of it.
I don't have a blog article about it and there is a story behind that. In 2018 I went to a conference in Cleveland and my hotel was in a building that had formerly been the Cleveland Department of Education. It contains two big murals, one depicting “The Progress of Education”:
I planned to write a blog article about these people. It's clear who some of them are. For example, Moses is easy to recognize at lower right, because of the glowing horns, and Confucius is next to him. Some people I was familiar with once they were identified for me: the red-haired guy second from right in the back row is Friedrich Fröbel, who I knew; his “gifts” are a forerunner of the Montessori materials.
But in doing the research I got to the bearded hat-wearing dude topmost on the right side and completely fell off the bus, because that is Johann Comenius who is famous because he wrote one of the most marvelous and enchanting books I've ever read, the Orbis Pictus.
I have to resist the temptation to say too much, because Orbis Pictus derailed the article about “The Progress of Education”, it then derailed its own article which has been in progress for eight years, and if I let it it will derail this article too, because every time I pick up Orbis Pictus I forget whatever I was doing and I am lost in the pages with a happy and innocent smile on my face.
I'm going to precommit to writing only one paragraph about this incredible book. It was the first illustrated children's book published in Europe, in 1658, and it was an immediate hit, being translated from German into English the following year, then into French, Italian, and many other languages. It swept the continent because everyone loved it.
Most of the book follows this pattern: there will be an engraved illustration, depicting some aspect of ordinary human activity, such as (I open it up to a random page) “Tame Foul” (that is, “fowl”):
Items of interest in the engraving are annotated with numbers, and the facing page explains the illustration, one item at a time:
The Cock 1 (which croweth in a morning), hath a comb, 2.
In a second column to the right of this is the same text, but in Latin, so that while the reader is learning about tame fowl, they are also learning Latin:
Gallus 1. (qui manè cantat) habet Cristam, 2.
The prose is limpid, gentle, pithy, and direct. It hits the important points of interest, invites questions, and ends before anyone can get bored. There are pages on anatomy, butchery, feasting, winemaking, various principal virtues, family trees, cities, burials, ships, wells, horology, amphibians.
Now I will reluctantly put it down, rather than leaving this article unfinished as I have so many before.
The Bible (New International Version, large print)
This of course is the cornerstone of Western culture and no well-educated person can be without a knowledge of what is in it. It is full of great wisdom and great stories, and also cruelty, evil lies, and reminders that the world now is in many ways better than it was because people are better.
I would like to understand the world I live in, and there is no way to understand 21st-century America without understanding the Bible.
The NIV is not the most poetical translation, but it is clear, modern, and accurate. (I got it on the recommendation of Sterling Hanenkampf. Thanks, Sterling!) In former times I had a collection of Bibles but this is the only one that remains. I even got rid of the old King James that belonged to my mother, since office space is precious and I have had a digital copy on my computer since the early 1990s.
I find that most of my articles mentioning the Bible are unpublished for some reason. It comes up a bit in connection with Ploni Almoni, and in passing in many other places.
One of the unfinished articles is a series of notes on the theme of Jesus's admonition “Do not put the Lord your God to the test” (Matthew 4:7) and its relationship to a lot of other things like lightning rods, Christian Science (not Christian science), how Larry Wall became a computer programmer, Pikuach nefesh, and the story of the old lady who refused to evacuate from her house during a flood. It'll be epic if I ever finish it, but I probably won't.
Another incomplete one is about the incredible story of Samson and Delilah:
She asks him flat out:
[Judges 16:6] Tell me the secret of your great strength, and how you can be tied up and subdued.
Instead of just telling her to fuck off, Samson lies:
[16:7] If anyone ties me with seven fresh bowstrings that have not been dried, I'll become as weak as any other man.
The Philistines bring her bowstrings and she tries it that night, but Samson snaps the bowstrings as easily as a piece of string snaps when it comes close to a flame. …
Then it goes as before! He tells her a different lie, knowing full well that she will betray him, and she does betray him, and he makes a fool of her again! (16:11–12)
Okay, that was fun. Let's do it again! (16:13–14)
After several repetitions of this, Samson decides that being shaved, blinded and crushed will be less exasperating than listening to any more of Delilah's nagging.
I read once that the whole point of the book of Judges is that the people in it are all terrible, they are all far from the path of righteousness, and so you definitely shouldn't act like them. I don't know if that interpretation is correct, but it is certainly true that the people in it are all terrible.
The Belles Heures of Duc de Berry
This book turned up in one of my very first blog articles, on abbreviations in medieval manuscripts, although I didn't know it at the time. In my teens, on a visit to the Metropolitan Museum of Art, I picked up a print of this:
Then I carried it with me for the next forty years, eventually framing it and hanging it up, and it is hanging in my house now.
Many years after, when I was still on Twitter and Twitter was still fun, I subscribed to a daily feed from the Met, and one day they tweeted this page, or perhaps another page from the same book, stylistically similar enough that I recognized it immediately. They said where it was from: it's the Belles Heures, a “book of hours”, which tells the reader when to pray and how, and which days are sacred to which saints. Very wealthy people had super-fancy ones made from the very best materials, with illustrations by the very best craftsmen.
The Duc de Berry was so wealthy that he had more than one, as I found out when I accidentally ordered and received the Tres Riches Heures. But I got the one I wanted eventually.
The Duc de Berry book is by Millard Meiss and Elizabeth H. Beatson, and alternates beween the magnificent color plates and prose discussing each one. From the inscription on the page above I had been able to figure out that this was John the Baptist (see previous article), and the authors aren't sure who the other two people are, but they did at least tell me that John was the Duc de Berry's name-saint. (Funny how John keeps popping up, isn't it?)
More recently I had another very similar Internet revelation. I've had this framed postcard hanging up for many years:
and thanks to a recent Mastodon toot by Cam Larios, I found out that it is from the “Black Hours” of the Morgan Library.
#8?
The banishment of the very large Roget 8th edition has left enough space on the shelf for an eighth book. I took a quick look around my office to see if there was anything else that wanted to fill that space, but nothing volunteered.
(Actually I think Tristan Needham's Visual Complex Analysis might be waving to me from across the room.)
[ Addendum 20260815: For now, the space on the right is being occupied by The Crazy Ape, by Nobel prizewinner Albert Szent-Györgyi. This short book imprinted itself on me deeply when I was fourteen years old and has guided me since. Published in 1970, it is about how wars are perpetrated by the old against the young. ]
Other stuff
There are other things in the photo that should not be on this shelf and I don't know why they are:
- A packet of googly eye stickers
- Glass and ceramic coasters that I don't use because my coffee cup is always on my electric mug warmer
- A small audio speaker that might or might not work
- A boxful of 8mm-helical scan backup tape from the 1990s
- A pair of old laptop 2.5-inch hard disks that I hope to someday get the data out of
- A set of Korean playing cards
The shelf is like my brain, I guess, full of stuff, and and what's in it doesn't always make sense or go together with the other stuff.
ispell. The four em-dashes were organically cultivated
and sustainably harvested.
[Other articles in category /book] permanent link