Computability in Europe 2006
Logical Approaches to Computational Barriers
|Author(s):||Costas Dimitracopoulos and Alla Sirokofskich|
|Slot:||Tue, 11:10-11:30, Faraday B (col. 2)|
A question asked by J. Paris (see Problem 34 in the list in ) is whether or not Δn induction implies Σn collection.
We sketch alternative proofs of results of T. Slaman () and N. Thapen () concerning this problem, especially for the case n=1. Our proofs depend on results of C. Dimitracopoulos and J. Paris () concerning relationships between Σn collection and (versions of) Σn pigeonhole principle.
 P. Clote and J. Krajicek: Open problems, Oxford Logic Guides, 23, Arithmetic, proof theory, and computational complexity (Prague, 1991), 1--19, Oxford Univ. Press, New York, 1993.
 C. Dimitracopoulos and J. Paris: The pigeonhole principle and fragments of arithmetic, Z. Math. Logik Grundlag. Math. 32 (1986), 73--80.
 T. A. Slaman: Σn-bounding and Δn-induction, Proc. Amer. Math. Soc. 132 (2004), 2449--2456.
 N. Thapen: A note on Δ1 induction and Σ1 collection, Fund. Math. 186 (2005), no. 1, 79--84.
|websites: Arnold Beckmann||2006-06-14|