sniffnoy | Back to ordinals, briefly

OK. This is, I think, going to be the last thing I do with well partial orders from quite some time. I haven't had a lot of time for math recently, I know; but when I do have time, it is now, I think, finally time for me to get back to integer complexity and addition chains.

But so let me tell you about what I was just doing with WPOs the past few days.

So: You may recall I had to retract this entry. The proof was wrong. I don't think it's fixable. But, that doesn't mean it's impossible to salvage anything from it! And I thought I could salvage something from it: I thought I could prove a bound for sequences of length less than ωⁿ (for any n<ω). This bound would not be triply-exponential in o(X), but rather would be a tower of n+1 exponentials.

Now obviously this is way more limited than what I originally claimed, and is a much worse bound there too. Still, it's something.

I spent a fair bit of time trying to make this salvage work, but I couldn't make the details work. (Aside obviously from in the ω² case, for which my original proof did in fact work.) Finally, I went back to the original 1959 paper by Erdös and Rado, where they proved this limited case without giving a bound (this was before Nash-Williams proved the general case). And what do you know, it had what I needed!

Erdös and Rado didn't give a bound on the type of the result -- probably because the notion of "type" was still 11 years in the future! But their proof is very proof-minable. That said, a straight proof-mine would yield a tower of 2n exponentials, not n+1. Fortunately, it wasn't too hard to take what they did, and combine it with what I was trying to do, and make the proof work.

So yay! It's not nearly what I originally claimed or was hoping for, but it's something!

But I think I've gone about as far as I can with WPOs for now. So... time to finally return to project #1! (I know, I know, I've said that before. But...)

-Harry