Ytukyg

Let $U subset mathbb{N} times mathbb{N}$, and let $U_n = { x mid (n, x) in U }$. Let's call $U$ universal for some class $mathcal{S}$ of subsets of $mathbb{N}$ if $S in mathcal{S} iff exists n : S = U_n$. In other words, the set of "cuts" of $U$ contains all the sets in $mathcal{S}$ and nothing more.

Now, let $U$ be universal for the class of all enumerable subsets of $mathbb{N}$. Prove that $K = { x mid (x, x) in U }$ is enumerable but not decidable.

So, my proof sketch is as follows:

Enumerability is obvious, so let's focus on decidability. I know that there exists an enumerable undecidable $F subset mathbb{N}$. By definition of $U$, it must be contained in a cut with some index $k$. Now, deciding whether $(k, k) in U$ is analogous to deciding whether $k in F$. Any function $f$ for the latter is not computable, hence, the whole function $u$ that decides whether $(x, x) in U$ for arbitrary $x$ is not computable, so $K$ is undecidable.

There are a couple of things I don't like about this.

Firstly, the proposition that $f$ being undecidable implies $u$ is undecidable seems to follow from the definitions in my book (where a set is decidable if its characteristic function is computable), but, intuitively, it just feels unjustified.

Secondly, have I proved too much? A similar argument could be applied to show that any $K' = { x mid (x, f(x)) in U }$ is undecidable for arbitrary $f$ — it's sufficient for $x$ to range over the whole $U$ to capture the undecidable set that's contained in its cut. Is that correct?

I guess I was overly obsessed with reducing this to something having to do with an enumerable undecidable set.

Indeed, the usual diagonalization approach just works: assume $K$ is decidable, then $overline{K} = { x mid (x, x) not in U }$ is also decidable, then $overline{K}$ is enumerable, then it's contained, let's say, in $U_x$ (by definition of $U$). Then the contradiction easily follows.