Separations of first and second order theories in bounded arithmetic |
| |
| Authors: | Masahiro Yasumoto |
| |
| Affiliation: | (1) Graduate School of Informatics, Nagoya University, Nagoya, 464-8601, Japan |
| |
| Abstract: | We prove that PTCN(n) (the polynomial time closure of the nonstandard natural number n in the model N of S2.) cannot be a model of U12. This implies that there exists a first order sentence of bounded arithmetic which is provable in U12 but does not hold in PTCN(n). |
| |
| Keywords: | Bounded Arithmetic Separation |
| 本文献已被 SpringerLink 等数据库收录！ |
