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)