Vol 57, No 4 (2018)

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 Acomputable 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 Areducibility.

We study elementary and universal theories of relatively free solvable groups in a group signature expanded by one predicate distinguishing primitive or annihilating systems of elements.

The objects considered here serve both as generalizations of numberings studied in [1] and as particular versions of A-numberings, where ???? is a suitable admissible set, introduced in [2] (in view of the existence of a transformation realizing the passage from e-degrees to admissible sets [3]). The key problem dealt with in the present paper is the existence of Friedberg (single-valued computable) and positive presentations of families. In [3], it was stated that the above-mentioned transformation preserves the majority of properties treated in descriptive set theory. However, it is not hard to show that it also respects the positive (negative, decidable, single-valued) presentations. Note that we will have to extend the concept of a numbering and, in the general case, consider partial maps rather than total ones. The given effect arises under the passage from a hereditarily finite superstructure to natural numbers, since a computable function (in the sense of a hereditarily finite superstructure) realizing an enumeration of the hereditarily finite superstructure for nontotal sets is necessarily a partial function.