# Is there a mapping reduction for every two language $A$ and $B$ to some language $C$?

One of my friend told me that there is a language $$C$$ for every two languages $$A$$ and $$B$$ s.t $$A \leq_{m} C$$ and $$B \leq_{m} C$$ , he simply define two languages $$A’=\{0w|w \in A\}$$ and $$B’=\{1w|w \in B\}$$ so $$C=A’ \cup B’$$ and he define the function $$f(w)=0w$$ if $$w \in A$$ and and $$f(w)=1w$$ otherwise. I suspect this function is turing-computable. Suppose $$A$$ be $$\overline{HP}$$ which is not RE. How we can decide if $$w \in A$$ ? Even i ask myself can we realy prove that such a mapp-reduction always exist ?

• The reduction always exists – you just defined it. May 18, 2021 at 21:52
• @YuvalFilmus But how f(w) decide that is w member of A or not ? Is that computable to check membership of w in arbitary language A ? May 18, 2021 at 21:55

We actually need to define two reductions: from $$A$$ to $$C$$ and from $$B$$ to $$C$$. The reduction from $$A$$ to $$C$$ maps $$w$$ to $$0w$$. The reduction from $$B$$ to $$C$$ maps $$w$$ to $$1w$$.