Positive numerations of families with one-valued numerations

Recursive functions and relations, subrecursive hierarchies (03D20) Recursively (computably) enumerable sets and degrees (03D25) Theory of numerations, effectively presented structures (03D45)

Review text

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.

Recommendations

Cites work

Cited in

(12)

This page was built for publication: Positive numerations of families with one-valued numerations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1062050)