Sets $A$ and $B$. $B$ is finite (have inite number of elements), $A$ is undecidable. Can $A$ $\cup$ $B$ be decidable?
I have and idea, but i'm not sure that it's correct.
What if $A \cup B$ is decidable. Then if $x \in N$ we can discover belogns it to $A \cup B$ or not. If yes then we need to prove that we can't discover if it's belongs to $A$. But we will start comparing $x$ with elements from $B$ and we will do that in finite amount of time because $B$ is finite. Then if $x$ not in B we can say that $x$ in A and "return 1" Seems like i have to prove that we can say that $x \notin A$. So now $A$ is decidable –
contradiction.
But i'm not sure how to prove fact that if $x \in B$ it's dont in $A$ because it may be.
I hope my thought are understandable.
Prove decidability. Sets A and B. B is finite (have inite number of elements), A is undecidable. Can $A$ $cup$ $B$ be decidable
computabilitydecidabilityturing-machines
Best Answer
The key is this: like $B$, the set $B\setminus A$ is also finite, hence decidable. Thus you can get a decision procedure for $A$ from one for $A\cup B$ as follows:
(I'll add that the fact that any finite set is decidable, no matter how complicated its definition, is often a point of a confusion. For instance the set that is $\emptyset$ if the Riemann hypothesis is true and $\{0\}$ if it is false is decidable. The thing is, we are only concerned about the existence of a decision procedure, not if we can actually determine concretely what the decision procedure actually is. We know if the Riemann hypothesis is true then there is one decision procedure (always say "no"), and if it is false, there is another decision procedure (only say "yes" if $x=0$, otherwise, say "no"), so either way, one exists, and that's good enough, regardless if we actually have any way of deciding whether the Riemann hypothesis is true or not.)