On Strong Structural Completeness of Varieties and Quasivarieties

Jul 16, 2026

The paper studies strong structural completeness for varieties and quasivarieties in the infinitary algebraic sense. A variety is structurally complete when generated as a quasivariety by its free algebras, and strongly structurally complete when generated as a prevariety by its free algebras. It proves that quasivarieties of finite type with the CEP, generated by finite algebras and containing an infinite irreducible algebra, fail to be SSCpl. It also characterizes when congruence meetsemidistributive varieties of finite type are SSCpl via tabularity, and derives consequences for Dummett’s and Medvedev’s logics.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages16

Reading Time40 min

Introduction

Structural completeness in algebraic logic

Finitary vs infinitary consequence relations

On Strong Structural Completeness of Varieties and Quasivarieties Alex Citkin Metropolitan Telecommunications New York, USA [acitkin@gmail.com](acitkin@gmail.com) We study structural completeness in the infinitary sense (strong structural completeness) in an algebraic setting. A variety is structurally complete (SCpl) if it is generated, as a quasivariety, by its free algebras, and it is strongly structurally complete (SSCpl) if it is generated, as a prevariety, by its free algebras. A quasivariety is SSCpl if it is generated, as a prevariety, by its free algebras. We prove that every quasivariety of finite type with the CEP that is generated by finite algebras and contains an infinite irreducible algebra is not SSCpl. Moreover, every congruence meetsemidistributive variety of finite type generated by finite algebras is SSCpl if and only if it is tabular. Thus, Dummett’s and Medvedev’s logics are SCpl but not SSCpl. A variety is primitive if it is SCpl and all its subvarieties are SCpl; it is strongly primitive if it is SSCpl and all its subvarieties are SSCpl. We prove that in primitive congruence-distributive varieties of finite type, the tabular subvarieties, and only those, are strongly primitive. This observation also yields a criterion for strong primitivity. Keywords: structural completeness, structural completeness in the infinitary sense, varieties of algebras, quasivarieties, prevarieties, primitive varieties 1 Introduction Propositional logic, understood as a consequence relation, can be defined in two ways: syntactically, by a deductive system—a pair consisting of a set of axioms and a set of structural inference rules—and semantically, by a class of models that, for each valuation (assignment), validates the conclusion whenever all the premises are validated. Since derivations are finite sequences of formulas, every deductive system defines a finitary structural consequence relation, whose equivalent algebraic semantics is a quasivariety (see [3]) . Moreover, any finitary structural consequence relation can be axiomatized by a deductive system (see [16]) . In addition, it was proved there that if the defining matrix is finite, then the consequence relation (or operator) determined by it is finitary. However, in general, consequence relations determined by an infinite algebra or by a class of algebras need not be finitary: even the simplest infinite Heyting algebra of order type ω + 1 determines a nonfinitary consequence relation. Note that this consequence relation is also determined by the class of all finite linearly ordered Heyting algebras; thus, infinite classes of finite algebras may define a non-finitary consequence relation. Not surprisingly, any finite set of similar finite algebras of finite type always determines a finitary consequence relation (see Section 3, where we give an algebraic proof of a generalization of the theorem from [16, Section 8], stating that a consequence relation defined by a finite matrix is finitary) . On the other hand, in Section 2, we prove that any infinite set of pairwise nonisomorphic finite algebras from a congruence semi-distributive variety always defines a non-finitary consequence relation. This justifies the interest in studying infinitary consequence relations. M. Bílková, M. Gattinger, I. van der Giessen, M. Girlando, Y. Wang (Eds.): Advances in Modal Logic 2026 (AiML 2026) EPTCS 447, 2026, pp. 262–277, doi:10.4204/EPTCS.447.15 © Alex Citkin This work is licensed under the Creative Commons Attribution License. Alex Citkin 263 The algebraic counterparts of finitary consequence relations are quasivarieties, that is, classes of algebras that can be defined by a set of quasiequations. A quasiequation is a κ-quasiequation of the form ε1 , . . . , εn ⇒ ε , where ε , εi (1 ≤ i ≤ n) are equations. Thus, every quasiequation contains only finitely many (possibly none) premises and therefore only finitely many variables. At the same ti

FAQs

What does it mean for a variety to be strongly structurally complete (SSCpl)?

A variety is SSCpl if it is generated as a prevariety by its free algebras, i.e., its structural completeness holds in the infinitary algebraic sense.

When does a quasivariety of finite type fail to be SSCpl?

Every quasivariety of finite type with the CEP that is generated by finite algebras and contains an infinite irreducible algebra is not SSCpl.

How are SSCpl varieties characterized in congruence meetsemidistributive varieties of finite type?

Every congruence meetsemidistributive variety of finite type generated by finite algebras is SSCpl if and only if it is tabular.

Jul 16, 2026

Upload by Lucas Martin