END-EXTENSIONS OF MODELS OF WEAK ARITHMETIC FROM COMPLEXITY-THEORETIC CONTAINMENTS

DOI10.1017/jsl.2015.53zbMath1376.03041arXiv1411.6864OpenAlexW2963100062MaRDI QIDQ2976370

Leszek Aleksander Kołodziejczyk

Publication date: 28 April 2017

Published in: The Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1411.6864

zbMATH Keywords

collection schemecomplexity classend-extensions

Mathematics Subject Classification ID

Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Models of arithmetic and set theory (03C62) Proof theory and constructive mathematics (03F99)

Related Items

Restricted polynomial induction versus parameter free ordinary induction, Restricted polynomial induction versus ordinary induction, Unifying the model theory of first-order and second-order arithmetic via \(\mathrm{WKL}_0^\ast\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The strength of sharply bounded induction requires MSP
• Bounded arithmetic and the polynomial hierarchy
• A proof-theoretic analysis of collection
• Computing and combinatorics. 5th annual international conference. COCOON '99, Tokyo, Japan, July 26--28, 1999. Proceedings
• Binary models generated by their tally part
• End extensions of models of linearly bounded arithmetic
• On axiom schemes for \(T\)-provably \(\Delta_1\) formulas
• The strength of sharply bounded induction
• Rudimentary Predicates and Relative Computation
• On End‐Extensions of Models of ¬exp