# Show that a set is reducible to another set

Consider an operator $$+$$ defined on $$P(\mathbb{N})$$ as follows

$$A + B = \{2x:\ x\in A\}\cup\{2x + 1:\ x\in B\}$$ Show that $$A$$ is $$m$$-reducible to $$A+B$$ and $$B$$ is $$m$$-reducible to $$A+B$$

As per the definition of reducibility $$B$$ is reducible to $$A$$ if there exists a total computable function $$f$$ such that for all $$x\in \mathbb{N}$$ $$x\in B \iff f(x) \in A$$

My Thoughts:

So, here given any two sets $$A$$ and $$B$$ I have to show that $$A$$ is reducible to $$A+B$$. That means that I have to come up with a function $$f$$ such that for all $$x\in\mathbb{N}$$ $$x\in A \iff f(x)\in A+B$$ If I take the function $$f(x) = 2x$$, then if $$x$$ is in $$A$$ then $$f(x)$$ is in $$A+B$$. And if $$f(x)$$ is in $$A+B$$ then $$f(x)$$ must be $$= 2y$$ for $$y\in A$$.

This looks like a correct argument to me, but I am not sure if there are any flaws in it.

• You have a complete argument in the answer. I'm not sure what you're asking. We're not here to grade your homework. – Yuval Filmus Mar 31 at 7:19
• I was not sure if the approach is correct. As I am doing it first time – Amit wadhwa Mar 31 at 10:09
• You should trust yourself more. The goal in mathematics is to reach a situation where you are able to recognize a correct mathematical argument. – Yuval Filmus Mar 31 at 10:28
• Haha yes sure thanks for the advice – Amit wadhwa Mar 31 at 10:32