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 Free Access
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 satisfies all equations that hold in a finite algebra
of the same signature if and only if
is a homomorphic image of a subalgebra of a finite power of
. On the other hand, if
is infinite, then in general one needs to take an infinite power in order to obtain a representation of
in terms of
, even if
is finite.
We show that by considering the natural topology on the functions of and
in addition to the equations that hold between them, one can do with finite powers even for many interesting infinite algebras
. More precisely, we prove that if
and
are at most countable algebras which are oligomorphic, then the mapping which sends each term function over
to the corresponding term function over
preserves equations and is Cauchy-continuous if and only if
is a homomorphic image of a subalgebra of a finite power of
.
Our result has the following consequences in model theory and in theoretical computer science: two -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
-categorical structure only depends on its topological polymorphism clone.
- [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
- [Ban83] B. Banaschewski, The Birkhoff theorem for varieties of finite algebras, Algebra Universalis 17 (1983), no. 3, 360–368. MR 729943, https://doi.org/10.1007/BF01194543
- [BJ11] Manuel Bodirsky and Markus Junker, ℵ₀-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
- [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, 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 (Kiev) 3 (1969), 1–10; ibid. 1969, no. 5, 1–9 (Russian, with English summary). MR 0300895
- [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
- [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-Berlin, 1981. MR 648287
- [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, 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, 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, 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
- [ES76] Samuel Eilenberg and M. P. Schützenberger, On pseudovarieties, Advances in Math. 19 (1976), no. 3, 413–418. MR 401604, https://doi.org/10.1016/0001-8708(76)90029-3
- [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. MR 1630445, https://doi.org/10.1137/S0097539794266766
- [Gei68] David Geiger, Closed systems of functions and predicates, Pacific J. Math. 27 (1968), 95–100. MR 234893
- [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, 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 𝜔-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 𝜔-stable 𝜔-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
- [Hod93] Wilfrid Hodges, Model theory, Encyclopedia of Mathematics and its Applications, vol. 42, Cambridge University Press, Cambridge, 1993. MR 1221741
- [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
- [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
- [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, 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, 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, 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, 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
- [Tru89] J. 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
- [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
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.