Let define $A \oplus B = \{2x \mid x \in A\} \cup \{2x + 1 \mid x \in B\}$. Prove that $A \oplus B$ is recursive if $A$ and $B$ are recursive.

I am currently having the following idea.

Since $A$ is recursive, $P_A$ the characteristic of $A$ is recursive. Similarly, $P_B$ is recursive.

So, we need to show that $P_{A \oplus B}$ is recursive.

How can I define the characteristic predicate of $A \oplus B$ in term of $P_A$ and $P_B$?


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.