2024/11/28 by Merlin Carl, Carl, Merlin · 1 citation
Computer Science · #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO)
paper · pdf · doi:10.48550/arxiv.2411.19386
openalex publication_date 2024/11/28 · openalex created_date 2024/12/05 · openalex updated_date 2026/07/28
This paper is an extended version of our work in \citeCa2025. We extend the concept of effective reducibility between statements of set theory with ordinal Turing machines (OTMs) explored in \citeCa2018 for Π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 and various principles related to the notion of cardinality, with respect to effective reducibility. This notion of reducibility is both different from (i.e., strictly weaker than) 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 Σ2-separation. We also consider an associated variant or Weihrauch reducibility.