∏ 0 1 Classes and Degrees of Theories

DOI10.2307/1996261zbMath0262.02041OpenAlexW4246804796WikidataQ56534778 ScholiaQ56534778MaRDI QIDQ5677474

Carl G. jun. Jockusch, Robert I. Soare

Publication date: 1972

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

Full work available at URL: https://doi.org/10.2307/1996261

Mathematics Subject Classification ID

Decidability of theories and sets of sentences (03B25) Other degrees and reducibilities in computability and recursion theory (03D30) General logic (03B99)

Related Items (only showing first 100 items - show all)

An inside/outside Ramsey theorem and recursion theory ⋮ Reverse mathematics and Weihrauch analysis motivated by finite complexity theory ⋮ Turing incomparability in Scott sets ⋮ The metamathematics of Stable Ramsey’s Theorem for Pairs ⋮ RELATIONSHIPS BETWEEN COMPUTABILITY-THEORETIC PROPERTIES OF PROBLEMS ⋮ THE REVERSE MATHEMATICS OF THE THIN SET AND ERDŐS–MOSER THEOREMS ⋮ Degrees of Unsolvability: A Tutorial ⋮ Prime Model with No Degree of Autostability Relative to Strong Constructivizations ⋮ Iterative Forcing and Hyperimmunity in Reverse Mathematics ⋮ Degrees containing members of thin Π10 classes are dense and co-dense ⋮ Members of thin Π₁⁰ classes and generic degrees ⋮ INFINITE STRINGS AND THEIR LARGE SCALE PROPERTIES ⋮ Orders on magmas and computability theory ⋮ OPEN QUESTIONS ABOUT RAMSEY-TYPE STATEMENTS IN REVERSE MATHEMATICS ⋮ DEEP CLASSES ⋮ An effectively closed set with no join property* ⋮ EXPANDING THE REALS BY CONTINUOUS FUNCTIONS ADDS NO COMPUTATIONAL POWER ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ ALMOST THEOREMS OF HYPERARITHMETIC ANALYSIS ⋮ Direct construction of Scott ideals ⋮ COMPUTABLY COMPACT METRIC SPACES ⋮ PA RELATIVE TO AN ENUMERATION ORACLE ⋮ Milliken’s Tree Theorem and Its Applications: A Computability-Theoretic Perspective ⋮ Combinatorial principles concerning approximations of functions ⋮ A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals ⋮ Array nonrecursiveness and relative recursive enumerability ⋮ Degrees of Indiscernibles in Decidable Models ⋮ GENERALIZATIONS OF THE RECURSION THEOREM ⋮ The weakness of the pigeonhole principle under hyperarithmetical reductions ⋮ Recursive Quantum Functions, Avoidable Points, & Shadow Points in Recursive Analysis ⋮ Immunity for Closed Sets ⋮ Medvedev Degrees of Generalized R.E. separating Classes ⋮ Partial Recursive Functions and Finality ⋮ Reverse mathematics and fully ordered groups ⋮ The canonical Ramsey theorem and computability theory ⋮ On the degree spectrum of a $\Pi ^0_1$ class ⋮ COMPUTABILITY IN UNCOUNTABLE BINARY TREES ⋮ Chain conditions in computable rings ⋮ Putnam’s Theorem on the Complexity of Models ⋮ Thin set theorems and cone avoidance ⋮ Recursively enumerable sets and degrees ⋮ Minimal Covers and Hyperdegrees ⋮ The atomic model theorem and type omitting ⋮ Degrees of bi-embeddable categoricity ⋮ A note on the join property ⋮ Recursive Euler and Hamilton Paths ⋮ Computable categoricity for algebraic fields with splitting algorithms ⋮ SEARCHING FOR AN ANALOGUE OF ATR₀ IN THE WEIHRAUCH LATTICE ⋮ Enumerations of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msubsup><mml:mi mathvariant="normal">Π</mml:mi><mml:mn>1</mml:mn><mml:mn>0</mml:mn></mml:msubsup></mml:math> Classes: Acceptability and Decidable Classes ⋮ Computability of Subsets of Metric Spaces ⋮ Weihrauch Complexity in Computable Analysis ⋮ THE PREHISTORY OF THE SUBSYSTEMS OF SECOND-ORDER ARITHMETIC ⋮ Abstract complexity theory and the \(\Delta_{2}^{0}\) degrees ⋮ \(\Pi_{1}^{0}\) classes and orderable groups ⋮ The Medvedev lattice of computably closed sets ⋮ Lowness for genericity ⋮ A context for belief revision: forward chaining-normal nonmonotonic rule systems ⋮ On categoricity spectra for locally finite graphs ⋮ Degrees of autostability relative to strong constructivizations of graphs ⋮ Whitehead's problem and reverse mathematics ⋮ Factorization of polynomials and \(\Sigma ^ 0_ 1\) induction ⋮ Members of countable \(\Pi ^ 0_ 1\) classes ⋮ Generalized notions of mind change complexity ⋮ Learning Families of Closed Sets in Matroids ⋮ When does randomness come from randomness? ⋮ Maximal theories ⋮ Recursion theory and ordered groups ⋮ A theory of nonmonotonic rule systems. II ⋮ The proof-theoretic strength of Ramsey's theorem for pairs and two colors ⋮ Measure theory and weak König's lemma ⋮ Term extraction and Ramsey's theorem for pairs ⋮ Randomness and universal machines ⋮ Coloring trees in reverse mathematics ⋮ The reverse mathematics of non-decreasing subsequences ⋮ Effective categoricity for distributive lattices and Heyting algebras ⋮ Cohesive sets and rainbows ⋮ Propagation of partial randomness ⋮ Turing degrees of multidimensional SFTs ⋮ Depth, Highness and DNR Degrees ⋮ Computational processes, observers and Turing incompleteness ⋮ Infinite dimensional proper subspaces of computable vector spaces ⋮ Antibasis theorems for \({\Pi^0_1}\) classes and the jump hierarchy ⋮ Effective algebraicity ⋮ The Bolzano-Weierstrass theorem is the jump of weak Kőnig's lemma ⋮ Effectively closed mass problems and intuitionism ⋮ Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes ⋮ On the uniform computational content of computability theory ⋮ Closed choice and a uniform low basis theorem ⋮ Oscillation in the initial segment complexity of random reals ⋮ The complexity of recursive constraint satisfaction problems ⋮ Spaces of orders and their Turing degree spectra ⋮ \(\varPi^1_1\)-conservation of combinatorial principles weaker than Ramsey's theorem for pairs ⋮ A blend of methods of recursion theory and topology. ⋮ Weakly Represented Families in Reverse Mathematics ⋮ Lowness, Randomness, and Computable Analysis ⋮ Demuth randomness and computational complexity ⋮ Inside the Muchnik degrees. II: The degree structures induced by the arithmetical hierarchy of countably continuous functions ⋮ Characterizing the strongly jump-traceable sets via randomness ⋮ Computability-theoretic and proof-theoretic aspects of partial and linear orderings ⋮ Confident and consistent partial learning of recursive functions

This page was built for publication: ∏ 0 1 Classes and Degrees of Theories