An official website of the United States government
We characterize the completely determined Borel subsets of HYP as exactly the [Formula: see text] subsets of HYP. As a result, HYP believes there is a Borel well-ordering of the reals, that the Borel Dual Ramsey Theorem fails, and that every Borel d-regular bipartite graph has a Borel perfect matching, among other examples. Therefore, the Borel Dual Ramsey Theorem and several theorems of descriptive combinatorics are not theories of hyperarithmetic analysis. In the case of the Borel Dual Ramsey Theorem, this answers a question of Astor, Dzhafarov, Montalbán, Solomon and the third author.
more »
« less
Katok’s special representation theorem for multidimensional Borel flows
Katok’s special representation theorem states that any free ergodic measure-preserving R^d-flow can be realized as a special flow over a Z^d-action. It provides a multidimensional generalization of the ‘flow under a function’ construction. We prove the analog of Katok’s theorem in the framework of Borel dynamics and show that, likewise, all free Borel R^d-flows emerge from Z^d-actions through the special flow construction using bi-Lipschitz cocycles.
more »
« less
- Award ID(s):
- 2153981
- PAR ID:
- 10515275
- Publisher / Repository:
- Cambridge University Press
- Date Published:
- Journal Name:
- Ergodic Theory and Dynamical Systems
- ISSN:
- 0143-3857
- Page Range / eLocation ID:
- 1 to 18
- Format(s):
- Medium: X
- Sponsoring Org:
- National Science Foundation
More Like this
-
-
A long-standing open problem in the theory of hyperfinite equivalence relations asks if the orbit equivalence relation generated by a Borel action of a countable amenable group is hyperfinite. In this paper we prove that this question always has a positive answer when the acting group is polycyclic, and we obtain a positive answer for all free actions of a large class of solvable groups including the Baumslag–Solitar group BS(1, 2) and the lamplighter group Z2 ≀ Z. This marks the first time that a group of exponential volume-growth has been verified to have this property. In obtaining this result we introduce a new tool for studying Borel equivalence relations by extending Gromov’s notion of asymptotic dimension to the Borel setting. We show that countable Borel equivalence relations of finite Borel asymptotic dimension are hyperfinite, and more generally we prove under a mild compatibility assumption that increasing unions of such equivalence relations are hyperfinite. As part of our main theorem, we prove for a large class of solvable groups that all of their free Borel actions have finite Borel asymptotic dimension (and finite dynamic asymptotic dimension in the case of a continuous action on a zero dimensional space). We also provide applications to Borel chromatic numbers, Borel and continuous Følner tilings, topological dynamics, and C∗-algebras.more » « less
-
Let $$\R$$ be a real closed field and $$\C$$ the algebraic closure of $$\R$$. We give an algorithm for computing a semi-algebraic basis for the first homology group, $$\HH_1(S,\mathbb{F})$$, with coefficients in a field $$\FF$$, of any given semi-algebraic set $$S \subset \R^k$$ defined by a closed formula. The complexity of the algorithm is bounded singly exponentially. More precisely, if the given quantifier-free formula involves $$s$$ polynomials whose degrees are bounded by $$d$$, the complexity of the algorithm is bounded by $$(s d)^{k^{O(1)}}$$. This algorithm generalizes well known algorithms having singly exponential complexity for computing a semi-algebraic basis of the zero-th homology group of semi-algebraic sets, which is equivalent to the problem of computing a set of points meeting every semi-algebraically connected component of the given semi-algebraic set at a unique point. It is not known how to compute such a basis for the higher homology groups with singly exponential complexity. As an intermediate step in our algorithm we construct a semi-algebraic subset $$\Gamma$$ of the given semi-algebraic set $$S$$, such that $$\HH_q(S,\Gamma) = 0$$ for $q=0,1$. We relate this construction to a basic theorem in complex algebraic geometry stating that for any affine variety $$X$$ of dimension $$n$$, there exists Zariski closed subsets \[ Z^{(n-1)} \supset \cdots \supset Z^{(1)} \supset Z^{(0)} \] with $$\dim_\C Z^{(i)} \leq i$, and $$\HH_q(X,Z^{(i)}) = 0$$ for $$0 \leq q \leq i$$. We conjecture a quantitative version of this result in the semi-algebraic category, with $$X$$ and $$Z^{(i)}$$ replaced by closed semi-algebraic sets. We make initial progress on this conjecture by proving the existence of $$Z^{(0)}$$ and $$Z^{(1)}$$ with complexity bounded singly exponentially (previously, such an algorithm was known only for constructing $$Z^{(0)}$$).more » « less
-
We continue to develop a program in geometric measure theory that seeks to identify how measures in a space interact with canonical families of sets in the space. In particular, extending a theorem of the first author and R. Schul in Euclidean space, for an arbitrary locally finite Borel measure in an arbitrary Carnot group, we develop tests that identify the part of the measure that is carried by rectifiable curves and the part of the measure that is singular to rectifiable curves. Our main result is entwined with an extension of the Analyst's Traveling Salesman Theorem, which characterizes subsets of rectifiable curves in R^2 (P. Jones, 1990), in R^n (K. Okikolu, 1992), or in an arbitrary Carnot group (the second author) in terms of local geometric least squares data called Jones' beta numbers. In a secondary result, we implement the Garnett-Killip-Schul construction of a doubling measure in R^n that charges a rectifiable curve in an arbitrary complete, doubling, locally quasiconvex metric space.more » « less
-
We show that the Priess-Crampe & Ribenboim fixed point theorem is provable in R C A 0 . Furthermore, we show that Caristi’s fixed point theorem for both Baire and Borel functions is equivalent to the transfinite leftmost path principle, which falls strictly between A T R 0 and Π 1 1 - C A 0 . We also exhibit several weakenings of Caristi’s theorem that are equivalent to W K L 0 and to A C A 0 . This article is part of the theme issue ‘Modern perspectives in Proof Theory’.more » « less
- Free Publicly Accessible Full Text
-
Accepted Manuscript1.0
- Journal Article:
- https://doi.org/10.1017/etds.2023.62
