##
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.