2012/03/08 by Manuel Bodirsky, Bodirsky, Manuel, Pinsker, Michael · 2 citations
Computer Science · Mathematics · #Advanced Topology and Set Theory #Computational Complexity (cs.CC) #FOS: Computer and information sciences #FOS: Mathematics #Logic (math.LO) #Logic in Computer Science (cs.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems #Rings and Algebras (math.RA)
paper · pdf · doi:10.48550/arxiv.1203.1876
openalex publication_date 2012/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 ω-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.