Profiniteness in finitely generated varieties is undecidable

DOI10.1017/JSL.2017.89zbMATH Open1412.08006arXiv1712.09056OpenAlexW3106192713WikidataQ128776174 ScholiaQ128776174MaRDI QIDQ4647112FDOQ4647112

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

Publication date: 4 January 2019

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

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.

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

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

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)

Cites Work

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

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)