Isomorphism of subshifts is a universal countable Borel equivalence relation
type: Item
instance of: scholarly article
title: Isomorphism of subshifts is a universal countable Borel equivalence relation
zbMATH Open document ID: 1180.03043
author: John D. Clemens
published in: Israel Journal of Mathematics
publication date: 2009-09-03T00:00:00Z
review text: 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.
reviewed by: T. Thrivikraman
Mathematics Subject Classification ID: 03E15
Mathematics Subject Classification ID: 54H05
zbMATH DE Number: 5601709
zbMATH Keywords: subshift
zbMATH Keywords: Borel equivalence relation
zbMATH Keywords: Polish space
MaRDI profile type: Publication
full work available at URL: s11856-009-0022-0
OpenAlex ID: W2077516133
cites work: The Structure of Hyperfinite Borel Equivalence Relations
cites work: COUNTABLE BOREL EQUIVALENCE RELATIONS
cites work: Q4323294
cites work: An Introduction to Symbolic Dynamics and Coding
DOI: 10.1007/S11856-009-0022-0
description: scientific article; zbMATH DE number 5601709