Forcing with bushy trees

DOI10.1017/BSL.2017.12MaRDI QIDQ5363371zbMATH OpenOpenAlexFDO

Authors Mushfeq Khan, Joseph S. Miller

Publication date 6 October 2017

Published in The Bulletin of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1503.08870

zbMATH Keywords

algorithmic randomnessbushy tree forcingdiagonally noncomputable functionsminimal degrees

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Hierarchies of computability and definability (03D55)

Abstract: We present several results that rely on arguments involving the combinatorics of "bushy trees". These include the fact that there are arbitrarily slow-growing diagonally noncomputable (DNC) functions that compute no Kurtz random real, as well as an extension of a result of Kumabe in which we establish that there are DNC functions relative to arbitrary oracles that are of minimal Turing degree. Along the way, we survey some of the existing instances of bushy tree arguments in the literature.

Recommendations

• Lowness for Kurtz randomness
• Ramsey-type graph coloring and diagonal non-computability
• Diagonally non-computable functions and fireworks
• On a question of Slaman and Groszek
• Binary subtrees with few labeled paths

Cites work

• A DNC function that computes no effectively bi-immune set
• A fixed-point-free minimal degree
• Algorithmic randomness and complexity.
• Binary subtrees with few labeled paths
• Comparing DNR and WWKL
• Comparing the strength of diagonally nonrecursive functions in the absence of _2⁰ induction
• Diagonally non-computable functions and bi-immunity
• Diagonally non-recursive functions and effective Hausdorff dimension
• scientific article; zbMATH DE number 4135927 (Why is no real title available?)
• scientific article; zbMATH DE number 3930980 (Why is no real title available?)
• scientific article; zbMATH DE number 4008384 (Why is no real title available?)
• Located sets and reverse mathematics

Cited in

(14)

• Highness properties close to PA completeness
• Coloring trees in reverse mathematics
• Effective bi-immunity and randomness
• Covering the Recursive Sets
• Degrees of unsolvability: a tutorial
• The weakness of being cohesive, thin or free in reverse mathematics
• Covering the recursive sets
• Diagonally non-computable functions and fireworks
• Muchnik degrees and cardinal characteristics
• Shift-complex sequences
• The coding power of a product of partitions
• Growth and irreducibility in path-incompressible trees
• On the Hausdorff dimension of maximal chains and antichains of Turing and hyperarithmetic degrees
• Ramsey-type graph coloring and diagonal non-computability

This page was built for publication: Forcing with bushy trees

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5363371)