NOTIONS OF DENSITY THAT IMPLY REPRESENTABILITY IN ALGEBRAIC LOGIC

Henkin and Tarski proved that an atomic cylindric algebra in which eve ry atom is a rectangle must be representable (as a cylindric set algeb ra). This theorem and its analogues for quasi-polyadic algebras with a nd without equality are formulated in Henkin, Monk and Tarski [13]. We introduce a natural and more general notion of rectangular density th at can be applied to arbitrary cylindric and quasi-polyadic algebras, not just atomic ones. We then show that every rectangularly dense cyli ndric algebra is representable, and we extend this result to other cla sses of algebras of logic, for example quasi-polyadic algebras and sub stitution-cylindrification algebras with and without equality, relatio n algebras, and special Boolean monoids. The results of op. cit. menti oned above are special cases of our general theorems. We point out an error in the proof of the Henkin-Monk-Tarski representation theorem fo r atomic, equality-free, quasi-polyadic algebras with rectangular atom s. The error consists in the implicit assumption of a property that do es not, in general, hold. We then give a correct proof of their theore m. Henkin and Tarski also introduced the notion of a rich cylindric al gebra and proved in op. cit. that every rich cylindric algebra of fini te dimension (or, more generally, of locally finite dimension) satisfy ing certain special identities is representable. We introduce a modifi cation of the notion of a rich algebra that, in our opinion, renders i t more natural. In particular, under this modification richness become s a density notion. Moreover, our notion of richness applies not only to algebras with equality, such as cylindric algebras, but also to alg ebras without equality. We show that a finite dimensional algebra is r ich iff it is rectangularly dense and quasi-atomic; moreover, each of these conditions is also equivalent to a very natural condition of poi nt density. As a consequence, every finite dimensional (or locally fin ite dimensional) rich algebra of logic is representable. We do not hav e to assume the validity of any special identities to establish this r epresentability. Not only does this give an improvement of the Henkin- Tarski representation theorem for rich cylindric algebras. it solves p ositively an open problem in op. cit. concerning the representability of finite dimensional rich quasi-polyadic algebras without equality. ( C) 1998 Published by Elsevier Science B.V. All rights reserved.