4
$\begingroup$

Are there examples of independence results over subsystems of true second order arithmetic that cannot be established using omega-models? To rule out trivial examples, let us assume that the base theory extends true first order arithemtic. A non example of such a statement would be Ramsey theorem for pairs since there is a computable coloring of pairs of integers into two colors without a computable (even from the halting problem, Jockusch) infinite homogeneous set.

An example of a use of non-omega models appears here - Also, see the introduction and question 6.1 in this paper.

I am not an expert in reverse mathematics so please feel free to offer any interesting known facts known to you here.

Improve this question
$\endgroup$
3
  • $\begingroup$ Related. $\endgroup$
    – Andrés E. Caicedo
    May 18, 2014 at 0:55
  • $\begingroup$ @Ashutosh: The base theory in your example from Chong–Slaman–Yang does not seem to extend "true first order arithmetic", unless you mean something different from what I understand. Could you clarify a bit on what you mean by "true first order arithmetic", please? $\endgroup$
    – Lawrence Wong
    May 18, 2014 at 9:05
  • $\begingroup$ I am not aware of any reverse math research in which the base theory includes true first-order arithmetic. But there is another point: the induction schemes in reverse mathematics all include set parameters. This is the case even for schemes like B$\Sigma^0_2$. Formulas of true first order arithmetic don't include set parameters. $\endgroup$
    – Carl Mummert
    May 18, 2014 at 10:54

1 Answer 1

Reset to default
7
$\begingroup$

Yes, of course there are. Any result that is equivalent to extra induction axioms will require nonstandard models for a semantic separation.

For example, Hirst proved that the pigeonhole principle $\mathsf{RT}^1_{<\infty}$ is equivalent to $B\Sigma^0_2$, and thus is not provable in $\mathsf{RCA}_0$. But $B\Sigma^0_2$ holds in every $\omega$-model.

Similarly, there is a variation of $\mathsf{ACA}_0$, denoted $\mathsf{ACA}'_0$, which has an axiom asying that for all $n$, $0^{(n)}$ exists. In contrast, $\mathsf{ACA}_0$ only proves that $0^{(n)}$ exists for standard $n$. So every $\omega$-model of $\mathsf{ACA}_0$ is a model of $\mathsf{ACA}'_0$.

For an example with non-arithmetical induction: $\mathsf{ACA}_0$ plus $\Sigma^1_1$ induction proves the consistency of $\mathsf{ACA}_0$, so $\mathsf{ACA}_0$ does not prove $\Sigma^1_1$ induction.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Thanks a lot! Could you provide some references here? And maybe explain what $RT^{1}_{<\infty}$ stands for? Sorry for my ignornace. $\endgroup$
    – Ashutosh
    May 18, 2014 at 1:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.