Showing the "converse" of a relation is semirecursive.

Question

I feel that I intuitively understand why this statement is correct, and I "think" I can explain it, but I don't know how to make it rigorous. I will show the problem, explain what I think the intuition is, attempt to show my a proof.

Problem: Let $R$ be semirecursive. Then, the converse of $R$, given by $$S(x,y)\iff R(y,x)$$ is semirecursive.

Expination: $R$ is semirecursive, so we can say $\exists t_0,Q(y,x,t_{0})$ where $Q$ is the relation that tells us whenever $(y,x)\in R$ in $t_{0}$ steps. Now, there is some $t_{1}$, where either $t_{1}<t_{0}$ or $t_{1}>t_{0}$, such that $W(x,y,t_{1})$ where $W$ is the relation that tells us whenever $(x,y)$ is in some set $S$. Hence, $S$ is semi recursive.

I have two other problems that are due that are similar to this one, so I want to make sure I can answer this one before I work on the others. Any help with clarifying some things that I may have gotten confused, or an alternative solution with an explanation would be much appreciated! Thank you!

Answer 1

Recall that $R(x,y)$ is semirecursive iff

$R(x,y) \leftrightarrow \exists z \ Z(x,y,z)$

for $Z$ recursive [see BBJ, page 81].

Then we have that the converse $S$ of $R$ is defined by :

$S(x,y) \leftrightarrow R(y,x) \leftrightarrow \exists z Z(y,x,z) \leftrightarrow \exists z \ Cn[Z, id_2^3(x,y,z), id_1^3(x,y,z), id_3^3(x,y,z)]$

[see page 64 for the projection functions and the composition operator $Cn$].