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
- shows strict hierarchy results for neat reducts,
with consequences for proof theory
- develops a representation theory for reducts
and for algebras defined by relational bases
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.
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.
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+i
≠ S 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.
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:
- Sn contains only 3 variables (each of which occurs
many times);
- Sn contains exactly one nonlogical binary relation
symbol (no function symbols, no constants, and no equality symbol);
- Sn has a proof in first-order logic with equality
that contains exactly n variables, but no proof containing only n-1 variables.
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.
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(CAn ∩ Crsn)
= S Ra(CAn ∩ Gn). 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.
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}.
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.
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.
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.