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$?
Best Answer
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
magicPropin the code which, if set to0.5(instead of the default0.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).