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 natural statements, 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.
$\begingroup$
$\endgroup$
3
-
1$\begingroup$ I assume the $\Pi^0_2$ in the body of your question is what you intended and the $\Sigma^0_2$ in the title isn't. But just in case you're actually interested in the title question, I think the Paris-Harrington theorem answers that. The point is that true $\Sigma^0_2$ sentences are consequences of true $\Pi^0_1$ ones. $\endgroup$– Andreas BlassCommented Nov 18, 2011 at 0:29
-
1$\begingroup$ @Andreas, yes, I fixed the title, thanks. $\endgroup$– KavehCommented Nov 18, 2011 at 1:39
-
$\begingroup$ Depending on how strict your definition of "natural" is, even Paris-Harrington might not be considered "natural." The condition of having as many elements as the least element was not "studied in combinatorics for its own sake." $\endgroup$– Timothy ChowCommented Nov 21, 2011 at 23:50
Add a comment
|
3 Answers
$\begingroup$
$\endgroup$
3
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:
For every recursive function $f:{\mathbb N}^k \to {\mathbb N}^k$, there exists $n_1 < \cdots < n_{k+1}$ such that $f(n_1,\ldots,n_k) \le f(n_2, \ldots, n_{k+1})$ coordinatewise.
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.
Friedman refers to the introduction of his forthcoming book Boolean Relation Theory and Incompleteness (downloadable from his website) for more information.
answered Nov 21, 2011 at 23:46
-
$\begingroup$ Thanks a lot for the example. I was guessing that Harvey may have an example. I guess that it is unlikely that I would get an answer which is more natural than this so I accept it. $\endgroup$– KavehCommented Nov 22, 2011 at 0:44
-
$\begingroup$ While we're holding our collective breath for the book to be published, is there some way fo finding out what the proofs are, short of travelling to Ohio? I've always wanted to know. $\endgroup$ Commented Sep 8, 2019 at 7:44
-
1$\begingroup$ @AndrejBauer : There's a fair amount of information on Friedman's website u.osu.edu/friedman.8 See for example the "downloadable manuscripts" and "Boolean relation theory book" links on the sidebar. $\endgroup$ Commented Sep 8, 2019 at 19:33
$\begingroup$
$\endgroup$
1
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.
-
$\begingroup$ Thanks, but your answer is essentially saying that the arithmetic hierarchy doesn't collapse, which I know, that is not what I want. Statements from logic/computability like Soundness, Halting, ... are not what I am looking for. $\endgroup$– KavehCommented Nov 20, 2011 at 21:28
$\begingroup$
$\endgroup$
I can't get you an answer better than Harvey Friedman's, but would a randomly-looking polynomial equation with some quantifier-prefix count as natural? If yes -- I can provide examples equivalent to 2-Con(T) for various theories T.
