Myhill's isomorphism theorem for creative sets

Every c.e. set one-one reduces to $K$. If $C=W_e$, let $m_e(x)$ be the code of a machine that ignores its actual input, enumerates $W_e$, and halts exactly when $x$ appears. Add to its finite description an unreachable chain of states whose length encodes $x$. This does not change its behaviour, and the fixed injective machine coding makes $x\mapsto m_e(x)$ total computable and one-one. Thus $x\in C⟺m_e(x)\in K\mathrm{.}$

Let $C$ be creative, put $P=\mathbb{N}\setminus C$, and choose a normalized total one-one productive function $p$ from [L1]. The fixed coding supplies a total computable padding map $\mathrm{pad}(e,y)$: it builds a machine simulating program $e$ and adds an unreachable state chain encoding the pair $(e,y)$. Hence ${\phi }_{\mathrm{pad}(e,y)}={\phi }_e$, and $\mathrm{pad}$ is one-one in the pair. Apply [L3] to the transformer that, from $(y,e)$, returns an index whose domain is $\{p(\mathrm{pad}(e,y))\}$ if program $y$ halts on $y$, and is empty otherwise. We obtain a total computable $q$ satisfying this fixed-point equation. Put $n(y):=\mathrm{pad}(q(y),y),g(y):=p(n(y))\mathrm{.}$ Then $n$, and therefore $g$, is one-one, and padding gives $W_{n(y)}=W_{q(y)}=\{\begin{array}{ll}\{g(y)\},& y\in K,\\ \mathrm{\varnothing },& y\mathrm{\notin }K\mathrm{.}\end{array}$ If $y\in K$ and $g(y)\in P$, productivity applied to $W_{n(y)}\subseteq P$ would force $g(y)\mathrm{\notin }{W}_{n(y)}$, a contradiction. If $y\mathrm{\notin }K$, then $W_{n(y)}=\mathrm{\varnothing }\subseteq P$, so productivity gives $g(y)\in P$. Therefore $y\in K⟺g(y)\in C,$ and $g$ is a one-one computable reduction $K{\le }_{1}C$.

Applying step 1.1 to $A$ and then step 1.2 to $B$ gives a one-one reduction $A{\le }_{1}B$ by composition. Reversing the roles of $A$ and $B$ gives $B{\le }_{1}A$.

Let $f$ witness $A{\le }_{1}B$ and let $g$ witness $B{\le }_{1}A$. Build finite membership-preserving partial bijections $h_s$ by stages. At a domain stage, choose the least $x\mathrm{\notin }\mathrm{dom}{h}_s$ and start with $y_0=f(x)$. While $y_i\in \mathrm{rng}{h}_s$, set $x_{i+1}=h_s^{-1}(y_i)$ and $y_{i+1}=f(x_{i+1})$. This search must leave the finite range: otherwise a repeated $y_i$ and injectivity of $f$ would eventually put the original unused $x$ in $\mathrm{dom}{h}_s$. Pair $x$ with the first unused $y_i$. Each passage through $f$ and $h_s^{-1}$ preserves and reflects membership, so the new pair does too.

At the alternating range stage, choose the least $y\mathrm{\notin }\mathrm{rng}{h}_s$ and start with $x_0=g(y)$. While $x_i\in \mathrm{dom}{h}_s$, set $y_{i+1}=h_s(x_i)$ and $x_{i+1}=g(y_{i+1})$. The symmetric injectivity argument finds an unused $x_i$ after finitely many steps. Pair that $x_i$ with $y$; again all traversed maps preserve and reflect membership. Thus every stage effectively extends the finite membership-preserving partial bijection.

Let $h:={\bigcup }_s{h}_s$. The alternating least-unused choices put every natural number eventually into both its domain and range, so $h$ is a bijection. It is computable because, on input $x$, one simulates stages until $x$ is paired. Every stage preserves $x\in A⟺h(x)\in B$, hence this equivalence holds for all $x$.

So $h$ is a computable permutation sending $A$ onto $B$. Taking $B=K$ and using [L2] gives the final clause.