World's most popular travel blog for travel bloggers.

# [Solved]: (Un)Decidability of disjoint decidable and undecidable sets

, ,
Problem Detail:

I thought of this question today: given are a decidable set \$A\$ and undecidable set \$B\$ for which \$A \cap B = \emptyset\$. Is \$A \cup B\$ decidable or undecidable?

I am almost sure that it is undecidable but cannot come up with an argument/proof as to why, or even a counterexample.

#### Answered By : Yuval Filmus

Hint: Suppose you could decide \$A \cup B\$. Using an algorithm for deciding \$A\$ and an algorithm for deciding \$A \cup B\$, can you decide \$B = (A \cup B) \setminus A\$?