Skip to main content
revised and expanded
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals forthat $F_\sigma$-Mathias forcing are precisely the computable onespreserves $\mathsf{ACA}_0$. In other words, for any non-computable setWhen restricted to $C$ in$\omega$-models the ground model theremain preservation theorem gives:

Theorem. If $\mathfrak{X}$ is aan arithmetically closed Turing ideal and $G$ is $F_\sigma$-Mathias generic $A$ that does not computeover $C$. Of course$\mathfrak{X}$, athen the Turing ideal generated by $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set$\mathfrak{X}\cup\{G\}$ is also arithmetically closed.

The paper actually goes further andmeaning of "$F_\sigma$-Mathias generic over $\mathfrak{X}$" is devoted to showing howthat the forcing consists $F_\sigma$-Mathias forcing preservesconditions coded in $\mathsf{ACA}_0$. Your collection$\mathfrak{X}$ and that the generic $G$ should meet all of the dense sets that are definable over $\mathfrak{X}$ is actuallyin the language of second-order part of an $\omega$-model ofarithmetic. $\mathsf{ACA}_0$(As usual, there is some flexibility in the second requirement. The preservation results of)

To derive the above from Theorem 4.3 of my paper show, observe that if $A$ is $F_\sigma$the names I used are a way of formalizing Turing functionals with built-Mathias genericin oracles from $\mathfrak{X}$. Therefore, then the arithmetic closureevaluation of a $\mathfrak{X}\cup\{A\}$$G$-total name is justa total computable function with respect to some oracle $G \oplus X$ where $X \in \mathfrak{X}$, and all such functions can be represented by a $G$-total name in this way. It follows that the recursive closureevaluation of that set.all (More precisely$G$-total names, which is how I define the generic extension of, is simply the Turing ideal generated by $\omega$-model with second-order part$\mathfrak{X}\cup\{G\}$.

The result you want then follows from the following:

Lemma. For every partial name $F$ coded in $\mathfrak{X}$ to be the model whose second-order part is the recursive closurecollection of $\mathfrak{X}\cup\{A\}$$\mathfrak{X}$-coded conditions $(a,A,\mu)$ such that, so the preservation theorem then saysfor some $x$, $(a,A,\mu)$ forces that this recursive closure$F(x) \neq C(x)$ is actually arithmetically closed wheneverdense.

Indeed, we may assume that $\mathfrak{X}$$(a,A,\mu)$ forces that $F$ is arithmetically closedtotal, otherwise some extension forces that $F(x)$ is undefined for some $x$.) Combined with Then, if $(a,A,\mu)$ does not decide all values of $F$, then some extension will decide a slight strengtheningvalue $F(x)$ to be different from $C(x)$. Finally, if $(a,A,\mu)$ decides all values of $F$ then the cone-avoiding result I provedresulting evaluation of $F$ is computable from $F$ and $(a,A,\mu)$. Therefore, you get that there for every $F \neq C$ since $C \notin \mathfrak{X}$ there.

Note that the above is really a meta-lemma since $F(x) \neq C(x)$ is expressible in $\mathfrak{X}$ for fixed input $x$ but not for all inputs at once. Nevertheless, the lemma gives a family of open dense sets for $F_\sigma$-Mathias forcing over $\mathfrak{X}$ and any generic $A$ such$G$ that meets all of these dense sets (and all those that are definable from $\mathfrak{X}$) will be as required by the theorem: the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids$\mathfrak{X}\cup\{G\}$ will not contain $C$. This last part requires some technical work beyond what I wrote in

Note that the same result cannot be achieved with ordinary Mathias forcing since Blass has shown that every Mathias generic set computes all hyperarithmetic reals.


An earlier version of this answer outlined a tweaking of the cone avoiding result at the end of my paper but I am willing to help!achieve the same goal. While that solution did work, it introduced some unnecessary complexity since the point of that result is that one can still arrange that the generic $G$ does not compute $C$ even if $C \in \mathfrak{X}$, provided that $C$ is not computable.

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set.

