How can a subset be undecidable?

Question

A subset of a set can have an undecidable member relation. Though how can you determine if $A$ is actually a subset of $B$ if the member relation of $A$ is not decidable? That feels contradictory because the definition of the subset relation uses the member relation: “If all the members of set $A$ are also members of set $B$, then $A$ is a subset of $B$”

Answer 1

Just because an implication is decidable does not mean that its premise or consequent are decidable.

For example, we know that $\sf ZFC$ proves that the $V=L$ implies the Continuum Hypothesis. Consider the sets $A=\{x\mid x=0\land V=L\}$ and $B=\{x\mid x=0\land\sf CH\}$. We can prove that $A\subseteq B$, but we cannot prove that either sets is non-empty, starting from just $\sf ZFC$.

Similarly, if you want to understand sets of natural numbers, then considering $\varphi(x)$ and $\psi(y)$, both in the language of arithmetic, such that both sets defined by the formulas are undecidable, but $\forall x(\varphi(x)\to\psi(x))$ will give you an example of two sets which are undecidable, but one is included in the other. For example, the set of all machines that halt with input $0$ or $1$, and the set of all machines that halt with input $0$.

We can concoct simple examples by taking $\psi$ to define a very simple set, e.g. $\{2^n\mid n\in\Bbb N\}$, or the set of primes, or any other set with a nice simple recursive enumeration, and then considering any undecidable set $A$, we can take the $n$th element of our nice set in its enumeration, for $n\in A$. This has the nice benefit of giving us "an explicit feeling about uncountably many sets", whereas the first method only applied to countably many sets.

Of course, we can improve upon the first method by introducing oracles, but it is still useful since it lets us see how this may happen even when neither sets is decidable themselves.