Seminar

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.)