MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

The question has relevance for constructing Scott sets with certain extra desirable properties. Suppose that $\mathfrak X$ is a countable arithmetically closed family of subsets of $\mathbb N$: whenever $B\in \mathfrak X$ and $C$ is definable in $\langle \mathbb N,+,\cdot, <,B, 0,1\rangle$, then $C\in\mathfrak X$.

Let us fix some $C\notin\mathfrak X$. I would like to find a set $A$ that is almost contained in either $B$ or $B^c$ for every $B\in\mathfrak X$, which has the property that $C$ is not in the arithmetic closure of $\mathfrak X$ with $A$. Thus, closing $\mathfrak X$ and $A$ under definability does not introduce $C$. I am willing to add such an $A$ by forcing (for a ground model set $C$) but I am inclining more and more towards a counterexample. Is there an arithmetically closed family $\mathfrak X$ and a set $C\notin\mathfrak X$ so that an $A$ almost contained in every element of $\mathfrak X$ or its complement always "codes in" $C$?

share|cite|improve this question
up vote 6 down vote accepted

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.

share|cite|improve this answer
François, I think I can construct such an $A$ also. But what I need is that $C$ is not definable from $A$, so not computable from any jump of $A$. – Victoria Gitman Sep 7 '13 at 20:22
Is this all written up in the paper? What are some properties of the forcing? – Victoria Gitman Sep 7 '13 at 20:25
Not the stronger cone-avoiding theorem but what you need is just a little more than the relativized version of the cone-avoiding theorem that I do prove in the paper. – François G. Dorais Sep 7 '13 at 20:27
Ideally, I would like a proper forcing notion, where it is sufficient to meet some $\omega_1$-many dense sets to ensure that the arithmetic closure of $\mathfrak X\cup \{A\}$ avoids $C$. But it is great to know about your example because it means that there is no obstacle to what I want to do! – Victoria Gitman Sep 7 '13 at 20:31
I see that your forcing satisfies axiom A, so it is proper. – Victoria Gitman Sep 7 '13 at 20:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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