Abstract

We discuss some new properties of the natural Galois connection among set relation algebras, permutation groups, and first order logic. In particular, we exhibit infinitely many permutational relation algebras without a Galois closed representation, and we also show that every relation algebra on a set with at most six elements is Galois closed and essentially unique. Thus, we obtain the surprising result that on such sets, logic with three variables is as powerful in expression as full first order logic. Key words: Relation algebras, Galois closure, clones of operations 0 Introduction and summary of results Logics with limited resources as well as questions of expressibility of relational properties- in particular on finite structures- have received considerable attention in areas like finite model theory, non- classical logics, and descriptive complexity. The interested reader is invited to consult [9], [11], [12], and [14] for more details. In this paper, we shall investigate problems relating to automorphism