Hajnal Andreka, Steven Givant, Szabolcs Mikulas, Istvan Nemeti, and Andras Simon

NOTIONS OF DENSITY THAT IMPLY REPRESENTABILITY IN ALGEBRAIC LOGIC

Abstract: Henkin and Tarski proved that an atomic cylindric algebra in which every atom is a rectangle must be representable (as a cylindric set algebra). This theorem and its analogues for quasi-polyadic algebras with and without equality are formulated in the Henkin-Monk-Tarski monograph on cylindric algebras [HMT].

We introduce a natural and more general notion of rectangular density that can be applied to arbitrary cylindric and quasi-polyadic algebras, not just atomic ones. We then show that every rectangularly dense cylindric algebra is representable, and we extend this result to other classes of algebras of logic, for example quasi-polyadic algebras and substitution-cylindrification algebras with and without equality, relation algebras, and special Boolean monoids. The results of [HMT] mentioned above are special cases of our general theorems.

We point out an error in the proof of the [HMT] representation theorem for atomic equality-free quasi-polyadic algebras with rectangular atoms. The error consists in the implicit assumption of a property that does not, in general, hold. We then give a correct proof of their theorem.

Henkin and Tarski also introduced the notion of a rich cylindric algebra and proved in [HMT] that every rich cylindric algebra of finite dimension (or, more generally, of locally finite dimension) satisfying certain special identities is representable.

We introduce a modification of the notion of a rich algebra that, in our opinion, renders it more natural. In particular, under this modification richness becomes a density notion. Moreover, our notion of richness applies not only to algebras with equality, but also to algebras without equality. We show that a finite dimensional algebra is rich iff it is rectangularly dense and quasi-atomic; moreover, each of these conditions is also equivalent to a very natural condition of point density. As a consequence, every finite dimensional (or locally finite dimensional) rich algebra of logic is representable. We do not have to assume the validity of any special identities to establish this representability. Not only does this give an improvement of the Henkin-Tarski representation theorem for rich cylindric algebras, it solves positively an open problem in [HMT] concerning the representability of finite dimensional rich quasi-polyadic algebras without equality.


Retrieve dvi, PostScript or PDF version.