The paper actually goes further and is devoted to showing how $F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. Your collection $\mathfrak{X}$ is actually the second-order part of an $\omega$-model of $\mathsf{ACA}_0$. The preservation results of the paper show that if $A$ is $F_\sigma$-Mathias generic, then the arithmetic closure of $\mathfrak{X}\cup\{A\}$ is just the recursive closure of that set. (More precisely, I define the generic extension of the $\omega$-model with second-order part $\mathfrak{X}$ to be the model whose second-order part is the recursive closure of $\mathfrak{X}\cup\{A\}$, so the preservation theorem then says that this recursive closure is actually arithmetically closed whenever $\mathfrak{X}$ is arithmetically closed.) Combined with a slight strengthening of the cone-avoiding result I proved, you get that there for every $C \notin \mathfrak{X}$ there is a $F_\sigma$-Mathias generic $A$ such that the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids $C$. This last part requires some technical work beyond what I wrote in the paper but I am willing to help!

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show that $F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. When restricted to $\omega$-models the main preservation theorem gives:

Theorem. If $\mathfrak{X}$ is an arithmetically closed Turing ideal and $G$ is $F_\sigma$-Mathias generic over $\mathfrak{X}$, then the Turing ideal generated by $\mathfrak{X}\cup\{G\}$ is also arithmetically closed.

The meaning of "$F_\sigma$-Mathias generic over $\mathfrak{X}$" is that the forcing consists $F_\sigma$-Mathias conditions coded in $\mathfrak{X}$ and that the generic $G$ should meet all of the dense sets that are definable over $\mathfrak{X}$ in the language of second-order arithmetic. (As usual, there is some flexibility in the second requirement.)

To derive the above from Theorem 4.3 of my paper, observe that the names I used are a way of formalizing Turing functionals with built-in oracles from $\mathfrak{X}$. Therefore, the evaluation of a $G$-total name is a total computable function with respect to some oracle $G \oplus X$ where $X \in \mathfrak{X}$, and all such functions can be represented by a $G$-total name in this way. It follows that the evaluation of all $G$-total names, which is how I define the generic extension, is simply the Turing ideal generated by $\mathfrak{X}\cup\{G\}$.

The result you want then follows from the following:

Lemma. For every partial name $F$ coded in $\mathfrak{X}$ the collection of $\mathfrak{X}$-coded conditions $(a,A,\mu)$ such that, for some $x$, $(a,A,\mu)$ forces that $F(x) \neq C(x)$ is dense.

Indeed, we may assume that $(a,A,\mu)$ forces that $F$ is total, otherwise some extension forces that $F(x)$ is undefined for some $x$. Then, if $(a,A,\mu)$ does not decide all values of $F$, then some extension will decide a value $F(x)$ to be different from $C(x)$. Finally, if $(a,A,\mu)$ decides all values of $F$ then the resulting evaluation of $F$ is computable from $F$ and $(a,A,\mu)$. Therefore, $F \neq C$ since $C \notin \mathfrak{X}$.

Note that the above is really a meta-lemma since $F(x) \neq C(x)$ is expressible in $\mathfrak{X}$ for fixed input $x$ but not for all inputs at once. Nevertheless, the lemma gives a family of open dense sets for $F_\sigma$-Mathias forcing over $\mathfrak{X}$ and any generic $G$ that meets all of these dense sets (and all those that are definable from $\mathfrak{X}$) will be as required by the theorem: the arithmetic closure of $\mathfrak{X}\cup\{G\}$ will not contain $C$.

Note that the same result cannot be achieved with ordinary Mathias forcing since Blass has shown that every Mathias generic set computes all hyperarithmetic reals.


An earlier version of this answer outlined a tweaking of the cone avoiding result at the end of my paper to achieve the same goal. While that solution did work, it introduced some unnecessary complexity since the point of that result is that one can still arrange that the generic $G$ does not compute $C$ even if $C \in \mathfrak{X}$, provided that $C$ is not computable.

extra details
Source Link
François G. Dorais
  • 44.4k
  • 6
  • 150
  • 233

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set.

