Reduction Complexities in Set Theory
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866913097713713152 |
|---|---|
| author | Carl, Merlin |
| author_facet | Carl, Merlin |
| contents | In \cite{Ca2016} and \cite{Ca2018}, we introduced a notion of effective reducibility between set-theoretical $Π_{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 $ψ$ in a reduction of $ϕ$ to $ψ$. 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 $ψ$ are required for effectivizing $ϕ$. 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2509_02766 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reduction Complexities in Set Theory Carl, Merlin Logic In \cite{Ca2016} and \cite{Ca2018}, we introduced a notion of effective reducibility between set-theoretical $Π_{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 $ψ$ in a reduction of $ϕ$ to $ψ$. 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 $ψ$ are required for effectivizing $ϕ$. 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. |
| title | Reduction Complexities in Set Theory |
| topic | Logic |
| url | https://arxiv.org/abs/2509.02766 |