Finite basis theorems for relatively congruence-distributive quasivarieties

Abstract:

$\mathcal {Q}$ is any quasivariety. A congruence relation $\Theta$ on a member ${\mathbf {A}}$ of $\mathcal {Q}$ is a $\mathcal {Q}$-congruence if ${\mathbf {A}}/\Theta \in \mathcal {Q}$. The set $Co{n_\mathcal {Q}}{\mathbf {A}}$ of all $\mathcal {Q}$-congruences is closed under arbitrary intersection and hence forms a complete lattice ${\mathbf {Co}}{{\mathbf {n}}_\mathcal {Q}}{\mathbf {A}}$. $\mathcal {Q}$ is relatively congruence-distributive if ${\mathbf {Co}}{{\mathbf {n}}_\mathcal {Q}}{\mathbf {A}}$ is distributive for every ${\mathbf {A}} \in \mathcal {Q}$. Relatively congruence-distributive quasivarieties occur naturally in the theory of abstract data types. $\mathcal {Q}$ is finitely generated if it is generated by a finite set of finite algebras. The following generalization of Baker’s finite basis theorem is proved. Theorem I. Every finitely generated and relatively congruence-distributive quasivariety is finitely based. A subquasivariety $\mathcal {R}$ of an arbitrary quasivariety $\mathcal {Q}$ is called a relative subvariety of $\mathcal {Q}$ if it is of the form $\mathcal {V} \cap \mathcal {Q}$ for some variety $\mathcal {V}$, i.e., a base for $\mathcal {R}$ can be obtained by adjoining only identities to a base for $\mathcal {Q}$. Theorem II. Every finitely generated relative subvariety of a relatively congruence-distributive quasivariety is finitely based. The quasivariety of generalized equality-test algebras is defined and the structure of its members studied. This gives rise to a finite algebra whose quasi-identities are finitely based while its identities are not. Connections with logic and the algebraic theory of data types are discussed.