2020/04/15 by Freund, Anton · 1 citation
#03A05 #03F30 #03F40 #68R10 #FOS: Mathematics #Logic (math.LO)
paper · doi:10.48550/arxiv.2004.06915
We present a new manifestation of Gödel's second incompleteness theorem and discuss its foundational significance, in particular with respect to Hilbert's program. Specifically, we consider a proper extension of Peano arithmetic (PA) by a mathematically meaningful axiom scheme that consists of Σ02-sentences. These sentences assert that each computably enumerable (Σ01-definable without parameters) property of finite binary trees has a finite basis. Since this fact entails the existence of polynomial time algorithms, it is important for computer science. On a technical level, our axiom scheme is a variant of an independence result due to Harvey Friedman. At the same time, the meta-mathematical properties of our axiom scheme distinguish it from most known independence results: Due to its logical complexity, our axiom scheme does not add computational strength. The only known method to establish its independence relies on Gödel's second incompleteness theorem. In contrast, Gödel's theorem is not needed for typical examples of Π02-independence (such as the Paris-Harrington principle), since computational strength provides an extensional invariant on the level of Π02-sentences.