“School of Mathematics”
Back to Papers HomeBack to Papers of School of Mathematics
| Paper IPM / M / 2336 |
|
| Abstract: | |
|
In this note we show that the intuitionistic theory of polynomial
induction on Π1b+-formulas does not imply the
intuitionistic theory IS21 of polynomial induction on
Σ1b+-formulas. We also show the converse assuming the
Polynomial Hierarchy does not collapse. Similar results hold also
for length induction in place of polynomial induction. We also
investigate the relation between various other intuitionistic
first-order theories of bounded arithmetic. Our method is mostly
semantical, we use Kripke models of the theories.
Download TeX format |
|
| back to top | |
