Isomorphism of subshifts is a universal countable Borel equivalence relation (Q839908)

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.