Computability in Europe 2006
Logical Approaches to Computational Barriers

Regular Talk:
On a problem of J. Paris

Speaker: Costas Dimitracopoulos
Author(s): Costas Dimitracopoulos and Alla Sirokofskich
Slot: Array, 11:10-11:30, col. 2


A question asked by J. Paris (see Problem 34 in the list in [1]) is whether or not Δn induction implies Σn collection.
We sketch alternative proofs of results of T. Slaman ([3]) and N. Thapen ([4]) concerning this problem, especially for the case n=1. Our proofs depend on results of C. Dimitracopoulos and J. Paris ([2]) concerning relationships between Σn collection and (versions of) Σn pigeonhole principle.

[1] 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.
[2] C. Dimitracopoulos and J. Paris: The pigeonhole principle and fragments of arithmetic, Z. Math. Logik Grundlag. Math. 32 (1986), 73--80.
[3] T. A. Slaman: Σn-bounding and Δn-induction, Proc. Amer. Math. Soc. 132 (2004), 2449--2456.
[4] N. Thapen: A note on Δ1 induction and Σ1 collection, Fund. Math. 186 (2005), no. 1, 79--84.

websites: Arnold Beckmann 2006-06-14