We extend the concept of effective reducibility between statements of set theory with ordinal Turing machines (OTMs) explored in [2] for \(\varPi _{2}\) -statements to statements of arbitrary quantifier complexity in prenex normal form and use this to compare various fundamental set-theoretical principles, including the power set axiom, the separation scheme, the collection scheme and the replacement scheme, with respect to effective reducibility. This notion of reducibility is both different from classical truth and from the OTM-realizability of the corresponding implications. Along the way, we obtain a computational characterization of HOD as the class of sets that are OTM-computable relative to every effectivizer of \(\varSigma _{2}\) -separation.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Full Generalized Effective Reducibility

  • Merlin Carl

摘要

We extend the concept of effective reducibility between statements of set theory with ordinal Turing machines (OTMs) explored in [2] for \(\varPi _{2}\) -statements to statements of arbitrary quantifier complexity in prenex normal form and use this to compare various fundamental set-theoretical principles, including the power set axiom, the separation scheme, the collection scheme and the replacement scheme, with respect to effective reducibility. This notion of reducibility is both different from classical truth and from the OTM-realizability of the corresponding implications. Along the way, we obtain a computational characterization of HOD as the class of sets that are OTM-computable relative to every effectivizer of \(\varSigma _{2}\) -separation.