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.



Natural statements independent from true $\Pi^0_2$ sentences
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.


