Are there languages $L_1$, $L_2$ such that such that $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ and two other languages such that $$L_1 \cap L_2 \leq_m\, L_1 \cup L_2?$$ And if so, what are they? How can i go about finding these?
$\begingroup$
$\endgroup$
$\begingroup$
$\endgroup$
How about taking $L_1=L_2$? Then we will have both $L_1 \cup L_2\leq_m\, L_1\cap L_2$ and $L_1 \cap L_2 \leq_m\, L_1 \cup L_2$.
If you want to have $L_1\not= L_2$, you just try $L_2=L_1\cup\{w\}$, where $w$ is a string not in $L_1$.
If you are determined to have infinity elements in both $L_1\setminus L_2$ and $L_2\setminus L_1$, try $L_1=L\cup aL$ and $L_2=L\cup bL$, where $L$ is an infinite language over $\Sigma$ and $a,b$ are two new symbols not in $\Sigma$.
By now, you should be able to see that there are lots of way to construct examples that satisfy the requirements.
-
$\begingroup$ My bad, it should be $$L_1 \cup L_2\leq_m\, L_1\cap L_2,$$ not $$L_1 \cup L_2\leq_m\, L_2\cap L_2,$$ but i like your solution, any solution for the edited one? $\endgroup$ – Karlberg Jun 10 '19 at 16:50
-
$\begingroup$ The same solution works. In fact, I did not notice it was $L_2\cap L_2$ when I wrote the answer. $\endgroup$ – John L. Jun 10 '19 at 16:51
