## 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

## Additional Information

**Manuel Bodirsky**- Affiliation: Laboratoire d’Informatique (LIX), CNRS UMR 7161, École Polytechnique, 91128 Palaiseau, France
- MR Author ID: 693478
- ORCID: 0000-0001-8228-3611
- Email: bodirsky@lix.polytechnique.fr
**Michael Pinsker**- Affiliation: Équipe de Logique Mathématique, Université Diderot - Paris 7, UFR de Mathématiques, 75205 Paris Cedex 13, France
- MR Author ID: 742015
- ORCID: 0000-0002-4727-918X
- Email: marula@gmx.at
- Received by editor(s): March 25, 2012
- Received by editor(s) in revised form: October 3, 2012
- Published electronically: August 8, 2014
- Additional Notes: The first author has received funding from the European Research Council under the European Community’s Seventh Framework Programme (FP7/2007-2013 Grant Agreement no. 257039)

The second author is grateful for support through an APART-fellowship of the Austrian Academy of Sciences. - © Copyright 2014
American Mathematical Society

The copyright for this article reverts to public domain 28 years after publication. - Journal: Trans. Amer. Math. Soc.
**367**(2015), 2527-2549 - MSC (2010): Primary 03C05, 03C40, 08A35, 08A30; Secondary 08A70
- DOI: https://doi.org/10.1090/S0002-9947-2014-05975-8
- MathSciNet review: 3301873