Proving innumerable number of RE-hard languages

Question

I'm trying to prove that there are uncountably many RE-hard languages, using Rice's theorem. However, every try leads me to the wrong conclusion the are innumerable many languages in RE...

EDIT: I tried to argue that for every subset S of $\Sigma^*$ there is a semantic property $P_S=${M s.t. L(M)=S}. This gave me innumerable many non-trivial semantic properties that satisfy Rice's lemma, but doesn't it also give me innumerable many RE languages (as I can create a TM to identify each subset)?

Thanks in advance

Answer 1

You've had a good idea, namely to associate to each $S\subseteq\mathbb{N}$ some special index set $I_S$. If this association is injective - so that $S\not=T\implies I_S\not=I_T$ - we'll be done.

However, your particular idea of looking at $P_S=\{e: W_e=S\}$ (I'm using more common notation here: "$W_e$" denotes the $e$th r.e. language, or equivalently the language accepted by the $e$th Turing machine) does not work. If $S$ is non-r.e., then $P_S=\emptyset$, and so in fact we only get countably many distinct index sets from this idea.

This is a situation where the details are actually obscuring the easy solution. The key is to just think about the abstract structure at play here. We have an equivalence relation $\sim$ on $\mathbb{N}$ given by $a\sim b$ iff the $a$th and $b$th Turing machines accept the same language. Now consider the set of equivalence classes $\mathbb{N}/\sim$.

How big is $\mathbb{N}/\sim$?

It's countably infinite. (Actually, all we'll need is that it's infinite.)

And what's the relationship between $\mathbb{N}/\sim$ and index sets? (HINT: for $X\subseteq\mathbb{N}/\sim$, think about $\bigcup X$ - that is, the set $\{e: \exists x\in X(e\in x)\}$ ...)

Index sets are basically equivalent to subsets of $\mathbb{N}/\sim$; more precisely, there is a bijection between the set of index sets and $\mathcal{P}(\mathbb{N}/\sim)$.

From this we get the desired result, since every index set is r.e.-hard and we've shown that there are uncountably many index sets because

$\mathbb{N}/\sim$ is infinite, so $\mathcal{P}(\mathbb{N}/\sim)$ is uncountable, so the set of index sets is uncountable since it's in bijection with $\mathcal{P}(\mathbb{N}/\sim)$.

Note that we've almost entirely ignored the computability-theoretic details here; all that's going on is that there's a connection between index sets and $\mathbb{N}/\sim$, and the latter we can analyze just by thinking combinatorially.

---

And we can get an even simpler argument if we avoid Rice's theorem entirely and think about the join operation $$X\oplus Y=\{2x: x\in X\}\cup\{2y+1: y\in Y\}.$$ Suppose $X$ is r.e.-hard (say, $X=\emptyset'$) and $Y$ is any other set; what can you say about $X\oplus Y$?