eprintid: 10139073
rev_number: 12
eprint_status: archive
userid: 608
dir: disk0/10/13/90/73
datestamp: 2021-11-25 08:10:58
lastmod: 2021-11-25 08:10:58
status_changed: 2021-11-25 08:10:58
type: article
metadata_visibility: show
creators_name: Egrot, ROB
creators_name: Hirsch, ROBIN
title: FIRST-ORDER AXIOMATISATIONS of REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS of UNBOUNDED QUANTIFIER DEPTH
ispublished: inpress
divisions: UCL
divisions: B04
divisions: C05
divisions: F48
note: This version is the author accepted manuscript. For information on re-use, please refer to the publisher’s terms and conditions.
abstract: Using a variation of the rainbow construction and various pebble and colouring games, we prove that RRA, the class of all representable relation algebras, cannot be axiomatised by any first-order relation algebra theory of bounded quantifier depth. We also prove that the class At(RRA) of atom structures of representable, atomic relation algebras cannot be defined by any set of sentences in the language of RA atom structures that uses only a finite number of variables.
date: 2021
date_type: published
official_url: https://doi.org/10.1017/jsl.2021.88
oa_status: green
full_text_type: other
language: eng
primo: open
primo_central: open_green
verified: verified_manual
elements_id: 1902818
doi: 10.1017/jsl.2021.88
lyricists_name: Hirsch, Robin
lyricists_id: RHIRS08
actors_name: Flynn, Bernadette
actors_id: BFFLY94
actors_role: owner
full_text_status: public
publication: Journal of Symbolic Logic
issn: 0022-4812
citation:        Egrot, ROB;    Hirsch, ROBIN;      (2021)    FIRST-ORDER AXIOMATISATIONS of REPRESENTABLE RELATION ALGEBRAS NEED FORMULAS of UNBOUNDED QUANTIFIER DEPTH.                   Journal of Symbolic Logic        10.1017/jsl.2021.88 <https://doi.org/10.1017/jsl.2021.88>.    (In press).    Green open access   
 
document_url: https://discovery.ucl.ac.uk/id/eprint/10139073/1/first-order-axiomatisations-of-representable-relation-algebras-need-formulas-of-unbounded-quantifier-depth.pdf