On universal numberings of generalized computable families

Abstract

The paper investigates the existence of universal generalized computable numberings of different families of sets and total functions. It was known that for every set A such that ∅ 0 ≤T A, a finite family S of A-c.e. sets has an A-computable universal numbering if and only if S contains the least set under inclusion. This criterion is not true for infinite families. For any set A there is an infinite A-computable family of sets S without the least element under inclusion that has an A-computable universal numbering; moreover, the family S consist pairwise not intersect sets. If A is a hyperimmune set, then an A-computable family F of total functions which contains at least two elements has no A-computable universal numbering. And if degT (A) is hyperimmune-free, then every A-computable finite family of total functions has an A-computable universal numbering. In this paper for a hyperimmune-free oracle A we show that any infinite effectively discrete family of sets has an A-computable universal numbering. It is also proved that if family S contains all co-finite sets and does not contain at least one co-c.e. set, then this family has no Σ −1 2 -computable universal numbering.