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)

Request Permissions   Purchase Content 
 

 

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?)


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.