In their paper "Well-partial orderings and hierarchies", D. H. J. De Jongh and Rohit Parikh showed that given any WPO X, we can define an ordinal o(X), which is the largest order type of any well-order extending X. (As in, yes, the maximum is achieved.) Then they proved some things about how to compute o(X) and computed some specific cases. In particular, o(X⨿Y)=o(X)⊕o(Y) and o(X×Y)=o(X)⊗o(Y), where ⊕ and ⊗ denote natural sum and natural product, respectively.
I'm surprised, however, that nowhere did they note the following rule:
o(X) is equal to the smallest ordinal greater than any o(L), where L is a lower set of X other than X itself.
Equivalently, if we use their notation l(x) to mean o({y: y≱x}), then one can state this as, o(X) is the smallest ordinal greater than any l(x).
I mean, this is kind of the rule you would expect if you know that o(X⨿Y)=o(X)⊕o(Y) and you know the recursion for natural addition. But it's surprising that they don't note this because it's basically just a rephrasing of what they did prove. You could say that it's an unnecessary rephrasing, but I think it's a helpful one, not to mention a clean one.
To be clear, this follows from the following facts that they proved:
1. If o(X) is a limit, it's the sup of all the l(x)
2. l(x) is always less than o(X)
3. o(X) is a successor iff X has a maximal element (call it x); in which case, o(X) is equal to o(X\{x})+1
Number 1 just is the statement above in the case where o(X) is a limit, and the case where it's a successor follows pretty easily from 2 and 3. There's also of course the case where o(X)=0, which is trivial.
So, that's the basic recursion. If you want to go computing o(X) for some WPOs but you don't know how to get an upper bound, it's an available tool (if possibly a hard to apply one).
(Also, unrelatedly, remember I said that as best as I could tell, nobody had ever studied super-Jacobsthal exponentiation before? Well, they don't give a name to it, and they don't really "study" it, but somehow, even though I'd looked at this paper a number of times before, I never noticed that De Jongh and Parikh briefly make use of it. I'd better edit my paper to mention that before I resubmit it!)
-Harry
I'm surprised, however, that nowhere did they note the following rule:
o(X) is equal to the smallest ordinal greater than any o(L), where L is a lower set of X other than X itself.
Equivalently, if we use their notation l(x) to mean o({y: y≱x}), then one can state this as, o(X) is the smallest ordinal greater than any l(x).
I mean, this is kind of the rule you would expect if you know that o(X⨿Y)=o(X)⊕o(Y) and you know the recursion for natural addition. But it's surprising that they don't note this because it's basically just a rephrasing of what they did prove. You could say that it's an unnecessary rephrasing, but I think it's a helpful one, not to mention a clean one.
To be clear, this follows from the following facts that they proved:
1. If o(X) is a limit, it's the sup of all the l(x)
2. l(x) is always less than o(X)
3. o(X) is a successor iff X has a maximal element (call it x); in which case, o(X) is equal to o(X\{x})+1
Number 1 just is the statement above in the case where o(X) is a limit, and the case where it's a successor follows pretty easily from 2 and 3. There's also of course the case where o(X)=0, which is trivial.
So, that's the basic recursion. If you want to go computing o(X) for some WPOs but you don't know how to get an upper bound, it's an available tool (if possibly a hard to apply one).
(Also, unrelatedly, remember I said that as best as I could tell, nobody had ever studied super-Jacobsthal exponentiation before? Well, they don't give a name to it, and they don't really "study" it, but somehow, even though I'd looked at this paper a number of times before, I never noticed that De Jongh and Parikh briefly make use of it. I'd better edit my paper to mention that before I resubmit it!)
-Harry
