A representation of recursively enumerable sets through Horn formulas in higher recursion theory
type: Item
instance of: scholarly article
title: A representation of recursively enumerable sets through Horn formulas in higher recursion theory
zbMATH Open document ID: 1389.03008
author: Juan A. Nido Valencia
author: Julio Solís-Daun
author: Luis Miguel Villegas Silva
published in: Periodica Mathematica Hungarica
publication date: 2017-11-10T00:00:00Z
review text: In the late 1950's, R. Smullyan showed: the r.e. (recursively enumerable) sets are exactly those that are representable in his elementary formal systems. This is a result in ordinary recursion theory in arithmetical setting. The authors of this article extend it to other recursion theories in set-theoretic setting: primitive set recursion, \(\beta\)-recursion, and recursion in admissible structures. First, they give careful definitions of r.e. sets and Horn clause theories (modern reformulation of elementary formal systems) in set-theoretic context. Also, succinct definitions of recursion theories in question are given. The direction of an r.e. set is representable is proved inductively following how that set is constructed. The proof of the other implication uses the fact that local satisfaction relation is definable. In the last section, the authors look at Smullyan's result from the set-theoretic view-point, utilizing the equivalence of the system of natural numbers and the system of hereditarily finite sets.
Mathematics Subject Classification ID: 03C70
Mathematics Subject Classification ID: 03D60
Mathematics Subject Classification ID: 03D65
Mathematics Subject Classification ID: 03E45
Mathematics Subject Classification ID: 03D75
zbMATH DE Number: 6806123
zbMATH Keywords: Horn theory
zbMATH Keywords: primitive recursive set functions
zbMATH Keywords: recursively enumerable set
zbMATH Keywords: \(\alpha\)-recursion theory
zbMATH Keywords: primitive recursively closed ordinals
zbMATH Keywords: admissible recursion
zbMATH Keywords: \(\beta\)-recursion
MaRDI profile type: Publication
full work available at URL: s10998-016-0148-x
OpenAlex ID: W2467957161
cites work: Infinitary logic and admissible sets
cites work: Q4075450
cites work: Q4318616
cites work: Fundamentals of generalized recursion theory
cites work: Q3511020
cites work: Infinite time Turing machines
cites work: The fine structure of the constructible hierarchy
cites work: Ordinal machines and admissible recursion theory
cites work: Q3125203
cites work: Q4040890
cites work: Q3819052
DOI: 10.1007/S10998-016-0148-X
Recommended article: Recursive axiomatizations for representable posets
Recommended article: DEFINABILITY OF RECURSIVELY ENUMERABLE SETS IN ABSTRACT COMPUTATIONAL COMPLEXITY THEORY
Recommended article: Expressibility in the elementary theory of recursively enumerable sets with realizability logic
Recommended article: On a Class of Recursively Enumerable Sets
Recommended article: Q3999549
Recommended article: The structures inside Turing degrees of recursively enumerable generic sets
Recommended article: Some Theorems on Classes of Recursively Enumerable Sets
Recommended article: Hyperarithmetical Index Sets in Recursion Theory
Recommended article: Q3343456
Recommended article: A note on recursive models of set theories
description: scientific article; zbMATH DE number 6806123