0
$\begingroup$

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

$\endgroup$
  • 1
    $\begingroup$ What have you tried? What do you know so far? $\endgroup$ – Thomas Andrews Sep 23 '20 at 12:45
  • $\begingroup$ @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. $\endgroup$ – Michael Palich Terentev Sep 23 '20 at 12:53
  • $\begingroup$ Well, what does it mean to show that $A$ is decidable? $\endgroup$ – Thomas Andrews Sep 23 '20 at 12:54
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Sep 23 '20 at 12:58
  • 1
    $\begingroup$ This is wrong. You need stronger hypotheses, namely, that $A$ and $B$ are computably enumerable. $\endgroup$ – bof Sep 23 '20 at 13:26
2
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – bof Sep 23 '20 at 13:23
  • $\begingroup$ @bof Can you please explain why this doesn't works? I'm new in theory of computability and e.t.c $\endgroup$ – Michael Palich Terentev Sep 23 '20 at 13:30
  • $\begingroup$ @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? $\endgroup$ – Leo163 Sep 23 '20 at 14:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.