Recursive Set in Partial Computable Function Problem

Question

Suppose $A, B, C$ are disjoint set such as shown on this figure. $f_1(x), f_2(x), f_3(x)$ is partially computable function.

why $A,B,C$ is recursive set?

Answer 1

Run $f_1, f_2, f_3$ in parallel.

• If $x \in A$ then $f_1(x) = 1$ and $f_3(x) = \circ$.
• If $x \in B$ then $f_1(x) = 1$ and $f_2(x) = \circ$.
• If $x \in C$ then $f_1(x) = 2$.
• If $x \notin A \cup B \cup C$ then $f_2(x) = f_3(x) = \circ$.

Therefore after a finite amount of time you will be able to distinguish the four cases.

Answer 2

Ok I am assuming the up arrow means that the computation diverges and that the tiny circle is a zero. All sets are recursive. From the functions we have enumerations of $C$ and $A\cup B$ (from $f_1$), enumerations of $\neg (A\cup C)$ and $\neg (B\cup C)$, the complements.

If $n$ is iin $A$ it will occur in the enumeration of $A\cup B$ and the enumeration of $\neg (B\cup C)$, all such common elements are in $A$. If $n$ is not in $A$ it will occur in the list of $C$ or $\neg (A\cup C)$.

A similar situation holds for $B$.

For $C$ if an element is in the list of $C$, then its in $C$, if $n$ is not in $C$ it occurs on one of the lists of $\neg (A\cup C)$ or $\neg (B\cup C)$.

Answer 3

Just write down what each of your $f_i$ functions does to each kind of input:

$$\begin{array}{r|ccc} x & f_1(x) & f_2(x) & f_3(x) \\ \hline \in A & 1 & \uparrow & 0 \\ \in B & 1 & 0 & \uparrow \\ \in C & 2 & \uparrow & \uparrow \\ \notin(A\cup B\cup C) & \uparrow & 0 & 0 \end{array} $$

So if you have an unknown input, just run all of $f_1$, $f_2$ and $f_3$ on it in parallel until either two of them have halted, or $f_1$ returns $2$. One of these will always happen, and what you know at that time will allow you to know exactly which line of the table you're in.