COMPUTABLE VS DESCRIPTIVE COMBINATORICS OF LOCAL PROBLEMS ON TREES
Felix Weilacher · Journal of Symbolic Logic · 2023
Abstract 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.