a post about math: small ordinals
I think i've come up with a new (to me) conceptualization of the ordinal ε0. It goes like this:
0
Then, we create an indexed family of successor functions. There's only one of them at this point, so let's just call it S. We imagine applying S to everything we've imagined so far:
S(0)
and everything new we imagine this way:
S(S(0)), S(S(S(0))), ...
Now we've got the natural numbers, ω.
Next, we imagine a successor function for every natural number (other than 0 -- we've already got a successor function for 0): S1, S2, S3, ... And we imagine applying all of those to everything we've got so far:
S1(0), S1(1), S1(2), S1(3), ...
S2(0), S2(1), S2(2), S2(3), ...
S3(0), S3(1), S3(2), S3(3), ...
...
(ω2 many things, so far)
We've got ω2 now, but we're not even close to done, because now we have to apply all the Sn's to everything we've just now imagined, yielding another ω items for each one -- ω3, the cube! This goes on for another ω steps until we reach ωω.
... But we don't stop there! Now for each of those things we've imagined, we imagine a new successor function Sα... etc.
I thought of this when i read a casual remark about transfinite induction up to ε0, i.e., the fact that ε0 is well-ordered, being essentially the assumption that there's a well-ordering on the set of finite rooted trees. And i thought, "Well of course there is! That's not hard to come up with...", and then tried it for binary trees, since hey, if you can do it for binary trees, you can probably do it for n-ary trees.. My first thought was the subterm ordering, but that's not a well-ordering because it's not a total-ordering. If you just go with a sort of "nested lexicographic" ordering and then try to figure out how it grows (i.e., what's the successor function, how do you find the limits, etc.), you kinda get to the above.
t ::= 0 | F(t1, t2)
0 ≤ t
F(t1, t2) ≤ F(t1', t2')
iff t1 < t1'
or t1 = t1' and t2 ≤ t2'
The indexed successor functions are really just thinly-veiled binary constructors, and we turn the crank until we've got everything possible. And we need that set to be well-ordered. That's ε0.
chrisamaphone (and i thought jcreed?) suggested an alternate interpretation. During that first big stage, where we imagined ω-many successor functions S0, S1, S2, etc., and all of the ways we could apply them to 0 and everything so-imagining, in some sense what we were really imagining was just lists of natural numbers: which successor function you're applying determines which nat you're cons'ing on to the front, and when you stop at 0, that's nil.
S5(S2(S7(S12(0)))) = [5; 2; 7; 12]
Except of course at later stages, it's not just lists of natural numbers, but lists of natural numbers and things so imagined by considering them as new potential list elements, and so on, etc. If you squint the right way, you can see that it's just a definition of n-ary trees, or S-expressions with a single atom. Funny, how coming from binary trees, thinking that should be enough to get n-ary, indeed, we get n-ary trees out just by a change of view!
Incidentally, if we think of doing lexicographic induction over lists of natural numbers, it's pretty clear that we're doing induction up to ωω, since we have ωn for any n. So naturally (or *cough* ordinarily), when we generalize the type of element recursively, we should wind up at something like ω(ω(ω...)). (That's not actually so obvious to me, now that i write it out, but ah well.. perhaps it is to someone!)
It seems that the Wikipedia article on Ordinal notation hints at some similar ideas in the section "A simplified example using a pairing function", but the order they give for their binary trees is weird. I wonder if there's some reason why the nested lexicographic order i thought of is inadequate or suboptimal.
- Start by imagining 0.
- Then, repeatedly:
- Imagine an indexed family of successor functions Sα, one for each element you've imagined so far, and
- Imagine applying each of those successor functions in every way possible to every element you've imagined so far, plus all the new ones you imagine this way, until you can't imagine anything new.
- Imagine doing that until it doesn't help you imagine anything new. That's ε0.
0
Then, we create an indexed family of successor functions. There's only one of them at this point, so let's just call it S. We imagine applying S to everything we've imagined so far:
S(0)
and everything new we imagine this way:
S(S(0)), S(S(S(0))), ...
Now we've got the natural numbers, ω.
Next, we imagine a successor function for every natural number (other than 0 -- we've already got a successor function for 0): S1, S2, S3, ... And we imagine applying all of those to everything we've got so far:
S1(0), S1(1), S1(2), S1(3), ...
S2(0), S2(1), S2(2), S2(3), ...
S3(0), S3(1), S3(2), S3(3), ...
...
(ω2 many things, so far)
We've got ω2 now, but we're not even close to done, because now we have to apply all the Sn's to everything we've just now imagined, yielding another ω items for each one -- ω3, the cube! This goes on for another ω steps until we reach ωω.
... But we don't stop there! Now for each of those things we've imagined, we imagine a new successor function Sα... etc.
I thought of this when i read a casual remark about transfinite induction up to ε0, i.e., the fact that ε0 is well-ordered, being essentially the assumption that there's a well-ordering on the set of finite rooted trees. And i thought, "Well of course there is! That's not hard to come up with...", and then tried it for binary trees, since hey, if you can do it for binary trees, you can probably do it for n-ary trees.. My first thought was the subterm ordering, but that's not a well-ordering because it's not a total-ordering. If you just go with a sort of "nested lexicographic" ordering and then try to figure out how it grows (i.e., what's the successor function, how do you find the limits, etc.), you kinda get to the above.
t ::= 0 | F(t1, t2)
0 ≤ t
F(t1, t2) ≤ F(t1', t2')
iff t1 < t1'
or t1 = t1' and t2 ≤ t2'
The indexed successor functions are really just thinly-veiled binary constructors, and we turn the crank until we've got everything possible. And we need that set to be well-ordered. That's ε0.
chrisamaphone (and i thought jcreed?) suggested an alternate interpretation. During that first big stage, where we imagined ω-many successor functions S0, S1, S2, etc., and all of the ways we could apply them to 0 and everything so-imagining, in some sense what we were really imagining was just lists of natural numbers: which successor function you're applying determines which nat you're cons'ing on to the front, and when you stop at 0, that's nil.
S5(S2(S7(S12(0)))) = [5; 2; 7; 12]
Except of course at later stages, it's not just lists of natural numbers, but lists of natural numbers and things so imagined by considering them as new potential list elements, and so on, etc. If you squint the right way, you can see that it's just a definition of n-ary trees, or S-expressions with a single atom. Funny, how coming from binary trees, thinking that should be enough to get n-ary, indeed, we get n-ary trees out just by a change of view!
Incidentally, if we think of doing lexicographic induction over lists of natural numbers, it's pretty clear that we're doing induction up to ωω, since we have ωn for any n. So naturally (or *cough* ordinarily), when we generalize the type of element recursively, we should wind up at something like ω(ω(ω...)). (That's not actually so obvious to me, now that i write it out, but ah well.. perhaps it is to someone!)
It seems that the Wikipedia article on Ordinal notation hints at some similar ideas in the section "A simplified example using a pairing function", but the order they give for their binary trees is weird. I wonder if there's some reason why the nested lexicographic order i thought of is inadequate or suboptimal.