Positive numerations of families with one-valued numerations (Q1062050): Difference between revisions

A result in the theory of numerations of families of recursively enumerable sets is proved. To state the main result, some definitions are necessary. A numeration \(\nu\) :\({\mathbb{N}}\to S\) of a family S of r.e. sets is computable if \(\{\) (x,n): \(x\in \nu (n)\}\) is r.e. - equivalently if there is a recursive function g:\({\mathbb{N}}\to {\mathbb{N}}\) for which \(\nu (n)=W_{g(n)}\) for all n. A numeration \(\nu\) is reducible to numeration \(\mu\), \(\nu\leq \mu\), if there is a recursive function f:\({\mathbb{N}}\to {\mathbb{N}}\) for which \(\nu =\mu f\); \(\nu\) is equivalent with \(\mu\) if \(\nu\leq \mu\) and \(\mu\leq \nu\). A computable numeration \(\nu\) is minimal if \(\mu\leq \nu\) implies that \(\nu\leq \mu\) for every computable \(\mu\) ; \(\nu\) is smallest if \(\nu\leq \mu\) for every computable numeration \(\mu\) of the same family S of r.e. sets; \(\nu\) is positive if \(\{\) (n,m): \(\nu (n)=\nu (m)\}\) is r.e.; \(\nu\) is one-valued if \(n\neq m\) implies \(\nu\) (n)\(\neq \nu (m).\) The main theorem proved now reads: Each family S admitting a one-valued computable numeration has either a smallest one-valued numeration or countably many nonequivalent positive numerations. This result follows from a lemma proved by a priority argument together with a previous result due to the author. The author has a counterexample showing that the main result cannot be improved to read ''nonequivalent one-valued numerations'' in place of ''nonequivalent positive numerations''.