Ivo Düntsch - WWW Library

Title: Expressibility of properties of relations
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: Journal of Symbolic Logic 60 (1995), 970 - 991
Abstract: We investigate in an algebraic setting the question in which logical languages the properties of being integral, permutational, or rigid of (algebras of) relations can be expressed. Vice versa, we discuss if and how these properties of concrete relations can be prescribed by the algebraic structure of the corresponding relation algebras. It turns out that a simple representable relation algebra A is integral (i.e. the identity relation is an atom of the Boolean part of A) if and only if in the corresponding first order structure no proper nonempty subset of the universe is definable by a formula with at most three variables. We also show that the property of a relation algebra to be permutational (i.e. having a representation with a transitive group of base automorphisms) is a general first order property, and that the negation of this property is not general first order. Furthermore, a binary relation is shown to be permutational if and only if no proper nonempty subset of the universe U is definable in the model <U,R>. Most results are generalised to n - ary relations and their (cylindric) algebras.

Rigidity turns out to be diametrically opposed to permuta tional: We show that, on finite sets, a binary relation R is rigid if and only if every subset of the universe U is definable in the model <U,R>, and we prove that rigidity is not expressible over finite sets in various extensions of first order logic, including existential MSO with built in linear order, and existential SO restricted to the Bernays - Schoenfinkel quantifier prefix class.

View technical report version