Skip to main content
3 of 3
Added missing 'in'.

Attribution of an equivalence of the existence of omega-models of RCA0

There are many well-known equivalences in reverse mathematics between statements of the form "Every set is contained a countable coded $\omega$-model of $T$" and $S$, where $S, T$ are subsystems of second order arithmetic and $T < S$ in the usual hierarchies. For example:

  • $\mathsf{ACA}_0^+$ is equivalent over $\mathsf{RCA}_0$ to "Every set is contained a countable coded $\omega$-model of $\mathsf{ACA}$". This is theorem 1.7(i) of Rathjen [2012]; the proof states it follows from lemma 3.4 of Afshari and Rathjen [2009].
  • $\mathsf{ATR}_0$ is equivalent over $\mathsf{RCA}_0$ to "Every set is contained a countable coded $\omega$-model of $\Delta^1_1\text{-}\mathsf{CA}$" (or $\Sigma^1_1\text{-}\mathsf{DC}$). This is theorem 1.7(ii) of Rathjen [2012] and is given as following from lemma VIII.4.19 of Simpson's book.
  • $\Pi^1_1\text{-}\mathsf{CA}_0$ is equivalent over $\mathsf{ACA}_0$ to "Every set is contained in a countable coded $\beta$-model". This is in Simpson's book as theorem VII.2.10 and doesn't have a prior attribution associated.

(I have left out results that concern $\beta_n$-models and stronger systems. If there are other equivalences below the strength of $\Pi^1_1\text{-}\mathsf{CA}_0$ I'd like to hear of them.)

There is an obvious omission from this list, namely that $\mathsf{ACA}_0$ is equivalent over $\mathsf{RCA}_0$ to the statement "Every set is contained in a countable coded $\omega$-model of $\mathsf{RCA}_0$".

In some current work I need a similar lemma, and would like to properly attribute the result. However, I haven't been able to track one down, or indeed find anywhere that this theorem is written down. My knowledge of the literature is not as extensive as it could be, so I might just have missed it, in which case a citation would be very much appreciated. Alternatively, perhaps it is simply too obvious a fact for anyone to have bothered. In that case it would be helpful to know, so I could simply note it as folklore.

Relatedly, is this case like that of $\Pi^1_1\text{-}\mathsf{CA}_0$ in the list above, in that we can drop the requirement that the $\omega$-model satisfies any particular theory? (Obviously there are some delicacies here regarding the precise statement of the equivalence.)


This question was inspired by a talk of Michael Rathjen on well-ordering principles and $\omega$-models, as well as François Dorais's blog post which mentions theorems of this sort.

[Afshari and Rathjen 2009] B. Afshari and M. Rathjen: Reverse Mathematics and Well-ordering Principles: A pilot study, Annals of Pure and Applied Logic 160 (2009) 231-237.

[Rathjen 2012] M. Rathjen. $\omega$-models and well-ordering principles. In N. Tennant, editor, Foundational Adventures: Essays in Honor of Harvey M. Friedman. College Publications, 2012.