Does "defined by cases" only work for decidable sets or also for semi-decidable sets?

Question

If $A,B\subseteq\mathbb{N}$ are disjoint decidable sets then it is clear to me that the function $f$ is defined as:

$f\left(x\right)=\begin{cases} 1 & \text{if }x\in A\\ 2 & \text{if }x\in B\\ \text{undefined} & \text{otherwise} \end{cases}$

is partial recursive.

This can be proved on base of the fact that the characteristic functions of $A$ and $B$ are total recursive functions.

Now I wondered:

What if $A$ and $B$ are not decidable but semi-decidable?

Intuitively I thought of procedures $a$ and $b$ that would eventually confirm (by halting) for $x\in\mathbb{N}$ that $x\in A$ and $x\in B$ respectively.

Letting them work side-by-side on input $x$ the following things can happen:

• $a$ halts and we conclude that $f\left(x\right)=1$
• $b$ halts and we conclude that $f\left(x\right)=2$
• Both do not halt so that $f\left(x\right)$ stays undefined.

However I failed to make this formal by means of functions or codes of functions.

My questions are:

• Is $f$ partial recursive if $A$ and $B$ are both semi-decidable?

• If so then how to prove it formally?

• If not then what is wrong with my intuition?

Thank you for taking notice of this question and sorry if it turns out to be a duplicate.

Answer 1

A partial function $f$ is partial recursive if there is a computational process, $F$ say, (e.g., a Turing Machine) that given an input $x$ to $f$ will always terminate if $x$ is in the domain of $f$ and, if that is so, $F$ will give the right value of $f(x)$.

In your case, you know that the two sets $A$ and $B$ are disjoint and semi-decidable. That means that there are computational processes $a$ and $b$ such that given an input $x \in A$, $a$ will terminate and $b$ will not and such that given an input $x \in B$, $b$ will terminate and $a$ will not. (Given an input that is not in $A \cup B$, both $a$ and $b$ will fail to terminate.)

Now you can come up with the desired computational process $F$: given an input $x$, $F$ should interleave a run of $a$ and a run of $b$ on input $x$. If $x \in A \cup B$, then exactly one of these runs will terminate and will tell $F$ whether $x$ is in $A$ or $B$. If $x \not\in A \cup B$, then $F$ will never terminate - and that is fine given our requirements on $F$.

Answer 2

Inspired by the comment of Rob Arthan I found this solution myself.

---

Let $G(x)$ and $H(x)$ denote the functions prescribed by:

$G\left(x\right)=\begin{cases} 1 & \text{if }x\in A\\ \text{undefined} & \text{otherwise} \end{cases}$

$H\left(x\right)=\begin{cases} 2 & \text{if }x\in B\\ \text{undefined} & \text{otherwise} \end{cases}$

Then both functions are partially recursive hence have codes.

Let $g$ be a code for $G$ and let $h$ be a code for $H$.

If $T(e,x,t)$ stands for Kleene's primitive recursive predicate for functions with domain $\mathbb N$ and $U$ is the primitive recursive function that provides the output of a computation $t$ we have:$$f(x)\simeq U(\mu t.[T(g,x,t)\vee T(h,x,t)])$$

From this it can be concluded that $f$ is a partial recursive function.