Relational bases, relation algebra - cylindric algebra connections

Go to home page   |   Reducts of relation algebras and cylindric algebras

Relation algebras are a common way to treat binary relations algebraically, and n-dimensional cylindric algebras handle n-ary relations. There are various connections between cylindric and relation algebras, and also between cylindric algebras of differing dimension. For example, taking the neat reduct of an n-dimensional cylindric algebra to its first m dimensions (where m<n) yields an m-dimensional cylindric algebra. A similar kind of reduct will turn a cylindric algebra of dimension at least 4 into a relation algebra.

This neat reduct process is closely related to first-order proof theory. Roughly, the laws holding in m-dimensional neat reducts of n-dimensional cylindric algebras correspond to the first-order sentences written with m variables (perhaps re-used) that can be proved using up to n variables.

Finding an intrinsic characterisation of when an algebra is a reduct of another of larger dimension, and studying the hierarchy so induced, has been of interest to workers such as Maddux, Monk, and Tarski since the 1960s. Maddux developed the n-dimensional cylindric basis for this purpose, and the related notion of relational basis. The work in the papers below

Connections between cylindric algebras and relation algebras

R. Hirsch and I. Hodkinson
RelMiCS, Warszawa, 1998
A short survey of our work on approximations to S Ra CAn --- relational bases, cylindric bases, cylindric hyperbases, etc.  Summarises some of the work from the papers below.

Relation algebras with n-dimensional bases

R. Hirsch and I. Hodkinson
Revised version in Ann. Pure Appl. Logic 101 (2000) 227-274
We study relation algebras with n-dimensional relational bases in the sense of Maddux.

Fix n with 3≤ n<ω. Write Bn for the class of semi-associative algebras with an n-dimensional relational basis, and RAn for the variety generated by Bn. We define a notion of representation for algebras in RAn, and use it to give an explicit (hence recursive) equational axiomatisation of RAn, and to reprove Maddux's result that RAn is canonical. We show that the algebras in RAn are precisely those that have a complete representation.

Then we prove that whenever 3< n<k≤ω, RAk is not finitely axiomatisable over RAn. This confirms a conjecture of Maddux. We also prove that Bn is elementary for n=3,4 only.

Relation algebra reducts of cylindric algebras and an application to proof theory

R. Hirsch and I. Hodkinson and R. Maddux
J. Symbolic Logic 67 (2002) 197-213
We show that S Ra CAn strictly contains S Ra CAn+1 for each n with 3 ≤ n < ω. We do this by defining a (finite weakly associative) algebra An and showing that it belongs to S Ra CAn but not to S Ra CAn+1.   This confirms a conjecture of Maddux.

It also shows that S Nrn CAn+iS Nrn CAn+i+1, for 2 < n <ω and i <ω. Here, Nrn denotes the neat reduct of a higher-dimensional cylindric algebra to n dimensions.  This answers question 2.12 of Henkin, Monk & Tarski [Cylindric Algebras Part I, North-Holland, 1971].

Our results show that for n≥4, n-variable proof theory for binary relations is less powerful than (n+1)-variable proof theory.

Provability with finitely many variables

R. Hirsch and I. Hodkinson and R. Maddux
Bull. Symbolic Logic 8 (2002) 348-379
For every finite n > 3 there is a logically valid sentence Sn with the following properties: This result was first proved in Relation algebra reducts of cylindric algebras and an application to proof theory (above) using the machinery of algebraic logic developed in several research monographs and papers.  Here we replicate the result and its proof entirely within the realm of (elementary) first-order binary predicate logic with equality.  We need the usual syntax, axioms, and rules of inference to show that Sn has a proof with only n variables. To show that Sn has no proof with only n-1 variables we use alternative semantics in place of the usual, standard, set-theoretical semantics of first-order logic.

Relation algebras from cylindric algebras, I

R. Hirsch and I. Hodkinson
Ann. Pure Appl. Logic 112 (2001) 225-266
doi: 10.1016/S0168-0072(01)00084-7
We characterise the class S Ra CAn of subalgebras of relation algebra reducts of n-dimensional cylindric algebras (for finite n, at least 4) by the notion of a hyperbasis, analogous to the cylindric basis of Maddux, and by relativised representations.  A corollary is that S Ra CAn = S Ra(CAnCrsn) = S Ra(CAnGn).  We give a game-theoretic approximation to the existence of a representation, and use it to obtain a recursive equational axiomatisation of S Ra CAn.  We include notes on n-variable proof theory, homogeneity, and related matters, and some open problems.

Relation algebras from cylindric algebras, II

R. Hirsch and I. Hodkinson
Ann. Pure Appl. Logic, 112 (2001) 267-297
doi: 10.1016/S0168-0072(01)00085-9
We prove, for each 4 ≤ n < ω, that S Ra CAn+1 cannot be defined, using only finitely many axioms, relative to S Ra CAn.  The construction also shows that for 3≤ m<n<ω, S Nrm CAn+1 is not finitely axiomatisable over S Nrm CAn.  In consequence, for a certain standard n-variable first-order proof system \vdash_{m,n} of m-variable formulas, there is no finite set of m-variable schemata whose m-variable instances, when added to \vdash_{m,n} as axioms, yield \vdash_{m,n+1}.

Weak representations of relation algebras and relational bases

Robin Hirsch, Ian Hodkinson, Roger Maddux
J. Symbolic Logic 76 (2011) 870-882.
It is known that for all finite n≥5, there are relation algebras with n-dimensional relational bases but no weak representations.  We prove that conversely, there are finite weakly representable relation algebras with no n-dimensional relational bases.  In symbols: neither of the classes RAn and wRRA contains the other.

A construction of cylindric and polyadic algebras from atomic relation algebras

Ian Hodkinson
Algebra Universalis 68 (2012) 257-285, doi 10.1007/s00012-012-0202-3.
Abstract Given a simple atomic relation algebra A and a finite n at least 3, we construct effectively an atomic n-dimensional polyadic equality-type algebra P such that for any subsignature L of the signature of P that contains the boolean operations and cylindrifications, the L-reduct of P is completely representable if and only if A is completely representable. If A is finite then so is P.
It follows that there is no algorithm to determine whether a finite n-dimensional cylindric algebra, diagonal-free cylindric algebra, polyadic algebra, or polyadic equality algebra is representable (for diagonal-free algebras this was known). We also obtain a new proof that the classes of completely representable n-dimensional algebras of these types are non-elementary, a result that remains true for infinite dimensions if the diagonals are present, and also for infinite-dimensional diagonal-free cylindric algebras.

Connections between relation algebras and cylindric algebras

Ian Hodkinson
Springer International Publishing Switzerland 2015 --- Proc. RAMiCS 2015, W. Kahl et al. (Eds.), Springer LNCS 9348, pp. 27-42, 2015.
DOI: 10.1007/978-3-319-24704-5_2
Abstract We give an informal description of a recursive representability-preserving reduction of relation algebras to cylindric algebras.