Isomorphism of subshifts is a universal countable Borel equivalence relation
Let \(A\) be a finite set of symbols. A one-dimensional subshift on \(A\) is a closed subset of \(A^{\mathbb Z}\) which is invariant under the shift operator \(S\), where \(S(x)(n) = x(n+1)\). Two subshifts \(X\) on \(A\) and \(Y\) on \(B\) are isomorphic if there is a homeomorphism \(\varphi : X \to Y\) which commutes with \(S\). A Borel equivalence relation is an equivalence relation \(E\) on a Polish space \(X\) such that \(E\) is Borel as a subset of \(X^2\). An equivalence relation \(E\) on a space \(X\) is Borel reducible to an equivalence relation \(F\) on a space \(Y\), \(E \leq_{\text B} F\), if there is a Borel measurable function \(f : X \to Y\) such that for all \(x_1, x_2 \in X\), we have \(x_1Ex_2\) if and only if \(f(x_1)Ef(x_2)\). An equivalence relation \(E\) is countable if every equivalence class of \(E\) is countable. We say \(E\) is a universal countable Borel equivalence relation if \(E\) is a countable Borel equivalence relation and for every countable Borel equivalence relation \(F\), we have \(F \leq_{\text B} E\). In this paper, the author proves that the isomorphism relation on one-dimensional subshifts is a universal countable Borel equivalence relation. It is also proved that the classification of higher-dimensional subshifts has, up to isomorphism, the same complexity as for the one-dimensional case. A couple of open problems, like finding the complexity of isomorphism of one-sided shifts on \(2^{\mathbb N}\), are mentioned towards the end of the paper.
- Topological full groups of minimal subshifts and the classification problem for finitely generated complete groups
- Dynamical simplices and Borel complexity of orbit equivalence
- On the complexity of topological conjugacy of Toeplitz subshifts
- The complexity of the topological conjugacy problem for Toeplitz subshifts
- Topological isomorphism for rank-1 systems
- Isomorphism and weak conjugacy of free Bernoulli subflows
- The complexity of topological conjugacy of pointed Cantor minimal systems
- Group colorings and Bernoulli subflows
- Quotients by countable normal subgroups are hyperfinite
- CLASSIFICATION OF ONE DIMENSIONAL DYNAMICAL SYSTEMS BY COUNTABLE STRUCTURES
- Set theory. Abstracts from the workshop held January 12--17, 2025
This page was built for publication: Isomorphism of subshifts is a universal countable Borel equivalence relation
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q839908)
