Deductive systems and finite axiomatization properties
Is Version Of
The notions of a deductive system, equational logic and Gentzen system can be generalized into the notion of a K-deductive system. A universal Horn logic is also a K-deductive system. In Part I the relationship between the existence of equivalence K-terms in a K-deductive system and some semantical properties of these systems is studied. In particular, a K-deductive system S has a finite system of equivalence formulas with parameters if the Leibniz operator on the filter lattice of every S-matrix is monotone. An equivalent semantics theorem, characterizing K-deductive systems that are equivalent to some Birkhoff-like systems, is proved and used to characterize algebraizable K-deductive systems. The connection between the implication terms and semantical properties of one-deductive systems is investigated.;In Part II a finite basis theorem for finitely generated filter-distributive proto-quasivarieties is proved. It says that if the language has only finitely many symbols, and if a K-deductive, filter-distributive, protoalgebraic system S is determined by a finite set of finite matrices, then S has a basis consisting of finitely many axioms and rules of inference. This theorem extends Pigozzi's finite basis theorem for relatively congruence-distributive quasivarieties and therefore also Baker's finite basis theorem for congruence-distributive varieties. If all tautologies of a finite matrix can be derived using only finitely many axioms and rules, then the matrix is called finitely axiomatizable. In particular, a finite algebra A is called finitely axiomatizable if there is a finite set of quasi-identities of A from which every identity of A can be derived. In Part III we consider the problem of finite axiomatizability of finite matrices and finite algebras. Three-element nonfinitely axiomatizable matrices are given. This solves the problem of finding a smallest and "simplest" possible non-finitely axiomatizable matrix that was posed by Rautenberg, independently by Wojtylak and restated by Dziobiak. Examples, that show that the underlying algebra of a finite nonfinitely axiomatizable matrix can be finitely axiomatizable, are given. The notion of the second-order finite axiomatization is proposed and two sufficient conditions for a finite algebra to be second-order finitely axiomatizable are presented.