SECOND ORDER DEFINABILITY VIA ENUMERATIONS by IVAN N. SOSKOV in Sofia (Bulgaria)')
An external characterization of two classes of second order computable objects on abstract structures is presented in this paper. Namely of the search computable functionals [6] and of the operators computable by means of REDS. In order to make the paper self-contained we briefly sketch some of the definitions and results from [3] and [4] in section 1.
1. Preliminaries
Let 91 = ( B ; el, 62, ..., 6, ; EL, Zz, ..., &) be a partial structure, where B is an arbitrary denumerable set, el, 6, . ..., 6, are partial functions of many arguments on B , Z1, Z2,. .., & are partial predicates of many arguments on B. There n, k B 0. The relationai type of % is the ordered pair (( a l , u 2 , . . ., a,), (b,, b2, ... , bk)), where each 8, is ui-ary and each Zj is b,-ary.
Denote by N the set of all natural numben.
An enumeration of the structure 2f is an ordered pair ( g S) , where 23 = (N; pl, p2, . , . , p"; a,, az , . . ., ak) is a partial structure of the same relational type as % and a is a partial and surjective mapping of N onto B such that the following conditions hold: (i) The domain of a (dom(a)) is closed with respect to the partial operations p l , . . ., p,,;
(ii) a(cpi(x,, . .., xJ) 1-ei(a(x1), ..., a(x,,)) for all x l r .
..,x,,, of dorn(a);
(iii) a j ( x l , ..., xbj) 2 Z j ( a ( x J , ..., a ( x b j ) ) for all x l , ..., xb, of dom(a).
Let (.,.) be an effective coding of the ordered pairs of natural numbers such that x < ( x , y ) and y < ( x , y ) . For example, ( x , y ) = 2"-3 y . We shall suppose also that there exist I) Research partially supported by the Ministry of Culture, Science and Education, Contract #247, 1988.