Difficulty of classification problems and the isomorphism of subshifts | Department of Mathematics

Difficulty of classification problems and the isomorphism of subshifts

Event Information
Event Location: 
GAB 406, 4-5 PM; Refreshments: GAB 472, 3:30 PM
Event Date: 
Monday, September 13, 2010 - 4:00pm

A classification problem in mathematics is the problem of determining when two of a given collection of structures are appropriately equivalent. A solution of a classification problem involves providing some manner for making the determination of equivalence, such as developing a complete system of invariants. The difficulty of a classification problem can be measured by considering how complicated such invariants must be. Using descriptive set theory, we can provide a precise notion of when one classification problem is fundamentally more complicated than another, and provide a number of standard benchmarks for levels of complexity. In this talk, I will first give an overview of this theory of Borel reducibility of equivalence relations and classification problems. I will then apply this theory to determine the complexity of the isomorphism problem for subshifts, i.e., the dynamical systems corresponding to topologically closed and shift-invariant subsets of the space of all bi-infinite sequences on a finite alphabet, considered up to shift-preserving topological isomorphism.