Forcing with bushy trees

DOI10.1017/BSL.2017.12MaRDI QIDQ5363371zbMATHOpenAlexFDO

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 randomnessminimal degreesbushy tree forcingdiagonally noncomputable functions

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Other Turing degree structures (03D28) 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

• 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?)
• 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 \(\Sigma_2^0\) induction
• Diagonally non-computable functions and bi-immunity
• Diagonally non-recursive functions and effective Hausdorff dimension
• Located sets and reverse mathematics

Cited in

(13)

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

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)