More on weird ordinal operations

[sniffnoy]

Edit: Argh missed some obvious things -- (α|k) and ((α|β))' aren't so terrible after all; I can indeed write down recursions for them. Entry now updated to reflect this.

Note: Last entry has been substantially revised since it was written.

OK. So last entry I introduced α^↓β and α^↵β, which are analogous to multichoose. I expect these have standard names, but I'm going to hold off on looking them up until I've worked out some more basics myself. We can also consider (α choose k), as well as the reverse-lexicographic version of that, which for some reason I didn't consider.

Also I want to use some different names because the above are too unwieldy for writing here in HTML. So I'll abbreviate (n choose m) as (n|m), and (n multichoose m) as ((n|m)). So I'll write ((α|β)) instead of α^↓β, and, uh, ((α|β))' instead of α^↵β; similarly (α|β) instead of (α choose β), and (α|β)' for the reverse version,. (I think α^↓β is a nicer operation than α^↵β, so the latter will get the prime. Similarly with why (α|β)' gets the prime.)

Anyway. Let's state some properties of these. Most are just copied over from last entry (with some variable names changed), but some are new:


(n|k)=(n|k)'=(n choose k) for n,k finite
(α|β)=(α|β)'=0 for β≥ω. Henceforth we will only consider (α|k) and (α|k)' when k is finite.
(α|0)=(α|0)'=1
(α|1)=(α|1)'=α
For k nonzero, (α|k) is strictly increasing in α, while (α|k)' is weakly increasing in α.
For α infinite, (α|k) is weakly increasing in k, while (α|k)' is strictly increasing in k.
(α|k) is continuous in α. (α|k)' is not continuous in α.
(α|k+l)≤(α|l)(α|k).
(α|k+l)'≤(α|k)'(α|l)'.

((n|k))=((n|k))'=(n multichoose k) for n,k finite
((α|0))=((α|0))'=1
((α|1))=((α|1))'=α
((0|α))=((0|α))'=0 for α>0
((1|α))=((1|α))'=1
((2|α))=((2|α))'=α+1
For β nonzero, ((α|β)) and ((α|β))' are strictly increasing in α.
For α nonzero, ((α|β)) is weakly increasing in β, while ((α|β))' is strictly increasing in β.
((α|β)) is continuous in α, but not β, while ((α|β))' is not continuous in either.
((α|β+γ))≤((α|γ))((α|γ))
((α|β+γ))'≤((α|β))'((α|γ))'

For k finite, (α|k)≤((α|k))≤α^k, and (α|k)'≤((α|k))'≤α^k.

For k>0, (α+1|k)=(α|k)+(α|k-1).
For k finite, ((α+1|k))=((α|k))+((α|k-1))+...+((α|0)).
More generally, ((α+1|β))=sum_{γ≤β} ((α|β-γ)), where by β-γ I mean the ordinal that is left when an initial segment of type γ is removed from β, i.e., the unique ordinal δ such that β=γ+δ. (This is a well-ordered sum so it makes sense.)

For k finite, (α|k+1)'=sum_{γ<α} (α-(γ+1)|k)', where α-(γ+1) is defined above.
((α|β+1))'=sum_{γ<α} ((α-γ|β))', where α-γ is defined above.
More generally, ((α|β))'=sum_{γ<α} sum_{δ<β} ((α-(γ+1)|δ))'.


Notice how (α|k), and ((α|β)), can be expressed recursively via the above properties; we know the case α=0, the case of α+1 is given by the analogues of Pascal's Identity, and finally, both these operations are continuous in α, handling the limit ordinal case. I do not know of a similar recursion for (α|k)' and ((α|β))'; this, along with their discontinuity, is why I consider them less nice. Although ((α|β))' does have better monotonicity/cancellation properties than ((α|β)). Still, these I have had to come up with "tricks" for computing each time.

Addendum: Oops -- now included above are ways for computing these as well (more "Pascal's Identities"); they're not nearly as bad as I thought, even though they lack continuity. Thing is that you have to primarily recurse on β (or k), rather than on α. Of course, really both involve recursing on both...

Examples up to ω, as last time, but now actually correct (I hope):

(n and k will always refer to finite numbers)

((n|k))=((n|k)) in the usual sense
((ω|k))=ω for k≥1
((n|ω))=ω^n-1+1 for n≥2
((ω|ω))=ω^ω

((n|k))'=((n|k))
((ω|k))'=ω^k
((n|ω))'=ω(n-1)+1 for n≥1
((ω|ω))'=ω^ω+1

(n|k)=(n|k) in the usual sense
(ω|k)=ω for k≥1

(n|k)'=(n|k) in the usual sense
(ω|k)'=ω^k

An example to show (α|k)' is not strictly increasing in α: (ω+1|2)'=ω². Also, ((ω+1|2))=ω²+1, which shows an example where (α|k)'<((α|k))'<α^k with α infinite, since (ω+1)²=ω²+ω+1.

For an example where (α|k)<((α|k)) with α infinite, we can consider (ω+1|2)=ω2, and ((ω+1|2))=ω2+1.


Questions I still have: Is (α|k)≤(α|k)'? For α infinite and k≥2, is this strict? Can an inequality between ((α|β)) and ((α|β))' be obtained if conditions are placed on the sizes of α and β? (Probably not.)

OK, probably about time I stop thinking about this and just look it up (i.e. ask math.SE...)

Addendum: But not before checking whether I can perhaps prove this via the above recursions, now that I have them...

-Harry