Non-finite-axiomatizability results in algebraic logic

E-ISSN： 1943-5886|57|3|832-843

ISSN： 0022-4812

Source： The Journal of Symbolic Logic, Vol.57, Iss.3, 1992-09, pp. : 832-843

Disclaimer: Any content in publications that violate the sovereignty, the constitution or regulations of the PRC is not accepted or approved by CNPIEC.

Previous Menu Next

Abstract

This paper deals with relation, cylindric and polyadic equality algebras. First of all it addresses a problem of B. Jónsson. He asked whether relation set algebras can be expanded by finitely many new operations in a “reasonable” way so that the class of these expansions would possess a finite equational base. The present paper gives a negative answer to this problem: Our main theorem states that whenever Rs⁺ is a class that consists of expansions of relation set algebras such that each operation of Rs⁺ is logical in Jónsson's sense, i.e., is the algebraic counterpart of some (derived) connective of first-order logic, then the equational theory of Rs⁺ has no finite axiom systems. Similar results are stated for the other classes mentioned above. As a corollary to this theorem we can solve a problem of Tarski and Givant [87], Namely, we claim that the valid formulas of certain languages cannot be axiomatized by a finite set of logical axiom schemes. At the same time we give a negative solution for a version of a problem of Henkin and Monk [74] (cf. also Monk [70] and Németi [89]).