Special Session:

Logic and Dynamical Systems

Stephen G. Simpson Pennsylvania State University http://www.math.psu.edu/simpson/ simpson@math.psu.edu

May 28, 2008

I am organizing a special session on Logic and Dynamical Systems. This will be part of the Joint Mathematics Meetings, January 5–8, 2009, in Washington, DC. Institutional sponsors are the American Mathematical Society (AMS) and the Association for Symbolic Logic (ASL). I thank Jeremy Avigad, chair of the ASL Committee on Meetings in North America, and Bernard Russo, Associate Secretary of the AMS.

In the last 15 years or so, there has been a tendency for increased interaction between mathematical logic and other parts of mathematics. In the last few years, one of the more fruitful interaction areas has been dynamical systems. Concepts and methods from several areas of mathematical logic have been introduced and applied in dynamical systems theory, including symbolic dynamics and ergodic theory. Relevant logical techniques have come from several sources including descriptive set theory (Borel classification), computational complexity (cellular automata), proof theory (reverse mathematics, proof mining), and recursion theory (degrees of unsolvability).

1. Towsner [7] has performed a proof-theoretic analysis of Furstenburg’s ergodic-theoretic proof of Szemerédi’s Theorem. In reverse-mathe-matical terms, Towsner has shown that the Furstenberg proof as a whole can be carried out in Π_{1}^{1} comprehension, while certain key lemmas are in fact equivalent to Π_{1}^{1} comprehension.

2. Cenzer/Dashti/King [2] have constructed a 1-dimensional subshift which is Π_{1}^{0} (i.e., effectively closed) yet contains no recursive points.

3. Hochman/Meyerovitch [5] have shown that each positive, right recursively enumerable real number is the entropy of a 2-dimensional subshift of finite type.

4. Simpson [6] has shown that the Medvedev degrees of 2-dimensional subshift of finite type are the same as the Medvedev degrees of nonempty Π_{1}^{0} sets in the Cantor space. Thus, in studying 2-dimensional subshifts of finite type, it becomes meaningful to ask about relationships between their dynamical properties and their degrees of unsolvability.

5. Clemens [3] has determined the descriptive set-theoretic complexity of the classification problem for subshifts. Namely, the isomorphism relation for 1-dimensional subshifts is universal among Borel equivalence relations which are “countable” (i.e., each equivalence class is countable).

6. The conference volume [4] presents an overview of some significant connections between descriptive set theory and dynamical system theory. Of central importance here is the descriptive set-theoretic study of Polish group actions.

7. Braverman/Yampolsky [1] have studied computational and recursiontheoretic aspects of Julia sets.

This special session will bring together interested experts in mathematical logic and dynamical systems theory. Among the speakers to be invited are:

Jeremy Avigad and Henry Towsner (Carnegie Mellon University), Douglas Cenzer, Ali Dashti, and Jonathan King (University of Florida), Matthew Foreman (University of California at Irvine), John Clemens and Stephen Simpson (Pennsylvania State University), Chi-Tat Chong (National University of Singapore), Jarkko Kari (University of Turku, Finland), Petr Kurka (Charles University, Prague), Bruno Durand (University of Provence, France), Benjamin Weiss (Hebrew University of Jerusalem), Tom Meyerovitch (Tel Aviv University), Alexander Kechris (California Institute of Technology), Gregory Hjorth (University of Melbourne), Michael Hochman (Princeton University), Mark Braverman and Michael Yampolsky (University of Toronto), Vladimir Pestov (University of Ottawa).

Note that Braverman, Dashti, Hochman, Meyerovitch, and Towsner are current or recent Ph.D. students.

References

[1] Mark Braverman and Michael Yampolsky. Non-computable Julia sets. Journal of the American Mathematical Society, 19:551–578, 2006.

[2] Douglas Cenzer, S. Ali Dashti, and Jonathan L. F. King. Effective symbolic dynamics. Mathematical Logic Quarterly, 2008. Preprint, 10 pages, accepted for publication.

[3] John D. Clemens. Isomorphism of subshifts is a universal countable Borel equivalence relation. Israel Journal of Mathematics, 2008. Preprint, 9 pages, accepted for publication.

[4] M. Foreman, A. S. Kechris, A. Louveau, and B. Weiss, editors. Descriptive Set Theory and Dynamical Systems. Number 277 in London Mathematical Society Lecture Note Series. Cambridge University Press, 2000. IV + 291 pages.

[5] Michael Hochman and Tom Meyerovitch. A characterization of the entropies of multidimensional shifts of finite type. 7 March 2007. Preprint, arXiv:math:DS/0703206v1, 27 pages.

[6] Stephen G. Simpson. Medvedev degrees of 2-dimensional subshifts of finite type. Ergodic Theory and Dynamical Systems, 2008. Preprint, 8 pages, 1 May 2007, accepted for publication.

[7] Henry Towsner. Some Results in Logic and Ergodic Theory. PhD thesis, Carnegie Mellon University, 2008.