COMPLEXITY OF EQUATIONS VALID IN ALGEBRAS OF RELATIONS
COMPLEXITY OF EQUATIONS VALID IN ALGEBRAS OF RELATIONS
Hajnal Andreka
Complexity of equations valid in algebras of relations
Content of Doctoral Dissertation with the Academy 1991. To appear in APAL.
`
Abstract.
We study algebras whose elements are relations, and the operations are natural
"manipulations" of relations. This area goes back to 140 years ago to works of
de Morgan, Peirce, Schr/"oder. Well known examples of such kinds of algebras
are the varieties RCA_n of cylindric algebras of n-ary relations, RPEA_n
of polyadic equality algebras of n-ary relations, and RRA of binary
relations with composition. We prove that any axiomatization, say E, of
RCA_n has to be very complex in the following sense: for every natura number
k there is an equation in E containing more than k distinct variables
and all the operation symbols, if n>2 is finite. Completely analogous
statement holds for the case when n is infinite. This improves Monk's famous
non-finitizability theorem for which we give here a simple proof. We prove
analogous nonfinitizability properties of the larger varieties SNr_nCA_{n+k}.
We prove that the complementation-free subreducts of RCA_n do not form a
variety. We also investigate the reason for this "non-finite axiomatizability"
behaviour of RCA_n. We look at all the possible reducts of RCA_n and
investigate which are finitely axiomatizable. We obtain several positive
results in this direction. Finally, we summarize the results and remaining
questions on a figure. We carry through the same programme for RPEAN_n and
for RRA. By looking into the reducts we also investigate what other kinds of
natural algebras of relations are possible with more positive behaviour than
that of the well known ones. Our investigations have direct consequences for
the logical properties of the n-variable fragment L_n of first order logic.
The reason for this is that RCA_n and RPEAN_n are the natural algebraic
counterparts of L_n while the varieties SNr_nCA_{n+k} are in connection
with the proof theory of L_n.