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.



Existence of an inseparable minimal pair
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$.


