MASS PROBLEMS AND HYPERARITHMETICITY

DOI10.1142/S0219061307000652zbMath1150.03013MaRDI QIDQ3521596

Stephen G. Simpson, Joshua A. Cole

Publication date: 26 August 2008

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

zbMATH Keywords

mass problemsdegrees of unsolvabilityhyperarithmetical hierarchylimit recursiveness

Mathematics Subject Classification ID

Other degrees and reducibilities in computability and recursion theory (03D30) Other Turing degree structures (03D28) Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Hierarchies of computability and definability (03D55)

Related Items

Implicit definability in arithmetic, CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS, Degrees of Unsolvability: A Tutorial, Randomness notions and partial relativization, Mass problems and density, Coding true arithmetic in the Medvedev degrees of \(\Pi^0_1\) classes, choice classes, 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, Lowness for bounded randomness, Medvedev degrees of two-dimensional subshifts of finite type, The importance of Π₁⁰ classes in effective randomness, On the degree spectrum of a $\Pi ^0_1$ class, DEMUTH’S PATH TO RANDOMNESS, Lowness for Kurtz randomness, Tracing and domination in the Turing degrees, Randomness and lowness notions via open covers, Mass problems associated with effectively closed sets

Cites Work

• Unnamed Item
• Embeddings into the Medvedev and Muchnik lattices of \(\Pi^0_1\) classes
• First-order theory of the degrees of recursive unsolvability
• Density of the Medvedev lattice of \(\Pi^0_1\) classes
• Computable structures and the hyperarithmetical hierarchy
• Strong jump-traceability. I: The computably enumerable case
• Lowness properties and approximations of the jump
• A Refinement of Lown and Highn for the R.E. Degrees
• Mass Problems and Randomness
• Uniform almost everywhere domination
• Randomness, lowness and degrees
• Interpretability and Definability in the Recursively Enumerable Degrees
• A splitting theorem for the Medvedev and Muchnik lattices
• A 1-generic degree with a strong minimal cover
• An extension of the recursively enumerable Turing degrees
• Almost everywhere domination and superhighness
• Mass problems and almost everywhere domination
• Low for random reals and positive-measure domination
• Comparing DNR and WWKL
• On a conjecture of Dobrinen and Simpson concerning almost everywhere domination
• Up to equimorphism, hyperarithmetic is recursive