2021/09/03 by Rob Egrot, Egrot, Rob, Robin Hirsch +1
Computer Science · #03G15 #Advanced Algebra and Logic #FOS: Mathematics #Logic (math.LO) #Logic, Reasoning, and Knowledge #Logic, programming, and type systems
paper · pdf · doi:10.48550/arxiv.2109.01357
openalex publication_date 2021/09/03 · openalex created_date 2021/09/13 · openalex updated_date 2026/07/28
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, 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.