pith. sign in

arxiv: 2509.02766 · v6 · submitted 2025-09-02 · 🧮 math.LO

Reduction Complexities in Set Theory

Merlin Carl This is my paper

Pith reviewed 2026-05-18 19:34 UTC · model grok-4.3

classification 🧮 math.LO
keywords set theoryeffective reducibilityWeihrauch reducibilityordinal cardinalityZFC independencequantifier complexitycomputational complexity
0
0 comments X

The pith

The minimal number of calls to an effectivizer needed to reduce set-theoretic statements is often independent of ZFC.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

This paper refines the analysis of computational complexity for set-theoretical statements by introducing an interpolation between effective reducibility and Weihrauch reducibility based on the exact number of calls allowed to an effectivizer. It applies this to make precise questions such as how many ordinals must be checked to compute the cardinality of a given ordinal. The work shows that answers to many such questions are independent of ZFC. A reader would care because this links computational models in set theory to questions that cannot be resolved by standard axioms alone.

Core claim

The central claim is that by measuring the number of calls required to an effectivizer for one statement to reduce another statement of arbitrary quantifier complexity, one obtains a precise measure of reduction complexity. For example, this formalizes and partially answers questions about the number of ordinals to check for being cardinals when computing the cardinality of a given ordinal. Many of the resulting minimal numbers turn out to be independent of ZFC.

What carries the argument

The number of allowed calls to an effectivizer in reductions between set-theoretical statements of arbitrary quantifier complexity, interpolating between effective and Weihrauch reducibility.

If this is right

  • Questions about the computational resources needed for set-theoretic tasks like ordinal cardinality can be formalized precisely.
  • Many minimal call counts for these tasks cannot be determined within ZFC.
  • The framework extends to statements with infinite quantifier complexity.
  • It provides a hierarchy of reduction complexities based on call numbers.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • This method could be applied to other problems in set theory to find more independence results in computational terms.
  • It may reveal connections between the strength of set-theoretic axioms and the complexity of reductions.
  • Extensions might include varying parameters beyond call counts in the interpolation.

Load-bearing premise

The interpolation between effective reducibility and Weihrauch reducibility via the number of allowed calls to an effectivizer faithfully captures the intended computational complexity without requiring additional unstated set-theoretic assumptions in the definitions.

What would settle it

A proof inside ZFC that fixes the exact minimal number of calls required to compute the cardinality of an arbitrary ordinal would show that the independence result fails for that particular task.

read the original abstract

In \cite{Ca2016} and \cite{Ca2018}, we introduced a notion of effective reducibility between set-theoretical $\Pi_{2}$-statements; in \cite{Ca2025}, this was extended to statements of arbitrary (potentially even infinite) quantifier complexity. We also considered a corresponding notion of Weihrauch reducibility, which allows only one call to the effectivizer of $\psi$ in a reduction of $\phi$ to $\psi$. In Stammes \cite{StammesMaster}, a considerably refined analysis through interpolating between these two notions was proposed, where one asks how many calls to an effectivizer for $\psi$ are required for effectivizing $\phi$. This allows us to make formally precise questions such as ``how many ordinals does one need to check for being cardinals in order to compute the cardinality of a given ordinal?'' and (partially) answer many of them. Many of these anwers turn out to be independent of ZFC.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 3 minor

Summary. The manuscript refines the author's prior notions of effective reducibility (arbitrary calls to an effectivizer) and Weihrauch reducibility (single call) for set-theoretic statements of arbitrary quantifier complexity by interpolating via the minimal number of calls required. It formalizes questions such as the number of ordinals that must be checked for being cardinals to compute the cardinality of a given ordinal, and establishes that many such minimal call counts are independent of ZFC, using explicit constructions in ZF and standard forcing or inner-model techniques for the independence arguments.

Significance. If the independence results hold, the work supplies a precise resource-sensitive measure of complexity for set-theoretic computations that lies strictly between effective and Weihrauch reducibility. The approach yields falsifiable predictions about call numbers and employs reproducible, well-defined constructions that remain valid in ZF, which strengthens the link between computability and set theory.

major comments (1)
  1. §4 (ordinal cardinality example): the independence claim that the minimal call count for computing |α| can be any finite number or infinite is load-bearing for the central thesis; the forcing construction used to separate the values should be stated explicitly with the poset and the generic filter properties that witness the different call numbers.
minor comments (3)
  1. Abstract: 'anwers' is a typographical error and should read 'answers'.
  2. §2.3: the notation for the interpolated reducibility relation could be introduced with an explicit symbol (e.g., ≤_n) rather than relying solely on prose description, to improve readability when comparing different call bounds.
  3. References: the entry for StammesMaster should include the year and institution to allow readers to locate the cited master thesis.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading of the manuscript and for the positive overall assessment. We address the single major comment below and will revise the text accordingly to improve clarity and explicitness.

