Back to Search Start Over

A corrected strategy for proving no finite variable axiomatisation exists for RRA

Authors :
Egrot, Rob
Hirsch, Robin
Publication Year :
2021

Abstract

We show that if for all finite $c$ there is a pair of non-isomorphic finite digraphs satisfying some additional conditions, one of which is that they cannot be distinguished in a certain $c$-colour node colouring game, then there can be no axiomatisation of the class of representable relation algebras in any first-order theory of arbitrary quantifier-depth using only finitely many variables. This corrects the proposed strategy of Hirsch and Hodkinson, \emph{Relation algebras by games}, North-Holland (2002), Problem 1. However, even for $c=2$, no pair of non-isomorphic graphs indistinguishable in the game is currently known.<br />Comment: This note is extracted from an earlier version of arXiv:2008.01329. A later version of this latter paper will omit this material

Subjects

Subjects :
Mathematics - Logic
03G15

Details

Database :
arXiv
Publication Type :
Report
Accession number :
edsarx.2109.01357
Document Type :
Working Paper