Effectively closed subgroups of the infinite symmetric group

Greenberg, Noam; Melnikov, Alexander; Nies, Andre; Turetsky, Daniel

doi:10.1090/proc/14055

Effectively closed subgroups of the infinite symmetric group
HTML articles powered by AMS MathViewer

by Noam Greenberg, Alexander Melnikov, Andre Nies and Daniel Turetsky PDF

Proc. Amer. Math. Soc. 146 (2018), 5421-5435 Request permission

Abstract:

We apply methods of computable structure theory to study effectively closed subgroups of $S_\infty$. The main result of the paper says that there exists an effectively closed presentation of $\mathbb {Z}_2$ which is not the automorphism group of any computable structure $M$. In contrast, we show that every effectively closed discrete group is topologically isomorphic to $\rm {Aut}(M)$ for some computable structure $M$. We also prove that there exists an effectively closed compact (thus, profinite) subgroup of $S_\infty$ that has no computable Polish presentation. In contrast, every profinite computable Polish group is topologically isomorphic to an effectively closed subgroup of $S_\infty$. We also look at oligomorphic subgroups of $S_\infty$; we construct a $\Sigma ^1_1$ closed oligomorphic group in which the orbit equivalence relation is not uniformly HYP. Our proofs rely on methods of computable analysis, techniques of computable structure theory, elements of higher recursion theory, and the priority method.

References

C. J. Ash and J. F. Knight, Pairs of recursive structures, Ann. Pure Appl. Logic 46 (1990), no. 3, 211–234. MR 1049387, DOI 10.1016/0168-0072(90)90004-L
C. J. Ash and J. Knight, Computable structures and the hyperarithmetical hierarchy, Studies in Logic and the Foundations of Mathematics, vol. 144, North-Holland Publishing Co., Amsterdam, 2000. MR 1767842
Paul Brodhead and Douglas Cenzer, Effectively closed sets and enumerations, Arch. Math. Logic 46 (2008), no. 7-8, 565–582. MR 2395559, DOI 10.1007/s00153-008-0065-7
Laurent Bienvenu, Noam Greenberg, and Benoit Monin, Continuous higher randomness, J. Math. Log. 17 (2017), no. 1, 1750004, 53. MR 3651213, DOI 10.1142/S0219061317500040
Vasco Brattka, Peter Hertling, and Klaus Weihrauch, A tutorial on computable analysis, New computational paradigms, Springer, New York, 2008, pp. 425–491. MR 2762094, DOI 10.1007/978-0-387-68546-5_{1}8
Yuri L. Ershov and Sergei S. Goncharov, Constructive models, Siberian School of Algebra and Logic, Consultants Bureau, New York, 2000. MR 1749622, DOI 10.1007/978-1-4615-4305-3
Su Gao, Invariant descriptive set theory, Pure and Applied Mathematics (Boca Raton), vol. 293, CRC Press, Boca Raton, FL, 2009. MR 2455198
Xiaolin Ge and J. Ian Richards, Computability in unitary representations of compact groups, Logical methods (Ithaca, NY, 1992) Progr. Comput. Sci. Appl. Logic, vol. 12, Birkhäuser Boston, Boston, MA, 1993, pp. 386–421. MR 1281158
Kojiro Higuchi and Takayuki Kihara, On effectively closed sets of effective strong measure zero, Ann. Pure Appl. Logic 165 (2014), no. 9, 1445–1469. MR 3210078, DOI 10.1016/j.apal.2014.04.013
Moshe Jarden, Algebraic extensions of finite corank of Hilbertian fields, Israel J. Math. 18 (1974), 279–307. MR 376617, DOI 10.1007/BF02757283
Peter La Roche, Effective Galois theory, J. Symbolic Logic 46 (1981), no. 2, 385–392. MR 613291, DOI 10.2307/2273630
Roger C. Lyndon and Paul E. Schupp, Combinatorial group theory, Ergebnisse der Mathematik und ihrer Grenzgebiete, Band 89, Springer-Verlag, Berlin-New York, 1977. MR 0577064
Timothy H. McNicholl, A note on the computable categoricity of $\ell ^p$ spaces, Evolving computability, Lecture Notes in Comput. Sci., vol. 9136, Springer, Cham, 2015, pp. 268–275. MR 3382366, DOI 10.1007/978-3-319-20028-6_{2}7
A. Melnikov. Computable topological groups and Pontryagin duality. To appear in Transactions of The American Mathematical Society.
Alexander G. Melnikov, Computably isometric spaces, J. Symbolic Logic 78 (2013), no. 4, 1055–1085. MR 3156512, DOI 10.2178/jsl.7804030
Alexander Melnikov and Antonio Montalbán, Computable Polish group actions, J. Symb. Log. 83 (2018), no. 2, 443–460. MR 3835072, DOI 10.1017/jsl.2017.68
G. Metakides and A. Nerode, Effective content of field theory, Ann. Math. Logic 17 (1979), no. 3, 289–320. MR 556895, DOI 10.1016/0003-4843(79)90011-1
Marian B. Pour-El and J. Ian Richards, Computability in analysis and physics, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1989. MR 1005942, DOI 10.1007/978-3-662-21717-7
L. S. Pontryagin, Topological groups, Gordon and Breach Science Publishers, Inc., New York-London-Paris, 1966. Translated from the second Russian edition by Arlen Brown. MR 0201557
Jan Reimann, Effectively closed sets of measures and randomness, Ann. Pure Appl. Logic 156 (2008), no. 1, 170–182. MR 2474448, DOI 10.1016/j.apal.2008.06.015
Gerald E. Sacks, Higher recursion theory, Perspectives in Mathematical Logic, Springer-Verlag, Berlin, 1990. MR 1080970, DOI 10.1007/BFb0086109
Rick L. Smith, THE THEORY OF PROFINITE GROUPS WITH EFFECTIVE PRESENTATIONS, ProQuest LLC, Ann Arbor, MI, 1979. Thesis (Ph.D.)–The Pennsylvania State University. MR 2628530
Rick L. Smith, Effective aspects of profinite groups, J. Symbolic Logic 46 (1981), no. 4, 851–863. MR 641497, DOI 10.2307/2273233