# Existence of an inseparable minimal pair

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.

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$$.

• @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? May 6 at 3:48
• 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. May 6 at 3:50
• Yeah, fair enough, I've deleted it. May 6 at 4:37