7
$\begingroup$

Recall that $X \subseteq 2^{\omega}$ is Turing independent if no $y \in X$ is computable from the Turing join of any finite subset of $X \setminus \{y\}$.

Question 1. Can we construct a Turing independent set $X \subseteq 2^{\omega}$ such that every real is computable from the Turing join of finitely many members of $X$?

Question 2. If the answer to Q1 is no, what happens if we weaken the requirement in Q1 to ``Every real is Turing comparable with the join of some finite subset of $X$"?

TIA.

Improve this question
$\endgroup$
4
  • $\begingroup$ Couldn't you just take a Hamel basis of the reals? $\endgroup$
    – Daniel Weber
    Commented Mar 6 at 18:56
  • 1
    $\begingroup$ @CommandMaster that might not be Turing independent, e.g. our Hamel basis could have elements satisfying $x=\pi y$. $\endgroup$
    – Noah Schweber
    Commented Mar 6 at 18:56
  • $\begingroup$ Oh, right. However, I think you can use the same argument with Zorn's lemma which shows the existence of a basis to prove the existence of a maximum Turing independent set $\endgroup$
    – Daniel Weber
    Commented Mar 6 at 19:00
  • $\begingroup$ @CommandMaster There are indeed maximal Turing-independent sets, but they don't satisfy the property the OP's after. See my answer. $\endgroup$
    – Noah Schweber
    Commented Mar 6 at 19:01

2 Answers 2

Reset to default
11
$\begingroup$

Q1 has a negative answer.

Let $X$ be an infinite Turing-independent set and fix elements $(r_i)_{i\in\omega}\in X$. The real $\bigoplus_{i\in\omega}r_i$ cannot be computed from the join of any finite $F\subseteq X$, since the join of such an $F$ would then compute some $r_i\not\in F$.

Of course, this does not address Q2.

Improve this answer
$\endgroup$
0
10
$\begingroup$

Q2 also has a negative answer. Take Noah's real $r$ which is not below any finite join of elements of $X$. Take 2 minimal degrees $m_1$ and $m_2$ such that $r$ is below their join. (It is known that every degree is the meet of a pair of joins of pairs of minimal degrees.) If either of them is above a join of elements of $X$ then it must belong to $X$ (by minimality). That can happen for at most one of them (by choice of $r$). At most one of them can be below a finite join of elements of $X$ (by choice of $r$). If either of these possibilities occurs then the other cannot (again by choice of $r$). Consequently, at most one of $m_1$ and $m_2$ is comparable with a finite join of elements of $X$.

Improve this answer
$\endgroup$

You must log in to answer this question.

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