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

Question

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.

Answer 1

There are a lot of subtleties here. For technical reasons, I'll use $\mathsf{WKL}_0$ instead of $\mathsf{RCA}_0$ to explain them.

The following two theorems are found in Simpson's book:

Theorem VIII.2.6. The following is provable in $\mathsf{WKL}_0$. For all $X \subseteq \mathbb{N}$, there exists a countable coded strict $\beta$-model $M$ such that $X \in M$.

Theorem VIII.2.11. The following is provable in $\mathsf{ACA}_0$. For all $X \subseteq \mathbb{N}$, there exists a countable $\omega$-model $M$ of $\mathsf{WKL}_0$ such that $X \in M$.

By Theorem VIII.2.2 countable coded strict $\beta$-model is a countable coded $\omega$-model which satisfies $\mathsf{WKL}_0$. In Theorem VIII.2.6, it is true that the $\omega$-model satisfies $\mathsf{WKL}_0$ but this is not provable in $\mathsf{WKL}_0$. Indeed, $\mathsf{WKL}_0$ is too weak to properly make sense of "satisfies" in this context.

Because of the subtleties I outlined in my blog post (see also this MO answer by Carl Mummert), the statement "every set is contained in a countable coded $\omega$-model of $\mathsf{WKL}_0$" has two possible meanings. This leads to a conundrum:

• If you interpret "satisfies" using the sort of translation as I outline at the end of my blog post, "every set is contained in a countable coded $\omega$-model of $\mathsf{WKL}_0$" is actually equivalent to $\mathsf{WKL}_0$.

• If you interpret "satisfies" using valuations as in Simpson's book, then the statement "every set is contained in a countable coded $\omega$-model of $\mathsf{WKL}_0$" is equivalent to $\mathsf{ACA}_0$.

The reason for this solely depends on the meaning of "satisfies" and not on the existence of the models in question. So please be careful when saying that $\mathsf{ACA}_0$ is equivalent to "every set is contained in an $\omega$-model of $\mathsf{RCA}_0$" (and variants).

That said, to address your reference request, Simpson writes in the notes to VIII.2:

Theorem VIII.2.11 and lemma VIII.2.15 are well known, but their origins seem difficult to trace. See the references in Shoenfield [220], e.g., Kleene [142, §72].

These references are:

• J. R. Shoenfield, Degrees of models, J. Symbolic Logic 25 (1960), 233–237.
• S. C. Kleene, Introduction to Metamathematics, Van Nostrand, 1952.

It is also unclear to me how to correctly attribute the result you have in mind.