Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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.

share|improve this question
    
Related. –  Andres Caicedo May 18 at 0:55
    
@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? –  Lawrence Wong May 18 at 9:05
    
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. –  Carl Mummert May 18 at 10:54
add comment

1 Answer 1

up vote 7 down vote accepted

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.

share|improve this answer
    
Thanks a lot! Could you provide some references here? And maybe explain what $RT^{1}_{<\infty}$ stands for? Sorry for my ignornace. –  Ashutosh May 18 at 1:28
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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