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
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article