Skip to content
DraconiticResearch
Search Sources API
189,280 studies31 sourcesUpdated 43 min ago
PreprintarXiv licencearXiv

The pattern of consistency strength for membership in a computably enumerable set

  • Joel David Hamkins
  • Atticus Stonestrom
Open at sourcePDFDOICite

Abstract

Every computable preorder relation on the natural numbers is the order of consistency strength for the membership assertions "n∈ A" in some computably enumerable set A. Moreover, for every computably enumerable list of theories T0,T1,T2,…, each extending PA, there is a computably enumerable set A such that each Tn is equiconsistent over PA with the membership assertion n∈ A. And similarly for both results when using instead the nonmembership assertions n∉ A.

Related

  1. A Computably Enumerable tt-Degree Without Computably Enumerable Irreducible m-Degrees
    Patrizio Cintioli
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  2. Order-preserving maps of the Turing degrees: regularity and consistency strength
    Liang Yu
    arXivPreprintCC0Full textLogic & foundationsarXiv
  3. A Reflection Calculus for Bar Induction and the Linearity of Consistency Strength Ordering
    Fedor Pakhomov, Vlad Lazar
    arXivPreprintarXiv licenceFull textLogic & foundationsarXiv
  4. A non-recursively enumerable set W⊆N, where N\W is recursively enumerable and the predicate n∈W expresses a fundamental property of n
    Apoloniusz Tyszka
    HALPreprintCC BY-NC-ND 4.0Full textAlgebra & number theoryLogic & foundationsHAL
  5. Controllability of polynomial systems is undecidable and not recursively enumerable
    Jun Liu, Ivan O. Shevchenko
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{hamkins2026pattern,
  title = {{The pattern of consistency strength for membership in a computably enumerable set}},
  author = {Joel David Hamkins and Atticus Stonestrom},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.24919},
  eprint = {2610.24919},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.24919},
}
RIS
TY  - UNPB
TI  - The pattern of consistency strength for membership in a computably enumerable set
AU  - Joel David Hamkins
AU  - Atticus Stonestrom
PY  - 2026
DA  - 2026/10/17
PB  - arXiv
DO  - 10.48550/arxiv.2610.24919
UR  - https://arxiv.org/abs/2610.24919
AB  - Every computable preorder relation on the natural numbers is the order of consistency strength for the membership assertions "n∈ A" in some computably enumerable set A. Moreover, for every computably enumerable list of theories T_0,T_1,T_2,…, each extending PA, there is a computably enumerable set A such that each T_n is equiconsistent over PA with the membership assertion n∈ A. And similarly for both results when using instead the nonmembership assertions n∉ A.
ER  -