Enumeration operator
A mapping of the set of all sets of natural numbers into itself (i.e. a mapping of 
into 
, where 
is the set of natural numbers), defined as follows. Let 
be a recursively-enumerable set having Gödel number 
, let 
be a finite set of natural numbers with canonical index 
(i.e. 
, where 
and 
) and let 
be the number of the ordered pair consisting of the numbers 
and 
for a certain specified one-to-one recursive encoding of the pairs. Each recursively-enumerable set 
yields a procedure that transforms any given set of natural numbers 
into the set 
of natural numbers 
with the property that 
for some 
with 
, i.e. 
belongs to 
and if the finite set 
is contained in 
, then 
is related to 
. In other words,
 |
This procedure enables one to obtain effectively from any enumeration on 
an enumeration on 
. It is called an enumeration operator and is denoted by 
. If 
for some enumeration operator 
, one says that 
is reducible in enumerability to 
(
).
If 
and 
are enumeration operators, their composite 
is also an enumeration operator. If 
is an enumeration operator and 
, then 
. If 
, then 
for some finite set 
. Each enumeration operator 
has a least fixed point, i.e. there exists a recursively-enumerable set 
such that 
, and if 
, then 
.
References
| [1] | H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) |
Enumeration operator. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumeration_operator&oldid=46831