Since long ago it is known the existence of non-recursive sets (i.e., non-$\Delta_1$), e.g., Halting problem. It is also known (firstly noticed by Trakhtenbrot, and deeply studied by Smullyan) the existence of (non-trivial) pairs of sets that are recursively inseparable; this means that there are sets $A,B \subseteq \mathbb{N}$ such that $A \subsetneq B$, and there is no recursive set $C$ such that $A \subseteq C \subseteq B$. An example of pair with this property is to consider $A$ as the set of (Gödel numbers of) first-order valid formulas, and $B$ as the set of (Gödel numbers of) first-order formulas valid in all finite structures.

I am interested on what it is known about the "natural" generalization of the provious notion to $\Delta_2$sets, and to $\Delta_3$, etc. To be more precise: what is it known about pairs of sets $A,B \subseteq \mathbb{N}$ such that:

  • $A \subsetneq B$,
  • there is no $\Delta_2$ set $C$ such that $A \subseteq C \subseteq B$.

Is there any such pair? Is there a general theory for this notion as the one developed by Smullyan for $\Delta_1$? Has this been studied in some papers?

Update 1: I am interested in non trivial and explicit examples. For the non trivial part it makes more sense to replace $A \subsetneq B$ with the following conditions: $A \subseteq B$, and $B \setminus A$ is infinite.

Update 2: To make my question closer to what happens in the $\Delta_1$ example given above let me add the constraints that $A$ is $\Sigma_2$-complete and B is $\Pi_2$-complete.

  • $\begingroup$ You should add the 'computability' tag. Also you have $A\subseteq C \subseteq D$ where should be $A \subseteq C \subseteq B$. $\endgroup$ – Quinn Culver Jan 20 '12 at 16:28
  • $\begingroup$ @Quinn: Thanks. I corrected the typo, and added the tag (somehow I missed it before, I only realized the "complexity" tag, which is not adequate here). $\endgroup$ – boumol Jan 20 '12 at 16:52
  • $\begingroup$ Retagged as "computability-theory". $\endgroup$ – Goldstern Jan 20 '12 at 17:14
  • $\begingroup$ It might be worth noting the more standard [equivalent] formulation: A set $C$ is a \emph{separating set} for a pair $(A,B)$ of disjoint sets if $A \subseteq C$ and $B \cap C = \emptyset$. A pair $(A,B$) of sets is recursively inseparable if there is no recursive set $C$ separating them. $\endgroup$ – Asher M. Kach Jan 20 '12 at 17:16
  • $\begingroup$ @Asher: Thanks, I forgot to say that I reformulated the recursive inseparability notion in my question. The relation is given by the equivalence between the following 2 conditions: (i) $A$ and $B$ are recursively inseparable in the sense of my question, (ii) $A$ and $\mathbb{N} \setminus B$ are recursively inseparable in the sense written down by Asher Kach (which is the common way). $\endgroup$ – boumol Jan 20 '12 at 17:25

Since you put no restrictions on the complexity of $A$ and $B$, this should be easy. Given any countable family $X$ of subsets of $\mathbb N$, there are sets $A\subseteq B$ with $B-A$ infinite and with no $C\in X$ satisfying $A\subseteq C\subseteq B$. List the elements of $X$ in an $\omega$-sequence $(C_n)$ and build $A$ and $B$ inductively as follows. At every stage, you will have decided for only finitely many natural numbers $k$ whether $k\in A$, $k\in B-A$, or $k\notin B$. At stage $n$, if $C_n$ has an element about which no decision has been made yet, choose one such element and put it out of $B$, thus ensuring that $C_n$ won't be a subset of $B$. Otherwise, choose an element outside $C_n$ about which no decision has been made and put that element into $A$, thus ensuring that $A$ won't be a subset of $C_n$. Finally (in stage $n$), choose another element about which no decision has yet been made and put it into $B-A$, thus ensuring that, at the end of the construction, $B-A$ will be infinite.

If $X$ is a class like $\Delta^0_2$ and you use a "reasonable" enumeration of it, and if, wherever I said "choose", you always take the smallest available number, then this process will give you some computability information about $A$ and $B$. You might, however, be able to do better by being more subtle in the construction.

  • $\begingroup$ Your answer is right, but let me point out that I would prefer an explanation that is not "a la Cantor". Let me exemplify this with one example. One can prove the existence of trascendental numbers by a trivial "a la Cantor" argument, but this is not as tricky as proving that some particular number is trascendental. I am more interested on the explicit presentation of two sets A and B with the above properties (let me point that for $\Delta_1$ this is known, I wrote a known natural example in my question) $\endgroup$ – boumol Jan 20 '12 at 17:20
  • 3
    $\begingroup$ Boumol, note that Cantor's diagonal method is constructive, and does produce a specific transcendental number. $\endgroup$ – Joel David Hamkins Jan 20 '12 at 18:06
  • $\begingroup$ Can we use Cantor's diagonal method to write down the decimal expression of a trascendental number? $\endgroup$ – boumol Jan 20 '12 at 19:17
  • 1
    $\begingroup$ @boumol: Yes. Since the number that we obtain is not rational, and since the construction gives an effective sequence of rational intervals that intersect just to the number being constructed, we can read the decimal expansion directly from that sequence. We just need to start with an effective enumeration of all the algebraic numbers when performing the construction. $\endgroup$ – Carl Mummert Jan 20 '12 at 19:25
  • $\begingroup$ Thanks for pointing this issue, I never realized before (I feel like a fool now). I have started to read the paper "Georg Cantor and transcendental numbers" by Robert Gray mathdl.maa.org/mathDL/22/… I suggest this reading for those people that were also surprised by Hamkin's statement. $\endgroup$ – boumol Jan 20 '12 at 19:48

It may be worth noting that the example of recursively inseparable sets (a la boumol's definition) in the question is very much related to a standard example of recursively inseparable sets (a la the traditional definition): Let $A := \{ e : \varphi_e(e) \downarrow = 0 \}$ and $B := \{ e : \varphi_e(e) \downarrow = 1 \}$. Then $(A,B)$ is recursively inseparable (a la the traditional definition).

Indeed, direct relativization of this result to the Halting Problem $K$ offers an explicit example of a pair of $\Delta^0_2$-inseparable sets.

CLAIM: Let $A := \{ e : \varphi^K_e(e) \downarrow = 0 \}$ and $B := \{ e : \varphi^K_e(e) \downarrow = 1 \}$. Then $(A,B)$ is $\Delta^0_2$-inseparable (a la the traditional definition).

PROOF: Towards a contradiction, fix a $\Delta^0_2$ set $C$ separating $A$ and $B$. Let $z$ be an index so that $C = \varphi^K_z$. Being a characteristic function, the function $\varphi^K_z$ satisfies either $\varphi^K_z(z) \downarrow = 1$ or $\varphi^K_z(z) \downarrow = 0$. If the former, then $z \in B$ (by definition) and $z \in C$ (as $C = \varphi^K_z$), contradicting $B \cap C = \emptyset$. If the latter, then $z \in A$ (by definition) so $z \in C$ (as $A \subseteq C$), contradicting $z \not \in C$ (as $C = \varphi^K_z$). Hence, in either case, we have a contradiction.

More generally, I expect that many of the results on recursive inseparability relativize in straightforward manners to yield results on, for example, $\Delta^0_2$-inseparability.


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.