# How can $A \cup B$ be decidable if $B$ is undecidable?

My assignment says:

"Determine if the following statement is correct: If $$A$$ and $$A \cup B$$ are decidable, then $$B$$ is decidable."

The solution says:

"Incorrect. If $$B = H_0 \subseteq \{0,1\}^*$$ is the halting problem with input $$\epsilon$$ and $$A = \{0,1\}^*$$, then $$A$$ and $$A \cup B$$ are decidable and $$B$$ is undecidable.

My question is:

How can $$A \cup B$$ be decidable if $$B$$ is undecidable? If for example $$b \in B$$ then $$b \in A \cup B$$ but a Turing Machine may not halt on $$b$$ because $$B$$ is undecidable, then how can $$A \cup B$$ still be decidable with $$b \in A \cup B$$ ?

• Take $A = \{0,1\}^*$. – Yuval Filmus Sep 16 at 10:10
• If it’s not clear enough (since it was mentioned in the solution you were given): in this case A union B is decidable no matter what B is, because A = A union B = all possible strings. The Turing machine can halt immediately without caring about B at all. – gnasher729 Sep 16 at 10:37

If $$A=\{0,1\}^*$$ then $$A\cup B=\{0,1\}^*$$, regardless of what $$B$$ is. $$\{0,1\}^*$$ is decidable, and choosing to express it as something involving undecidable things doesn't change that fact.
The question "Is $$w$$ in $$A\cup B$$?" is equivalent to "Is at least one of the following statements true? $$w$$ is in $$A$$; $$w$$ is in $$B$$; $$w$$ is in both $$A$$ and $$B$$?" In the case $$A=\{0,1\}^*$$, we can answer "Yes, $$w$$ is in $$A$$" and the rest of the questions are irrelevant. It doesn't even matter if we can't answer "Is $$w$$ in $$B$$?", because we don't need to.
Here's a more practical example that might help. Suppose I give you a number $$x$$ and ask you "Is $$x\in\text{Integers}\cup\text{Primes}$$?" Figuring out if a large number is prime is quite difficult, but you can easily answer my question by checking if $$x$$ is an integer. You can ignore the "prime" part completely.