Metarecursive sets
This is a fundamental paper concerning generalizations of recursion theory, and it, along with the papers cited below, are required reading in the subject. Metarecursion theory is recursion theory on the recursive ordinals. Using any \(\Pi_1^1\) set \(\mathbf{Q}\) of unique notations for \(\omega_1\) we have the following definitions: a metafinite set (of recursive ordinals) is a hyperarithmetic subset of \(\mathbf{Q}\); a metarecursive set is a \(\Delta_1^1\) set with respect to \(\mathbf{Q}\); a metarecursive function has a \(\Pi_1^1\) subset of \(\mathbf{Q}^2\) as its graph; meta-r. e. and bounded are defined in obvious ways. A simple analogy with an ordinary-recursion-theory triviality is: metafinite if and only if bounded and metarecursive. This is typical, and two of the most important examples, which assist in the ``lifting up of priority arguments, are: the union of a metafinite set of metafinite sets is metafinite; the range of a metarecursive function restricted to a metafinite set is metafinite. The two results proved along these lines are: the existence of a maximal meta-r. e. set (where maximal is defined by a very strong analogy); Post's problem (where relative metarecursiveness is defined in a weak way -- there is some question about the correct relativized definition). However, there exist bounded, meta-r.e. sets which are not metafinite; this and a more general phenomenon called irregularity stand in the way of lifting up priority arguments. For further clarification on all these points, see \textit{G. E. Sacks}' subsequent paper [Trans. Am. Math. Soc. 124, 1--23 (1966; Zbl 0149.24704)]. An early section of the paper under review discusses various approaches to generalizing recursion theory. This section, although interesting, could use further clarification and should be read in conjunction with Kreisel's earlier paper [Theory of Models, Proc. 1963 Int. Symp. Berkeley, 190--205 (1965; Zbl 0225.02040)]. It is then shown that metarecursion is \(\omega_1\)-recursion in the sense of \textit{S. A. Kripke} [Meeting of the Association for Symbolic Logic, April 21, 1964, J. Symb. Logic 29, 161--162 (1964; \url{doi:10.2307/2271646})]; much that can be said for metarecursion can be said for \(\alpha\)-recursion for admissible \(\alpha\) (again see Sacks ibid.).
- scientific article; zbMATH DE number 3073037 (Why is no real title available?)
- On the degrees less than 0'
- On the Forms of the Predicates in the Theory of Constructive Ordinals (Second Paper)
- Recursively enumerable sets of positive integers and their decision problems
- The recursively enumerable degrees are dense
- TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
- Ordinal machines and admissible recursion theory
- Descriptive characterizations of computational complexity
- Post's problem without admissibility
- Effective oracles
- Theories of Rogers semilattices of analytical numberings
- On the reducibility of \(\Pi_ 1^ 1\) sets
- Enumeration reducibility and computable structure theory
- On a positive set theory with inequality
- The Role of True Finiteness in the Admissible Recursively Enumerable Degrees
- Minimal Covers and Hyperdegrees
- Barwise: Infinitary Logic and Admissible Sets
- Transfinite recursion and computation in the iterative conception of set
- Computability in uncountable binary trees
- THE THEORY OF THE METARECURSIVELY ENUMERABLE DEGREES
- Metarecursively enumerable sets and admissible ordinals
- Measure-Theoretic Uniformity in Recursion Theory and Set Theory
- Persistent and invariant formulas relative to theories of higher order
- Atomic models higher up
This page was built for publication: Metarecursive sets
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5536268)