# FG1 Seminar talk

2012-03-02

Michael **Pinsker***Topological Birkhoff*

Abstract:

One of the most fundamental mathematical contributions of Garrett
Birkhoff is the HSP theorem, which implies that a finite algebra B
satisfies all equations that hold in a finite algebra A of the same
signature if and only if B is a homomorphic image of a subalgebra
of a finite power of A . On the other hand, if A is infinite,
then in general one needs to take an *infinite* power in order to
obtain a representation of B in terms of A , even if B is
finite.

We show that by considering the natural topology on the functions of
A and B in addition to the equations that hold between them, one can
do with finite powers even for many interesting infinite algebras A.
More precisely, we prove that if A and B are at most countable
algebras which are oligomorphic, then the mapping which sends
each function from A to the corresponding function in B
preserves equations and is *continuous* if and only if B is a
homomorphic image of a subalgebra of a *finite* power of 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.

(Joint work with Manuel Bodirsky, Ecole Polytechnique)