Natural statements independent from true $\Pi^0_2$ sentences - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-23T22:17:03Z http://mathoverflow.net/feeds/question/81190 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/81190/natural-statements-independent-from-true-pi0-2-sentences Natural statements independent from true $\Pi^0_2$ sentences Kaveh 2011-11-17T17:50:57Z 2012-11-09T22:26:31Z <p>I am looking for sentences in the language of first order arithmetic ($0,1,+,\cdot,\leq$) which are independent from $\Pi^0_2$ consequences of true arithmetic $\Pi^0_2\text{-}\mathsf{Th}(\mathbb{N})$. I want <em>natural statements</em>, e.g. statements that have been studied in number theory or combinatorics for their own sake. The motivation comes from looking for true statements that are not provable in $\mathsf{I}\Delta_0(L)$ where $L$ contains arbitrary fast growing (computable) functions.</p> http://mathoverflow.net/questions/81190/natural-statements-independent-from-true-pi0-2-sentences/81454#81454 Answer by none for Natural statements independent from true $\Pi^0_2$ sentences none 2011-11-20T21:11:18Z 2011-11-20T21:11:18Z <p>If computability counts, Turing famously showed that if M is a Turing machine equipped with an oracle for the regular halting problem, then M's own halting problem is undecidable by M. And if M2 is a machine with an oracle for M, then M2 can't decide its own halting problem, and so on. If I'm not mistaken, that can be turned into independent statements at every level of the arithmetic hierarchy. Having access to the true $\Pi_2^0$ sentences amounts to having M2. It doesn't help you with M3, etc.</p> http://mathoverflow.net/questions/81190/natural-statements-independent-from-true-pi0-2-sentences/81558#81558 Answer by Timothy Chow for Natural statements independent from true $\Pi^0_2$ sentences Timothy Chow 2011-11-21T23:46:12Z 2011-11-21T23:46:12Z <p>I passed this question on to Harvey Friedman, who provided the following information. Friedman has shown that the following statement is equivalent to the 2-consistency of PA:</p> <blockquote> <p>For every recursive function $f:{\mathbb N}^k \to {\mathbb N}^k$, there exists $n_1 &lt; \cdots &lt; n_{k+1}$ such that $f(n_1,\ldots,n_k) \le f(n_2, \ldots, n_{k+1})$ coordinatewise.</p> </blockquote> <p>Friedman also says that there are versions of Paris-Harrington and Kruskal's tree theorem that work. For example, "Every infinite recursive sequence of finite trees has a tree that is inf-preserving-embeddable into a later tree" is equivalent to the 2-consistency of $\Pi^1_2$ bar induction.</p> <p>Friedman refers to the introduction of his forthcoming book <i>Boolean Relation Theory and Incompleteness</i> (downloadable from his website) for more information.</p>