# Many-one-reductions with finite image

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?
• There are no restrictions on the type of reduction? – 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.
• @PålGD $K$ is standard notation? Maybe if everybody teaches from the same book. – Raphael Mar 19 '15 at 10:56
• @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. – Pål GD Mar 19 '15 at 11:27
• @PålGD I know at least $H$ (for "Halteproblem"). – Raphael Mar 19 '15 at 12:30
• There is a main problem. $f(K)$ is an infinite set is false. how do you say " the image of f is necessarily infinite" – Homan Mar 21 '15 at 9:57