Varieties with decidable finite algebras. II: Permutability
type: Item
instance of: scholarly article
title: Varieties with decidable finite algebras. II: Permutability
zbMATH Open document ID: 0679.08003
DOI: 10.1007/BF01236871
author: Paweł M. Idziak
published in: Algebra Universalis
publication date: 1989-01-01T00:00:00Z
review text: [This article is reviewed together with the preceding one (see Zbl 0679.08002).] The two papers prove the following theorem (which refines the main result of \textit{P. M. Idziak}'s paper [ibid. 26, No.1, 33-47 (1989; Zbl 0668.08008)]): If V is a finitely generated variety of finite type and congruence distributive, then the following are equivalent: (1) \(Th(V_{fin})\) is decidable, (2) \(Th(V_{fin})\) is not hereditarily undecidable, (3) V is congruence permutable and congruence linear. (Congruence linearity means that in any subdirectly irreducible algebra of V, congruences form a chain; \(V_{fin}\) is the class of finite algebras in V.) Let V be a congruence distributive variety. Part I shows that if V has a finite subdirectly irreducible algebra, with two incomparable congruences, then \(Th(V_{fin})\) is hereditarily undecidable. Part II shows that if V has a finite algebra with non- permutable congruences, then \(Th(V_{fin})\) is hereditarily undecidable. The proofs use semantical interpretation and a special kind of Boolean power. A noteworthy lemma shows that, for a congruence modular variety, having a finite algebra with non-permutable congruences implies having a finite algebra A and two atoms in Con(A) which do not permute.
Mathematics Subject Classification ID: 08B10
Mathematics Subject Classification ID: 03B25
zbMATH DE Number: 4112669
zbMATH Keywords: finitely generated variety
zbMATH Keywords: congruence distributive
zbMATH Keywords: decidable
zbMATH Keywords: congruence permutable
zbMATH Keywords: congruence linear
zbMATH Keywords: subdirectly irreducible algebra
zbMATH Keywords: hereditarily undecidable
zbMATH Keywords: semantical interpretation
zbMATH Keywords: Boolean power
zbMATH Keywords: congruence modular
reviewed by: Aldo Ursini
MaRDI profile type: Publication
cites work: Decidability and Boolean representations
cites work: Varieties with decidable finite algebras. I: Linearity
description: scientific article; zbMATH DE number 4112669