skip to content

On the computational content of the Baire Category Theorem

Tuesday 3rd July 2012 - 11:00 to 12:00
INI Seminar Room 1
We present results on the classification of the computational content of the Baire Category Theorem in the Weihrauch lattice. The Baire Category Theorem can be seen as a pigeonhole principle that states that a large (= complete) metric space cannot be decomposed into a countable number of small (= nowhere dense) pieces (= closed sets). The difficulty of the corresponding computational task depends on the logical form of the statement as well as on the information that is provided. In the first logical form the task is to find a point in the space that is left out by a given decomposition of the space that consists of small pieces. In the contrapositive form the task is to find a piece that is not small in a decomposition that exhausts the entire space. In both cases pieces can be given by descriptions in negative or positive form. We present a complete classification of the complexity of the Baire Category Theorem in all four cases and for certain types of spaces. The results are based on joint work with Guido Gherardi and Alberto Marcone, on the one hand, and Matthew Hendtlass and Alexander Kreuzer, on the other hand. One obtains a refinement of what is known in reverse mathematics in this way.

[1] Vasco Brattka and Guido Gherardi. "Effective choice and boundedness principles in computable analysis." The Bulletin of Symbolic Logic, 17(1):73–117, 2011.

[2] Vasco Brattka and Guido Gherardi. "Weihrauch degrees, omniscience principles and weak computability." The Journal of Symbolic Logic, 76(1):143–176, 2011.

[3] Vasco Brattka, Guido Gherardi, and Alberto Marcone. "The Bolzano-Weierstrass theorem is the jump of weak KŐnig's lemma." Annals of Pure and Applied Logic, 163:623–655, 2012.

[4] Vasco Brattka, Matthew Hendtlass, and Alexander P. Kreuzer. "On the Weihrauch complexity of computability theory." unpublished notes, 2012.

[5] Vasco Brattka. "Computable versions of Baire's category theorem." In Jiří Sgall, Aleš Pultr, and Petr Kolman, editors, Mathematical Foundations of Computer Science 2001, volume 2136 of Lecture Notes in Computer Science, pages 224–235, Berlin, 2001. Springer.
26th International Symposium, MFCS 2001, Mariánské Lázně, Czech Republic, August 27-31, 2001.

[6] Douglas K. Brown and Stephen G. Simpson. "The Baire category theorem in weak subsystems of second order arithmetic." The Journal of Symbolic Logic, 58:557–578, 1993.

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
Presentation Material: 
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons