TOPOLOGICAL BIRKHOFF
Publikation: Beitrag in Fachzeitschrift › Forschungsartikel › Beigetragen › Begutachtung
Beitragende
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 term function over A to the corresponding term function over B preserves equations and is Cauchy-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 w-categorical structure only depends on its topological polymorphism clone.
Details
Originalsprache | Englisch |
---|---|
Aufsatznummer | PII S0002-9947(2014)05975-8 |
Seiten (von - bis) | 2527-2549 |
Seitenumfang | 23 |
Fachzeitschrift | Transactions of the American Mathematical Society |
Jahrgang | 367 |
Ausgabenummer | 4 |
Publikationsstatus | Veröffentlicht - Apr. 2015 |
Peer-Review-Status | Ja |
Externe IDs
ORCID | /0000-0001-8228-3611/work/142241117 |
---|
Schlagworte
Schlagwörter
- SMALL INDEX PROPERTY, OMEGA-CATEGORICAL STRUCTURES, FINITE-ALGEBRAS, CONSTRAINT SATISFACTION, SUBGROUPS, THEOREM