SOME ABSOLUTE PROPERTIES OF A-COMPUTABLE NUMBERINGS

摘要

For an arbitrary set A of natural numbers, we prove the following statements: every finite family of A-computable sets containing a least element under inclusion has an A-computable universal numbering; every infinite A-computable family of total functions has (up to A-equivalence) either one A-computable Friedberg numbering or infinitely many such numberings; every A-computable family of total functions which contains a limit function has no A-computable universal numberings, even with respect to A-reducibility.