Topological Birkhoff

Details Topological Birkhoff Topological Birkhoff

2012-03-08

arxiv.org/abs/1203.1876v1

Mathematics

Logic

21 pages

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Topological Birkhoff does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Topological Birkhoff, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Topological Birkhoff will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-17976