Enumeration operator

A mapping of the set of all sets of natural numbers into itself (i.e. a mapping of $ 2 ^ {\mathbf N} $ into $ 2 ^ {\mathbf N} $, where $ \mathbf N $ is the set of natural numbers), defined as follows. Let $ W _ {z} $ be a recursively-enumerable set having Gödel number $ z $, let $ D _ {u} $ be a finite set of natural numbers with canonical index $ u $( i.e. $ D _ {u} = \{ x _ {1} \dots x _ {n} \} $, where $ x _ {1} < \dots < x _ {n} $ and $ 2 ^ {x _ {1} } + \dots + 2 ^ {x _ {n} } = u $) and let $ \langle x, u \rangle $ be the number of the ordered pair consisting of the numbers $ x $ and $ u $ for a certain specified one-to-one recursive encoding of the pairs. Each recursively-enumerable set $ W _ {z} $ yields a procedure that transforms any given set of natural numbers $ B $ into the set $ A $ of natural numbers $ x $ with the property that $ \langle x , u \rangle \in W _ {z} $ for some $ u $ with $ D _ {u} \subset B $, i.e. $ \langle x, u\rangle $ belongs to $ W _ {z} $ and if the finite set $ D _ {u} $ is contained in $ B $, then $ x $ is related to $ A $. In other words,

$$ A = \{ {x } : {( \exists u)(\langle x, u\rangle \in W _ {z} \wedge D _ {u} \subseteq B) } \} . $$

This procedure enables one to obtain effectively from any enumeration on $ B $ an enumeration on $ A $. It is called an enumeration operator and is denoted by $ \Phi _ {z} $. If $ \Psi ( B) = A $ for some enumeration operator $ \Psi $, one says that $ A $ is reducible in enumerability to $ B $( $ A \leq _ {e} B $).

If $ \Phi $ and $ \Psi $ are enumeration operators, their composite $ \Phi \Psi $ is also an enumeration operator. If $ \Psi $ is an enumeration operator and $ B _ {1} \subseteq B $, then $ \Psi ( B _ {1} ) \subseteq \Psi ( B) $. If $ x \in \Psi ( B _ {1} ) $, then $ x \in \Psi ( D) $ for some finite set $ D \subseteq B _ {1} $. Each enumeration operator $ \Psi $ has a least fixed point, i.e. there exists a recursively-enumerable set $ A $ such that $ \Psi ( A) = A $, and if $ \Psi ( B) = B $, then $ A \subseteq B $.

References

[1]	H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967)