Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 73

Deprecated: Function split() is deprecated in /srv/www/htdocs-cs/cie06/db-code.php on line 80
CiE 2006 - Regular Talk: - On a problem of J. Paris
Computability in Europe 2006
Logical Approaches to Computational Barriers

Print current page  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)


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
Warning: date(): It is not safe to rely on the system's timezone settings. You are *required* to use the date.timezone setting or the date_default_timezone_set() function. In case you used any of those methods and you are still getting this warning, you most likely misspelled the timezone identifier. We selected the timezone 'UTC' for now, but please set date.timezone to select your timezone. in /srv/www/htdocs-cs/cie06/conf-code.php on line 135
2006-06-14 Valid HTML 4.01! Valid CSS! eXTReMe Tracker hit counters by