\input zb-basic
\input zb-ioport
\iteman{io-port 04041897}
\itemau{Kummer, Martin}
\itemti{The length problem for co-r.e. sets.}
\itemso{Z. Math. Logik Grundlagen Math. 34, No.3, 277-282 (1988).}
\itemab
Let $R\sb 1$ be the set of total recursive one-place functions and let Fin(M), $M\subseteq \omega$, be the set of finite functions $\delta$ whose domain is an initial segment of $\omega$ such that $\vert dom(\delta)\vert \in M$ ($\vert X\vert$ denotes the cardinality of X). A characterization is given, in terms of retraceable sets, of the co-r.e. sets L which satisfy $R\sb 1\cup Fin(L)$ r.e. Namely, it is proved that if A is r.e., then $R\sb 1\cup Fin(A\sp c)$ is r.e. iff every r.e. and co-retraceable subset of A is recursive. This extends an earlier result of {\it J. Mohrherr} (unpublished) and gives a partial solution to the ``length problem'' of {\it V. Sperschneider} [Lect. Notes Comput. Sci. 171, 88-102 (1984; Zbl 0544.03018)]. Further, it is shown that the class of co-r.e. sets L satisfying $R\sb 1\cup Fin(L)$ r.e. is recursively invariant. Some corollaries on r.e. co-retraceable/-regressive sets follow easily.
\itemrv{M.Kummer}
\itemcc{}
\itemut{r.e. families of partial recursive functions; retraceable sets; co-r.e. sets}
\itemli{doi:10.1002/malq.19880340311}
\end