Feb. 10th, 2016

sniffnoy: (Sonic)
I don't think this is known, but again, I'm not a logician.

So: Let's say you have a well partial order X. De Jongh and Parikh proved it has some largest extending ordinal, o(X). Moreover, they proved that o(X) is the smallest ordinal greater than any o(L), where L ranges over proper downwardly-closed subsets of X.

Question: Say X is a WPO, and you're given an ordinal α<o(X). Can you find a downward-closed subset L of X with o(L)=α?

It certainly seems like you should be able to! But you'll notice that this doesn't follow immediately from the above characterization, which merely guarantees that there's some downward-closed L with o(L)≥α. How do you get it exactly on the nose?

This problem stumped me for several days, but it turns out there's an easy answer: Iterate! Each time you iterate this, o(L) goes down; and since you're working with ordinals, well, it has to terminate. When it terminates, there's your L. I'm glad such a simple problem turned out to have such a clean solution!

(I guess I've left out a few steps here, but nothing that isn't easy to fill in. Also, since you're passing to initial segments, you don't need to phrase it in terms of o(L) going down, it's simpler without that, but that's how I originally thought of it.)


September 2017

17181920 212223
Page generated Sep. 26th, 2017 07:20 am
Powered by Dreamwidth Studios