The paper actually goes further and is devoted to showing how $F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. Your collection $\mathfrak{X}$ is actually the second-order part of an $\omega$-model of $\mathsf{ACA}_0$. The preservation results of the paper show that if $A$ is $F_\sigma$-Mathias generic, then the arithmetic closure of $\mathfrak{X}\cup\{A\}$ is just the recursive closure of that set. (More precisely, I define the generic extension of the $\omega$-model with second-order part $\mathfrak{X}$ to be the model whose second-order part is the recursive closure of $\mathfrak{X}\cup\{A\}$, so the preservation theorem then says that this recursive closure is actually arithmetically closed whenever $\mathfrak{X}$ is arithmetically closed.) Combined with a slight strengthening of the cone-avoiding result I proved, you get that there for every $C \notin \mathfrak{X}$ there is a $F_\sigma$-Mathias generic $A$ such that the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids $C$. This last part requires some technical work beyond what I wrote in the paper but I am willing to help!

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set.

The paper actually goes further and is devoted to showing how $F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. Your collection $\mathfrak{X}$ is actually the second-order part of an $\omega$-model of $\mathsf{ACA}_0$. The preservation results of the paper show that if $A$ is $F_\sigma$-Mathias generic, then the arithmetic closure of $\mathfrak{X}\cup\{A\}$ is just the recursive closure of that set. Combined with a slight strengthening of the cone-avoiding result I proved, you get that there for every $C \notin \mathfrak{X}$ there is a $F_\sigma$-Mathias generic $A$ such that the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids $C$.

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set.

The paper actually goes further and is devoted to showing how $F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. Your collection $\mathfrak{X}$ is actually the second-order part of an $\omega$-model of $\mathsf{ACA}_0$. The preservation results of the paper show that if $A$ is $F_\sigma$-Mathias generic, then the arithmetic closure of $\mathfrak{X}\cup\{A\}$ is just the recursive closure of that set. (More precisely, I define the generic extension of the $\omega$-model with second-order part $\mathfrak{X}$ to be the model whose second-order part is the recursive closure of $\mathfrak{X}\cup\{A\}$, so the preservation theorem then says that this recursive closure is actually arithmetically closed whenever $\mathfrak{X}$ is arithmetically closed.) Combined with a slight strengthening of the cone-avoiding result I proved, you get that there for every $C \notin \mathfrak{X}$ there is a $F_\sigma$-Mathias generic $A$ such that the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids $C$. This last part requires some technical work beyond what I wrote in the paper but I am willing to help!

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

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set.

The paper actually goes further and hence all sets inis devoted to showing how $\mathcal{X}$$F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. Your collection $\mathfrak{X}$ is actually the second-order part of an $\omega$-model of $\mathsf{ACA}_0$. The preservation results of the paper show that if $A$ is $F_\sigma$-Mathias generic, then the arithmetic closure of $\mathfrak{X}\cup\{A\}$ is just the recursive closure of that set. Combined with a slight strengthening of the cone-avoiding result I proved, you get that there for every $C \notin \mathfrak{X}$ there is a $F_\sigma$-Mathias generic $A$ such that the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids $C$.

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set and hence all sets in $\mathcal{X}$.

In my paper, A variant of Mathias forcing that preserves $\mathsf{ACA}_0$ [Archive for Mathematical Logic 51 (2012), 751–780; arXiv:1110.6559, doi:10.1007/s00153-012-0297-4], I show the needed reals for $F_\sigma$-Mathias forcing are precisely the computable ones. In other words, for any non-computable set $C$ in the ground model there is a $F_\sigma$-Mathias generic $A$ that does not compute $C$. Of course, a $F_\sigma$-Mathias generic will be almost contained in or almost disjoint from any ground model set.

The paper actually goes further and is devoted to showing how $F_\sigma$-Mathias forcing preserves $\mathsf{ACA}_0$. Your collection $\mathfrak{X}$ is actually the second-order part of an $\omega$-model of $\mathsf{ACA}_0$. The preservation results of the paper show that if $A$ is $F_\sigma$-Mathias generic, then the arithmetic closure of $\mathfrak{X}\cup\{A\}$ is just the recursive closure of that set. Combined with a slight strengthening of the cone-avoiding result I proved, you get that there for every $C \notin \mathfrak{X}$ there is a $F_\sigma$-Mathias generic $A$ such that the arithmetic closure of $\mathfrak{X}\cup\{A\}$ avoids $C$.

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