# How to prove that the reduction relation is not symmetric

I know that the reduction relation is not symmetric. Writing formal proofs is the main core of the course I take on Theory of Computation. So I'm trying to prove that theorem. For that I need to show two languages $$L_{1},L_{2}$$ so $$L_{1}\leq L_{2}$$ and $$L_{2}\not\leq L_{1}$$. My textbook suggests to use $$L_{1}\triangleq\Sigma^{*}$$ and $$L_{2}\triangleq HP$$ and show that $$L_{1}\leq L_{2}$$ and $$L_{2}\not\leq L_{1}$$. So I need to split the proof into two sections:

• Prove $$L_{1}\leq L_{2}$$ - Stuck. Not sure how to prove it formally.
• Prove $$L_{2}\not\leq L_{1}$$. I want to use that $$HP\not \in R$$. So lets assume by contradiction that $$HP\leq\Sigma^{*}$$. This means there such function $$f\,:\,\Sigma^{*}\to\Sigma^{*}$$ between $$HP$$ and $$\Sigma^*$$. How to continue?

The definition of reduction: Given two languages $$L_1$$ and $$L_2$$, we say that there is reduction from $$L_1$$ to $$L_2$$ (and mark $$L_1\leq L_2$$) if there is a function $$f\,:\,\Sigma^{*}\to\Sigma^{*}$$ so:

• $$f$$ is full - for each $$x\in \Sigma^*$$ there is one $$y\in \Sigma^*$$ so $$f(x)=y$$.
• $$f$$ can be computed - there is a Turing machine that can compute $$f$$.
• fulfils: $$x\in L_1$$ iff $$f(x)\in L_2$$.

As formality is important, how do I fill the blank spaces up to the full proof?

In order to show that $$L_1 \leq L_2$$, we need to come up with a computable function $$f$$ such that $$x \in L_1$$ iff $$f(x) \in L_2$$. Since $$L_1 = \Sigma^*$$, every $$x$$ satisfies $$x \in L$$, and so we need to find a computable function $$f$$ such that $$f(x) \in L_2$$ for all $$x$$. The easiest way to satisfy this is to choose $$f$$ to be a constant function.
In order to show that $$L_2 \not\leq L_1$$, we need to show that $$f$$ is a computable function that it is not the case that $$x \in L_2$$ iff $$f(x) \in L_1$$. That is, we need to show that for every computable $$f$$ there exists $$x$$ such that it is not the case that $$x \in L_2$$ iff $$f(x) \in L_1$$. Since $$L_1 = \Sigma^*$$, we always have $$f(x) \in L_1$$, so the only way in which "$$x \in L_2$$ iff $$f(x) \in L_1$$" can fail is if $$x \notin L_2$$. That is, we need to show that for every computable $$f$$ there exists $$x$$ such that $$x \notin L_2$$. The goal doesn't involve $$f$$, so it suffices to show that there exists $$x$$ such that $$x \notin L_2$$.
• For the first part: how to prove that if $f(x)=1$ then $x\in \Sigma^*$ iff $f(x)\in HP$? May 15, 2021 at 14:29