Logical Approaches to Computational Barriers

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 |