
One of the most fundamental mathematical contributions of Garrett Birkhoff is the HSP theorem, which implies that a finite algebra B \mathbf {B} satisfies all equations that hold in a finite algebra A \mathbf {A} of the same signature if and only if B \mathbf {B} is a homomorphic image of a subalgebra of a finite power of A \mathbf {A} . On the other hand, if A \mathbf {A} is infinite, then in general one needs to take an infinite power in order to obtain a representation of B \mathbf {B} in terms of A \mathbf {A} , even if B \mathbf {B} is finite. We show that by considering the natural topology on the functions of A \mathbf {A} and B \mathbf {B} in addition to the equations that hold between them, one can do with finite powers even for many interesting infinite algebras A \mathbf {A} . More precisely, we prove that if A \mathbf {A} and B \mathbf {B} are at most countable algebras which are oligomorphic, then the mapping which sends each term function over A \mathbf {A} to the corresponding term function over B \mathbf {B} preserves equations and is Cauchy-continuous if and only if B \mathbf {B} is a homomorphic image of a subalgebra of a finite power of A \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.
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Logic in Computer Science, Rings and Algebras (math.RA), FOS: Mathematics, Mathematics - Logic, Mathematics - Rings and Algebras, Computational Complexity (cs.CC), Logic (math.LO), Logic in Computer Science (cs.LO)
FOS: Computer and information sciences, Computer Science - Computational Complexity, Computer Science - Logic in Computer Science, Rings and Algebras (math.RA), FOS: Mathematics, Mathematics - Logic, Mathematics - Rings and Algebras, Computational Complexity (cs.CC), Logic (math.LO), Logic in Computer Science (cs.LO)
| citations This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 34 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Top 10% | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Top 10% |
