View technical report version
| 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
|