Profiniteness in finitely generated varieties is undecidable

DOI10.1017/JSL.2017.89MaRDI QIDQ4647112zbMATH OpenOpenAlexWikidataFDO

Authors Michał M. Stronkowski, A. M. Nurakunov

Publication date 4 January 2019

Published in Journal of Symbolic Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1712.09056

zbMATH Keywords

undecidabilityprofinite algebrasstandard varieties

Mathematics Subject Classification ID

Equational classes, universal algebra in model theory (03C05) Other topological algebraic systems and their representations (22A30) Undecidability and degrees of sets of sentences (03D35) Products, amalgamated products, and other kinds of limits and colimits (08B25) Stone spaces (Boolean spaces) and related structures (06E15)

Abstract: Profinite algebras are exactly those that are isomorphic to inverse limits of finite algebras. Such algebras are naturally equipped with Boolean topologies. A variety $mathcalV$ is standard if every Boolean topological algebra with the algebraic reduct in $mathcalV$ is profinite. We show that there is no algorithm which takes as input a finite algebra $mathbfA$ of a finite type and decide whether the variety $mathcalV(mathbfA)$ generated by $mathbfA$ is standard. We also show the undecidability of some related properties. In particular, we solve a problem posed by Clark, Davey, Freese and Jackson. We accomplish this by combining two results. The first one is Moore's result saying that there is no algorithm which takes as input a finite algebra $mathbfA$ of a finite type and decides whether $mathcalV(mathbfA)$ has definable principal subcongruences. The second is our result saying that possessing definable principal subcongruences yields possessing finitely determined syntactic congruences for varieties. The latter property is known to yield standardness.

Recommendations

• Standard topological algebras: syntactic and principal congruences and profiniteness
• A sufficient condition for finite decidability
• The undecidability of the definability of principal subcongruences
• Finitely Decidable Congruence Modular Varieties
• Varieties with decidable finite algebras. II: Permutability

Cites work

• scientific article; zbMATH DE number 432733 (Why is no real title available?)
• scientific article; zbMATH DE number 3940199 (Why is no real title available?)
• scientific article; zbMATH DE number 3751028 (Why is no real title available?)
• scientific article; zbMATH DE number 7218 (Why is no real title available?)
• scientific article; zbMATH DE number 3572729 (Why is no real title available?)
• scientific article; zbMATH DE number 1226180 (Why is no real title available?)
• scientific article; zbMATH DE number 2171495 (Why is no real title available?)
• scientific article; zbMATH DE number 3893269 (Why is no real title available?)
• A partially ordered space which is not a Priestley space
• Definable principal subcongruences.
• Finite equational bases for finite algebras in a congruence-distributive equational class
• PRINCIPAL AND SYNTACTIC CONGRUENCES IN CONGRUENCE-DISTRIBUTIVE AND CONGRUENCE-PERMUTABLE VARIETIES
• Para primal varieties: A study of finite axiomatizability and definable principal congruences in locally finite varieties
• Profinite algebras and affine boundedness
• Quasivarieties with definable relative principal subcongruences
• Relation formulas for protoalgebraic equality free quasivarieties; Pałasińska's theorem revisited
• Representation of Distributive Lattices by means of ordered Stone Spaces
• Residual bounds for compact totally disconnected algebras
• Simple compact topological lattices
• Standard topological algebras: syntactic and principal congruences and profiniteness
• THE RESIDUAL BOUND OF A FINITE ALGEBRA IS NOT COMPUTABLE
• The Theory of Representation for Boolean Algebras
• The axiomatizability of topological prevarieties
• The parameterized local deduction theorem for quasivarieties of algebras and its application
• The undecidability of the definability of principal subcongruences
• The variety generated by \(\mathbb {A}(\mathcal {T})\) -- two counterexamples

Cited in

(6)

• Finitary PCF is not decidable
• Finite degree clones are undecidable
• The complexity of quasivariety lattices. II
• Profinite locally finite quasivarieties
• DETERMINING WHETHER ${\mathsf V}({\bf A})$ HAS A MODEL COMPANION IS UNDECIDABLE
• Bounded generation does not imply finite presentation

This page was built for publication: Profiniteness in finitely generated varieties is undecidable

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4647112)