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.

$\endgroup$
3
  • $\begingroup$ Related. $\endgroup$ Commented 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$ Commented 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$ Commented May 18, 2014 at 10:54

1 Answer 1

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.

$\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
    Commented May 18, 2014 at 1:28

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .