Recursively enumerable sets and degrees

DOI10.1090/S0002-9904-1978-14552-2zbMath0401.03018MaRDI QIDQ4184825

Robert I. Soare

Publication date: 1978

Published in: Bulletin of the American Mathematical Society (Search for Journal in Brave)

zbMATH Keywords

UndecidabilitySurveyDegrees of UnsolvabilityIncompletenessSimple SetEmbedding ConjectureInclusion LatticeInfinite Injury Priority MethodJump OperationMaximal SetRecursively Enumerable Sets and DegreesRelative RecursivenessUpper Semilattice

Mathematics Subject Classification ID

Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations (03-02) Recursively (computably) enumerable sets and degrees (03D25) Other degrees and reducibilities in computability and recursion theory (03D30)

Related Items

\(\Pi_{1}^{0}\) classes and orderable groups, On speedable and levelable vector spaces, The computable dimension of ordered abelian groups, Definable structures in the lattice of recursively enumerable sets, On the orbits of hyperhypersimple sets, Nonlowness is independent from fickleness, Undecidability of \(L(F_{\infty})\) and other lattices of r.e. substructures, Structural interactions of the recursively enumerable T- and W-degrees, An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees, The structure of the honest polynomial m-degrees, Degrees of Transducibility, Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets, Intervals and sublattices of the r.e. weak truth table degrees. I: Density, On the Turing degrees of minimal index sets, Jumps of quasi-minimal enumeration degrees, On the embedding of α-recursive presentable lattices into the α-recursive degrees below 0′, An infinite version of Arrow's theorem in the effective setting, \(\Sigma_ 2\) induction and infinite injury priority arguments. II. Tame \(\Sigma_ 2\) coding and the jump operator, The degrees of conditional problems, Decomposition of Recursively Enumerable Degrees, \(\Sigma_ 5\)-completeness of index sets arising from the recursively enumerable Turing degrees, Nonbounding and Slaman triples, \(\Sigma_ 5\)-completeness of index sets arising from the lattice of recursively enumerable sets, Traces, traceability, and lattices of traces under the set theoretic inclusion, The Quotient Semilattice of the Recursively Enumerable Degrees Modulo the Cappable Degrees, Transducer degrees: atoms, infima and suprema, Unnamed Item, Binary search and recursive graph problems, From undecidability of non-triviality and finiteness to undecidability of learnability, The theory of the recursively enumerable weak truth-table degrees is undecidable, Unnamed Item, Not every finite lattice is embeddable in the recursively enumerable degrees, Initial segments of the lattice of ideals of r.e. degrees, Density of recursively inseparable R. E. Sets and universal recrusively inseparability, Separable algorithmic representations of classical systems and their applications, Splitting properties and jump classes, Upper bounds on ideals in the computably enumerable Turing degrees, Some connections between bounded query classes and non-uniform complexity., On strongly jump traceable reals, Quantitative continuity and Computable Analysis in Coq, Immunity, simplicity, probabilistic complexity classes and relativizations, Frequency computation and bounded queries, Training digraphs, High and low Kleene degrees of coanalytic sets, Orbits of hyperhypersimple sets and the lattice of Σ⁰₃ sets, Infima in the d.r.e. degrees, Strong jump-traceability. I: The computably enumerable case, Notes on computable analysis, \(\Pi_1^0 \) classes, LR degrees and Turing degrees, Singular Coverings and Non-Uniform Notions of Closed Set Computability, On relativized nondeterministic polynomial-time bounded computations, Cupping and noncupping in the enumeration degrees of \(\Sigma_ 2^ 0\) sets, From index sets to randomness in ∅ⁿ: random reals and possibly infinite computations part II, Lattice nonembeddings and intervals of the recursively enumerable degrees, Hierarchy of Computably Enumerable Degrees II, On the theory of the PTIME degrees of the recursive sets, Computable de Finetti measures, Hyperhypersimple sets and \(\Delta _ 2\) systems, On the complexity of finding the chromatic number of a recursive graph. I: The bounded case, Formalizing forcing arguments in subsystems of second-order arithmetic, On the finiteness of the recursive chromatic number, Sets of generator and automorphism bases for the enumeration degrees, A necessary and sufficient condition for embedding ranked finite partial lattices into the computably enumerable degrees, The dense simple sets are orbit complete with respect to the simple sets, A low and a high hierarchy within NP, Oracle-dependent properties of the lattice of NP sets, Strong reducibilities, The density of infima in the recursively enumerable degrees, On effectively computable realizations of choice functions

Cites Work

• Recursion, metarecursion, and inclusion
• Simplicity of recursively enumerable sets
• A theorem on hyperhypersimple sets
• On a Class of Complete Simple Sets
• Axiomatizable theories with few axiomatizable extensions
• Completeness, the Recursion Theorem, and Effectively Simple Sets
• The Degrees of Hyperimmune Sets
• A Dichotomy of the Recursively Enumerable Sets
• A minimal pair of Π₁⁰ classes
• Degrees in Which the Recursive Sets are Uniformly Recursive
• The Friedberg-Muchnik Theorem Re-Examined
• A note on universal sets
• Some theorems on R-maximal sets and major subsets of recursively enumerable sets
• The Halting Problem Relativized to Complements
• Degrees of unsolvability complementary between recursively enumerable degrees, Part 1
• Minimal Upper Bounds for Sequences of Recursively Enumerable Degrees
• ∏ 0 1 Classes and Degrees of Theories
• Recursive Enumerability and the Jump Operator
• An Unsolvable Problem of Elementary Number Theory
• On Computable Numbers, with an Application to the Entscheidungsproblem
• Classes of Recursively Enumerable Sets and Their Decision Problems
• Two Notes on Recursively Enumerable Sets
• A Theorem on Hypersimple Sets
• Recursively enumerable sets of positive integers and their decision problems
• Productive Sets
• Creative sets
• [Russian Text Ignored]
• The word problem
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On degrees of recursive unsolvability
• Computing degrees of unsolvability
• d-simple sets, small sets, and degree classes
• A lattice property of Post's simple set
• \(r\)-maximal major subsets
• Some lowness properties and computational complexity sequences
• On some games which are relevant to the theory of recursively enumerable sets
• The elementary theory of recursively enumerable sets
• Recursively enumerable many-one degrees
• Three theorems on the degrees of recursively enumerable sets
• The recursively enumerable degrees are dense
• A maximal set which is not complete
• Word problems and recursively enumerable degrees of unsolvability. A sequel on finitely presented groups
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• The class of recursively enumerable subsets of a recursively enumerabl e set
• Hypersimple sets with retraceable complements
• Interpolation and embedding in the recursively enumerable degrees
• Jump restricted interpolation in the recursively enumerable degrees
• On the degrees less than 0'
• On degrees of unsolvability
• General recursive functions of natural numbers
• The upper semi-lattice of degrees of recursive unsolvability
• On completely recursively enumerable classes and their key arrays
• A criterion for completeness of degrees of unsolvability
• Degrees of unsolvability associated with classes of formalized theories
• TWO RECURSIVELY ENUMERABLE SETS OF INCOMPARABLE DEGREES OF UNSOLVABILITY (SOLUTION OF POST'S PROBLEM, 1944)
• Quasicreative Sets
• Retraceable Sets
• Some Theorems on Classes of Recursively Enumerable Sets
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• Undecidable and creative theories
• A minimal degree less than 0’
• Constructive Analogues of the Group of Permutations of the Natural Numbers
• Reducibility and Completeness for Sets of Integers
• Recursively Enumerable Sets and Retracing Functions
• Bounding minimal pairs
• A Decidable Fragment of the Elementary Theory of the Lattice of Recursively Enumerable Sets
• Deficiency Sets and Bounded Information Reducibilities
• Post's program and incomplete recursively enumerable sets.
• On subcreative sets and S-reducibility
• Prioric games and minimal degrees below $0^{(1)}$
• A Completely Mitotic Nonrecursive R.E. Degree
• Minimal pairs and high recursively enumerable degrees
• w tt-Complete Sets are not Necessarily tt-Complete
• Uniform enumeration operations
• The weak truth table degrees of recursively enumerable sets
• Boolean algebras, splitting theorems, and $Δ^0_2$ sets
• The infinite injury priority method
• Congruence relations, filters, ideals, and definability in lattices of α-recursively enumerable sets
• On complexity properties of recursively enumerable sets
• The decision problem for recursively enumerable degrees
• Banach–Mazur games, comeager sets and degrees of unsolvability
• A recursively enumerable degree which will not split over all lesser ones
• Determining Automorphisms of the Recursively Enumerable Sets
• Degrees of classes of RE sets
• Recursively enumerable vector spaces
• On elementary theories of some lattices or α-recursively enumerable sets
• Nowhere simple sets and the lattice of recursively enumerable sets
• Computational complexity, speedable and levelable sets
• Hilbert's Tenth Problem is Unsolvable
• On Group-Theoretic Decision Problems and Their Classification. (AM-68)
• Post's problem and his hypersimple set
• Jump equivalence of the Δ₂⁰ hyperimmune sets
• A Theory of Positive Integers in Formal Logic. Part I
• On the Lattice of Recursively Enumerable Sets
• Automorphisms of the lattice of recursively enumerable sets
• Mitotic recursively enumerable sets
• Π₁⁰ classes and Boolean combinations of recursively enumerable sets
• Degrees of Unsolvability. (AM-55)
• On the Degrees of Index Sets
• A minimal pair of recursively enumerable degrees
• On a question of G. E. Sacks
• On a Theorem of Lachlan and Martin
• Two Theorems on Hyperhypersimple Sets
• The Priority Method I
• A Simple Set Which is Not Effectively Simple
• Complete Recursively Enumerable Sets
• On a Problem of G. E. Sacks
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• The impossibility of finding relative complements for recursively enumerable degrees
• Some Notions of Reducibility and Productiveness
• Distributive Initial Segments of the Degrees of Unsolvability
• Sublattices of the Recursively Enumerable Degrees
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• The degrees of hyperhyperimmune sets
• On the Degrees of Index Sets. II
• Relationships Between Reducibilities
• Effectively Simple Sets
• Degrees of recursively enumerable sets which have no maximal supersets
• Recursive Functions Modulo Co-r-Maximal Sets
• Turing degrees and many-one degrees of maximal sets