Some open questions in algebraic logic
Attributions are to the best of my knowledge -- corrections welcome, as
are solutions.
Below, unless otherwise stated, n denotes a finite integer.
-
Is RRA axiomatisable in first-order logic with n variables, for any
finite
n?
-
Is SRaCA5 closed under completions?
(For n>5, SRaCAn is not closed under completions.)
- Is RA5 closed under completions?
(For n>5, RAn is not closed under completions.)
- Let n>4. Is there a set of canonical equations
axiomatising SRaCAn? Or RAn?
- Is there a variety of BAOs that is closed under completions
(hence canonical) but with no canonical axiomatisation?
- Str RCAn is the class of atom structures
of full complex algebras that are representable n-dimensional cylindric algebras.
For infinite n, is Str RCAn an elementary class?
(For n<3, Str RCAn is elementary,
and for finite n at least 3, Str RCAn is non-elementary.)
-
It is known that RAn properly contains SRaCAn
for
each n>4, and that SRaCAn is not finitely axiomatisable
over
RAn, but that the intersection of all RAn is RRA,
which is contained in any given SRaCAn.
Is there a function f:\omega -> \omega such that RAf(n)\subseteq
SRaCAn for all n>4?
Is there a recursive f?
- Is every algebra in SRaCAn (n>4) embeddable in an atomic relation algebra
with a n-dimensional
cylindric basis?
(Not every atomic algebra in SRaCAn has a n-dimensional
cylindric basis itself. E.g., a representable projective-plane Lyndon
algebra
with at least 6 atoms has no 5-dimensional cylindric basis. But it
clearly
embeds in an atomic relation algebra with such a basis.)
- [R Maddux] Is it decidable whether a finite relation algebra has
a finite
representation (i.e., with finite base)?
-
For fixed finite n at least 5, is it decidable whether a finite
relation
algebra is a subalgebra of the relation algebra reduct of a finite n-dimensional cylindric
algebra?
(It is undecidable whether a finite relation algebra is a subalgebra of the relation algebra reduct
of
a possibly infinite n-dimensional cylindric algebra - i.e., is in SRaCAn.)
- [R Maddux] What is the limiting probability of a finite
relation algebra being representable?
Problems of T S Ahmed:
-
Is there an uncountable atomic algebra A in Nr3CA\omega
which has no complete representation? (For countable algebras the
answer is `no'.)
-
Is the intersection of Nr3CAn for finite n equal
to Nr3CA\omega?
-
What can be said about the number of different CA\omegas
that
a given CA3 can be a neat reduct of?
Ian Hodkinson, Nov 2008, amended Mar 2012