Skip to main content
2 of 3
reordered
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

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:

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

François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233