The Two-Variable Guarded Fragment with Transitive Relations

We consider the restriction of the guarded fragment to the two-variable case where, in addition, binary relations may be specied as transitive. We show that (i) this very restricted form of the guarded fragment without equality is undecidable and that (ii) when allowing non-unary relations to occur only in guards, the logic becomes decidable. The latter subclass of the guarded fragment is the one that occurs naturally when translating multi-modal logics of the type K4, S4 or S5 into rst-order logic. We also show that the loosely guarded fragment without equality and with a single transitive relation is undecidable.