2
$\begingroup$

I'm working on the following problem from Soare: If $A$ is one-reducible to $B$ ($A \leq_1 B$) and $A, B$ c.e., $A$ infinite then $A$ is one-reducible to $B$ via some $f$ such that $f(A)=B$.

I know $A \leq_1 B$ if there's a total computable 1-1 function $f$ such that $\forall x (x\in A \; \text{iff} \; f(x) \in B)$. So I suppose that $A \leq_1 B$ via a function $g$. Now I need to extend $g$ to $f$ so that it's onto.

Any hint?

1 Answers 1

2

You would want to build the extended function $f$ inductively, using $g$ as a parameter. Intuitively: $B$ is c.e., so we can watch for more elements to appear in $B$ over time. and $A$ is c.e. and infinite, so if we have only looked at a finite piece of $A$ so far, we can always effectively enumerate a new element of $A$. So we start imitating $g$, but whenever a new element of $B$ appears we temporarily pause imitating $g$ to enumerate a new element of $A$ and send it to that new element of $B$.

The construction goes by stages. At each stage $i$ we have already made a function $f_i$ with finite domain $D_i$; in the end we will let $f = \bigcup f_i$ and we will have $\mathbb{N} = \bigcup D_i$. At each stage $i$ we have also already made a finite subset $B_i$ of $B$ and a finite subset $A_i$ of $A$. Let $A_0 = B_0 = D_0 = f_0 = \emptyset$.

At stage $i$ we first enumerate $B$ for $i$ steps. If this gives a new element $b \in B \setminus B_i$, we put $b \in B_{i+1}$, we enumerate a new element $a \in A \setminus (D_i \cup A_i)$ and put $a \in A_{i+1}$, and we let $f_{i+1}(a) = b$. After that, or if there is no such $b$, we then ask whether $i \in D_{i}$. If it is not, we let $f_{i+1}(i) = g(i)$, so that $i \in D_{i+1}$. Then we go on to stage $i+1$.

The function $f = \bigcup f_i$ is computable because $f(i)$ is determined no later than stage $i$ and because the construction at each stage is computable. The construction guarantees that $f$ is a function, is onto $B$, and is a 1-reduction from $A$ to $B$.