Hostname: page-component-cd9895bd7-gxg78 Total loading time: 0 Render date: 2024-12-26T12:48:46.807Z Has data issue: false hasContentIssue false
  • English
  • Français

PROFINITENESS IN FINITELY GENERATED VARIETIES IS UNDECIDABLE

Published online by Cambridge University Press:  21 December 2018

ANVAR M. NURAKUNOV  and
MICHAŁ M. STRONKOWSKI
ANVAR M. NURAKUNOV
Affiliation:
INSTITUTE OF MATHEMATICS NATIONAL ACADEMY OF SCIENCES OF THE KYRGYZ REPUBLIC PR. CHU 265A, BISHKEK720071, KYRGYZSTANE-mail: [email protected]
MICHAŁ M. STRONKOWSKI
Affiliation:
FACULTY OF MATHEMATICS AND INFORMATION SCIENCES WARSAW UNIVERSITY OF TECHNOLOGY UL. KOSZYKOWA 75, 00-662WARSAW, POLAND E-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

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 ${\cal V}$ is standard if every Boolean topological algebra with the algebraic reduct in ${\cal V}$ is profinite.

We show that there is no algorithm which takes as input a finite algebra A of a finite type and decide whether the variety $V\left( {\bf{A}} \right)$ generated by A 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 theorem saying that there is no algorithm which takes as input a finite algebra A of a finite type and decides whether $V\left( {\bf{A}} \right)$ 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.

Keywords

22A3003D3503C0506E1508B25profinite algebrasstandard varietiesundecidability
Type
Articles
Information
The Journal of Symbolic Logic , Volume 83 , Issue 4 , December 2018 , pp. 1566 - 1578
Copyright
Copyright © The Association for Symbolic Logic 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

Baker, K. A., Finite equational bases for finite algebras in a congruence-distributive equational class. Advances in Mathematics, vol. 24 (1977), no. 3, pp. 207–243.CrossRefGoogle Scholar
Baker, K. A. and Wang, J., Definable principal subcongruences. Algebra Universalis, vol. 47 (2002), no. 2, pp. 145–151.CrossRefGoogle Scholar
Burris, S. and Sankappanavar, H. P., A Course in Universal Algebra, Graduate Texts in Mathematics, vol. 78, Springer-Verlag, New York, 1981. The Millennium Edition is available at http://www.math.uwaterloo.ca/snburris/htdocs/ualg.html.CrossRefGoogle Scholar
Clark, D. M. and Davey, B. A., Natural Dualities for the Working Algebraist, Cambridge Studies in Advanced Mathematics, vol. 57, Cambridge University Press, Cambridge, 1998.Google Scholar
Clark, D. M., Davey, B. A., Freese, R. S., and Jackson, M., Standard topological algebras: Syntactic and principal congruences and profiniteness. Algebra Universalis, vol. 52 (2004), pp. 343–376.CrossRefGoogle Scholar
Clark, D. M., Davey, B. A., Haviar, M., Pitkethly, J. G., and Talukder, M. R., Standard topological quasi-varieties. Houston Journal of Mathematics, vol. 29 (2003), no. 4, pp. 859–887.Google Scholar
Clark, D. M., Davey, B. A., Jackson, M. G., and Pitkethly, J. G., The axiomatizability of topological prevarieties. Advances in Mathematics, vol. 218 (2008), no. 5, pp. 1604–1653.CrossRefGoogle Scholar
Clark, D. M. and Krauss, P. H., Topological quasivarieties. Acta Scientiarum Mathematicarum (Szeged), vol. 47 (1984), no. 1–2, pp. 3–39.Google Scholar
Clinkenbeard, D. J., Simple compact topological lattices. Algebra Universalis, vol. 9 (1979), no. 3, pp. 322–328.CrossRefGoogle Scholar
Czelakowski, J. and Dziobiak, W., The parameterized local deduction theorem for quasivarieties of algebras and its application. Algebra Universalis, vol. 35 (1996), no. 3, pp. 373–419.CrossRefGoogle Scholar
Davey, B. A., Duality theory on ten dollars a day, Algebras and Orders (Rosenberg, I. G. and Sabidussi, G., editors), NATO Advanced Science Institutes Series B: Physics, vol. 389, Kluwer Academic Publishers, Dordrecht, 1993, pp. 71–111.CrossRefGoogle Scholar
Davey, B. A., Jackson, M., Maróti, M., and McKenzie, R. N., Principal and syntactic congruences in congruence-distributive and congruence-permutable varieties. Journal of the Australian Mathematical Society, vol. 85 (2008), no. 1, pp. 59–74.CrossRefGoogle Scholar
Jackson, M., Residual bounds for compact totally disconnected algebras. Houston Journal of Mathematics, vol. 34 (2008), no. 1, pp. 33–67.Google Scholar
Johnstone, P. T., Stone Spaces, Cambridge Studies in Advanced Mathematics, vol. 3, Cambridge University Press, Cambridge, 1986. Reprint of the 1982 edition.Google Scholar
McKenzie, R., Para primal varieties: A study of finite axiomatizability and definable principal congruences in locally finite varieties. Algebra Universalis, vol. 8 (1978), no. 3, pp. 336–348.CrossRefGoogle Scholar
McKenzie, R., The residual bound of a finite algebra is not computable. International Journal of Algebra and Computation, vol. 6 (1996), no. 1, pp. 29–48.CrossRefGoogle Scholar
Moore, M., The undecidability of the definability of principal subcongruences, this Journal, vol. 80 (2015), no. 2, pp. 384–432.Google Scholar
Moore, M., The variety generated by $\mathbb A\left( {\cal T} \right)$—Two counterexamples. Algebra Universalis, vol. 75 (2016), no. 1, pp. 21–31.CrossRefGoogle Scholar
Nurakunov, A. M. and Stronkowski, M. M., Quasivarieties with definable relative principal subcongruences. Studia Logica, vol. 92 (2009), no. 1, pp. 109–120.CrossRefGoogle Scholar
Nurakunov, A. M. and Stronkowski, M. M., Relation formulas for protoalgebraic equality free quasivarieties; Pałasińska’s theorem revisited. Studia Logica, vol. 101 (2013), no. 4, pp. 827–847.CrossRefGoogle Scholar
Pontryagin, L. S., Topological Groups, Translated from the second Russian edition by Brown, Arlen, Gordon and Breach Science Publishers, Inc., New York-London-Paris, 1966.Google Scholar
Priestley, H. A., Representation of distributive lattices by means of ordered stone spaces. Bulletin of the London Mathematical Society, vol. 2 (1970), pp. 186–190.CrossRefGoogle Scholar
Schneider, F. M. and Zumbrägel, J., Profinite algebras and affine boundedness. Advances in Mathematics, vol. 305 (2017), pp. 661–681.CrossRefGoogle Scholar
Stone, M. H., The theory of representations for Boolean algebras. Transactions of the American Mathematical Society, vol. 40 (1936), no. 1, pp. 37–111.Google Scholar
Stralka, A., A partially ordered space which is not a Priestley space. Semigroup Forum, vol. 20 (1980), no. 4, pp. 293–297.CrossRefGoogle Scholar
Taylor, W., Varieties of topological algebras. The Journal of the Australian Mathematical Society. Series A, vol. 23 (1977), no. 2, pp. 207–241.CrossRefGoogle Scholar
Wang, J., A proof of the Baker conjecture. Acta Mathematica Sinica, vol. 33 (1990), no. 5, pp. 626–633.Google Scholar