0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

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.