Reconstructing the topology of clones

Bodirsky, Manuel; Pinsker, Michael; Pongrácz, András

doi:10.1090/tran/6937

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