10
$\begingroup$

For $x, y \subseteq \omega$,

(a) We write $x \leq_T y$ if $x$ is Turing reducible to $y$.

(b) We write $x \leq_L y$ if $x \in L(y)$ where $L(y)$ is the smallest model of ZFC that contains all ordinals and $y$. Let $L = L(\emptyset)$.

Note that $x \leq_T y \implies x \in L(y)$.

I have two questions.

(1) Is there an infinite $x \subseteq \omega$ such that for every $y \subseteq x$, if $x \leq_T y$ then $x \setminus y$ is finite?

If the answer to (1) is yes, then

(2) Assume $\mathbb{R} \cap L \neq \mathbb{R}$. Does there exist an infinite $x \subseteq \omega$ such that for every $y \subseteq x$, if $x \leq_L y$ then $x \setminus y$ is finite?

Improve this question
$\endgroup$

2 Answers 2

Reset to default
11
$\begingroup$

The answer to (1) is yes, as shown in: Robert I. Soare, Sets with no subsets of higher degree, Journal of Symbolic Logic 24 (1969), 53--56. The property in the title of this paper seems weaker, but Soare gets it via a positive answer to (1). He also says in his paper that Paul Cohen also obtained this result independently, in unpublished work.

Improve this answer
$\endgroup$
2
  • $\begingroup$ @MihaHabič A Cohen real itself doesn't work, because if there is a computable $C$ such that $A$ has infinitely many elements in $C$ and infinitely many elements not in $C$ then we can encode $A$ into a coinfinite subset $B$ of $A$ by just letting the $n$th element of $B$ be in $C$ iff $n$ is in $A$. Glancing at Soare's paper quickly, it looks like he uses Mathias forcing. $\endgroup$
    – Denis Hirschfeldt
    Commented Oct 3, 2017 at 14:08
  • $\begingroup$ Mathias forcing works for a consistent "yes" for (2). Thank you for the pointer! $\endgroup$
    – Todd Eisworth
    Commented Oct 3, 2017 at 20:56
7
$\begingroup$

For (2), what happens if we are in $L[r]$ with $r$ a Sacks real? Since this has minimal degree, all non-constructible $x\subseteq\omega$ have the same degree of constructibility, and if we split a non-constructible set into two disjoint pieces, at least one must be non-constructible. This would be a consistent "no" answer for (2), as we may split any infinite subset of $\omega$ into two infinite pieces.

Edit:

Denis' comment on Mathias forcing got me to thinking, and a look back at Mathias' original "Happy Families" paper has what we need for a consistent "yes" answer to (2).

In particular, Theorem 8.2 of the paper tells us exactly what we want: if $F$ is a Ramsey ultrafilter in $L$ and $X$ is Mathias generic over $L$ with respect to $F$, then $Z\subseteq X$ and $X\leq_L Z$ implies $X\setminus Z$ is finite.

So (2) is actually independent of ZFC.

Note as well that (2) has a positive answer if the set of constructible reals is countable, as any infinite pseudo-intersection for the filter generated by $F$ in $V$ is Mathias generic over $L$ for $F$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .