arnold beckmann's pages

Applications of cut-free infinitary derivations to generalized recursion theory

File: PDF-File

Author: Arnold Beckmann and Wolfram Pohlers
Title: Applications of cut-free infinitary derivations to generalized recursion theory
Journal: Ann.Pure.Appl.Logic 1998, 94: 7-19
DOI: 10.1016/S0168-0072(97)00063-8

Abstract: In this paper we introduce an infinitary proof system for a language of second order arithmetic which is complete for Π 1 1 - sentences. The main observation there is the Boundedness Theorem telling that the order-type of a Σ 1 1 - definable well-ordering < is less than or equal to the truth complexity of TI(<) . The commonly known Boundedness Principle of Generalized Recursion Theory will be obtained as a consequence of our proof theoretical Boundedness Theorem which in turn is a consequence of cut-freeness. This yields a proof of the Boundedness Principle which does not use the Analytical Hierarchy Theorem.

websites: Arnold Beckmann 2017-08-28 Valid HTML 4.01! Valid CSS!