Show that $B$ is decidable 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?
 A: "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

*

*$A=(A\setminus B)\sqcup (A\cap B)$ is semi-decidable

*$B$ is semi-decidable

*$A\cap B$ is decidable

*$(A\cup B)^c$ is decidable

Condition 1 and condition 3 imply


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

Condition 4 and condition 5 imply


*$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.
