Back to Search
Start Over
Separations of first and second order theories in bounded arithmetic.
- Source :
- Archive for Mathematical Logic; Aug2005, Vol. 44 Issue 6, p685-688, 4p
- Publication Year :
- 2005
-
Abstract
- We prove that PTC<subscript> N</subscript>( n) (the polynomial time closure of the nonstandard natural number n in the model N of S<subscript>2</subscript>.) cannot be a model of U<superscript>1</superscript><subscript>2</subscript>. This implies that there exists a first order sentence of bounded arithmetic which is provable in U<superscript>1</superscript><subscript>2</subscript> but does not hold in PTC<subscript> N</subscript>( n). [ABSTRACT FROM AUTHOR]
- Subjects :
- POLYNOMIALS
NATURAL numbers
MATHEMATICAL models
ARITHMETIC
MATHEMATICAL logic
Subjects
Details
- Language :
- English
- ISSN :
- 09335846
- Volume :
- 44
- Issue :
- 6
- Database :
- Complementary Index
- Journal :
- Archive for Mathematical Logic
- Publication Type :
- Academic Journal
- Accession number :
- 17744570
- Full Text :
- https://doi.org/10.1007/s00153-005-0281-3