Show that $B$ is decidable

Question

Let $A$ and $B$ be semi decidable languages. Moreover, $A \cup B$ and $A \cap B$ are decidable. I want to show that $B$ is decidable.

Firstly, I would like to know if the following approach works:

First, we can check if $w \in A \cup B$. Since this is decidable, we know that either $w \in A$ or $w \in B$. Now, I wanted to argue that, since $A$ is semi-decidable, so is $A^c$, where $A^c$ is the complement of $A$. Then $A^c \cap B$ is also decidable and wen can simply check if $w \in A^c \cap B$, but I am not sure if that is correct?

Answer 1

"First, we can check if $w \in A \cup B$. Since this is decidable, we know that either $w \in A$ or $w \in B$."

I am failing to understand your proof right here.

• By the definition of "decidable", we know that there is a Turing machine that upon input $w$, it will always run to a halt, telling whether $w\in A\cup B$ or not. That is vastly different from "either $w\in A$ or $w\in B$".
• It should be allowed/possible that $w\not \in A\cup B$.

---

Here is an approach to prove. Instead of reasoning on the level of each input to a Turing machine, let us reason on the level of semi-decidability and decidability.

The conditions are

1. $A=(A\setminus B)\sqcup (A\cap B)$ is semi-decidable
2. $B$ is semi-decidable
3. $A\cap B$ is decidable
4. $(A\cup B)^c$ is decidable

Condition 1 and condition 3 imply

5. $A\setminus B$ is semi-decidable.

Condition 4 and condition 5 imply

6. $B^c = (A\cup B)^c \cup (A\setminus B)$ is semi-decidable.

Condition 2 and condition 6 imply $B$ is decidable.

---

Exercise (provided by Johannes Kloos). Let $A$ and $B$ be semi-decidable languages such that both $A\cup B$ and $A\cap B$ are co-semi-decidable languages. Show that $B$ is decidable.