I'm trying to learn about reductions and I came across this example in my book:
Let the "merge" of two languages L1,L2$\subset${0,1}* be:
L1$\bot$L2 = {x0 | x$\in$L1}$\cup${y1|y$\in$L2}
I think that either original language is many-one reducible to L1$\bot$L2, but I don't quite know how I would prove it.
Let $f:\{0,1\}^*\to\{0,1\}^*:x\mapsto x0$; then for any $x\in\{0,1\}^*$ we have $x\in L_1$ if and only if $f(x)\in L_1\perp L_2$, so it’s true that $L_1\le_m L_1\perp L_2$. A very similar argument shows that $L_2\le_m L_1\perp L_2$ as well.
Of course you do have to show that $x\in L_1$ if and only if $f(x)\in L_1\perp L_2$, but this isn’t hard. If $x\in L_1$, then by definition $f(x)\in L_1\perp L_2$, and if $f(x)=\in L_1\perp L_2$, then either $f(x)=y0$ for some $y\in L_1$, or $f(x)=y1$ for some $y\in L_2$. Since anything of the form $f(x)$ ends in $0$, it must be that $f(x)=y0$ for some $y\in L_1$, and clearly this implies that $x=y\in L_1$.