read point-by-point responses

  1. Referee: §4 (ordinal cardinality example): the independence claim that the minimal call count for computing |α| can be any finite number or infinite is load-bearing for the central thesis; the forcing construction used to separate the values should be stated explicitly with the poset and the generic filter properties that witness the different call numbers.

    Authors: We agree that an explicit description of the forcing construction will make the independence results easier to verify. In the revised version we will expand the relevant paragraphs in §4 to name the poset (a product of Cohen or Levy collapses chosen to control the cardinal-checking oracle calls), state its key properties (properness, preservation of cardinals below a fixed bound, and the density of conditions forcing additional ordinal checks), and describe the generic filter's action in ensuring that the minimal number of calls required equals any prescribed finite or infinite value. These details are already implicit in the standard forcing techniques cited, but spelling them out will strengthen the exposition without altering the proofs. revision: yes

Circularity Check

0 steps flagged

Minor self-citation in foundational definitions; core independence results remain independent

full rationale

The manuscript extends effective reducibility and Weihrauch reducibility from the author's prior works (Ca2016, Ca2018, Ca2025) and incorporates a call-count interpolation from Stammes. These citations supply the base notions, but the new formalization of reduction complexity via minimal effectivizer calls, the specific set-theoretic questions (e.g., ordinal cardinality checks), and the independence proofs via forcing and inner models are defined and executed directly in the present paper without reducing any central claim to a prior fitted quantity or self-referential loop. No self-definitional, fitted-input, or ansatz-smuggling patterns appear in the derivation chain.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The paper relies on standard background from set theory and computability; no free parameters or invented entities are visible in the abstract.

axioms (1)
  • domain assumption ZFC set theory axioms
    Independence results are stated relative to ZFC.

pith-pipeline@v0.9.0 · 5692 in / 1203 out tokens · 44286 ms · 2026-05-18T19:34:45.971203+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages · 2 internal anchors

  1. [1]

    M. Carl. Generalized Effective Reducibility. In: A. Beckmann et al. (eds.) Pursuit of the Universal. 12th Conference on Computability in Europe. (2016)

    work page 2016

  2. [2]

    M. Carl. Effectivity and Reducibility with Ordinal Turing Machines. Computability, vol. 10(4) (2021)

    work page 2021

  3. [3]

    M. Carl. Full Generalized Effective Reducibility. CiE 2025 Proceedings. In: A. Beck- mann et al. (eds.) Crossroads of Computability and Logic: Insights, Inspirations, and Innovations. 21st Conference on Computability in Europe. Proceedings. (2025)

    work page 2025

  4. [4]

    M. Carl. Effective Reducibility for Statements of Arbitrary Quantifier Complexity with Ordinal Turing Machines. PreprintarXiv:2411.19386(2025)

    work page internal anchor Pith review Pith/arXiv arXiv 2025

  5. [5]

    M. Carl. Ordinal Computability. An Introduction to Infinitary Machines. De Gruyter Berlin Boston (2019)

    work page 2019

  6. [6]

    Gasarch, G

    W. Gasarch, G. Martin. Bounded Queries in Recursion Theory. Progress in Com- puter Science and Applied Logic, vol. 16. Birkh¨ auser Boston Basel (1998)

    work page 1998

  7. [7]

    W. Gasarch. Bounded queries in recursion theory: a survey. Proceedings of the Sixth Annual Structure in Complexity Theory Conference. (1991)https://doi.org/10. 1109/SCT.1991.160245

    work page arXiv 1991

  8. [8]

    Gasarch, F

    W. Gasarch, F. Stephan. A Techniques Oriented Survey of Bounded Queries. In: S. Cooper, J. Truss (eds.). Models and Computability. London Mathematical Society Lecture Note Series. Cambridge University Press (1999)

    work page 1999

  9. [9]

    Joel David Hamkins (https://mathoverflow.net/users/1946/ joel-david-hamkins), Complexity of definable global choice functions, URL (version: 2024-06-08):https://mathoverflow.net/q/472862

    work page 1946

  10. [10]

    W. Hodges. On the effectivity of some field constructions. Proceedings of the Lon- don Mathematical Society, vol. s3-32(1) (1976)

    work page 1976

  11. [11]

    T. Jech. Set Theory. Third Millenium Edition. Springer Berlin Heidelberg New York (2003)

    work page 2003

  12. [12]

    P. Koepke. Turing Computations on Ordinals. The Bulletin of Symbolic Logic. vol. 11(3)

    work page

  13. [13]

    K. Kunen. Set Theory. An Introduction to Independence Proofs. Elsevier Amster- dam (1980)

    work page 1980

  14. [14]

    Passmann

    R. Passmann. The first-order logic of CZF is intuitionistic first-order logic. The Journal of Symbolic Logic, vol. 89(1) (2022)

    work page 2022

  15. [15]

    J. Reitz. The Ground Axiom. PhD Thesis, City University of New York (2024) https://arxiv.org/pdf/math/0609064

    work page internal anchor Pith review Pith/arXiv arXiv 2024