EDIT, 2/25, 7 PM: I'm no longer confident that the claims in this entry are correct. I've found a serious mistake in my proof. It seems like fixable, but I haven't succeeded so far.
EDIT, 2/27, 1:30 AM: THIS ENTRY AS ORIGINALLY POSTED IS FALSE. I've edited to be true, but, uh, much less interesting. False statements are in strikethrough, added statements are in bold.
So I've been thinking more about big multichoose and WPOs recently. I'll use Rev(A,B) to denote the set of order-reversing maps from A to B.
So recall, I figured out how to compute o(Rev(α,β)) (where α and β are ordinals) and showed that for any WPO X, o(Rev(α,X))≤o(Rev(α,o(X))). Or to state it another way -- which is the way the proof actually goes -- I figured out how to compute an upper bound on o(Rev(α,X)) based on α and o(X), and showed that when X is total, this upper bound is attained.
The other day I noticed that in fact, if o(X) is an (infinite) initial ordinal, then this upper bound is also attained. (Because in this case, o(X) embeds in X.) In other words, in this case, the value of o(Rev(α,X)) depends only on α and o(X), and not on any further details about X.
Could there be other values of o(X) for which this is true, I wondered? More specifically, could it be true whenever o(X) is a power of ω? (It's certainly not true when o(X) isn't a power of ω.)
It took me quite a while to find a counterexample, but eventually I did: Take α=ω, and take X to be Rado's order. In this case, o(X)=ω², and o(Rev(ω,ω²))=ωω²+2, while o(Rev(ω,X))=ωω2+2.
It should not have taken me so long to find a counterexample. A simpler counterexample is α=ω, X=ω×ω. I computed o(Rev(ω,ω×ω)) incorrectly earlier, and got ωω²+2; in fact it is ωω2+2, the same as for Rado's order. What's more, this is really easy to see, since Rev(X,Y×Z) = Rev(X,Y) × Rev(X,Z), so it's just the natural product of two copies of omega multichoose omega, which is ωω+1. Somehow I entirely failed to notice this.
So that's it -- problem solved, right? Well, not quite. Rado's order is a famous example of a WPO which is not a BPO. This leaves the question: Could the statement be true if we require that X be a BPO? Or what if instead of requiring that X be a BPO, we just insist on the weaker requirement that Rev(X,2) be a WPO, or something like that?So far, I have no counterexample to this. It's definitely not true, see above.
Unfortunately, I know very little about the theory of BPOs, so I think I am unlikely to resolve such a question (though perhaps a bit more likely if it turns out that only a weaker hypothesis is needed). But I thought this was worth putting out there.
Note, by the way, that if o(X) is a power of ω and, in addition, we have that α is finite, then the statement is true without any further hypothesis on X; hence why my counterexample above had α=ω. Note that o(X) is also as small as a counterexample can be, as o(X)=ω². (This remark is still true.)
By the way, I also tried proving the statement, by means analogous to how I proved that the bound is attained if X is total, and found that much of a proof went surprisingly well. There were three problems that arose, essentially:
1. How do we go from the case where α is a power of ω, to the case where it isn't? I was able to solve this problem.
2. How can we handle the case where α is a power of ω and o(X)=ωβ, where β is a limit ordinal? I was able to solve this problem (assuming an inductive hypothesis, of course).
3. How can we handle the case where α is a power of ω and o(X)=ωβ, where β is a successor ordinal? This turned out to be a real problem, even assuming an inductive hypothesis! And indeed, the counterexample I mentioned above has o(X)=ω².But the fact that it's just this one part of the proof that turned out to be a problem does incline me to think that it might indeed be possible to prove it with additional hypotheses on X.
Note: If X has a bottom element, everything I'm saying still works if we restrict to functions which are eventually 0. Pretty sure. And of course if α finite we can restrict to strictly decreasing functions.
EDIT: It totally works! Just using the hypothesis that Rev(X,2) is a WPO, too! This is amazing! Not only that, but there's a generalization that covers both this case and the case where X is total! (Though not also the case where o(X) is initial.) Namely, you require that Rev(X,2) be a WPO, and that X=X1+...+Xr, where each o(Xi) is a power of ω. In the case where X is total you have Cantor normal form, and in the amazing case, r=1. And once again it works if we remove the requirement that Rev(X,2) be WPO but add the requirement that α be finite.
EDIT 2: Sorry, just noticed a mistake in my proof.I think this is fixable.
-Harry
EDIT, 2/27, 1:30 AM: THIS ENTRY AS ORIGINALLY POSTED IS FALSE. I've edited to be true, but, uh, much less interesting. False statements are in strikethrough, added statements are in bold.
So I've been thinking more about big multichoose and WPOs recently. I'll use Rev(A,B) to denote the set of order-reversing maps from A to B.
So recall, I figured out how to compute o(Rev(α,β)) (where α and β are ordinals) and showed that for any WPO X, o(Rev(α,X))≤o(Rev(α,o(X))). Or to state it another way -- which is the way the proof actually goes -- I figured out how to compute an upper bound on o(Rev(α,X)) based on α and o(X), and showed that when X is total, this upper bound is attained.
The other day I noticed that in fact, if o(X) is an (infinite) initial ordinal, then this upper bound is also attained. (Because in this case, o(X) embeds in X.) In other words, in this case, the value of o(Rev(α,X)) depends only on α and o(X), and not on any further details about X.
Could there be other values of o(X) for which this is true, I wondered? More specifically, could it be true whenever o(X) is a power of ω? (It's certainly not true when o(X) isn't a power of ω.)
It took me quite a while to find a counterexample, but eventually I did: Take α=ω, and take X to be Rado's order. In this case, o(X)=ω², and o(Rev(ω,ω²))=ωω²+2, while o(Rev(ω,X))=ωω2+2.
It should not have taken me so long to find a counterexample. A simpler counterexample is α=ω, X=ω×ω. I computed o(Rev(ω,ω×ω)) incorrectly earlier, and got ωω²+2; in fact it is ωω2+2, the same as for Rado's order. What's more, this is really easy to see, since Rev(X,Y×Z) = Rev(X,Y) × Rev(X,Z), so it's just the natural product of two copies of omega multichoose omega, which is ωω+1. Somehow I entirely failed to notice this.
So that's it -- problem solved, right? Well, not quite. Rado's order is a famous example of a WPO which is not a BPO. This leaves the question: Could the statement be true if we require that X be a BPO? Or what if instead of requiring that X be a BPO, we just insist on the weaker requirement that Rev(X,2) be a WPO, or something like that?
Note, by the way, that if o(X) is a power of ω and, in addition, we have that α is finite, then the statement is true without any further hypothesis on X; hence why my counterexample above had α=ω. Note that o(X) is also as small as a counterexample can be, as o(X)=ω². (This remark is still true.)
By the way, I also tried proving the statement, by means analogous to how I proved that the bound is attained if X is total, and found that much of a proof went surprisingly well. There were three problems that arose, essentially:
1. How do we go from the case where α is a power of ω, to the case where it isn't? I was able to solve this problem.
2. How can we handle the case where α is a power of ω and o(X)=ωβ, where β is a limit ordinal? I was able to solve this problem (assuming an inductive hypothesis, of course).
3. How can we handle the case where α is a power of ω and o(X)=ωβ, where β is a successor ordinal? This turned out to be a real problem, even assuming an inductive hypothesis! And indeed, the counterexample I mentioned above has o(X)=ω².
Note: If X has a bottom element, everything I'm saying still works if we restrict to functions which are eventually 0. Pretty sure. And of course if α finite we can restrict to strictly decreasing functions.
EDIT 2: Sorry, just noticed a mistake in my proof.
-Harry
