🚀 go-pugleaf

In a previous article, chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) says:

>A question for Recursion Theorists.
>
>If you take a partial recursive function phi and two sets I and J such that
> dom(phi) contains I and range(phi) is included in J, you can define an
> obvious set-theoretic function f:I->J.
>
>The question is: does EVERY surjective f admit a section, i.e. a g:J->I
> obtained in the same way from a partial recursive function, say psi, such
> that
>	for each j in J    f(g(j))=j       ?
>
>People-who-know will see I'm actually defining a category and asking "does
> every good (i.e surjective) epi split?"
>
>I suspect this to be false, but I can't manage to find a counter-example; the
> difficulties arise from the clumsiness of restricting arbitrarily the domain
> of a partial recursive function.
>

	Surely it is true, unless I misunderstaood the question.  Given 
sets I and J and a partial recursive psi that maps I onto J here is an
algorithm for a section g:

	to find gn for n in J, start evaluating psi for each m in I.
Of course you can not just start with the first m in I and evaluate 
psi for it, since psi might be undefined for it.  So take a few steps 
on the first element of I, then a few on the second, then a few more 
on the first, a few more on the second and a few on the third, then a
few more on the first....  This way we would eventually find the value 
of psi for each element of I where it is defined.  Since psi maps I 
onto J we will eventually finish evaluating psi on some element of I 
that gives n.  Define gn to be that element.  

	This algorithm may work for values of n not in J.  Indeed
it can not be defined precisely on J unless J is r.e.  But it is
defined for all of J.

Colin McLarty