Advanced search
Add to list

Predicativity through transfinite reflection

(2017) JOURNAL OF SYMBOLIC LOGIC. 82(3). p.787-808
Author
Organization
Abstract
Let T be a second-order arithmetical theory, Lambda a well-order, lambda < Lambda and X subset of N. We use [lambda vertical bar X](T)(Lambda)phi as a formalization of "phi is provable from T and an oracle for the set X, using omega-rules of nesting depth at most lambda". For a set of formulas Gamma, define predicative oracle reflection for T over Gamma (Pred-O-RFNG(T)) to be the schema that asserts that, if X subset of N, Lambda is a well-order and phi is an element of Gamma, then for all lambda < Lambda ([lambda vertical bar X](T)(Lambda)phi -> phi ). In particular, define predicative oracle consistency (Pred-O-Cons(T)) as Pred-O-RFN.({0= 1}) (T). Our main result is as follows. Let ATR(0) be the second-order theory of Arithmetical Transfinite Recursion, RCA(0)(*) be Weakened Recursive Comprehension and ACA be Arithmetical Comprehension with Full Induction. Then, ATR(0) RCA(0)(*) + Pred-O-Cons(RCA(0)(*)) = RCA(0)(*) + Pred-O-RFN Pi 12 (ACA). We may even replace RCA(0)(*) by the weaker ECA(0), the second-order analogue of Elementary Arithmetic. Thus we characterize ATR(0), a theory often considered to embody Predicative Reductionism, in terms of strong reflection and consistency principles.
Keywords
second-order arithmetic, reflection principles, provability logic, PROVABILITY ALGEBRAS, PRINCIPLES, INDUCTION, SYSTEMS, ORDINALS, LOGIC

Citation

Please use this url to cite or link to this publication:

MLA
Cordón-Franco, Andrés et al. “Predicativity Through Transfinite Reflection.” JOURNAL OF SYMBOLIC LOGIC 82.3 (2017): 787–808. Print.
APA
Cordón-Franco, A., Fernández-Duque, D., Joosten, J. J., & Lara-Martín, F. F. (2017). Predicativity through transfinite reflection. JOURNAL OF SYMBOLIC LOGIC, 82(3), 787–808.
Chicago author-date
Cordón-Franco, Andrés, David Fernández-Duque, Joost J Joosten, and Francisco Félix Lara-Martín. 2017. “Predicativity Through Transfinite Reflection.” Journal of Symbolic Logic 82 (3): 787–808.
Chicago author-date (all authors)
Cordón-Franco, Andrés, David Fernández-Duque, Joost J Joosten, and Francisco Félix Lara-Martín. 2017. “Predicativity Through Transfinite Reflection.” Journal of Symbolic Logic 82 (3): 787–808.
Vancouver
1.
Cordón-Franco A, Fernández-Duque D, Joosten JJ, Lara-Martín FF. Predicativity through transfinite reflection. JOURNAL OF SYMBOLIC LOGIC. 2017;82(3):787–808.
IEEE
[1]
A. Cordón-Franco, D. Fernández-Duque, J. J. Joosten, and F. F. Lara-Martín, “Predicativity through transfinite reflection,” JOURNAL OF SYMBOLIC LOGIC, vol. 82, no. 3, pp. 787–808, 2017.
@article{8566405,
  abstract     = {Let T be a second-order arithmetical theory, Lambda a well-order, lambda < Lambda and X subset of N. We use [lambda vertical bar X](T)(Lambda)phi as a formalization of "phi is provable from T and an oracle for the set X, using omega-rules of nesting depth at most lambda". 
For a set of formulas Gamma, define predicative oracle reflection for T over Gamma (Pred-O-RFNG(T)) to be the schema that asserts that, if X subset of N, Lambda is a well-order and phi is an element of Gamma, then 
for all lambda < Lambda ([lambda vertical bar X](T)(Lambda)phi -> phi ). 
In particular, define predicative oracle consistency (Pred-O-Cons(T)) as Pred-O-RFN.({0= 1}) (T). Our main result is as follows. Let ATR(0) be the second-order theory of Arithmetical Transfinite Recursion, RCA(0)(*) be Weakened Recursive Comprehension and ACA be Arithmetical Comprehension with Full Induction. Then, 
ATR(0) RCA(0)(*) + Pred-O-Cons(RCA(0)(*)) = RCA(0)(*) + Pred-O-RFN Pi 12 (ACA). 
We may even replace RCA(0)(*) by the weaker ECA(0), the second-order analogue of Elementary Arithmetic. 
Thus we characterize ATR(0), a theory often considered to embody Predicative Reductionism, in terms of strong reflection and consistency principles.},
  author       = {Cordón-Franco, Andrés and Fernández-Duque, David and Joosten, Joost J and Lara-Martín, Francisco Félix},
  issn         = {0022-4812},
  journal      = {JOURNAL OF SYMBOLIC LOGIC},
  keywords     = {second-order arithmetic,reflection principles,provability logic,PROVABILITY ALGEBRAS,PRINCIPLES,INDUCTION,SYSTEMS,ORDINALS,LOGIC},
  language     = {eng},
  number       = {3},
  pages        = {787--808},
  title        = {Predicativity through transfinite reflection},
  url          = {http://dx.doi.org/10.1017/jsl.2017.30},
  volume       = {82},
  year         = {2017},
}

Altmetric
View in Altmetric
Web of Science
Times cited: