Some remarks on ω‐powers of enumerated sets and their applications to ω‐operations

The main topic of this paper, similarly as of [5], are w-operations and their lifting from the category of sets to the category of enumerated sets. But there is a certain difference between these two papers. In [5] covariant hom-functors, investigated in [4], have been used. In this paper so called "w-powers of enumerated sets", considered by E R ~ O V in [l], are mostly applied. One important fact should be stressed here. Let S be an arbitrary enumerated set. Then for every N-admissible enumeration j ([4], Definition 4) obviously there exists the enumerated set Hom(N, j ) (S). However, it may happen that the w-power S" does not exist. Anyhow, if it exists, the properties of the enumerated set S" are much better than the properties of the enumerated set Hom(N, j ) (S). It was mentioned already in the introduction to [4]. It is not our goal to decide what of the two ways of the description of the w-operations is better. But we try to compare these two ways. We also give some facts which show that the use of w-powers may be useful (see, for example, Theorem 9 and Theorem 17). In this paper we make free use of the notation and definitions given in [4] and [5] as well as in the book [l]. So we kindly ask the reader to consult the said publications. Here we will give only some technical notations which will be necessary later. For a given set A, we denote the cardinal number of A by [ A / . If y is a partial function, then by Arg w and Val y we denote the set of arguments and the set of values of y, respectively. The set of all natural numbers will be denoted by N. By z: N2 -+ N we shall denote a fixed general recursive bijection. B y c1 and c2 we shall denote the components of the function fl. By { Q ) x } ~ ~ ~ we denote a fixed Godel enumeration of the set of all partial recursive functions of arity 1. Moreover, W, := Arg px. The set of all general recursive functions of arity 1 will be denoted by O1. By NSET we will denote the category of all enumerated sets. The enumerated set (N, l N ) will be denoted by N. For simplicity, the functor hom(N) will be denoted by "horn". Moreover, i f j is an arbitrary N-admissible enumeration, then by Hom(j) we denote the functor Hom(N, j). Let S = (S, v ) be a non-empty enumerated set and let F : S -+ S be an w-operation on the set S. By F[v] we denote the restriction of F to the set hom(S). We assume the reader to be familar with the concept of w-power of enumerated set see [l], p. 324. This concept will be fundamental for our considerations. Let S = (S, v ) be an arbitrary non-empty enumerated set for which the w-power S" exists. Then by v" we shall denote the enumeration from the enumerated set S". Thus S" = (hom(S), v"). By w-NSET we denote the class of all enumerated sets S for which the set S" exists. Frequently we shall consider the class w-NSET as a full subcategory of the category NSET. The following simple observation will be useful later: