Uncomputability of subset relation

Question

I suppose this obvious question should already be answered in plenty of places, but for some reasons I cannot find a proof of this anywhere.

Prove or disprove that their exist a set $X$ that is decidable, yet the relation $A\subseteq X$ is not decidable where $A$ is arbitrary decidable set.

And,

Prove or disprove that their exist a set $X$ that is decidable, yet the relation $X\subseteq A$ is not decidable where $A$ is arbitrary decidable set.

I am only beginner to computability, so I hope for some easy to understand proof if possible. Thank you for your help.

Answer 1

First off, if you have a solution to one of the halves, you also have one for the other -- just replace $X$ and $A$ with their complements, which preserves decidability and makes $A\subseteq X$ into $\overline X\subseteq \overline A$.

Second, there's an important subtlety here. The problem is about whether we can find some $X$ such that there is/isn't a machine $M$ that takes as input a decidable set $A$ and returns a boolean saying whether $A\subseteq X$ or not.

However, $M$ can't literally take $A$ as input, because most decidable sets are infinite, and the machine has to complete in finite time. Therefore, in order to make any sense of the problem we need to interpret it such that the input to $M$ is not $A$ itself, but the code/index for a machine/program that decides $A$. And that gives us lots of leverage because we know that there can be several different machines that decide the same $A$ but can't be proved to decide the same $A$.

Finally, a hint: Keeping the previous point in mind, you can actually take $X=\varnothing$ in the first half of the problem. In other words: It is impossible, given an always-halting machine, to decide whether the $A$ it decides is empty or not!

Answer 2

To see what's really going on, it's easier to begin by looking at arbitrary sets (in other words, temporarily ignore the requirement that the sets should be decidable/computable). So we just want a set $X$ such that there is no algorithm to tell whether an arbitrary set $A$ is a subset of $X$. Because we are looking at arbitrary sets, we need to pass them to the algorithm as oracles.

Suppose that $\mathbb{N}\setminus X$ was finite. Then only a finite number of numbers are not in $X$. So we could just check that these numbers are not in $A$, and if not then $A$ would be a subset of $X$. This can be done algorithmically. So we need $\mathbb{N}\setminus X$ to be infinite.

To take that option all the way, what if $X$ is finite? Say $X = \{1\}$ (we could pick any finite set). Now, to tell whether an arbitrary set $A$ is a subset of $X$, it looks like we need to check that every number other than $1$ is not in $A$. That's an infinite number of numbers to check, which seems impossible to do by algorithm.

To prove it's impossible, suppose otherwise (for a contradiction). Suppose $\phi_e$ is an algorithm such that, for an arbitrary set $A$, $\phi_e^A = 1$ if $A \subseteq \{1\}$ and $\phi_e^A = 0$ otherwise. Run the algorithm with input $A_1 = \{1\}$. The algorithm must halt in a finite number of steps and return $1$. Keep track of all the numbers which the algorithm asks about in $A_1$ - there can only be finitely many of these, because the algorithm halts in a finite number of steps. Let $N$ be the largest number that the algorithm queries when it is run on $A_1$. Then, if we let $A_2 = \{1, N+1\}$, the algorithm must return $1$ when run on $A_2$, since $A_1$ and $A_2$ agree on all the numbers that the algorithm will query. But $A_2 \not \subseteq X$, so the algorithm is not always correct, and we have our contradiction.

Now, that proof can be easily converted into a proof where we only look at computable sets and we pass them to the algorithm via their indices instead of passing them as oracles. This is simply because $X$, $A_1$, and $A_2$ are all computable!

In this way, a decent number of elementary questions about computability "on indices" can be answered by first solving the problem for arbitrary sets passed as oracles, and then checking that the sets that are actually used in the construction are computable.

---

Here is how to convert the proof to work with indices. It's actually a routine procedure, once you have the right viewpoint. Don't look at $A_2$ as fixed from the outset. Instead, imagine that the elements of $A_2$ are determined one at a time by an adversary. The adversary can defeat $\phi_e$ as follows. First, the adversary makes $A_2$ look more and more like $A_1$, but without committing that $A_2$ really will equal $A_1$ in the end. Eventually, $\phi_e$ has to give an answer, but since the adversary can always change $A_2$ at a later point, there is no answer $\phi_e$ can give that the adversary can't beat. (It's almost like the Saturday Night Live game "what number am I thinking of?".)

To work with indices, let $i_1$ be any index for a finite (or more generally, coinfinite) set $X$ and let $\phi_e$ be as above, but taking indices rather than oracles. We make an index $i_2$, using the recursion theorem, that will compute a set $B$. Given input $n$, $i_2$ first computes $\phi_e$ on input $i_2$ for $n$ steps. If $\phi_e$ halts in $n$ or fewer steps and returns $1$, then $i_2$ puts $n$ in $B$ if and only if $n$ is not in $X$. Otherwise, $i_2$ puts $n$ in $B$ is and only if $n$ is in $X$. (Remember that $X$ is computable from index $i_1$, which we can code into $i_2$.) Now $i_2$ has played the same strategy with indices that $A_2$ played with oracles! Eventually, $\phi_e$ has to return some answer on input $i_2$. If $\phi_e $ ever returns $1$ (claiming $B \subseteq X$) then $i_2$ ensures $B \not\subseteq X$ because $B$ will be cofinite. Otherwise, if $\phi_e$ never returns $1$, then $i_2$ ensures $B \subseteq X$ (in fact $B = X$ in this case.) Either way, $\phi_e$ gets it wrong (or fails to return an answer, which is also a loss for $\phi_e$)

Remarks

1. The number $M$ in this second proof corresponding to $N$ in the proof above is the number of steps that $\phi_e$ takes to halt on input $i_2$. If $\phi_e(i_2) = 1$ then $B \supseteq \{M, M+1, M+2,\ldots, \}$. The importance of $A_1$ and $A_2$ being computable is that we can make $i_2$ pretend to compute $A_1$ for some time, but at any moment we can switch it to computing a set like $A_2$.

2. The process of going from the proof with oracles to the proof with indices, using the recursion theorem, is very general. Once you have the right perspective, the same technique can be applied to many elementary computability questions. Essentially: whenever the strategy that the adversary uses to construct an oracle is computable, we can code that strategy into an index.

3. Another intuition to get from this sort of proof is that static analysis of indices is useless. There may be some trivial property that can be identified solely by looking at the index, but the more helpful intuition is that the only way to tell what an index does is to run it. Indeed, this is one reason to call them "indices" instead of "programs" - to emphasize that an index is a black box.