Full Generalized Effective Reducibility
摘要
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.