Skip to Main Content

Transactions of the American Mathematical Society

Published by the American Mathematical Society since 1900, Transactions of the American Mathematical Society is devoted to longer research articles in all areas of pure and applied mathematics.

ISSN 1088-6850 (online) ISSN 0002-9947 (print)

The 2020 MCQ for Transactions of the American Mathematical Society is 1.48.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

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
Similar Articles
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