![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
sniffnoyRETRACTION January 5th 2020: Unfortunately, this proof is wrong. I have to retract this entry. Original entry follows.
EDIT September 6th: Various corrections; see below. (More slight corrections September 10th.)
(...except I'm not actually going to go into detail on the proof here.)
Welp, so, I fixed the proof from last entry. It's not as simple, and the bounds are worse, but it's still a quite simple proof of Nash-Williams's theorem, and the upper bounds we get are still much better than what Schmidt claimed.
The thing is that now, if X is our starting WPO, we need to, as part of this, look at weakly decreasing sequences in D(X). So all of this now relies on knowing about weakly decreasing sequences in WPOs. More specifically, the way the proof works is that we get a quasi-embedding from finite-image sequences in X of length less than ωγ to RevC(ωγ,D(X))*.
Obviously that's nowhere near as good as (γ x D(X))* like I originally claimed, but it's still pretty good.
Note of course that there's the problem on getting a bound on o(RevC(ωγ,D(X))). Obviously this is easier if we assume my conjecture that o(Rev0(α,X))<=o(Rev0(α,o(X))). But if we don't assume that, well, we still have a bound at least, due to
Aschenbrenner and Pong's proof showing that there's a quasi-embedding from Rev(A,B) into D(B×I(A)).
In terms of how big this is, well, let's compare:
What I claimed before--
Total case: Singly exponential in α, doubly exponential in β
General case: Singly exponential in α, triply exponential in β
What we get now if we assume my conjecture--
Total case: Doubly exponential in α, triply exponential in β
General case: Doubly exponential in α, quadruply exponential in β
What I can prove right now without the conjecture--
Total case: Doubly exponential in α, triply exponential in β
General case: Doubly exponential in α, quadruply exponential in β
ADDENDUM September 6th: You may notice that the above two are exactly the same. Earlier I messed up and thought the second was better. It's not. I mean, it is, but not in terms of how many stacked exponentials there are. However I found a newer way that really does bring that down, which is that instead of using a quasi-embedding into RevC(ωγ,D(X))*, we use a quasi-embedding into D(γ×X)*. This yields:
What I can prove right now without the conjecture, the new way--
Total case: Doubly exponential in α, triply exponential in β
General case: Doubly exponential in α, triply exponential in β
Anyway, one way or another, it's way better than what Schmidt claimed.
Unfortunately however there are some good reasons why this can't be tight in general. For countable ordinals maybe it could be? But once you get into uncountables things can very definitely drop below this. It's a mess of cofinality restrictions, basically. I think I'm basically going to put this problem down for now due to the mess...
Although, if you're willing to introduce the function that is, given an ordinal ωγ, what is the order type of the set of all δ such that there is a cofinal subset of ωγ with order type ωδ, and are willing to phrase things in terms of that, then you
can make things tighter, and who knows, maybe you can even get the exact answer that way. But I don't really expect to prove it if so. Probably get a lower bound that is roughly on the same order, but getting things
exactly is another matter.
(I asked a related question on math.stackexchange here: https://math.stackexchange.com/questions/2903636/given-an-ordinal-with-a-particular-cofinality-can-we-find-other-cofinal-subsets )
Heh, I was worried for a bit that as a proof of Nash-Williams's theorem this is circular, since it relies on weakly decreasing seqeuences in WPOs, and my initial proof that Rev(α,X) is a WPO was to invoke Nash-Williams's theorem! But of course we have Aschenbrenner & Pong's proof that doesn't rely on that. So you really could do this in a few pages I think with nothing complicated. Hooray! Just the bounds are a
mess...
EDIT September 6th: Various corrections; see below. (More slight corrections September 10th.)
(...except I'm not actually going to go into detail on the proof here.)
Welp, so, I fixed the proof from last entry. It's not as simple, and the bounds are worse, but it's still a quite simple proof of Nash-Williams's theorem, and the upper bounds we get are still much better than what Schmidt claimed.
The thing is that now, if X is our starting WPO, we need to, as part of this, look at weakly decreasing sequences in D(X). So all of this now relies on knowing about weakly decreasing sequences in WPOs. More specifically, the way the proof works is that we get a quasi-embedding from finite-image sequences in X of length less than ωγ to RevC(ωγ,D(X))*.
Obviously that's nowhere near as good as (γ x D(X))* like I originally claimed, but it's still pretty good.
Note of course that there's the problem on getting a bound on o(RevC(ωγ,D(X))). Obviously this is easier if we assume my conjecture that o(Rev0(α,X))<=o(Rev0(α,o(X))). But if we don't assume that, well, we still have a bound at least, due to
Aschenbrenner and Pong's proof showing that there's a quasi-embedding from Rev(A,B) into D(B×I(A)).
In terms of how big this is, well, let's compare:
What I claimed before--
Total case: Singly exponential in α, doubly exponential in β
General case: Singly exponential in α, triply exponential in β
What we get now if we assume my conjecture--
Total case: Doubly exponential in α, triply exponential in β
General case: Doubly exponential in α, quadruply exponential in β
What I can prove right now without the conjecture--
Total case: Doubly exponential in α, triply exponential in β
General case: Doubly exponential in α, quadruply exponential in β
ADDENDUM September 6th: You may notice that the above two are exactly the same. Earlier I messed up and thought the second was better. It's not. I mean, it is, but not in terms of how many stacked exponentials there are. However I found a newer way that really does bring that down, which is that instead of using a quasi-embedding into RevC(ωγ,D(X))*, we use a quasi-embedding into D(γ×X)*. This yields:
What I can prove right now without the conjecture, the new way--
Total case: Doubly exponential in α, triply exponential in β
General case: Doubly exponential in α, triply exponential in β
Anyway, one way or another, it's way better than what Schmidt claimed.
Unfortunately however there are some good reasons why this can't be tight in general. For countable ordinals maybe it could be? But once you get into uncountables things can very definitely drop below this. It's a mess of cofinality restrictions, basically. I think I'm basically going to put this problem down for now due to the mess...
Although, if you're willing to introduce the function that is, given an ordinal ωγ, what is the order type of the set of all δ such that there is a cofinal subset of ωγ with order type ωδ, and are willing to phrase things in terms of that, then you
can make things tighter, and who knows, maybe you can even get the exact answer that way. But I don't really expect to prove it if so. Probably get a lower bound that is roughly on the same order, but getting things
exactly is another matter.
(I asked a related question on math.stackexchange here: https://math.stackexchange.com/questions/2903636/given-an-ordinal-with-a-particular-cofinality-can-we-find-other-cofinal-subsets )
Heh, I was worried for a bit that as a proof of Nash-Williams's theorem this is circular, since it relies on weakly decreasing seqeuences in WPOs, and my initial proof that Rev(α,X) is a WPO was to invoke Nash-Williams's theorem! But of course we have Aschenbrenner & Pong's proof that doesn't rely on that. So you really could do this in a few pages I think with nothing complicated. Hooray! Just the bounds are a
mess...
