Conjecture (1) of [Ma83] is confirmed here by the following result: if $3 \leq \alpha < \omega$, then there is a finite relation algebra of dimension $\alpha$, which is not a relation algebra of dimension $\alpha + 1$. A logical consequence of this theorem is that for every finite $\alpha \geq 3$ there is a formula of the form $S \subseteq T$ (asserting that one binary relation is included in another), which is provable with $\alpha + 1$ variables, but not provable with only $\alpha$ variables (using a special sequent calculus designed for deducing properties of binary relations).
Publié le : 1992-12-14
Classification:
Logic,
Complexity of proofs,
provability with finitely many variables,
relation algebras,
relational basis,
dimension,
03G15,
03F20
@article{1183744112,
author = {Maddux, Roger D.},
title = {Relation Algebras of Every Dimension},
journal = {J. Symbolic Logic},
volume = {57},
number = {1},
year = {1992},
pages = { 1213-1229},
language = {en},
url = {http://dml.mathdoc.fr/item/1183744112}
}
Maddux, Roger D. Relation Algebras of Every Dimension. J. Symbolic Logic, Tome 57 (1992) no. 1, pp. 1213-1229. http://gdmltest.u-ga.fr/item/1183744112/