A more specific statement of the result from the paper is:
Lemma 1 Suppose that the theory T is omega consistent with repsect to some formula P(y) and that T has a finitely axiomatizable subtheory S satisfying
(i) Each recursive relation is definable in S
(ii) For every m = 0, 1, ….,
)
Then each subtheory of T is of complete degree
Also:
Corallary 6 Let T be the theory ZF or any extension of ZF. If T is omega consistent with respect to the formula yinomega then the degrees of subtheories of T are exactly the complete degrees.
ETA: Is this what you were referring to in:
Is there a formal system (not talking about the standard integers, I guess)
I’m not sure, I don’t see a related reply/comment. Either way, I’m not 100% sure I’m following all of the arguments in the papers, but it appears that the theories that are of intermediate degree are necessarily very unusual and complicated, and I’m not sure how feasible it would be to construct one explicitly.
ETA2: I found yet another interesting paper that seems to state that finding a natural example of a problem of intermediate degree is a long standing open problem.
A more specific statement of the result from the paper is:
Also:
ETA: Is this what you were referring to in:
I’m not sure, I don’t see a related reply/comment. Either way, I’m not 100% sure I’m following all of the arguments in the papers, but it appears that the theories that are of intermediate degree are necessarily very unusual and complicated, and I’m not sure how feasible it would be to construct one explicitly.
ETA2: I found yet another interesting paper that seems to state that finding a natural example of a problem of intermediate degree is a long standing open problem.
Thanks again for taking the time to parse all that!
Yeah, kind of. I didn’t know the results but for some reason felt that subtheories of arithmetic shouldn’t lead to intermediate degrees.
No problem! It’s an interesting topic with lots of surrounding results that are somewhat surprising (at least to me).