Forcing with bushy trees

DOI10.1017/BSL.2017.12zbMATH Open1421.03021arXiv1503.08870OpenAlexW2963802191MaRDI QIDQ5363371FDOQ5363371

Authors: Mushfeq Khan, Joseph S. Miller 

Publication date: 6 October 2017

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

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.

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

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

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)

Cites Work

• Algorithmic randomness and complexity.
• Title not available (Why is that?)
• Title not available (Why is that?)
• Comparing DNR and WWKL
• Located sets and reverse mathematics
• Diagonally non-computable functions and bi-immunity
• A DNC function that computes no effectively bi-immune set
• Comparing the strength of diagonally nonrecursive functions in the absence of \(\Sigma_2^0\) induction
• A fixed-point-free minimal degree
• Diagonally non-recursive functions and effective Hausdorff dimension
• Binary subtrees with few labeled paths
• Title not available (Why is that?)

Cited In (12)

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

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)