4
$\begingroup$

An inseparable minimal pair is a pair of sets $A, B \subseteq \mathbb{N}$ which are

  • inseparable: there is no computable $C \subseteq \mathbb{N}$ such that $A \subseteq C$ and $B \subseteq \mathbb{N} \setminus C$, and
  • minimal pair: if $C \leq_T A$ and $C \leq_T B$ then $C$ is computable.

(I do not care whether $A$ and $B$ are c.e. sets, but one would normally require them to be so.)

According to MR0822684 the following paper contains the construction of an inseparable minimal pair:

Ding, De Cheng (PRC-NAN): A minimal pair of recursively inseparable r.e. sets. (Chinese. English summary) Nanjing Daxue Xuebao Shuxue Bannian Kan 1 (1984), no. 2, 268–271.

However, the paper seems quite inaccessible from this half of the globe. I am hoping someone can either provide a more easily accessible reference, or a direct argument showing that such a thing exists.

$\endgroup$

1 Answer 1

3
$\begingroup$

Here's a construction of a computably inseparable minimal pair. I believe that it is not hard to modify this construction to give c.e. sets by using a priority construction. However, I have not checked this fact carefully and to keep things as simple as possible I will not do so here (i.e. I will not prove the c.e. version).

The construction is similar to the construction of a minimal pair in Soare's book (Turing Computability, Theorem 6.2.3). The main difference is that it is a little tricky to make sure $A$ and $B$ stay disjoint.

We will construct two disjoint sets $A$ and $B$ using the method of finite extensions (i.e. Cohen forcing). In particular we will choose two increasing sequences of finite binary strings $\sigma_0 \leq \sigma_1 \leq \sigma_2 \leq \ldots$ and $\tau_0 \leq \tau_1 \leq \tau_2 \leq \ldots$ and then set $A$ to be the limit of the first sequence and $B$ to be the limit of the second sequence. Along the way we will make sure that for each $e$, $\{n \mid \sigma_e(n) = 1\}$ and $\{n \mid \tau_e(n) = 1\}$ are disjoint.

On stage $e$ of the construction we will ensure that $A$ and $B$ satisfy two sorts of requirements.

  1. There is some $n$ such that either $\varphi_e(n)$ is equal to neither $0$ nor $1$ (either because it diverges or because it converges with an output larger than $1$) or $\varphi_e(n) = 0$ and $n \in A$ or $\varphi_e(n) = 1$ and $n \in B$. This ensures that $\varphi_e$ does not compute a set separating $A$ and $B$.
  2. Either $\varphi_e^A$ is a computable function, there is some $n$ such that $\varphi_e^A(n)$ is equal to neither $0$ nor $1$ or there is some $n$ such that $\varphi_e^A(n) \neq \varphi_e^B(n)$. This ensures that $\varphi_e^A$ and $\varphi_e^B$ are either not equal, not total, not $\{0,1\}$-valued or that $\varphi_e^A$ is computable. If we do this for every $e$ it is enough to ensure $A$ and $B$ form a minimal pair (see remark 6.2.2 of Soare).

Here's what we do on stage $e$. Taking care of the first requirement is easy. If $\varphi_e(n)$ is not equal to either $0$ or $1$ for some $n$ then we are already done. Otherwise there is some $n$ where neither $\sigma_e$ nor $\tau_e$ are defined yet for which $\varphi_e(n)\downarrow \in \{0,1\}$. We can then extend $\sigma_e$ or $\tau_e$ to satisfy the requirement (while keeping the sets they define disjoint). If $\varphi_e(n) = 0$ then we extend $\sigma_e$ so that it has value $1$ on $n$ and if $\varphi_e(n) = 1$ then we extend $\tau_e$ to be $1$ on $n$.

Now let's explain how to take care of the second requirement. Let $\sigma$ and $\tau$ denote the strings resulting from taking care of the first requirement at stage $e$. Note that by extending $\sigma$ or $\tau$ with $0$'s we may assume that they have the same length. For any $n \in \mathbb{N}$ and $b \in \{0, 1\}$ say that $\varphi^A_e(n) = b$ is possible if there is some $\rho \in 2^\omega$ such that $\varphi^{\sigma^\frown\rho}_e(n)\downarrow = b$ (where as usual $^\frown$ refers to concatenation of finite strings). We now break into two cases.

Case 1: For every $n$, at most one of $\varphi_e^A(n) = 0$ and $\varphi_e^A(n) = 1$ is possible. In this case we are done because either $\varphi_e^A$ is not a total, $\{0,1\}$-valued function or it is computable (in this case, to compute its value on $n$, just search for any $\rho$ such that $\varphi_e^{\sigma^\frown \rho}(n)$ converges and outputs a value in $\{0,1\}$ and output its value). In other words, we can just set $\sigma_{e + 1} = \sigma$ and $\tau_{e + 1} = \tau$.

Case 2: For some $n$, both $\varphi_e^A(n) = 0$ and $\varphi_e^A(n) = 1$ are possible. Fix one such $n$ and fix $\rho_0$ and $\rho_1$ witnessing that $\varphi_e^A(n) = 0$ and $\varphi_e^A(n) = 1$ are possible. We now break into a few subcases.

Subcase 2.1: There is some $\gamma \in 2^{< \omega}$ such that $\varphi_e^{\tau^\frown \gamma}(n) = 1$ and $\{m \mid \gamma(m) = 1\}$ is disjoint from $\{m \mid \rho_0(m) = 1\}$. In this case we may satisfy the requirement by setting $\sigma_{e + 1} = \sigma^\frown \rho_0$ and $\tau_{e + 1} = \tau^\frown\gamma$ (which guarantees that $\varphi_e^A(n) \neq \varphi_e^B(n)$).

Subcase 2.2: There is some $\gamma \in 2^{< \omega}$ such that $\varphi_e^{\tau^\frown \gamma}(n) = 0$ and $\{m \mid \gamma(m) = 1\}$ is disjoint from $\{m \mid \rho_1(m) = 1\}$. In this case we may satisfy the requirement by setting $\sigma_{e + 1} = \sigma^\frown \rho_1$ and $\tau_{e + 1} = \tau^\frown\gamma$.

Subcase 2.3: For all $\gamma \in 2^{< \omega}$, if $\varphi_e^{\tau^\frown\gamma}(n)\downarrow\in \{0,1\}$ then there is some $m$ such that $\gamma(m) = 1$ and either $\rho_0(m) = 1$ or $\rho_1(m) = 1$. In this case, define $\tau_{e + 1}$ by extending $\tau$ to be $0$ on every $m$ such that $\rho_0(m) = 1$ and on every $m$ such that $\rho_1(m) = 1$. This ensures that $\varphi_e^B(n)$ either diverges or takes a value other than $0$ or $1$.

$\endgroup$
3
  • $\begingroup$ @NoahSchweber Isn't the argument for minimal-pair-ness basically just the argument I gave in my answer? Or do you have a simpler argument in mind? $\endgroup$ May 6 at 3:48
  • $\begingroup$ Also note that the sets I build are just two sufficiently mutually Cohen generics so I don't think what I did is very different from what you suggest. $\endgroup$ May 6 at 3:50
  • $\begingroup$ Yeah, fair enough, I've deleted it. $\endgroup$ May 6 at 4:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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