Title:	Binary relations and permutation groups
Authors:	Hajnal Andréka , Mathematical Institute , Hungarian Academy of Sciences, Ivo Düntsch , Dept of Computer Science , Brock University , St Catherines, Ontario, L2S 3A1, Canada István Németi , Mathematical Institute , Hungarian Academy of Sciences,
Status:	Mathematical Logic Quarterly 41 (1995), 197 - 216
Abstract:	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. In this paper, we investigate problems relating to automorphisms (i.e. edge preserving permutations) of binary relations. Our approach will be algebraic using Tarski's relation algebras. Roughly speaking, a relation algebra is a description of how various relations must interact among each other. More concretely, given a set R = {R_i: i < n} of binary relation R on a set U, we form the closure of this set under the Boolean operations, composition of relations, and converse, and add the identity as an extra constant; the result will be an algebra A of binary relations (BRA). Since the operations used are first order definable, any automorphism of the first order structure (U,R) will preserve all the relations in A as well. Such an automorphism will be called a base automorphism of the algebra A (We use the qualified term to distinguish them from the automorphisms of the algebra). A fundamental result by Tarski states that A contains exactly those binary relations on U which are definable in (U,R) by first order formulas having at most three variables. Thus, the equational logic of relation algebras corresponds roughly to the three variable fragment of full first order logic. Conversely, given a representation B of an abstract simple relation algebra A (i.e. B is a BRA isomorphic to A), the algebraic structure of A will tell us something about the properties of and the connections among the relations in B. We exhibit connections between the structure of BRAs and their groups of base automorphisms. The notion of Galois closure will play a major role: A BRA on a finite set U is Galois closed iff its atoms are the orbits of the action of its group of base automorphisms on U x U. The Galois closure of a BRA A on U is the smallest Galois closed algebra above A. It turns out that the nonempty subsets definable by formulas of first order logic in the model (U,R), R in A, are exactly the unions of the atoms of the Galois closure of A which are below the identity - equivalently, the unions of orbits of the group of base automorphisms of A. Furthermore, A is shown to be Galois closed iff A contains all relations definable in the model (U,R), R in A, and that, whenever an edge (a,b) of an atom R of A has a first order property, then all edges of R have this property. We also show that the property of a BRA to be Galois closed is a general first order property for finite models, and that its negation is not. With regard to the question which properties of concrete relations can be prescribed by the structure of an abstract relation algebra, we exhibit an RA A which has a representation with a transitive group of base automorphisms, but no representation of A is Galois closed. This seems a rather strong result: The algebraic structure of A - which in general reflects only logic with three variables - tells us something about a property of all representations of A which is not even general first order. Finally, we show that every BRA 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.

View technical report version