# Relation between sets and partially computable functions

I encountered this problem.

Let $A$ , $B$ , $C$ be disjoint sets $(A\cap B = B\cap C = A\cap C = \emptyset)$. The $f_1, f_2$ and $f_3$ are partially computable functions that are defined as follow:

$$f_1(x) = \begin{cases} 1 & x \in A\cup B \\ 2 & x \in C \\ \uparrow & \text{otherwise.} \end{cases}$$

$$f_2(x) = \begin{cases} \uparrow & x \in A\cup C \\ 0 & \text{otherwise.} \end{cases}$$

$$f_3(x) = \begin{cases} \uparrow & x \in B\cup C \\ 0 & \text{otherwise.} \end{cases}$$

Then which of the following is true?

1. $A,B,C$ are recursive.
2. $A,B,C$ are not r.e.
3. $A,B,C$ are r.e. but not recursive.
4. $C$ is recursive but $A,B$ are not recursive.

I really don't know how to understand what kind of sets the $A,B,C$ are! what information $f_1,f_2,f_3$ are giving us about the sets?

The problem only makes sense if $A,B,C \subseteq \mathbb{N}$ and you are to assume that the $f_i$ are partially computable functions.

Your task is to check the definitions of (semi)-decidability and show resp. refute that $A$, $B$ and $C$ fulfill them.

• The right answer is option 1 but I don't know why! This is Ph.D. Entrance Examination – M a m a D Dec 14 '14 at 11:40
• @Drupalist Check if you can construct $\chi_A$, $\chi_B$ and $\chi_C$ from the $f_i$. – Raphael Dec 15 '14 at 11:57

As you said yourself, 1 is true.

To decide one of the languages, you let Turing machines or some other model of computation of all the functions run in parallel. You do so until one of the following happens:

1. $f_1$ halts with output 2: $x \notin A, x \notin B, x \in C$
2. $f_1$ halts with output 1 and $f_2$ halts: $x \notin A, x \in B, x \notin C$
3. $f_1$ halts with output 1 and $f_3$ halts: $x \in A, x \notin B, x \notin C$
4. $f_2$ and $f_3$ halt: $x \notin A, x \notin B, x \notin C$

One of these cases must happen at some point. Therefore, this algorithm decides A, B and C.

• Thanks. It is the way I justify the answer: Set $A$ is recursive if and only if $x \in A$ is computable. Since we can decide whether $x \in A$ or $x \in B$ or $x \in C$ then $A,B,C$ are recursive. is it true? – M a m a D Jan 11 '15 at 4:35
• Yes, though have to be careful about the wording of your solution: "I can decide $x \in A$ or $x \in B$ or $x \in C$" sounds like "I can decide $x \in A \cup B \cup C$. To avoid ambuguity one should say something like "I can decide whether x \in A, and whether x \in B, ...\$. But that is just formalism, the difficulty of that problem is finding the algorithm to decide the three sets. – Andreas T Jan 11 '15 at 12:55