Deductive systems and finite axiomatization properties

Thumbnail Image
Pałasińska, Katarzyna
Major Professor
Don Pigozzi
Committee Member
Journal Title
Journal ISSN
Volume Title
Research Projects
Organizational Units
Organizational Unit
Journal Issue
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.

Subject Categories
Sat Jan 01 00:00:00 UTC 1994