Hostname: page-component-78c5997874-fbnjt Total loading time: 0 Render date: 2024-11-19T05:18:34.008Z Has data issue: false hasContentIssue false
  • English
  • Français

On Tao's “finitary” infinite pigeonhole principle

Published online by Cambridge University Press:  12 March 2014

Jaime Gaspar  and
Ulrich Kohlenbach
Get access Rights & Permissions [Opens in a new window]

Abstract

In 2007, Terence Tao wrote on his blog an essay about soft analysis, hard analysis and the finitization of soft analysis statements into hard analysis statements. One of his main examples was a quasi-finitization of the infinite pigeonhole principle IPP, arriving at the “finitary” infinite pigeonhole principle FIPP1. That turned out to not be the proper formulation and so we proposed an alternative version FIPP2. Tao himself formulated yet another version FIPP3 in a revised version of his essay.

We give a counterexample to FIPP1 and discuss for both of the versions FIPP2 and FIPP3 the faithfulness of their respective finitization of IPP by studying the equivalences IPP ↔ FIPP2 and IPP ↔ FIPP3 in the context of reverse mathematics ([9]). In the process of doing this we also introduce a continuous uniform boundedness principle CUB as a formalization of Tao's notion of a correspondence principle and study the strength of this principle and various restrictions thereof in terms of reverse mathematics, i.e., in terms of the “big five” subsystems of second order arithmetic.

Type
Research Article
Information
The Journal of Symbolic Logic , Volume 75 , Issue 1 , March 2010 , pp. 355 - 371
Copyright
Copyright © Association for Symbolic Logic 2010

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1] Brown, Douglas K., Notions of compactness in weak subsystems of second order arithmetic, Reverse mathematics 2001 (Simpson, S.G., editor), Lecture Notes in Logic, vol. 21, Association for Symbolic Logic, La Jolla, CA, 2005, pp. 47–66.Google Scholar
[2] Ferreira, Fernando and Oliva, Paulo, Bounded functional interpretation, Annals of Pure and Applied Logic, vol. 135 (2005), pp. 73–112.Google Scholar
[3] Hirst, Jeffry L., Combinatorics in subsystems of second order arithmetic, Ph.D. thesis, Pennsylvania State University, 1987.Google Scholar
[4] Kohlenbach, Ulrich, Mathematically strong subsystems of analysis with low rate of growth of provably recursive functionals, Archive for Mathematical Logic, vol. 36 (1996), pp. 31–71.Google Scholar
[5] Kohlenbach, Ulrich, Arithmetizing proofs in analysis, Logic Colloquium '96 (San Sebastián) (Larrazabal, J.M., Lascar, D., and Mints, G., editors), Springer Lecture Notes Logic, vol. 12, Springer, Berlin, 1998, pp. 115–158.Google Scholar
[6] Kohlenbach, Ulrich, Foundational and mathematical uses of higher types, Reflections on the foundations of mathematics: Essays in Honor of Solomon Feferman (Sieg, W. et al., editors), Lecture Notes in Logic, vol. 15, Association for Symbolic Logic, Urbana, IL, 2002, pp. 92–116.Google Scholar
[7] Kohlenbach, Ulrich, A logical uniform boundedness principle for abstract metric and hyperbolic spaces, Proceedings of the 13th Workshop on Logic, Language, Information and Computation (WoLLIC 2006), Electronic Notes in Theoretical Computer Science, vol. 165, Elsevier Sci. B. V., Amsterdam, 2006, pp. 81–93.Google Scholar
[8] Kohlenbach, Ulrich, Applied proof theory: proof interpretations and their use in mathematics, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2008.Google Scholar
[9] Simpson, Stephen G., Subsystems of second order arithmetic, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1999.Google Scholar
[10] Tao, Terence, Soft analysis, hardanalysis, and thefinite convergence principle, http://terrytao.wordpress.com, 2007, Appeared in “T. Tao, Structure and Randomness: Pages from Year One of a Mathematical Blog, American Mathematical Society, pp. 298, 2008.”.Google Scholar
[11] Tao, Terence, The correspondence principle and finitary ergodic theory, http://terrytao.wordpress.com, 2008.Google Scholar
[12] Troelstra, A. S. and van Dalen, D., Constructivism in mathematics. Vol. I and II, North-Holland Publishing Co., Amsterdam, 1988.Google Scholar