Topological Birkhoff

Bodirsky, Manuel; Pinsker, Michael

doi:10.1090/S0002-9947-2014-05975-8

Topological Birkhoff
HTML articles powered by AMS MathViewer

by Manuel Bodirsky and Michael Pinsker PDF

Trans. Amer. Math. Soc. 367 (2015), 2527-2549 Request permission

Abstract:

One of the most fundamental mathematical contributions of Garrett Birkhoff is the HSP theorem, which implies that a finite algebra $\mathbf {B}$ satisfies all equations that hold in a finite algebra $\mathbf {A}$ of the same signature if and only if $\mathbf {B}$ is a homomorphic image of a subalgebra of a finite power of $\mathbf {A}$. On the other hand, if $\mathbf {A}$ is infinite, then in general one needs to take an infinite power in order to obtain a representation of $\mathbf {B}$ in terms of $\mathbf {A}$, even if $\mathbf {B}$ is finite.

We show that by considering the natural topology on the functions of $\mathbf {A}$ and $\mathbf {B}$ in addition to the equations that hold between them, one can do with finite powers even for many interesting infinite algebras $\mathbf {A}$. More precisely, we prove that if $\mathbf {A}$ and $\mathbf {B}$ are at most countable algebras which are oligomorphic, then the mapping which sends each term function over $\mathbf {A}$ to the corresponding term function over $\mathbf {B}$ preserves equations and is Cauchy-continuous if and only if $\mathbf {B}$ is a homomorphic image of a subalgebra of a finite power of $\mathbf {A}$.

Our result has the following consequences in model theory and in theoretical computer science: two $\omega$-categorical structures are primitive positive bi-interpretable if and only if their topological polymorphism clones are isomorphic. In particular, the complexity of the constraint satisfaction problem of an $\omega$-categorical structure only depends on its topological polymorphism clone.

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
B. Banaschewski, The Birkhoff theorem for varieties of finite algebras, Algebra Universalis 17 (1983), no. 3, 360–368. MR 729943, DOI 10.1007/BF01194543
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
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
V. G. Bodnarčuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov, Galois theory for Post algebras. I, II, Kibernetika (Kiev) 3 (1969), 1–10; ibid. 1969, no. 5, 1–9 (Russian, with English summary). MR 300895
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, Constraint satisfaction problems with infinite templates. In Heribert Vollmer, editor, Complexity of Constraints (a collection of survey articles), volume 5250 of Lecture Notes in Computer Science, pages 196–228. Springer, 2008.
Manuel Bodirsky, Complexity classification in infinite-domain constraint satisfaction. Memoire d’habilitation à diriger des recherches, Université Diderot – Paris 7. Preprint available at arXiv:1201.0856, 2012.
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, DOI 10.1007/978-1-4613-8130-3
Nadia Creignou, Phokion G. Kolaitis, and Heribert Vollmer, editors. Complexity of Constraints - An Overview of Current Research Themes [Result of a Dagstuhl Seminar], volume 5250 of Lecture Notes in Computer Science. Springer, 2008.
Peter J. Cameron and Jaroslav Ne et il, Homomorphism-homogeneous relational structures, Combin. Probab. Comput. 15 (2006), no. 1-2, 91–103. MR 2195577, DOI 10.1017/S0963548305007091
B. A. Davey, M. G. Jackson, J. G. Pitkethly, and C. Szabó, Finite degree: algebras in general and semigroups in particular, Semigroup Forum 83 (2011), no. 1, 89–110. MR 2824076, DOI 10.1007/s00233-011-9313-y
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
Samuel Eilenberg and M. P. Schützenberger, On pseudovarieties, Advances in Math. 19 (1976), no. 3, 413–418. MR 401604, DOI 10.1016/0001-8708(76)90029-3
Tomás Feder and Moshe Y. Vardi, The computational structure of monotone monadic SNP and constraint satisfaction: a study through Datalog and group theory, SIAM J. Comput. 28 (1999), no. 1, 57–104. MR 1630445, DOI 10.1137/S0097539794266766
David Geiger, Closed systems of functions and predicates, Pacific J. Math. 27 (1968), 95–100. MR 234893, DOI 10.2140/pjm.1968.27.95
Michael Garey and David Johnson, A guide to NP-completeness. CSLI Press, Stanford, 1978.
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
Martin Goldstern, Michael Pinsker, and Saharon Shelah, A closed algebra with a non-Borel clone and an ideal with a Borel clone, Internat. J. Algebra Comput. 23 (2013), no. 5, 1115–1125. MR 3096314, DOI 10.1142/S0218196713500197
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
Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741, DOI 10.1017/CBO9780511551574
Keith Kearnes. Personal communication, 2007.
Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597, DOI 10.1007/978-1-4612-4190-4
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
Petar Marković, Miklós Maróti, and Ralph McKenzie, Finitely related clones and algebras with cube terms, Order 29 (2012), no. 2, 345–359. MR 2926316, DOI 10.1007/s11083-011-9232-2
Dragan Ma ulović and Maja Pech, Oligomorphic transformation monoids and homomorphism-homogeneous structures, Fund. Math. 212 (2011), no. 1, 17–34. MR 2771586, DOI 10.4064/fm212-1-2
J. Opatrný, Total ordering problem, SIAM J. Comput. 8 (1979), no. 1, 111–114. MR 522973, DOI 10.1137/0208008
Jan Reiterman, The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1982), no. 1, 1–10. MR 634411, DOI 10.1007/BF02483902
Saharon Shelah, Can you take Solovay’s inaccessible away?, Israel J. Math. 48 (1984), no. 1, 1–47. MR 768264, DOI 10.1007/BF02760522
Joseph Schreier and Stanisław Marcin Ulam, Über die Permutationsgruppe der natürlichen Zahlenfolge, Studia Mathematica 4 (1933), 134–141.
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