Abstract:
If $\nu_0$ and $\nu_1$ are two numerations of the set $S$, then $\nu_0$ will be said to be $e$-reducible to $\nu_1$ provided there exists an enumeration operator $\Phi$ such that ($\forall s\in S$) $[\nu_0^{-1}(s)=\Phi(\nu_1^{-1}(s))]$.
In this paper both $e$-reducibility and upper semilattices of $e$-equivalent computable families of recursively enumerable sets are studied. Some of these semilattices admit an elegant description; for others sufficient conditions are found in order that they have an $e$-principal numeration or be countable.
Bibliography: 7 titles.
Fulltext:
PDF file (729 kB)
