The Main Results

Our context is the study of $\omega$-models of subsystems of second order arithmetic [5, Chapter VIII]. As in [5, Chapter VII], a $\beta$-model is an $\omega$-model M such that, for all $\Sigma^1_1$ sentences $\varphi$ with parameters from M, $\varphi$ is true if and only if $M\models\varphi$. Theorems 1.1 and 1.3 below are an interesting supplement to the results on $\beta$-models which have been presented in Simpson [5, §§VII.2 and VIII.6].

Let HYP denote the set of hyperarithmetical reals. It is well known that, for any $\beta$-model M, HYP is properly included in M, and each $X\in\mathrm{HYP}$ is definable in M.

Theorem 1.1   There exists a countable $\beta$-model satisfying

$\forall X\,($if X is definable, then $X\in\mathrm{HYP})$.

Proof.Fix a recursive enumeration S_e, $e\in\omega$, of the $\Sigma^1_1$ sets of reals. If p is a finite subset of $\omega\times\omega^{<\omega}$, say that $\langle X_n\rangle_{n\in\omega}$ meets p if $X_{n_1}\oplus\cdots\oplus X_{n_k}\in S_e$ for all $(e,\langle n_1,\dots,n_k\rangle)\in p$. Let $\mathcal{P}$ be the set of p such that there exists $\langle X_n\rangle_{n\in\omega}$ meeting p. Put $p\le q$ if and only if $p\supseteq q$. Say that $\mathcal{D}\subseteq\mathcal{P}$ is dense if for all $p\in\mathcal{P}$ there exists $q\in\mathcal{D}$ such that $q\le p$. Say that $\mathcal{D}$ is definable if it is definable over the $\omega$-model HYP, i.e., arithmetical in the complete $\Pi^1_1$ subset of $\omega$. Say that $\langle G_n\rangle_{n\in\omega}$ is generic if for every dense definable $\mathcal{D}\subseteq\mathcal{P}$ there exists $p\in\mathcal{D}$ such that $\langle G_n\rangle_{n\in\omega}$ meets p. We can show that for every $p\in\mathcal{P}$ there exists a generic $\langle G_n\rangle_{n\in\omega}$ meeting p. (This is a fusion argument, a la Gandy forcing.) Clearly $\{G_n:n\in\omega\}$ is a $\beta$-model. We can also show that, if C is countable and $C\cap\mathrm{HYP}=\emptyset$, then there exists a generic $\langle G_n\rangle_{n\in\omega}$ such that $C\cap\{G_n:n\in\omega\}=\emptyset$. Let $L_2(\langle X_n\rangle_{n\in\omega})$ be the language of second order arithmetic with additional set constants X_n, $n\in \omega$. Let $\varphi$ be a sentence of $L_2(\langle X_n\rangle_{n\in\omega})$. We say that p forces $\varphi$, written $p\Vdash\varphi$, if for all generic $\langle G_n\rangle_{n\in\omega}$ meeting p, the $\beta$-model $\{G_n:n\in\omega\}$ satisfies $\varphi[\langle X_n/G_n\rangle_{n\in\omega}]$. It can be shown that, for all generic $\langle G_n\rangle_{n\in\omega}$, the $\beta$-model $\{G_n:n\in\omega\}$ satisfies $\varphi[\langle X_n/G_n\rangle_{n\in\omega}]$ if and only if $\langle G_n\rangle_{n\in\omega}$ meets some p such that $p\Vdash\varphi$. If $\pi$ is a permutation of $\omega$, define an action of $\pi$ on $\mathcal{P}$ and $L_2(\langle X_n\rangle_{n\in\omega})$ by $\pi(p)=\{(e,\langle\pi(n_1),\dots,\pi(n_k)\rangle):(e,\langle n_1,\dots,n_k\rangle)\in p\}$ and $\pi(X_n)=X_{\pi(n)}$. It is straightforward to show that $p\Vdash\varphi$ if and only if $\pi(p)\Vdash\pi(\varphi)$. The support of $p\in\mathcal{P}$ is defined by $\mathrm{supp}(p)=\bigcup\{\{n_1,\dots,n_k\}:(e,\langle n_1,\dots,n_k\rangle)\in p\}$. Clearly if $p,q\in\mathcal{P}$ and $\mathrm{supp}(p)\cap\mathrm{supp}(q)=\emptyset$, then $p\cup q\in\mathcal{P}$. We claim that if $\langle G_n\rangle_{n\in\omega}$ and $\langle G'_n\rangle_{n\in\omega}$ are generic, then the $\beta$-models $\{G_n:n\in\omega\}$ and $\{G'_n:n\in\omega\}$ satisfy the same L₂-sentences. Suppose not. Then for some $p,q\in\mathcal{P}$ we have $p\Vdash\varphi$ and $q\Vdash\lnot\,\varphi$, for some L₂-sentence $\varphi$. Let $\pi$ be a permutation of $\omega$ such that $\mathrm{supp}(\pi(p))\cap\mathrm{supp}(q)=\emptyset$. Since $\pi(\varphi)=\varphi$, we have $\pi(p)\Vdash\varphi$, hence $\pi(p)\cup q\Vdash\varphi$, a contradiction. This proves our claim. Finally, let $M=\{G_n:n\in\omega\}$ where $\langle G_n\rangle_{n\in\omega}$ is generic. Suppose $A\in M$ is definable in M. Let $\langle G'_n\rangle_{n\in\omega}$ be generic such that $M'=\{G'_n:n\in\omega\}$ has $M\cap M'=\mathrm{HYP}$. Let $\varphi(X)$ be an L₂-formula with X as its only free variable, such that $M\models(\exists$ exactly one $X)\,\varphi(X)$, and $M\models\varphi(A)$. Then $M'\models(\exists$ exactly one $X)\,\varphi(X)$. Let $A'\in M'$ be such that $M'\models\varphi(A')$. Then for each $n\in \omega$, we have that $n\in A$ if and only if $M\models\exists X\,(\varphi(X)$ and $n\in X)$, if and only if $M'\models\exists X\,(\varphi(X)$ and $n\in X)$, if and only if $n\in A'$. Thus A=A'. Hence $A\in\mathrm{HYP}$. This completes the proof.$\Box$

Remark 1.2   Theorem 1.1 has been announced without proof by Friedman [3, Theorem 4.3]. Until now, a proof of Theorem 1.1 has not been available.

We now improve Theorem 1.1 as follows.

Let $\le_\mathrm{HYP}$ denote hyperarithmetical reducibility, i.e., $X\le_\mathrm{HYP} Y$ if and only if X is hyperarithmetical in Y.

Theorem 1.3   There exists a countable $\beta$-model satisfying

$(*)\qquad\forall X\,\forall Y\,($if X is definable from Y, then $X\le_\mathrm{HYP}Y)$.

The $\beta$-model which we shall use to prove Theorem 1.3 is the same as for Theorem 1.1, namely $M=\{G_n:n\in\omega\}$ where $\langle G_n\rangle_{n\in\omega}$is generic. In order to see that M has the desired property, we first relativize the proof of Theorem 1.1, as follows. Given Y, let $\mathcal{P}^Y$ be the set of $p\in\mathcal{P}$ such that there exists $\langle X_n\rangle_{n\in\omega}$ meeting p with X₀=Y. (Obviously 0 plays no special role here.) Say that $\langle G_n\rangle_{n\in\omega}$ is generic over Y if, for every dense $\mathcal{D}^Y\subseteq\mathcal{P}^Y$ definable from Y over $\mathrm{HYP}(Y)=\{X:X\le_\mathrm{HYP}Y\}$, there exists $p\in\mathcal{D}^Y$ such that $\langle G_n\rangle_{n\in\omega}$ meets p.

Lemma 1.4   If $\langle G_n\rangle_{n\in\omega}$ is generic over Y, then G₀=Y, and $\{G_n:n\in\omega\}$ is a $\beta$-model satisfying $\forall X\,($if X is definable from Y, then $X\le_\mathrm{HYP}Y)$.

Proof.The proof of this lemma is a straightforward relativization to Y of the proof of Theorem 1.1.$\Box$

Consequently, in order to prove Theorem 1.3, it suffices to prove the following lemma.

Lemma 1.5   If $\langle G_n\rangle_{n\in\omega}$ is generic, then $\langle G_n\rangle_{n\in\omega}$ is generic over G₀.

Proof.It suffices to show that, for all p forcing $(\mathcal{D}^{X_0}$ is dense in $\mathcal{P}^{X_0})$, there exists $q\le p$ forcing $\exists r\,(r\in\mathcal{D}^{X_0}$ and $\langle X_n\rangle_{n\in\omega}$ meets r). Assume $p\Vdash(\mathcal{D}^{X_0}$ is dense in $\mathcal{P}^{X_0})$. Since $p\Vdash p\in\mathcal{P}^{X_0}$, it follows that $p\Vdash\exists q\,(q\le p$ and $q\in\mathcal{D}^{X_0})$. Fix $p'\le p$ and $q'\le p$ such that $p'\Vdash q'\in\mathcal{D}^{X_0}$. Put $S'=\{X_0:\langle X_n\rangle_{n\in\omega}$ meets $p'\}$. Then S' is a $\Sigma^1_1$ set, so let $e\in\omega$ be such that S'=S_e. Claim 1: $\{(e,\langle0\rangle)\}\Vdash q'\in\mathcal{D}^{X_0}$. If not, let $p''\le\{(e,\langle0\rangle)\}$ be such that $p''\Vdash q'\notin\mathcal{D}^{X_0}$. Let $\pi$ be a permutation such that $\pi(0)=0$ and $\mathrm{supp}(p')\cap\mathrm{supp}(\pi(p''))=\{0\}$. Then $p'\cup\pi(p'')\in\mathcal{P}$ and $\pi(p'')\Vdash q'\notin\mathcal{D}^{X_0}$, a contradiction. This proves Claim 1. Claim 2: $q'\cup\{(e,\langle0\rangle)\}\in\mathcal{P}$. To see this, let $\langle G'_n\rangle_{n\in\omega}$ be generic meeting $\{(e,\langle0\rangle)\}$. By Claim 1 we have $q'\in\mathcal{D}^{G'_0}$. Hence $q'\in\mathcal{P}^{G'_0}$, i.e., there exists $\langle X_n\rangle_{n\in\omega}$ meeting q' with X₀=G'₀. Thus $\langle X_n\rangle_{n\in\omega}$ meets $q'\cup\{(e,\langle0\rangle)\}$. This proves Claim 2. Finally, put $q''=q'\cup\{(e,\langle0\rangle)\}$. Then $q''\le q'\le p$ and $q''\Vdash(q'\in\mathcal{D}^{X_0}$ and $\langle X_n\rangle_{n\in\omega}$ meets q'). This proves our lemma.$\Box$

The proof of Theorem 1.3 is immediate from Lemmas 1.4 and 1.5.