# 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) |

**How to Cite This Entry:**

Enumeration operator.

*Encyclopedia of Mathematics.*URL: http://encyclopediaofmath.org/index.php?title=Enumeration_operator&oldid=46831