Binary models generated by their tally part

DOI10.1007/BF01270627MaRDI QIDQ1337500zbMATH OpenOpenAlexFDO

Authors Fernando Ferreira

Publication date 5 January 1995

Published in Archive for Mathematical Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01270627

zbMATH Keywords

bounded collection schememodels of arithmeticpolynomial time hierarchytally part of a modeltheories of bounded arithmetic

Mathematics Subject Classification ID

Models of arithmetic and set theory (03C62) First-order arithmetic and fragments (03F30)

Review text

This paper deals with theories of bounded arithmetic, and with a question of Wilkie and Paris. We introduce and study a class of models of the bounded theory \(\text{PV}_ n\). These models, which are generated by their tally part, have a curious feature: they are end-extendable or satisfy the bounded collection scheme for \(\Sigma^ b_ n\)-formulae only if they are closed under exponentiation. As an application, we show that if the theory \(I\Delta_ 0+\neg\exp\) proves the bounded collection scheme, then the polynomial time hierarchy does not collapse (and, \textit{a fortiori}, \(\text{P}\neq\text{NP}\)).

Recommendations

• scientific article; zbMATH DE number 999649
• On End‐Extensions of Models of ¬exp
• End-extensions of models of weak arithmetic from complexity-theoretic containments
• Structures interpretable in models of bounded arithmetic
• scientific article; zbMATH DE number 1136103

Cites work

• Bounded arithmetic and the polynomial hierarchy
• scientific article; zbMATH DE number 4137758 (Why is no real title available?)
• scientific article; zbMATH DE number 4160708 (Why is no real title available?)
• scientific article; zbMATH DE number 3689386 (Why is no real title available?)
• scientific article; zbMATH DE number 176204 (Why is no real title available?)
• Provability of the pigeonhole principle and the existence of infinitely many primes

Cited in

(3)

• End-extensions of models of weak arithmetic from complexity-theoretic containments
• scientific article; zbMATH DE number 1136103 (Why is no real title available?)
• Models of Bounded Arithmetic Theories and Some Related Complexity Questions

This page was built for publication: Binary models generated by their tally part

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1337500)