Logo

Mathematical Sciences Research Institute

Home » MT Postdoc Seminar: A hop, skip, and a jump through the degrees of relative provability

Seminar

MT Postdoc Seminar: A hop, skip, and a jump through the degrees of relative provability March 14, 2014 (11:00 AM PDT - 12:00 PM PDT)
Parent Program: Model Theory, Arithmetic Geometry and Number Theory
Location: MSRI: Simons Auditorium
Speaker(s) Uri Andrews (University of Wisconsin)
Description No Description

Video
No Video Uploaded
Abstract/Media

The topic of this talk arises from two directions. On the one hand, Gödel's incompleteness theorem tell us that given any sufficiently strong, consistent, effectively axiomatizable theory T for first-order arithmetic, there is a statement that is true but not provable in T. On the other hand, over the past seventy years, a number of researchers studying witnessing functions for various combinatorial statements have realized the importance of fast-growing functions and the fact that their totality is often not provable over a given sufficiently strong, consistent, effectively axiomatizable theory T for first-order arithmetic (e.g. the Paris-Harrington and the Kirby-Paris theorems).



I will talk about the structure induced by giving the order (for a fixed T) of relative provability for totality of algorithms. That is, for algorithms describing functions f and g, we say f ≤ g if T along with the totality of g suffices to prove the totality of f. It turns out that this structure is rich, and encodes many facets of the nature of provability over sufficiently strong, consistent, effectively axiomatizable theories for first-order arithmetic. (Work joint with Mingzhong Cai, David Diamondstone, Steffen Lempp, and Joseph S. Miller.)

No Notes/Supplements Uploaded No Video Files Uploaded