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)

 
 

 

Topological Birkhoff


Authors: Manuel Bodirsky and Michael Pinsker
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
Published electronically: August 8, 2014
MathSciNet review: 3301873
Full-text PDF

Abstract | References | Similar Articles | Additional Information

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 [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 (87k:03026), https://doi.org/10.1016/0168-0072(86)90037-0
  • [Ban83] B. Banaschewski, The Birkhoff theorem for varieties of finite algebras, Algebra Universalis 17 (1983), no. 3, 360-368. MR 729943 (85k:08007), https://doi.org/10.1007/BF01194543
  • [BJ11] Manuel Bodirsky and Markus Junker, $ \aleph _0$-categorical structures: endomorphisms and interpretations, Algebra Universalis 64 (2010), no. 3-4, 403-417. MR 2781087 (2012e:03065), https://doi.org/10.1007/s00012-011-0110-y
  • [BKJ05] 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 (2005k:68181), https://doi.org/10.1137/S0097539700376676
  • [BKKR69] V. G. Bodnarčuk, L. A. Kalužnin, V. N. Kotov, and B. A. Romov,
    Galois theory for Post algebras, I, II, Kibernetika 1969, no. 3, 1-10; ibid 1969, no. 5, 1-9. MR 0300895 (46:55)
  • [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 (2007g:68061), https://doi.org/10.1093/logcom/exi083
  • [Bod08] 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.
  • [Bod12] 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.
  • [BS81] Stanley Burris and H. P. Sankappanavar, A course in universal algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York, 1981. MR 648287 (83k:08001)
  • [CKV08] 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.
  • [CN06] Peter J. Cameron and Jaroslav Nešetřil, Homomorphism-homogeneous relational structures, Combin. Probab. Comput. 15 (2006), no. 1-2, 91-103. MR 2195577 (2007c:05160), https://doi.org/10.1017/S0963548305007091
  • [DJPS] 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 (2012k:20112), https://doi.org/10.1007/s00233-011-9313-y
  • [DPT86] 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 (88i:20004), 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 (91g:03067), https://doi.org/10.1016/0168-0072(90)90034-Y
  • [ES76] Samuel Eilenberg and M. P. Schützenberger, On pseudovarieties, Advances in Math. 19 (1976), no. 3, 413-418. MR 0401604 (53 #5431)
  • [FV99] 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 (electronic). MR 1630445 (2000e:68063), https://doi.org/10.1137/S0097539794266766
  • [Gei68] David Geiger, Closed systems of functions and predicates, Pacific J. Math. 27 (1968), 95-100. MR 0234893 (38 #3207)
  • [GJ78] Michael Garey and David Johnson,
    A guide to NP-completeness.
    CSLI Press, Stanford, 1978.
  • [GP08] Martin Goldstern and Michael Pinsker, A survey of clones on infinite sets, Algebra Universalis 59 (2008), no. 3-4, 365-403. MR 2470587 (2009j:08007), https://doi.org/10.1007/s00012-008-2100-2
  • [GPS13] 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, https://doi.org/10.1142/S0218196713500197
  • [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 (2000c:03027), 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 (94d:03063), https://doi.org/10.1112/jlms/s2-48.2.204
  • [Hod93] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741 (94e:03002)
  • [Kea07] Keith Kearnes.
    Personal communication, 2007.
  • [Kec95] Alexander S. Kechris, Classical descriptive set theory, Graduate Texts in Mathematics, vol. 156, Springer-Verlag, New York, 1995. MR 1321597 (96e:03057)
  • [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 (92f:03029), https://doi.org/10.1112/plms/s3-62.1.25
  • [MMM] 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, https://doi.org/10.1007/s11083-011-9232-2
  • [MP11] Dragan Mašulović and Maja Pech, Oligomorphic transformation monoids and homomorphism-homogeneous structures, Fund. Math. 212 (2011), no. 1, 17-34. MR 2771586 (2012c:03083), https://doi.org/10.4064/fm212-1-2
  • [Opa79] J. Opatrný, Total ordering problem, SIAM J. Comput. 8 (1979), no. 1, 111-114. MR 522973 (80e:68117), https://doi.org/10.1137/0208008
  • [Rei82] Jan Reiterman, The Birkhoff theorem for finite algebras, Algebra Universalis 14 (1982), no. 1, 1-10. MR 634411 (84c:08008), https://doi.org/10.1007/BF02483902
  • [She84] Saharon Shelah, Can you take Solovay's inaccessible away?, Israel J. Math. 48 (1984), no. 1, 1-47. MR 768264 (86g:03082a), https://doi.org/10.1007/BF02760522
  • [SS33] Joseph Schreier and Stanisław Marcin Ulam,
    Über die Permutationsgruppe der natürlichen Zahlenfolge,
    Studia Mathematica 4 (1933), 134-141.
  • [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 (94f:08018)
  • [Tru89] J. K. Truss, Infinite permutation groups. II. Subgroups of small index, J. Algebra 120 (1989), no. 2, 494-515. MR 989913 (90c:20005), https://doi.org/10.1016/0021-8693(89)90212-3
  • [Tsa] 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, 08A30, 08A70

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


Additional Information

Manuel Bodirsky
Affiliation: Laboratoire d’Informatique (LIX), CNRS UMR 7161, École Polytechnique, 91128 Palaiseau, France
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
Email: marula@gmx.at

DOI: https://doi.org/10.1090/S0002-9947-2014-05975-8
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.
Article copyright: © Copyright 2014 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.

American Mathematical Society