1 results
COMPUTABLE VS DESCRIPTIVE COMBINATORICS OF LOCAL PROBLEMS ON TREES
- Part of
-
- Journal:
- The Journal of Symbolic Logic , First View
- Published online by Cambridge University Press:
- 04 July 2023, pp. 1-15
-
- Article
-
- You have access
- Open access
- HTML
- Export citation
-
We study the position of the computable setting in the “common theory of locality” developed in [4, 5] for local problems on
$\Delta $-regular trees, 
$\Delta \in \omega $. We show that such a problem admits a computable solution on every highly computable 
$\Delta $-regular forest if and only if it admits a Baire measurable solution on every Borel 
$\Delta $-regular forest. We also show that if such a problem admits a computable solution on every computable maximum degree 
$\Delta $ forest then it admits a continuous solution on every maximum degree 
$\Delta $ Borel graph with appropriate topological hypotheses, though the converse does not hold.
