5
$\begingroup$

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.

$\endgroup$

1 Answer 1

4
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Thanks for such a careful explication of the subtleties, François. When formulating the question I was interpreting satisfaction in the second manner you list, but I should have been more explicit: as you rightly say, one should be careful when stating this theorem and its variants. Thankfully the lemma I am actually using does not rely on the meaning of "satisfies" in this manner (I am happy to state it in detail if that's informative). $\endgroup$ Mar 13, 2014 at 16:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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