A representation of recursively enumerable sets through Horn formulas in higher recursion theory

作者：Nido Valencia Juan A; Solis Daun Julio E; Villegas Silva Luis M

来源：Periodica Mathematica Hungarica, 2016, 73(1): 1-15.

DOI：10.1007/s10998-016-0148-x

• Horn theory
• Primitive recursive set functions
• Recursively enumerable set
• alpha-Recursion theory
• Primitive recursively closed ordinals
• Admissible recursion
• beta-Recursion

We extend a classical result in ordinary recursion theory to higher recursion theory, namely that every recursively enumerable set can be represented in any model by some Horn theory, where can be any model of a higher recursion theory, like primitive set recursion, -recursion, or -recursion. We also prove that, under suitable conditions, a set defined through a Horn theory in a set is recursively enumerable in models of the above mentioned recursion theories.

• 出版日期2016-9