Metraipolis › archive › dc_fdb683bd62c0
CIC + EM $\vdash$ Con(ZF): the consistency of ZF in type theory with excluded middle and no choice — arXiv:2609.23143
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.23143
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-09T21:57:55.609Z
- SHA-256 of the archived text
99bf047054fe7d751883bd6671162799c52ae0a3353e3aefe00a7afee6611cb8- Stable URL of this page
https://metraipolis.com/documento/dc_fdb683bd62c0
How to cite
CIC + EM $\vdash$ Con(ZF): the consistency of ZF in type theory with excluded middle and no choice — arXiv:2609.23143 — arXiv (en), https://arxiv.org/abs/2609.23143 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fdb683bd62c0 (Metraipolis archive dc_fdb683bd62c0, sha256 99bf047054fe7d751883bd6671162799c52ae0a3353e3aefe00a7afee6611cb8)
BibTeX
@misc{dcfdb683bd62c0,
title = {CIC + EM $vdash$ Con(ZF): the consistency of ZF in type theory with excluded middle and no choice — arXiv:2609.23143},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.23143},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fdb683bd62c0; sha256 99bf047054fe7d751883bd6671162799c52ae0a3353e3aefe00a7afee6611cb8},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.23143. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
The sets-as-trees interpretation of set theory in a dependent type theory with an impredicative universe of propositions validates Zermelo set theory, and it validates Replacement if the type theory has a choice or description operator, which turns a functional relation into a function. It has been natural to expect that without such an operator the strength of the type theory drops well below that of $\mathrm{ZF}$. We show that it does not. In the type theory of Lean with two predicative universes, from excluded middle as the only assumption and with no axiom (no choice, no propositional extensionality, no quotients), we prove the consistency of $\mathrm{ZF}$, stated outright for a first-order proof system. The proof is formalized. The mechanism is the large elimination of the accessibility predicate over a type as large as the type of sets: a recursion on accessibility whose recursive calls are guarded by propositions, and whose later calls are indexed by the value of an earlier call, computes as a term any ordinal that is specified by a proposition through a well-founded tree of a certain shape. We give a rule that produces such a tree for every ordinal, unless some $V_\rho$ is already a model of $\mathrm{ZF}$; the rule does not choose a cofinal map into a limit ordinal but takes all definable ones at once. In the first case the sets-as-trees satisfy Replacement for arbitrary propositional relations. Either way $\mathrm{ZF}$ has a model. Finally, the double negation of excluded middle suffices, and what remains of it is exactly that membership is not not well-founded in the stable reading of sets; this in turn implies the double negation of Markov's principle.
Tema degli esploratori: matematica e informatica teorica (retro-catalogo arXiv: annunci del 2026-09-22 in math.LO).
Categorie arXiv: Logic (math.LO) ; Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2609.23143 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T21:44:20.584Z dalla pagina https://arxiv.org/catchup/math.LO/2026-09-22?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).