2

I‌ prepare for Final-Exam on Complexity Course. in one of my prof. old-exam I see this question:

Suppose $A_n$={$x \in \mathbb{N}\mid n \in W_x $}. Which of them is false?

1) Set $A_n$ for each natural number is r.e

2) $ \forall n A_n =_m K$ (K is Halting Set)

3) $\forall l \forall k A_l =_m A_k$

4) $ \cap_{n \in \mathbb{N}} A_n^c $ is a complete r.e set

Short answer of her exam is (4)‌ is right. Who can help me with learning and defining some hint for this question. I‌ think when $‌ A \leq_m B$ and $‌ B \leq_m A$ we have $A‌ =_m B$, that called equivalence relation. (just I think)‌ ( $\leq_m$ means many-one reducible).

Thanks.

Carl Mummert
  • 81,604

1 Answers1

1

1) Yes, $A_n$ is r.e for all $n$. Consider the program $P$ such that $$P(x)=\phi_x(n)$$ then $Dom(P)=A_n$

2) As $A_n$ is r.e then $A_n\le_m K$ (because $K$ is complete). Consider the recursive function $s$, obtained by snm, such that $$\phi_{s(x)}(y)=\phi_x(x)$$ Then $x\in K$ iff $s(x)\in A_n$, so $K\le_m A_n$. Hence $A_n=_m K$

3) $=_m$ is a transitive relation, so $A_l=_m K=_m A_k$

4) False. $E=\cup A_n^c$ is the set of all $i$ such that $Dom(\phi_i)=\emptyset$. Suppose that $E$ is r.e. Then for some $e$ $E=W_e$

But then using $\phi_e$ you can build $P$ such that $$P(x)=\mbox{halts if } s(x)\in E $$

Then $Dom(P)=K^c$, which would make $K^c$ re, and as $K$ is re, it would make both set computable. A contradiction.

Xoff
  • 10,310