Oct. 9th, 2015

sniffnoy: (SMPTE)
EDIT Oct 12: Corrected a mistake in question 0, and also expanded it slightly. Also pretty sure I've proved question 1 and therefore 2 and 3; see note below.

So, OK, I know how to compute big multichoose now. But I was going through some old notes of mine and I found a few questions about it I still hadn't answered. Two of them, I suppose, could potentially be solved based on my computation rule, but that seems like it would be quite ugly. I still don't have a resolution to these questions; I'm going to state them here.

Notation: I'll write ((α multichoose β)) for my "big multichoose" operation. Given posets A and B, I'll write Rev(A,B) for the set of order-reversing maps from A to B, considered as a poset. Now, all orders considered here will be WPOs; in general, given WPOs A and B, the order Rev(A,B) is not necessarily a WPO, but I'll only consider cases where it is. In particular, for any ordinal α and a WPO B, Rev(α,B) is a WPO. Remember, ((α multichoose β)) is by definition o(Rev(β,α)).

So suppose A, B, and Rev(A,B) are WPOs; then it's easy to see that o(Rev(A,B))≥o(Rev(o(A),B)). Adding more relations to A just removes points from Rev(A,B), so o(Rev(A,B)) goes down.

However, it's less clear what happens if we instead take o(Rev(A,o(B))) instead of o(Rev(o(A),B)). Adding more relations to B adds points to Rev(A,B), which would appear to make o(Rev(A,B)) go up; however, it also adds relations to Rev(A,B), which would appear to make o(Rev(A,B)) go down.

So naively, it could go either up or down. However, I have never once seen it go down! I've only see it go up or stay the same.

So, question 0: If A, B, Rev(A,B), and Rev(A,o(B)) are all WPOs, does one have o(Rev(A,B))≤o(Rev(A,o(B))? (And if A, B, and Rev(A,o(B)) are all WPOs, does this imply that Rev(A,B) is too?)

And in case that's false, the more specific question 1: If α is an ordinal and B is a WPO, does one have o(Rev(α,B))≤o(Rev(α,o(B)))?

Note that if this is true, it cannot be simply because o(B) is an extension of B! One can find other extensions that make this false. For instance, suppose α=2, and B is the disjoint union of ω and 1; one may extent B to an order of type ω, but this will cause o(Rev(α,B)) to go down.

So far, I've been able to prove this in the case when α is finite, by making use of my computation rule. (I think attempting to prove this without making use of my computation rule will be impractical.)

The above two questions don't purely deal with big multichoose and thus can't be settled by my computation rules. The next two questions potentially could.

With Rev, one has the obvious isomorphisms Rev(A⨿B,C)=Rev(A,C)×Rev(B,C), Rev(A,B×C)=Rev(A,B)×Rev(A,C), and Rev(A,Rev(B,C))=Rev(A×B,C).

If one combines the first of these isomorphisms with the inequality o(Rev(A,B))≥o(Rev(o(A),B)) mentioned above, one obtains the inequality

((α multichoose β⊕γ)) ≤ ((α multichoose β)) ⊗ ((α multichoose γ)).

However, attempting to turn the other two isomorphisms into inequalities would require the use of the inequality in question 1. So this gives rise to questions 2 and 3 -- keep in mind that a positive answer to question 1 (or, y'know, question 0) would settle both of these in the affirmative:

Question 2: Is ((α⊗β multichoose γ)) ≥ ((α multichoose γ)) ⊗ ((β multichoose γ))?

Question 3: Is ((α multichoose β⊗γ)) ≤ (( ((α multichoose β)) multichoose γ))?

Because I can currently prove question 1 in the case where α is finite, I can prove both of these in the case where γ is finite.

EDIT Oct 12: I'm pretty sure I have now proven question 1 in general, therby proving questions 2 and 3. Unfortunately the proof is not simple. As for question 0... well, it's pretty obviously true when A and B are both finite. Other than that I haven't gotten very far, but I can't find a counterexample. If it is indeed false, perhaps it's worth asking with the assumptions that A and B are both BPOs instead of merely WPOs. (We can call that question 1/2.)

Both these could be potentially answered by purely computational means, though it would be somewhat unsatisfying. Right now, though, if this is true, I have not done even that. Although I can at least verify that they're true when the inputs are powers of ω; that case, at least, is straightforward computationally...


October 2017

8910111213 14
Page generated Oct. 24th, 2017 12:12 am
Powered by Dreamwidth Studios