Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic (Q866557)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic |
scientific article |
Statements
Partial collapses of the \(\Sigma _1\) complexity hierarchy in models for fragments of bounded arithmetic (English)
0 references
14 February 2007
0 references
It is shown that, for each \(n\) there exists a model of \(T^n_2\) in which standard iterations of \(\#\) on some element are cofinal (so it is not a model of exp), and in which every strict \(\exists \Pi^b_{n+1}\) formula is equivalent to a \(\exists \Pi^b_{n}\) formula. As the authors note, this does not mean that the bounded hierarchy collapses in the model. The existence of such a model is still an open question. The key to the result is the fact that if \(M\) is a \(\Sigma^b_{n+1}\)-maximal model in which standard iterations of \(\#\) on some element are cofinal, then in \(M\) any strict \(\Sigma^b_{n+1}\) formula is equivalent to an infinite conjunction of partial consistency statements for the \(\Pi^b_n\) diagram of \(M\).
0 references
bounded arithmetic
0 references
consistency statements
0 references
maximal models
0 references
bounded formula hierarchy
0 references