Characterization of Recursively Enumerable Sets
Wright, Jesse B.
J. Symbolic Logic, Tome 37 (1972) no. 1, p. 507-511 / Harvested from Project Euclid
Let $N, O$ and $S$ denote the set of nonnegative integers, the graph of the constant 0 function and the graph of the successor function respectively. For sets $P, Q, R \subseteq N^2$ operations of transposition, composition, and bracketing are defined as follows: $P^\cup = \{\langle x, y\rangle | \langle y, x\rangle \epsilon P\}, PQ = \{\langle x, z\rangle | \exists y\langle x, y\rangle \epsilon P & \langle y, z\rangle \epsilon Q\}$, and $\lbrack P, Q, R\rbrack = \cup_{n \epsilon M}(P^nQR^n)$. THEOREM. The class of recursively enumerable subsets of $N^2$ is the smallest class of sets with $O$ and $S$ as members and closed under transposition, composition, and bracketing. This result is derived from a characterization by Julia Robinson of the class of general recursive functions of one variable in terms of function composition and "definition by general recursion." A key step in the proof is to show that if a function $F$ is defined by general recursion from functions $A, M, P$ and $R$ then $F = \lbrack P^\cup, A^\cup M, R\rbrack$. The above definitions of the transposition, composition, and bracketing operations on subsets of $N^2$ can be generalized to subsets of $X^2$ for an arbitrary set $X$. In this abstract setting it is possible to show that the bracket operation can be defined in terms of $K, L$, transposition, composition, intersection, and reflexive transitive closure where $K: X \rightarrow X$ and $L: X \rightarrow X$ are functions for decoding pairs.
Publié le : 1972-09-14
Classification: 
@article{1183738316,
     author = {Wright, Jesse B.},
     title = {Characterization of Recursively Enumerable Sets},
     journal = {J. Symbolic Logic},
     volume = {37},
     number = {1},
     year = {1972},
     pages = { 507-511},
     language = {en},
     url = {http://dml.mathdoc.fr/item/1183738316}
}
Wright, Jesse B. Characterization of Recursively Enumerable Sets. J. Symbolic Logic, Tome 37 (1972) no. 1, pp.  507-511. http://gdmltest.u-ga.fr/item/1183738316/