Poly-time reduction is not antisymmetric Lemma. (Transitivity) &quot;$\leq_p$&quot; is a transitive relation on languages, i.e., if $L_1 \leq_p L_2$ and $L_2 \leq_p L_3$, then $L_1 \leq_p L_3$.
Proof. By definition, there are poly-time functions $f$ and $g$ such that $x \in L_1 \Leftrightarrow f(x) \in L_2$ and $y \in L_2 \Leftrightarrow g(y) \in L_3$, thus $x \in L_1 \Leftrightarrow f(x) \in L_2 \Leftrightarrow g(f(x)) \in L_3$. Obviously, $g(f(\cdot))$ is poly-time (since $|f(x)|$ is polynomial in $|x|$).

This lemma proves that &quot;$\leq_p$&quot; is transitive, but how would I prove that it is not antisymmetric?
By definition, a relation $R$ is antisymmetric if $aRb$ and $bRa$ implies $a=b$. Therefore, to show that $R$ is not antisymmetric, we have to find $a \neq b$ such that $aRb$ and $bRa$.

Specializing this to your case, you have to find two different languages $L_1 \neq L_2$ such that $L_1 \leq_p L_2$ And $L_2 \leq_p L_1$. Finding a pair of such languages isn't too challenging, so I leave it to you.