Reconstructing the topology of clones
HTML articles powered by AMS MathViewer
- by Manuel Bodirsky, Michael Pinsker and András Pongrácz PDF
- Trans. Amer. Math. Soc. 369 (2017), 3707-3740 Request permission
Abstract:
Function clones are sets of functions on a fixed domain that are closed under composition and contain the projections. They carry a natural algebraic structure, provided by the laws of composition which hold in them, as well as a natural topological structure, provided by the topology of pointwise convergence, under which composition of functions becomes continuous. Inspired by recent results indicating the importance of the topological ego of function clones even for originally algebraic problems, we study questions of the following type: In which situations does the algebraic structure of a function clone determine its topological structure? We pay particular attention to function clones which contain an oligomorphic permutation group, and discuss applications of this situation in model theory and theoretical computer science.References
- Gisela Ahlbrandt and Martin Ziegler, Quasi-finitely axiomatizable totally categorical theories, Ann. Pure Appl. Logic 30 (1986), no. 1, 63–82. Stability in model theory (Trento, 1984). MR 831437, DOI 10.1016/0168-0072(86)90037-0
- Silvia Barbina, Automorphism groups of $\omega$-categorical structures, Ph.D. thesis, University of Leeds, 2004.
- Robert Barham, Automatic homeomorphicity of locally moving clones, Preprint, arXiv:1512.00251, 2015.
- Manuel Bodirsky and Hubie Chen, Quantified equality constraints, SIAM J. Comput. 39 (2010), no. 8, 3682–3699. MR 2745770, DOI 10.1137/080725209
- Manuel Bodirsky, Hubie Chen, and Michael Pinsker, The reducts of equality up to primitive positive interdefinability, J. Symbolic Logic 75 (2010), no. 4, 1249–1292. MR 2767967, DOI 10.2178/jsl/1286198146
- Manuel Bodirsky, David Evans, Michael Kompatscher, and Michael Pinsker, A counterexample to the reconstruction of $\omega$-categorical structures from their endomorphism monoids, Israel J. Math., to appear.
- Manuel Bodirsky, Martin Hils, and Barnaby Martin, On the scope of the universal-algebraic approach to constraint satisfaction, 25th Annual IEEE Symposium on Logic in Computer Science LICS 2010, IEEE Computer Soc., Los Alamitos, CA, 2010, pp. 90–99. MR 2953898
- Garrett Birkhoff, On the structure of abstract algebras, Math. Proc. Cambridge Philos. Soc. 31 (1935), no. 4, 433–454.
- Manuel Bodirsky and Markus Junker, $\aleph _0$-categorical structures: endomorphisms and interpretations, Algebra Universalis 64 (2010), no. 3-4, 403–417. MR 2781087, DOI 10.1007/s00012-011-0110-y
- Howard Becker and Alexander S. Kechris, The descriptive set theory of Polish group actions, London Mathematical Society Lecture Note Series, vol. 232, Cambridge University Press, Cambridge, 1996. MR 1425877, DOI 10.1017/CBO9780511735264
- Manuel Bodirsky and Jan Kára, The complexity of equality constraint languages, Theory Comput. Syst. 43 (2008), no. 2, 136–158. MR 2393133, DOI 10.1007/s00224-007-9083-9
- Manuel Bodirsky and Jan Kára, The complexity of temporal constraint satisfaction problems, J. ACM 57 (2010), no. 2, Art. 9, 41. MR 2606084, DOI 10.1145/1667053.1667058
- Andrei A. Bulatov, Andrei A. Krokhin, and Peter Jeavons, Constraint satisfaction problems and finite algebras, Automata, languages and programming (Geneva, 2000) Lecture Notes in Comput. Sci., vol. 1853, Springer, Berlin, 2000, pp. 272–282. MR 1795899, DOI 10.1007/3-540-45022-X_{2}4
- Andrei Bulatov, Peter Jeavons, and Andrei Krokhin, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34 (2005), no. 3, 720–742. MR 2137072, DOI 10.1137/S0097539700376676
- Silvia Barbina and Dugald MacPherson, Reconstruction of homogeneous relational structures, J. Symbolic Logic 72 (2007), no. 3, 792–802. MR 2354901, DOI 10.2178/jsl/1191333842
- Manuel Bodirsky and Jaroslav Ne et il, Constraint satisfaction with countable homogeneous templates, J. Logic Comput. 16 (2006), no. 3, 359–373. MR 2239084, DOI 10.1093/logcom/exi083
- Manuel Bodirsky, Complexity classification in infinite-domain constraint satisfaction, Mémoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Available at arXiv:1201.0856, 2012.
- Manuel Bodirsky and Michael Pinsker, Reducts of Ramsey structures, Model theoretic methods in finite combinatorics, Contemp. Math., vol. 558, Amer. Math. Soc., Providence, RI, 2011, pp. 489–519. MR 3418644, DOI 10.1090/conm/558/11058
- Manuel Bodirsky and Michael Pinsker, Schaefer’s theorem for graphs, J. ACM 62 (2015), no. 3, Art. 19, 52. MR 3366998, DOI 10.1145/2764899
- Manuel Bodirsky and Michael Pinsker, Topological Birkhoff, Trans. Amer. Math. Soc. 367 (2015), no. 4, 2527–2549. MR 3301873, DOI 10.1090/S0002-9947-2014-05975-8
- Libor Barto and Michael Pinsker, The algebraic dichotomy conjecture for infinite domain constraint satisfaction problems, Proceedings of the 31st Annual IEEE Symposium on Logic in Computer Science–LICS 2016, pp. 615–622.
- Stanley Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York-Berlin, 1981. MR 648287
- Manuel Bodirsky and Friedrich Martin Schneider, A topological characterisation of endomorphism monoids of countable structures, Algebra Universalis, to appear. Preprint available at arXiv:1508.07404.
- Mike Behrisch, Galois theory for semiclones, Algebra Universalis 76 (2016), no. 3, 385–413. MR 3556819, DOI 10.1007/s00012-016-0407-y
- Peter J. Cameron, Oligomorphic permutation groups, London Mathematical Society Lecture Note Series, vol. 152, Cambridge University Press, Cambridge, 1990. MR 1066691, DOI 10.1017/CBO9780511549809
- M. Droste, W. C. Holland, and H. D. Macpherson, Automorphism groups of infinite semilinear orders. I, II, Proc. London Math. Soc. (3) 58 (1989), no. 3, 454–478, 479–494. MR 988099, DOI 10.1112/plms/s3-58.3.454
- John D. Dixon, Peter M. Neumann, and Simon Thomas, Subgroups of small index in infinite symmetric groups, Bull. London Math. Soc. 18 (1986), no. 6, 580–586. MR 859950, DOI 10.1112/blms/18.6.580
- David M. Evans and P. R. Hewitt, Counterexamples to a conjecture on relative categoricity, Ann. Pure Appl. Logic 46 (1990), no. 2, 201–209. MR 1042609, DOI 10.1016/0168-0072(90)90034-Y
- David M. Evans, Subgroups of small index in infinite general linear groups, Bull. London Math. Soc. 18 (1986), no. 6, 587–590. MR 859951, DOI 10.1112/blms/18.6.587
- Martin Goldstern and Michael Pinsker, A survey of clones on infinite sets, Algebra Universalis 59 (2008), no. 3-4, 365–403. MR 2470587, DOI 10.1007/s00012-008-2100-2
- Bernhard Herwig, Extending partial isomorphisms for the small index property of many $\omega$-categorical structures, Israel J. Math. 107 (1998), 93–123. MR 1658539, DOI 10.1007/BF02764005
- Wilfrid Hodges, Ian Hodkinson, Daniel Lascar, and Saharon Shelah, The small index property for $\omega$-stable $\omega$-categorical structures and for the random graph, J. London Math. Soc. (2) 48 (1993), no. 2, 204–218. MR 1231710, DOI 10.1112/jlms/s2-48.2.204
- David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685, DOI 10.1090/conm/076
- Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
- Wilfrid Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. MR 1462612
- Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
- Keith A. Kearnes and Emil W. Kiss, The shape of congruence lattices, Mem. Amer. Math. Soc. 222 (2013), no. 1046, viii+169. MR 3076179, DOI 10.1090/S0065-9266-2012-00667-8
- Daniel Lascar, Autour de la propriété du petit indice, Proc. London Math. Soc. (3) 62 (1991), no. 1, 25–53 (French, with English summary). MR 1078212, DOI 10.1112/plms/s3-62.1.25
- Christian Pech and Maja Pech, Polymorphism clones of homogeneous structures (universal homogeneous polymorphisms and automatic homeomorphicity), Preprint, arXiv:1502.07769, 2015.
- Evgenia B. Rabinovich, Embedding theorems and de Bruijn’s problem for bounded symmetry groups, Dokl. Akad. Nauk. Belor. S.S.R. 21 (1977), no. 9, 784–7. (Russian)
- Christian Rosendal, Automatic continuity of group homomorphisms, Bull. Symbolic Logic 15 (2009), no. 2, 184–214. MR 2535429, DOI 10.2178/bsl/1243948486
- Matatyahu Rubin, On the reconstruction of $\aleph _0$-categorical structures from their automorphism groups, Proc. London Math. Soc. (3) 69 (1994), no. 2, 225–249. MR 1281964, DOI 10.1112/plms/s3-69.2.225
- Stephen W. Semmes, Endomorphisms of infinite symmetric groups, Abstracts Amer. Math. Soc. 2:426 (1981).
- Walter Taylor, Abstract clone theory, Algebras and orders (Montreal, PQ, 1991) NATO Adv. Sci. Inst. Ser. C: Math. Phys. Sci., vol. 389, Kluwer Acad. Publ., Dordrecht, 1993, pp. 507–530. MR 1233798
- J. K. Truss, Infinite permutation groups. II. Subgroups of small index, J. Algebra 120 (1989), no. 2, 494–515. MR 989913, DOI 10.1016/0021-8693(89)90212-3
- Todor Tsankov, Unitary representations of oligomorphic groups, Geom. Funct. Anal. 22 (2012), no. 2, 528–555. MR 2929072, DOI 10.1007/s00039-012-0156-9
Additional Information
- Manuel Bodirsky
- Affiliation: Institut für Algebra, TU Dresden, 01062 Dresden, Germany
- MR Author ID: 693478
- ORCID: 0000-0001-8228-3611
- Email: Manuel.Bodirsky@tu-dresden.de
- Michael Pinsker
- Affiliation: Department of Algebra, MFF UK, Sokolovska 83, 186 00 Praha 8, Czech Republic
- MR Author ID: 742015
- ORCID: 0000-0002-4727-918X
- Email: marula@gmx.at
- András Pongrácz
- Affiliation: Department of Algebra and Number Theory, University of Debrecen, 4032 Debrecen, Egyetem Square 1, Hungary
- MR Author ID: 915593
- Email: pongracz.andras@science.unideb.hu
- Received by editor(s): January 23, 2014
- Received by editor(s) in revised form: February 29, 2016
- Published electronically: January 6, 2017
- Additional Notes: The first and third authors have received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 257039). The first author also received funding from the German Science Foundation (DFG, project number 622397)
The second author has been funded through projects I836-N23 and P27600 of the Austrian Science Fund (FWF). The third author was also partially supported by the Hungarian Scientific Research Fund (OTKA) grant no. K109185. - © Copyright 2017 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 369 (2017), 3707-3740
- MSC (2010): Primary 03C05, 03C40, 08A35, 20B27; Secondary 08A70
- DOI: https://doi.org/10.1090/tran/6937
- MathSciNet review: 3605985