Almost structural completeness; an algebraic approach

Wojciech Dzik , Michał Stronkowski

Abstract

A deductive system is structurally complete if all of its admissible inference rules are derivable. For several important systems, like the modal logic S5, failure of structural completeness is caused only by the underivability of a passive rule, i.e., a rule whose premise is not unifiable by any substitution. Neglecting passive rules leads to the notion of almost structural completeness, that means, to the derivability of admissible non-passive rules. We investigate almost structural completeness for quasivarieties and varieties of general algebras. The results apply to all algebraizable deductive systems. Firstly, various characterizations of almost structurally complete quasivarieties are presented. Two of them are general: the one expressed with finitely presented algebras, and the one expressed with subdirectly irreducible algebras. The next one is restricted to quasivarieties with the finite model property and equationally definable principal relative congruences, where the condition is verifiable on finite subdirectly irreducible algebras. Some connections with exact and projective unification are included. Secondly, examples of almost structurally complete varieties are provided. Particular emphasis is put on varieties of closure algebras, that are known to constitute adequate semantics for normal extensions of the modal logic S4. A certain infinite family of such almost structurally complete, but not structurally complete, varieties is constructed. Every variety from this family has a finitely presented unifiable algebra which does not embed into any free algebra for this variety. Hence unification is not unitary there. This shows that almost structural completeness is strictly weaker than projective unification for varieties of closure algebras.
Author Wojciech Dzik
Wojciech Dzik,,
-
, Michał Stronkowski ZAK
Michał Stronkowski,,
- Department of Algebra and Combinatorics
Journal seriesAnnals of Pure and Applied Logic, ISSN 0168-0072
Issue year2016
Vol167
No7
Pages525-556
Publication size in sheets1.55
Keywords in EnglishAlmost structural completeness, Structural completeness, Quasivarieties, Axiomatization, Modal normal logics, Varieties of closure algebras
Abstract in PolishPraca poświęcona jest prawie strukturalnej zupełności, która jest osłabieniem klasycznej własności strukturalnej zupełności dla logik zdaniowych. Przedstawiono algebraiczną analizę nowej własności. Następnie poprzez przedstawienie wielu przykładów uzasadniono dlaczego nowa własność jest lepsza od starej.
DOIDOI:10.1016/j.apal.2016.03.002
URL http://www.sciencedirect.com/science/article/pii/S0168007216300197
Languageen angielski
Score (nominal)25
ScoreMinisterial score = 20.0, 28-11-2017, ArticleFromJournal
Ministerial score (2013-2016) = 25.0, 28-11-2017, ArticleFromJournal
Publication indicators WoS Impact Factor: 2016 = 0.647 (2) - 2016=0.746 (5)
Citation count*0
Cite
Share Share

Get link to the record
msginfo.png


* presented citation count is obtained through Internet information analysis and it is close to the number calculated by the Publish or Perish system.
Back