Remote Access Transactions of the American Mathematical Society
Green Open Access

Transactions of the American Mathematical Society

ISSN 1088-6850(online) ISSN 0002-9947(print)

 
 

 

Reconstructing the topology of clones


Authors: Manuel Bodirsky, Michael Pinsker and András Pongrácz
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
Published electronically: January 6, 2017
MathSciNet review: 3605985
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [AZ86] 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, https://doi.org/10.1016/0168-0072(86)90037-0
  • [Bar04] Silvia Barbina,
    Automorphism groups of $ \omega $-categorical structures,
    Ph.D. thesis, University of Leeds, 2004.
  • [Bar15] Robert Barham, Automatic homeomorphicity of locally moving clones, Preprint, arXiv:1512.00251, 2015.
  • [BC10] Manuel Bodirsky and Hubie Chen, Quantified equality constraints, SIAM J. Comput. 39 (2010), no. 8, 3682-3699. MR 2745770, https://doi.org/10.1137/080725209
  • [BCP10] 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, https://doi.org/10.2178/jsl/1286198146
  • [BEKP15] 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.
  • [BHM10] 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
  • [Bir35] Garrett Birkhoff, On the structure of abstract algebras, Math. Proc. Cambridge Philos. Soc. 31 (1935), no. 4, 433-454.
  • [BJ11] Manuel Bodirsky and Markus Junker, $ \aleph _0$-categorical structures: endomorphisms and interpretations, Algebra Universalis 64 (2010), no. 3-4, 403-417. MR 2781087, https://doi.org/10.1007/s00012-011-0110-y
  • [BK96] 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
  • [BK08] Manuel Bodirsky and Jan Kára, The complexity of equality constraint languages, Theory Comput. Syst. 43 (2008), no. 2, 136-158. MR 2393133, https://doi.org/10.1007/s00224-007-9083-9
  • [BK09] Manuel Bodirsky and Jan Kára, The complexity of temporal constraint satisfaction problems, J. ACM 57 (2010), no. 2, Art. 9, 41. MR 2606084, https://doi.org/10.1145/1667053.1667058
  • [BKJ00] 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, https://doi.org/10.1007/3-540-45022-X_24
  • [BKJ05] Andrei A. Bulatov, Andrei A. Krokhin, and Peter Jeavons, Classifying the complexity of constraints using finite algebras, SIAM J. Comput. 34 (2005), no. 3, 720-742. MR 2137072, https://doi.org/10.1137/S0097539700376676
  • [BM07] Silvia Barbina and Dugald MacPherson, Reconstruction of homogeneous relational structures, J. Symbolic Logic 72 (2007), no. 3, 792-802. MR 2354901, https://doi.org/10.2178/jsl/1191333842
  • [BN06] Manuel Bodirsky and Jaroslav Nešetřil, Constraint satisfaction with countable homogeneous templates, J. Logic Comput. 16 (2006), no. 3, 359-373. MR 2239084, https://doi.org/10.1093/logcom/exi083
  • [Bod12] 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.
  • [BP11] 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, https://doi.org/10.1090/conm/558/11058
  • [BP15a] Manuel Bodirsky and Michael Pinsker, Schaefer's theorem for graphs, J. ACM 62 (2015), no. 3, Art. 19, 52. MR 3366998, https://doi.org/10.1145/2764899
  • [BP15b] Manuel Bodirsky and Michael Pinsker, Topological Birkhoff, Trans. Amer. Math. Soc. 367 (2015), no. 4, 2527-2549. MR 3301873, https://doi.org/10.1090/S0002-9947-2014-05975-8
  • [BP16] 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.
  • [BS81] 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
  • [BS16] 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.
  • [BTVG16] Mike Behrisch, Galois theory for semiclones, Algebra Universalis 76 (2016), no. 3, 385-413. MR 3556819, https://doi.org/10.1007/s00012-016-0407-y
  • [Cam90] Peter J. Cameron, Oligomorphic permutation groups, London Mathematical Society Lecture Note Series, vol. 152, Cambridge University Press, Cambridge, 1990. MR 1066691
  • [DHM89] Manfred Droste, Charles W. Holland, and Dugald Macpherson, Automorphism groups of infinite semilinear orders. I, II, Proc. London Math. Soc. (3) 58 (1989), no. 3, 454-478, 479-494. MR 988099, https://doi.org/10.1112/plms/s3-58.3.454
  • [DNT86] 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, https://doi.org/10.1112/blms/18.6.580
  • [EH90] 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, https://doi.org/10.1016/0168-0072(90)90034-Y
  • [Eva86] David M. Evans, Subgroups of small index in infinite general linear groups, Bull. London Math. Soc. 18 (1986), no. 6, 587-590. MR 859951, https://doi.org/10.1112/blms/18.6.587
  • [GP08] Martin Goldstern and Michael Pinsker, A survey of clones on infinite sets, Algebra Universalis 59 (2008), no. 3-4, 365-403. MR 2470587, https://doi.org/10.1007/s00012-008-2100-2
  • [Her98] Bernhard Herwig, Extending partial isomorphisms for the small index property of many $ \omega $-categorical structures, Israel J. Math. 107 (1998), 93-123. MR 1658539, https://doi.org/10.1007/BF02764005
  • [HHLS93] 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, https://doi.org/10.1112/jlms/s2-48.2.204
  • [HM88] David Hobby and Ralph McKenzie, The structure of finite algebras, Contemporary Mathematics, vol. 76, American Mathematical Society, Providence, RI, 1988. MR 958685
  • [Hod93] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741
  • [Hod97] Wilfrid Hodges, A shorter model theory, Cambridge University Press, Cambridge, 1997. MR 1462612
  • [Jec03] Thomas Jech, Set theory, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2003. The third millennium edition, revised and expanded. MR 1940513
  • [KK13] Keith A. Kearnes and Emil W. Kiss, The shape of congruence lattices, Mem. Amer. Math. Soc. 222 (2013), no. 1046, viii+169. MR 3076179, https://doi.org/10.1090/S0065-9266-2012-00667-8
  • [Las91] 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, https://doi.org/10.1112/plms/s3-62.1.25
  • [PP15] Christian Pech and Maja Pech, Polymorphism clones of homogeneous structures (universal homogeneous polymorphisms and automatic homeomorphicity), Preprint, arXiv:1502.07769, 2015.
  • [Rab77] 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)
  • [Ros09] Christian Rosendal, Automatic continuity of group homomorphisms, Bull. Symbolic Logic 15 (2009), no. 2, 184-214. MR 2535429, https://doi.org/10.2178/bsl/1243948486
  • [Rub94] 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, https://doi.org/10.1112/plms/s3-69.2.225
  • [Sem81] Stephen W. Semmes, Endomorphisms of infinite symmetric groups, Abstracts Amer. Math. Soc. 2:426 (1981).
  • [Tay93] 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
  • [Tru89] John K. Truss, Infinite permutation groups. II. Subgroups of small index, J. Algebra 120 (1989), no. 2, 494-515. MR 989913, https://doi.org/10.1016/0021-8693(89)90212-3
  • [Tsa12] Todor Tsankov, Unitary representations of oligomorphic groups, Geom. Funct. Anal. 22 (2012), no. 2, 528-555. MR 2929072, https://doi.org/10.1007/s00039-012-0156-9

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC (2010): 03C05, 03C40, 08A35, 20B27, 08A70

Retrieve articles in all journals with MSC (2010): 03C05, 03C40, 08A35, 20B27, 08A70


Additional Information

Manuel Bodirsky
Affiliation: Institut für Algebra, TU Dresden, 01062 Dresden, Germany
Email: Manuel.Bodirsky@tu-dresden.de

Michael Pinsker
Affiliation: Department of Algebra, MFF UK, Sokolovska 83, 186 00 Praha 8, Czech Republic
Email: marula@gmx.at

András Pongrácz
Affiliation: Department of Algebra and Number Theory, University of Debrecen, 4032 Debrecen, Egyetem Square 1, Hungary
Email: pongracz.andras@science.unideb.hu

DOI: https://doi.org/10.1090/tran/6937
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.
Article copyright: © Copyright 2017 American Mathematical Society

American Mathematical Society