sniffnoy: (Sonic)
[personal profile] sniffnoy
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.)

-Harry

July 2017

S M T W T F S
      1
2345678
9101112131415
16 171819202122
23242526272829
3031     
Page generated Jul. 26th, 2017 12:50 pm
Powered by Dreamwidth Studios