🚀 go-pugleaf

In article <1992Sep29.161016.19533@ghost.dsi.unimi.it> chinnici@ghost.dsi.unimi.it (roberto riccard chinnici) writes:
>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.

Thanks for the nice problem.  If I is recursively enumerable, there is
such a section.  In general, there is not, by the following finite-injury
priority argument.

Let f be the left projection function for some pairing function.
Let J be the set of natural numbers.

Note: the range of f is N, so the range of any section of f must be infinite.

We construct I by deleting elements from N; note that this makes I co-r.e.
In the construction, we will refer to certain requirements R_i:

R_i: range phi_i is finite or there is y in N such that phi_i(y) not in I.

We will also restrain some numbers into I for certain requirements.  These
restraints can be broken for higher-priority (lower-numbered) requirements,
but the standard finite-injury argument will establish that every requirement
gets met.

Stage s:
   Search for s steps for i such that requirement i is not met, and there
   are x,y such that phi_i(x) = y, f(y)=x, and y is not held in I for any
   requirement i'<i.  Let i0 be the least i so found; let x0 and y0 be
   corresponding values of x and y.

   Delete y from I.
   Find y'>y, not yet deleted from I (there will always be such), and
   restrain y' into I for requirement i0.

   Mark requirement i0 as being met.
   Unmark all requirements i with i>i0.
End state s.

I will leave the verification up to the reader.  The basic structure of
the proof is that every requirement will be met, either by default
(phi_i has finite range) or by being met in the construction.  The
latter will happen to each requirement at most a finite number of times
(2^(i-1) will do it).  Then note that meeting every requirement is enough
to establish that f|I has no section.

Mark
-- 
Mark A. Fulk			University of Rochester
Computer Science Department	fulk@cs.rochester.edu