Let $K$ be the halting set and suppose $K \leq_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$.

  1. How can $f(K)$ be a finite set?
  2. Why if‌ $B$ is recursive, is $f^{-1}(B)$ also recursive?
  • $\begingroup$ There are no restrictions on the type of reduction? $\endgroup$ – Raphael Mar 19 '15 at 10:55

As the name suggests, a many-one reduction can map many instances of $K$ onto a single instance of $A$. If there are no restrictions on the power of $f$, then you can pick some $a\in A$ and $b\notin A$ and then define $$f(x)=\begin{cases} a &\text{ if }x\in K\\ b &\text{ if }x\notin K\,. \end{cases}$$

However, if $f$ is restricted to be computable then the image of $f$ is necessarily infinite. This is because every finite set is computable so, if the image of $f$ were finite, you'd have a computable reduction from the halting set to a computable set, which is impossible because that would mean the halting set would be computable too.

If $B$ is recursive and $f$ is computable then you can decide whether $x\in f^{-1}(B)$ just by checking whether $f(x)\in B$. If $B$ isn't recursive or $f$ isn't computable, all the bets are off.

  • $\begingroup$ @PålGD $K$ is standard notation? Maybe if everybody teaches from the same book. $\endgroup$ – Raphael Mar 19 '15 at 10:56
  • 2
    $\begingroup$ @Raphael $K$ has been used to denote the halting set since the days of Gödel and Post. Every text book on recursion theory (e.g. Soare, Rogers, Odifreddi), all use $K$ to denote this set. Post called Gödel's diagonal set, $K = \{e \mid e \in W_e\}$ the complete set because every c.e. set $W_e$ is computable in $K$ [Soare, 2009]. I think cs.sx should accept $K$ as standard notation here. $\endgroup$ – Pål GD Mar 19 '15 at 11:27
  • $\begingroup$ @PålGD I know at least $H$ (for "Halteproblem"). $\endgroup$ – Raphael Mar 19 '15 at 12:30
  • $\begingroup$ There is a main problem. $f(K)$ is an infinite set is false. how do you say " the image of f is necessarily infinite" $\endgroup$ – Homan Mar 21 '15 at 9:57
  • $\begingroup$ @PålGD, would you please help me about my last comment? $\endgroup$ – Homan Mar 21 '15 at 17:23

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.