Formalizations of The Matchstick Diagram Representation of Ordinals

Question

The matchstick diagram is a really interesting and intuitive method of representing countable ordinals. However, because of how difficult it is to graphically represent ordinals with it, I started wondering about how large the ordinals can be.

The "$\omega_1$ of matchstick diagrams", or $\omega_1^{md}$, is what I came up with.

---

Let $\mathbb{Q}_{2}:=\{\frac{1}{2^n}:n\in\mathbb{N}\}$.

For a countable limit ordinal $\alpha$, let a matchstick diagram of $\alpha$ be a function $f:\alpha\rightarrow\mathbb{Q}_{2}$ such that:

• $f(0)=1$
• $f(\beta+1)=\frac{f(\beta)}{2}$ for any $\beta<\alpha$.
• $\sum_{\beta<\alpha}f(\beta+1)$ converges to a rational number.

Let a matchstick diagram $f$ of $\alpha$ have length $z$ for some $z\in\mathbb{Q}$ iff $\sum_{\beta<\alpha}f(\beta+1)=z$.

$\omega_1^{md}$ is the smallest limit ordinal with no matchstick diagram. Equivalently, $\omega_1^{md}$ is the supremum of all ordinals with matchstick diagrams.

---

Notably, if $\alpha$ has a matchstick diagram at all, then for every $z>1$, there is a $y<z$ and a matchstick diagram of $\alpha$ of length $y$.

Also notable is the fact that $\omega$ is the only countable limit ordinal with a matchstick diagram of length $1$.

In terms of ordinals with matchstick diagrams, one can be constructed for $\zeta_0$.

Finally, $\omega_1$ has no matchstick diagram, because then it would be in bijection with $\mathbb{Q}_2$. In fact, any ordinal with a matchstick diagram is countable.

First question: Is it possible that $\omega_1^{md}=\omega_1$?

Second question: If $\omega_1^{md}$ is always countable, what is a better lower bound for it than $\zeta_0$?

Answer 1

Noah Schweber already gave a satisfactory answer, but let me make an extended comment that also gives an answer (not in the most efficient way, but in a way that is, I hope, both instructive and "constructive" to some extent), with a computer implementation of sorts.

I think that I'm somewhat responsible for the Internet popularity of the "matchstick" representation of ordinals when I uploaded this image of $\omega^2$ to Wikipedia which has, since, crept up all over the place (e.g., in Joel David Hamkins's answer in this question), even though much better images have been produced afterwards.

(Incidentally, I don't remember where I learned about this matchstick representation in the first place. I know it appears in Paul Taylor's book Practical Foundations of Mathematics, and I think that's where I got the name "matchstick" to use on Wikipedia, but I think I had seen similar diagrams much earlier… Perhaps in Gamow's One Two Three Infinity? I don't have it anymore so I can't check.)

It's easy to show that every countable ordinal is order-isomorphic to a closed subset of $\mathbb{R}$ (or a to a discrete one, if we prefer), but perhaps we want stronger constraints, like placing the matchsticks at rational or even dyadic positions and/or imposing regularity constraints like you do.

(For instance, I spent a lot of time asking myself whether it was more æsthetically appealing to place the matchsticks representing $\omega$ at exponentially decreasing intervals like $\sum_{k=1}^N\frac{1}{2^k}$, or instead as something like $1-\frac{1}{N}$ which is how one would see the rungs of an infinite ladder in perspective. I ended up settling on the former, but the latter may be intellectually more satisfactory.)

