# A,B decidable: proof that A\B is decidable too

For an assignment I have to proof that for two given decidable languages A,B, A\B is decidable too.

My idea is as follows: If B is empty or doesnt have elements in common with A, then A\B is decidable because A\B=A.

If B is not empty and intersects with A, A\B is just a smaller subset of A and therefore decidable.

I have a feeling that this is either the wrong idea or not formalized enough. I would really appreciate any hints regarding that.

EDIT: A subset of a decidable language is NOT always decidable too, this was a misconception.

• Why do you think a subset of a decidable language is still decidable? Nov 10 '18 at 11:01
• This is obviously a misconception, thanks for pointing that out. That leaves me with no useful approach to this assignment though. Can you point me in the right direction? Nov 10 '18 at 11:07
• You can try to make use of the fact that $B$ is decidable. Nov 10 '18 at 11:26
• I can't think of any way to utilize that. Can you elaborate? Nov 10 '18 at 11:33

Let $$M_A$$ and $$M_B$$ be deciders for $$A$$ and $$B$$ respectively. You can construct a TM $$M$$,

$$M$$ = "On input x,

$$\qquad$$ 1. Simulate $$M_A$$ on x.

$$\qquad$$ 2. Reject if $$M_A$$ rejects. Else simulate $$M_B$$ on x.

$$\qquad$$ 3. Accept if $$M_B$$ rejects. Else reject."

$$Correctness$$:

$$\qquad$$ $$M$$ always halts as $$M_A$$ and $$M_B$$ always halts. $$M$$ accepts if $$M_A$$ accepts and $$M_B$$ rejects i.e, $$x \in A$$ and $$x \notin B$$. $$M$$ rejects otherwise.