Definition:Enumeration Operator (Recursion Theory)

This page is about Enumeration Operator in the context of Recursion Theory. For other uses, see Enumeration Operator.

Definition

Let $\phi \subseteq \N$ be recursively enumerable.

Let $\pi : \N^2 \to \N$ be the Cantor pairing function.

Then, $\map \pi {x, y}$ codes the pair $\tuple {x, y}$.

Define the mapping $\psi : \powerset \N \to \powerset \N$ as:

$\map \psi A = \set {x \in \N : \exists \text { finite } B \subseteq A : \map \pi {x, b} \in \phi}$

where $b \in \N$ is the code number for $B$.

Then $\psi$ is an enumeration operator.

Also see

• Definition:Enumeration

Sources

• 1967: Hartley Rogers, Jr.: Theory of Recursive Functions and Effective Computability
• Enumeration operator. Encyclopedia of Mathematics. URL: https://www.encyclopediaofmath.org/index.php?title=Enumeration_operator&oldid=46831