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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.