Relation algebras from cylindric algebras. II
type: Item
instance of: scholarly article
title: Relation algebras from cylindric algebras. II
zbMATH Open document ID: 1001.03058
DOI: 10.1016/S0168-0072(01)00085-9
author: Robin Hirsch
author: Ian Hodkinson
published in: Annals of Pure and Applied Logic
publication date: 2002-12-11T00:00:00Z
reviewed by: Roger Maddux
Mathematics Subject Classification ID: 03G15
Mathematics Subject Classification ID: 03C05
Mathematics Subject Classification ID: 03C25
Mathematics Subject Classification ID: 03F20
zbMATH DE Number: 1713720
zbMATH Keywords: relation algebras
zbMATH Keywords: cylindric algebras
zbMATH Keywords: non-finite axiomatizability
MaRDI profile type: Publication
cites work: Complexity of equations valid in algebras of relations. I: Strong non-finitizability
cites work: Q3998034
cites work: Q5616133
cites work: Cylindric algebras. Part II
cites work: Relation algebras from cylindric algebras. I
cites work: Representability is not decidable for finite relation algebras
cites work: Relation algebras with \(n\)-dimensional relational bases
cites work: Relation algebra reducts of cylindric algebras and an application to proof theory
cites work: Q4003410
cites work: Q4011720
cites work: Some Varieties Containing Relation Algebras
cites work: A sequent calculus for relation algebras
cites work: Q4011723
cites work: The origin of relation algebras in the development and axiomatization of the calculus of relations
cites work: Relation algebras of every dimension
cites work: Nonfinite axiomatizability results for cylindric and relation algebras
cites work: On the representation theory for cylindric algebras
cites work: Nonfinitizability of classes of representable cylindric algebras
cites work: Q4040000
cites work: Q4273440
Wikidata QID: Q127932383
review text: If \(K\) and \(L\) are elementary classes with \(K\subseteq L\), then \(K\) is ``not finitely axiomatizable relative to'' \(L\) iff there is no set \(\Sigma\) of first-order sentences with the property that an algebra is in \(K\) iff it is in \(L\) and is also a model of \(\Sigma\). By definition, if \(3\leq m<n<\omega\), then \(\mathbf{S}{\mathsf RaCA}_n\) is the class of subalgebras of relation-algebraic reducts of cylindric algebras of dimension \(n\), \(\mathbf{S}{\mathsf Nr}_m{\mathsf CA}_n\) is the class of subalgebras of neat \(m\)-reducts of cylindric algebras of dimension \(n\), and \({\mathsf RA}_n\) is the class of relation algebras whose perfect extensions have an \(n\)-dimensional relational basis. In this paper it is proved that if \(3\leq m<n<\omega\), then \(\mathbf{S}{\mathsf Nr}_m{\mathsf CA}_{n+1}\) is not finitely axiomatizable relative to \(\mathbf{S}{\mathsf Nr}_m{\mathsf CA}_n\) and \(\mathbf{S}{\mathsf RaCA}_{n+1}\) is not finitely axiomatizable relative to \(\mathbf{S}{\mathsf RaCA}_n\). The construction also shows that \(\mathbf{S}{\mathsf RaCA}_{n+1}\) is not finitely axiomatizable relative to \({\mathsf RA}_{n+1}\) and \(\mathbf{S}{\mathsf RaCA}_{n+1}\) is not finitely axiomatizable relative to \({\mathsf RA}_{n+1}\cap\mathbf{S}{\mathsf RaCA}_n\). The key to these results is the construction, for \(4\leq n<\omega\) and \(0<r<\omega\), of a complete atomic symmetric integral relation algebra \(\mathfrak{A}(n,r)\) whose atoms are \(1\text{{}'}\) and \(a^k(i,j)\) for \(i<n-1\), \(j<r\), and \(k<(nr)^{nr}\), and whose forbidden cycles are \((1\text{{}'},x,y)\) where \(x\neq y\), and also \((a^k(i,j),a^{k'}(i,j),a^{k''}(i,j'))\) where \(j\leq j'\). The algebra \(\mathfrak{A}(n,r)\) is in \({\mathsf RA}_{n+1}\cap\mathbf{S}{\mathsf RaCA}_n\) and not in \(\mathbf{S}{\mathsf RaCA}_{n+1}\), but an ultraproduct of these algebras does lie in \(\mathbf{S}{\mathsf RaCA}_{n+1}\). These are significant results that considerably expand the hierarchies of …
description: scientific article; zbMATH DE number 1713720