Last edit: OOPS! Some computations below are wrong. I've fixed them, made some strikeouts to some other things, etc.; any further corrections will be put in a new entry.
Edit next day: Strict increasingness in "base" added; continuity question answered. Also note about finite exponent.
OOPS next day: Some of the computations below were incorrect. Fixed now.
Also: New question at bottom. Adding notes about (α choose n).
Another possible OOPS: Previously I asserted α↓n=α↵n for n finite, but rethinking it's not clear to me that this is true. Will have to think more on this.
I assume these have been studied before but I've no idea what they're called. I suppose I should ask MathUnderflow.
Julian posed the following problem the other day: Say we have well-ordered sets α and β, and consider the set of all weakly decreasing functions from β to α. Order them lexicographically; is this a well-order?
The answer, unsurprisingly, is yes; this isn't too hard (though it took him and Jordan and I like an hour to figure it out), so I'll not give a proof here. Actually Julian was really only interested in the case α=β=ω, but he figured it ought to be true in general.
Furthermore, if we order reverse-lexicographically, this is a well-order as well. (This one is easier to prove.)
I'll denote the first of these by α↓β, and the latter by α↵β since I have no idea what they're normally called. (Actually I'm using \searrow and \swarrow, respectively, but those don't exist in HTML unless I want to look up the Unicode code points.)
Anyway. The point is, Julian and Ashley were looking at a certain decreasing sequence in ω↓ω, wanted to be sure it terminated, hence the question. But what's noteworthy is that the sequence was only well-defined because, for 1≤n<ω, ω↓n=ω↵n=ω, which is lower than I would have expected.
It's easy to compute in the finite case; m↓n=m↵=(m multichoose n). I'd call the operation (α multichoose β) except there's two of them. It's tempting to define (α choose β) by restricting to strictly decreasing functions, but of course this is 0 for any β≥ω! Still, it's perhaps worth thinking about for n finite...
To state some trivialities, obviously (α choose 0)=α↓0=α↵0=1 for all α, (α choose 1)=α↓1=α↵1=α for all α, 0↓α=0↵α=0 for α>0, and 1↓α=1↵α=1 for all α. And α↓β and α↵β are strictly increasing in α (for β>0), and weakly increasing in β (for α>0). While (α choose n) is strictly increasing in α for n>0, and weakly increasing in n for α infinite. Also α↓(β+γ)≤α↓γα↓β, and α↵(β+γ)≤α↵βα↵γ.And of course (α choose n)≤α↓n=α↵n≤αn for n finite.
Since ω↓ω was the original motivation, I've computed α↓β and α↵β for α,β≤ω. At least, I think I've computed these correctly -- other people may want to check. In the below, n and m will always be finite. I'm not listing special cases which are obvious and which would be trouble to list.
m↓n=(m multichoose n)
ω↓n=ω for n≥1
m↓ω=ωm-1+1 for m≥2
ω↓ω=ωω
m↵n=(m multichoose n)
ω↵n=ωn
m↵ω=ω(m-1)+1 for m≥1
ω↵ω=ωω+1
One thing worth noting: Assuming my computations above are correct, α↵β is not continuous in either variable. α↓β, however, while discontinuous in β, might be continuous in α. I would expect not, but it is consistent with the above computations.
Update next day: Yeah, it's continuous in α; this is actually pretty easy, though I personally still find it a little surprising. (α choose n) is continuous in α as well.
New question: Is α↵β≤α↓β? I have no idea why this might be so, but it holds in all examples so far...
Answer added in last edit: No, I miscomputed ω↵n; the correct value shows this is false.
So that's kind of neat. I don't know, anyone know anything about these operations? (Or have any corrections?) I guess I should probably ask Math.SE and find out what they're actually called.
Tangentially, I think I'll also try asking there if anyone knows anything about this Jacobsthal natural power operation Wikipedia mentions...
-Harry
Edit next day: Strict increasingness in "base" added; continuity question answered. Also note about finite exponent.
OOPS next day: Some of the computations below were incorrect. Fixed now.
Also: New question at bottom. Adding notes about (α choose n).
Another possible OOPS: Previously I asserted α↓n=α↵n for n finite, but rethinking it's not clear to me that this is true. Will have to think more on this.
I assume these have been studied before but I've no idea what they're called. I suppose I should ask MathUnderflow.
Julian posed the following problem the other day: Say we have well-ordered sets α and β, and consider the set of all weakly decreasing functions from β to α. Order them lexicographically; is this a well-order?
The answer, unsurprisingly, is yes; this isn't too hard (though it took him and Jordan and I like an hour to figure it out), so I'll not give a proof here. Actually Julian was really only interested in the case α=β=ω, but he figured it ought to be true in general.
Furthermore, if we order reverse-lexicographically, this is a well-order as well. (This one is easier to prove.)
I'll denote the first of these by α↓β, and the latter by α↵β since I have no idea what they're normally called. (Actually I'm using \searrow and \swarrow, respectively, but those don't exist in HTML unless I want to look up the Unicode code points.)
Anyway. The point is, Julian and Ashley were looking at a certain decreasing sequence in ω↓ω, wanted to be sure it terminated, hence the question. But what's noteworthy is that the sequence was only well-defined because, for 1≤n<ω, ω↓n=ω↵n=ω, which is lower than I would have expected.
It's easy to compute in the finite case; m↓n=m↵=(m multichoose n). I'd call the operation (α multichoose β) except there's two of them. It's tempting to define (α choose β) by restricting to strictly decreasing functions, but of course this is 0 for any β≥ω! Still, it's perhaps worth thinking about for n finite...
To state some trivialities, obviously (α choose 0)=α↓0=α↵0=1 for all α, (α choose 1)=α↓1=α↵1=α for all α, 0↓α=0↵α=0 for α>0, and 1↓α=1↵α=1 for all α. And α↓β and α↵β are strictly increasing in α (for β>0), and weakly increasing in β (for α>0). While (α choose n) is strictly increasing in α for n>0, and weakly increasing in n for α infinite. Also α↓(β+γ)≤α↓γα↓β, and α↵(β+γ)≤α↵βα↵γ.
Since ω↓ω was the original motivation, I've computed α↓β and α↵β for α,β≤ω. At least, I think I've computed these correctly -- other people may want to check. In the below, n and m will always be finite. I'm not listing special cases which are obvious and which would be trouble to list.
m↓n=(m multichoose n)
ω↓n=ω for n≥1
m↓ω=ωm-1+1 for m≥2
ω↓ω=ωω
m↵n=(m multichoose n)
ω↵n=ωn
m↵ω=ω(m-1)+1 for m≥1
ω↵ω=ωω+1
One thing worth noting: Assuming my computations above are correct, α↵β is not continuous in either variable. α↓β, however, while discontinuous in β, might be continuous in α. I would expect not, but it is consistent with the above computations.
Update next day: Yeah, it's continuous in α; this is actually pretty easy, though I personally still find it a little surprising. (α choose n) is continuous in α as well.
New question: Is α↵β≤α↓β? I have no idea why this might be so, but it holds in all examples so far...
Answer added in last edit: No, I miscomputed ω↵n; the correct value shows this is false.
So that's kind of neat. I don't know, anyone know anything about these operations? (Or have any corrections?) I guess I should probably ask Math.SE and find out what they're actually called.
Tangentially, I think I'll also try asking there if anyone knows anything about this Jacobsthal natural power operation Wikipedia mentions...
-Harry
