Artículo
On the quantifier complexity of Δ n+1 (T)– induction
Autor/es | Cordón Franco, Andrés
Fernández Margarit, Alejandro Lara Martín, Francisco Félix |
Departamento | Universidad de Sevilla. Departamento de Ciencias de la Computación e Inteligencia Artificial |
Fecha de publicación | 2004 |
Fecha de depósito | 2019-06-27 |
Publicado en |
|
Resumen | In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class ... In this paper we continue the study of the theories IΔ n+1 (T), initiated in [7]. We focus on the quantifier complexity of these fragments and theirs (non)finite axiomatization. A characterization is obtained for the class of theories such that IΔ n+1 (T) is Π n+2 –axiomatizable. In particular, IΔ n+1 (IΔ n+1 ) gives an axiomatization of Th Π n+2 (IΔ n+1 ) and is not finitely axiomatizable. This fact relates the fragment IΔ n+1 (IΔ n+1 ) to induction rule for Δ n+1 –formulas. Our arguments, involving a construction due to R. Kaye (see [9]), provide proofs of Parsons’ conservativeness theorem (see [16]) and (a weak version) of a result of L.D. Beklemishev on unnested applications of induction rules for Π n+2 and Δ n+1 formulas (see [2]). |
Identificador del proyecto | DGES PB96-1345 |
Cita | Cordón Franco, A., Fernández Margarit, A. y Lara Martín, F.F. (2004). On the quantifier complexity of Δ n+1 (T)– induction. Archive for Mathematical Logic, 43 (3), 371-398. |
Ficheros | Tamaño | Formato | Ver | Descripción |
---|---|---|---|---|
On the quantifier complexity.pdf | 516.3Kb | [PDF] | Ver/ | |