Logical Approaches to Computational Barriers
Print this page
Regular Talk:
On a problem of J. Paris
| Speaker: | Costas Dimitracopoulos |
| Author(s): | Costas Dimitracopoulos and Alla Sirokofskich |
| Slot: | Tue, 11:10-11:30, Faraday B (col. 2) |
Abstract
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
|