Binary models generated by their tally part (Q1337500)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Binary models generated by their tally part |
scientific article |
Statements
Binary models generated by their tally part (English)
0 references
5 January 1995
0 references
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}\)).
0 references
models of arithmetic
0 references
tally part of a model
0 references
theories of bounded arithmetic
0 references
bounded collection scheme
0 references
polynomial time hierarchy
0 references