Anyway, in trying to systematize this "matchstick" representation of ordinals, I wrote this interactive page which uses JavaScript (and HTML5 canvas) to display various ordinals, which you can then click on various parts in order to zoom. I would like to say a word about how it works. The JavaScript code is readable (it's not obfuscated or minified, just choose "view source" and you can read it inside the HTML), and one of the interesting features is that I coded an ordinal representation system for ordinals up to $\zeta_0 := \varphi(2,0)$ (the smallest fixed point of $\alpha \mapsto \varphi(1,\alpha) := \varepsilon_\alpha$) and used it to systematically display names and matchstick representations of the ordinals.

Two things are missing for the program in question to answer your question: (1) you ask for the position of the matchsticks to be dyadic rationals and for the ratio of distances between two successive matchsticks to be $1/2$, and (2) you want the ordinals represented to be much greater than $\zeta_0$. Now (1) is trivially fixed, in fact, there is a variable called magicProp in the code which, if set to 0.5 (instead of the default 0.3), will give exactly the condition you ask for. As for (2), it is clear that $\zeta_0$ plays no particular rôle here: it just so happens that I was too lazy to code a representation system for much larger ordinals in JavaScript, but it can be done and plugged into the program; obviously any computer program can only deal with ordinals less than $\omega_1^{\mathrm{CK}}$, but you did not ask for a computer program.

So, to wrap it all up, here is one simple lemma which basically makes my program work and solves your question:

Lemma: Any ordinal $\alpha < \omega_1$ which is of the form $\omega^\gamma$ with $\gamma>0$ can be written as the sum of a sequence $\sum_{i<\omega} \beta_i$ where each $\beta_i < \alpha$ is itself a power of $\omega$.

Proof. If $\gamma = \gamma'+1$ is successor, write it as the sum of $\omega$ terms all equal to $\omega^{\gamma'}$. Otherwise, write $\gamma$ as limit of an increasing sequence $(\gamma_i)_{i<\omega}$, then $\omega^\gamma = \sum_{i<\omega} \omega^{\gamma_i}$ (because in fact $\sum_{i\leq n} \omega^{\gamma_i} = \omega^{\gamma_n}$), as announced.

(In my JavaScript program, this lemma is implemented by the function summingSequence, essentially with the proof I just gave.)

Now inductively define a matchstick ordinal representation inside $[0,1)$ for any $\alpha < \omega_1$ which is a power of $\omega$ as follows: if $\alpha = 1$ just use a single matchstick at position $0$; otherwise, write $\alpha = \sum_{i<\omega} \beta_i$ as given by the lemma, divide the interval $[0,1)$ into countably many consecutive subintervals, each one $p$ times the length of the previous one (for what you ask, take $p=1/2$, whereas my program uses $p=3/10$), and place a scaled copy of the matchstick representation of each $\beta_i$ inside each consecutive interval.

You asked for the interval between the two first matchsticks to be $1$, but this is immediately solved by scaling the above construction (simply note that if $p=1/2$, the interval it provides is of the form $1/2^k$ for some $k$). The case of ordinals which aren't pure powers of $\omega$ is easily handled by the Cantor normal form and I won't describe it.

Anyway, my answer is essentially the same as Joel David Hamkins's, but I wanted to emphasize that it can be more or less implemented (up to whatever ordinal you are willing to code an ordinal notation system for).

Of course, the disappointing fact is that such representations are not at all enlightening. When I first saw matchstick representations, I thought, oh, this is wonderful, if I could draw one for some difficult-to-imagine ordinal like $\varepsilon_0$ it would help me visualize $\varepsilon_0$, but of course this is not at all true, as the interactive JavaScript page shows: with the construction described above, all large ordinals look boringly the same, they are visually indistinguishable from the obvious self-similar set consisting of countably many copies of itself laid end to end (each $p$ times the size of the previous one).

Answer 2

Yes, $\omega_1^{md}$ is just $\omega_1$.

Fix some countable limit ordinal $\alpha\ge\omega^2$ (so that there are infinitely many limit ordinals $<\alpha$ - ordinals $<\omega^2$ can be handled separately). Let $l(\alpha)$ be the set of limit ordinals $<\alpha$, including $0$; since $\alpha$ is countable, fix some enumeration $\{\gamma_i: i\in\omega\}$ of $l(\alpha)$ - with $\gamma_0=0$ to address your first rule - and define $f:\alpha\rightarrow\mathbb{Q}_2$ as follows: $$\mbox{for $i, n\in\omega$, $f(\gamma_i+n)=2^{-i-n}$.}$$ (Note that this does in fact define $f$ on all of $\alpha$; in particular, $f(\gamma_i)=2^{-i-0}=2^{-i}$.)

Then $f$ is a matchstick diagram of $\alpha$, in fact one of length $2$.

Answer 3

I prefer to think of the matchstick representations a little differently than you present them. Namely, your function $f$ provides the amount to jump up by at each step, the difference between each match and the next match. I find it more natural to present it is as an order isomorphism of the ordinal into the dyadic rationals, such that at successor stages, the amount of increase is always half the immediately preceding increase; while at limits, a new step-size can be established. But it seems to be an equivalent notion.

(More images here)

