# Prove the decidability of an enumerable set. A and B are enumerable, C is decidable.

Sets A and B are enumerable, C is decidable. $$A$$ $$\subseteq$$ $$C$$ $$\subseteq$$ $$A$$ $$\cup$$ $$B$$. $$A$$ $$\cap$$ $$B$$ = $$\emptyset$$.Prove that A is decidable too

• What have you tried? What do you know so far? – Thomas Andrews Sep 23 '20 at 12:45
• @ThomasAndrews it's quite hard to answer your question. It's a new field of math to me. It started in my university 3 weeks ago, so we don't know hard theorems. Some basic facts anddefinitions. – Michael Palich Terentev Sep 23 '20 at 12:53
• Well, what does it mean to show that $A$ is decidable? – Thomas Andrews Sep 23 '20 at 12:54
• And what does enumerable mean? Put these in the question. I know for sure that decidable has two (equivalent) definitions, and the answers people give will be different depending on which definition is used. – Thomas Andrews Sep 23 '20 at 12:58
• This is wrong. You need stronger hypotheses, namely, that $A$ and $B$ are computably enumerable. – bof Sep 23 '20 at 13:26

Here is an algorithm to determine if a number $$n$$ is in $$A$$ or not. First of all, ask if $$n\in C$$: if $$n\not\in C$$, then $$n\not\in A$$ since $$A\subseteq C$$. If instead $$n\in C$$, we proceed as follows: we ask at the same time if $$n\in A$$ and if $$n\in B$$. Notice that this question will be answered in a finite amount of time, since $$C\subseteq A\cup B$$, and exactly one of the two questions will have positive answer, since $$A\cap B=\emptyset$$. Hence, $$A$$ is decidable.
• The OP did not say that $A$ and $B$ are recursively (or "computably") enumerable, only that they are "enumerable", so I don't think this works. – bof Sep 23 '20 at 13:23
• @bof you're right, I answered assuming that what the OP meant was that $A$ and $B$ are computably enumerable, since this would then become a fairly standard exercise about basic computability theory. Michael, can you please clarify what you mean by enumerable? – Leo163 Sep 23 '20 at 14:27