Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Consider the following theorem of Koepke-Koerwien-Siders:

"A set x of ordinals is ordinal computable [either by ordinal Turing machines or ordinal register machines--my comment] if and only if it is an element of the constructible universe L"

Consider also the following theorem from Kunen's book SET THEORY: An Introduction to Independence Proofs:

Theorem 3.5 (Kunen, 1980, pg 171): If M is any transitive proper class model of ZF-P [P is the power set axiom--my comment], L=L^(M) is a proper subset of M.

Kunen uses this theorem to prove (assuming M=HOD) that L is a proper subset of HOD.

Assuming V=HOD, are there sets of ordinals definable in HOD that are not ORM (Ordinal Register Machine--respectively Ordinal Turing Machine) computable? I ask the question because HOD as does OD, relies on definability from a finite set of ordinal parameters. It should be noted that in problem 22 of Kunen (1980) Chapter 6, one is asked to prove that for L^(n) (that is, L defined in n'th-order logic, n>=2) that L^(n)=HOD). Assuming that the problem is not ill-formed, it can be deemed a theorem. This theorem might be deemed a mitigating factor.

share|improve this question
Kunen does not use $\subset$ to mean "proper subset". –  François G. Dorais Jan 20 '13 at 14:18
I'm not sure I understand what the question is, but $0^\#$, if it exists, is a hereditarily ordinal-definable set of ordinals (indeed, a $\Pi_1$-definable set of integers) that isn't constructible (hence not ordinal machine computable). –  Gro-Tsen Jan 20 '13 at 15:05
Theorem 3.5 as quoted is wrong, but Francois's comment explains at least part of what's wrong with it. L is a subclass of any such M, but not necessarily a proper subclass. In particular, M could be L. –  Andreas Blass Jan 20 '13 at 18:44
The next sentence after Theorem 3.5 in the question is also wrong for the same reason. L is a subclass of HOD, but not necessarily a proper subclass. –  Andreas Blass Jan 20 '13 at 18:46
Thomas, all of these questions have well-known answers. I think you just need to do a little more careful research. In addition to Kunen, check out what Jech (Set Theory) and Kanamori (Higher Infinite) say on L, HOD, and other inner models. –  François G. Dorais Jan 21 '13 at 18:41
show 6 more comments

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.