One can prove that every countable ordinal has a matchstick representation by transfinite induction. If this is true for all ordinals below $\alpha$, a countable limit ordinal, then pick an increasing cofinal $\omega$ sequence $\alpha_n\to\alpha$. By induction, we have representations of each $\alpha_n$, and therefore also of the differences $\alpha_{n+1}-\alpha_n$. These can be scaled down by arbitrary factors $\frac1{2^n}$, to be made as small as desired. So we can just place the matchstick representations of these ordinals one atop the other, scaling so as to achieve any desired limit. Indeed, we can arrange inductively that all limit ordinals are mapped to dyadic rationals. This would correspond in your presentation to insisting on the (dyadic) rational convergence property not just at the top at $\alpha$, but at all ordinals along the way.

So $\omega_1^{md}=\omega_1$.

Answer 4

To add to the answers already given, we can also construct a matchstick diagram for $\omega_1$ over an uncountable nonstandard model of the Rational numbers. The following is a construction of such a nonstandard model; I will define an uncountable matchstick representation at the end if you would like to skip there.

Let $\mathbb{Z}_{\omega^1}$ be the set of formal differences of ordinals less than $\omega_1$ sharing no powers of $\omega$ in their Cantor normal forms, so if $\uparrow^\alpha$ denotes the set of exponents in the Cantor normal form of $\alpha\in O_n$ then $$\mathbb{Z}_{\omega^1}=\{\alpha-\beta:\alpha,\beta<\omega_1\wedge\uparrow^\alpha\cap\uparrow^\beta=\emptyset\}.$$ We define addition by $$(\alpha-\beta)+(\gamma-\zeta)=(\alpha+\gamma)-(\beta+\zeta),$$ using natural (not recursive) ordinal addition, negation by switching the positive and negative parts, and multiplication by $$(\alpha-\beta)\times(\gamma-\zeta)=(\alpha\gamma+\beta\zeta)-(\alpha\zeta+\beta\gamma),$$ using natural ordinal multiplication, ordered by $$\alpha-\beta\leq\gamma-\zeta\iff\alpha+\zeta\leq\gamma+\beta,$$ once again under natural addition. $\mathbb{Z}_{\omega^1}$ is now the Grothendieck group of $\omega^1$ endowed with a multiplicative structure and an ordering that makes it a discretely ordered ring.

Now, let $\mathbb{Q}_{\omega_1}$ be the field of fractions for this ring, ordered by $$\frac{\alpha-\beta}{\gamma-\zeta}\leq\frac{\alpha'-\beta'}{\gamma'-\zeta'}\iff(\alpha\gamma'+\beta\zeta')+(\alpha'\zeta+\beta'\gamma)\leq(\alpha'\gamma+\beta'\zeta)+(\alpha\zeta'+\beta\gamma')$$ (this is just the formal expansion of the expected ordering here for a field of fractions). Then $\mathbb{Q}_{\omega_1}$ is an uncountable nonstandard model of $\mathbb{Q}$ properly containing a subfield isomorphic to $\mathbb{Q}$, so we can preserve all matchstick representations for countable limit ordinals in $\mathbb{Q}_{\omega_1}$.

I'm not certain, but I believe we may equivalently consider Surreal numbers $x$ of length less than $\omega_1$ such that the sign expansion of $x$ is eventually constant at all countable limit ordinals.

EDIT: This correspondence with the surreals is not quite right, as even $\frac{1}{3}$ has a countable sign expansion $+--+-+-+-\dots$ which is not eventually constant. Perhaps it is all surreals $x$ of length less than $\omega_1$ such that the sign expansion of $x$ is eventually repeating or constant at all countable limit ordinals? I do not have a method of proof in mind yet, but after more consideration I believe that this is the correct characterization.

---

Now, for the part relevant to your question. First, we define $$\mathbb{Q}^2_{\omega_1}=\{\frac{1}{2^n\omega^m}:n<\omega\wedge m<\omega_1\}$$ as the nonstandard analogue of $\mathbb{Q}_2$, call them 'nonstandard dyadic rationals'. For $\alpha\in O_n$ such that $|\alpha|=\omega_1$, define a 'matchstick diagram' $f:\alpha\rightarrow\mathbb{Q}^2_{\omega^1}$ by $$f(0)=1,$$ $$f(\beta+1)=\frac{f(\beta)}{2},$$ $$\sum_{\beta<\gamma}\frac{f(\beta+1)}{2}\ \text{converges to a nonstandard dyadic rational for all limit ordinals}\ \gamma\leq\alpha.$$ Then I believe this should suffice for a matchstick diagram representation of uncountable ordinals in bijection with $\omega_1$ in addition to countable ones, so the answer for your question depends (from this perspective) on the size of the model of the rationals over which you build your matchstick diagrams.