# Given three languages L1 L2 L3 that do not intirsect could one be TR and the other TD and the third neither

where $L_{1} \cup L_{2} \cup L_{3} = \sum^{*}$ and

$L_{1} \cap L_{2} = \emptyset$ and $L_{2} \cap L_{3} = \emptyset$ and $L_{1} \cap L_{3} = \emptyset$

is it possible that $L_{1}$ is decidable, $L_{2}$ is recognizable but not decidable

and $L_{3}$ is not recognizable?

If so please give an example, if not why?

By recognizable I mean Turing Recognizable.

To make things a little easier (I think!) I have reached a conclusion that it is very much possible, I only can't think of an example of such 3 languages.

• Although the question has been answered already, you should give your post a better title. The current one is not even a bad title, it is not a title at all. Second, 2 of 3 tags you chose for your question are not related at all to your question. Last, use \emptyset instead of \phi if you want an emptyset symbol. – ttnick Mar 10 '18 at 14:08

Is is indeed possible.

Consider the halting problem set $$H = \big\{ \big(\langle M \rangle, w\big): M \big( w \big) \space halts \big\}$$

and its complement $$\overline{H} = \big\{ \big(\langle M \rangle, w\big): M \big( w \big) \space doesn't \space halt \big\}$$

We know that H is recognizable and not decidable. That means that $$\overline{H}$$ is not recognizable because, otherwise, H would be decidable.

Now take $$L_1 = \emptyset \space \big( decidable \big)$$ $$L_2 = H \space \big( recognizable \space and \space not \space decidable \big)$$ $$L_3 = \overline{H} \space \big( not \space recognizable \big)$$

We have that $$L_1 \cup L_2 \cup L_3 = \Sigma^*$$ and $$L_1 \cap L_2 = L_2 \cap L_3 = L_1 \cap L_3 = \emptyset$$

• I think you are right on the money, except for this little issue I'm having. How do you know $\phi$ is not in H or it's complement? – Anwar Saiah Mar 10 '18 at 14:07
• If it is in H then $$H \cap L_1 = L_1 = \emptyset$$ as wanted. Same applies to $$\overline{H}$$ So it doesn't really matter where it is. – Kyrylo Yefimenko Mar 10 '18 at 14:14
• I have another open question could you take a look at it, cs.stackexchange.com/questions/88803/… – Anwar Saiah Mar 10 '18 at 14:51
• @KyryloYefimenko Do you assume that all strings are of the form $\big(\langle M \rangle, w\big)$, or is $L_1$ actually the set of strings that do not code a TM with its input? – Hendrik Jan Mar 11 '18 at 1:31