Topological Birkhoff
From MaRDI portal
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.
Recommendations
Cites work
- scientific article; zbMATH DE number 432742 (Why is no real title available?)
- scientific article; zbMATH DE number 3751028 (Why is no real title available?)
- scientific article; zbMATH DE number 53151 (Why is no real title available?)
- scientific article; zbMATH DE number 722611 (Why is no real title available?)
- scientific article; zbMATH DE number 3336786 (Why is no real title available?)
- A closed algebra with a non-Borel clone and an ideal with a Borel clone
- A survey of clones on infinite sets
- Autour De La Propriété Du Petit Indice
- Can you take Solovay's inaccessible away?
- Classifying the Complexity of Constraints Using Finite Algebras
- Closed systems of functions and predicates
- Complexity of constraints. An overview of current research themes
- Constraint Satisfaction Problems with Infinite Templates
- Constraint Satisfaction with Countable Homogeneous Templates
- Counterexamples to a conjecture on relative categoricity
- Extending partial isomorphisms for the small index property of many \(\omega\)-categorical structures
- Finite degree: algebras in general and semigroups in particular
- Finitely related clones and algebras with cube terms.
- Homomorphism-Homogeneous Relational Structures
- Infinite permutation groups. II: Subgroups of small index
- Oligomorphic transformation monoids and homomorphism-homogeneous structures
- On pseudovarieties
- Quasi finitely axiomatizable totally categorical theories
- Subgroups of small Index in infinite Symmetric Groups
- The Birkhoff theorem for finite algebras
- The Birkhoff theorem for varieties of finite algebras
- The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
- The Small Index Property for ω‐Stable ω‐Categorical Structures and for the Random Graph
- Total Ordering Problem
- Unitary representations of oligomorphic groups
- \({\aleph_{0}}\)-categorical structures: endomorphisms and interpretations
Cited in
(36)- PROJECTIVE CLONE HOMOMORPHISMS
- On the descriptive complexity of temporal constraint satisfaction problems
- CORES OVER RAMSEY STRUCTURES
- Uniform Birkhoff
- Reconstructing the topology of clones
- Smooth approximations: an algebraic approach to CSPs over finitely bounded homogeneous structures
- On a stronger reconstruction notion for monoids and clones
- Homogeneous structures: model theory meets universal algebra. Abstracts from the workshop held January 3--9, 2021 (online meeting)
- scientific article; zbMATH DE number 1264888 (Why is no real title available?)
- A complexity dichotomy in spatial reasoning via Ramsey theory
- Galois theory for semiclones
- A dichotomy for first-order reducts of unary structures
- A counterexample to the reconstruction of -categorical structures from their endomorphism monoid
- Polymorphism clones of homogeneous structures: gate coverings and automatic homeomorphicity
- Reconstructing the topology of the elementary self-embedding monoids of countable saturated structures
- An order out of nowhere: a new algorithm for infinite-domain CSPs
- \( \omega \)-categorical structures avoiding height 1 identities
- Generalized completion problems with forbidden tournaments
- Smooth approximations and relational width collapses
- An algebraic proof of the dichotomy for graph orientation problems with forbidden tournaments
- Hrushovski's encoding and -categorical CSP monsters
- Complexity classification transfer for CSPs via algebraic products
- When symmetries are not enough: a hierarchy of hard constraint satisfaction problems
- Equations in oligomorphic clones and the constraint satisfaction problem for \(\omega \)-categorical structures
- A topological characterisation of endomorphism monoids of countable structures
- Exploring new topologies for the theory of clones
- Smooth approximations and CSPs over finitely bounded homogeneous structures
- Polish topologies on endomorphism monoids of relational structures
- Taylor's modularity conjecture and related problems for idempotent varieties
- A uniform Birkhoff theorem
- The wonderland of reflections
- The language of stratified sets is confluent and strongly normalising
- Topology Is Irrelevant (In a Dichotomy Conjecture for Infinite Domain Constraint Satisfaction Problems)
- Reconstructing the topology on monoids and polymorphism clones of the rationals
- Solving equation systems in ω-categorical algebras
- Constraint satisfaction problems for reducts of homogeneous graphs
This page was built for publication: Topological Birkhoff
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5496670)
