×

Complete description of substitutions in cylindric algebras and other algebraic logics. (English) Zbl 0797.03062

Rauszer, Cecylia (ed.), Algebraic methods in logic and in computer science. Papers of the XXXVIII semester on algebraic methods in logic and their computer science applications held in Warsaw (Poland) between September 15 and December 15, 1991. Warsaw: Polish Academy of Sciences, Institute of Mathematics. Banach Cent. Publ. 28, 327-342 (1993).
The main result of this paper provides sets of defining relations for the full semigroups of finite non-permutational transformations of a set into itself. Let \(I\) be a set with two or more elements. For distinct \(i\) and \(j\) in \(I\), let \([i/j]\) be the function (called a replacement) that sends \(i\) to \(j\) and leaves all other elements of \(I\) unchanged. Let \(NP(I)\) be the set of functions from \(I\) to \(I\) that are not permutations and leave all but finitely many elements of \(I\) fixed. \(NP(I)\) forms a semigroup under composition. For every semigroup \(S\), the map that sends each replacement \([i/j]\) to \(t^ i_ j\in S\) extends to a homomorphism from \(NP(I)\) to \(S\) if and only if, for all distinct \(i,j,k,m,n\in I\), \(t^ i_ j t^ i_ j= t^ i_ j\), \(t^ i_ j t^ i_ k= t^ i_ j\), \(t^ i_ j t^ j_ i= t^ j_ i\), \(t^ i_ j t^ j_ k= t^ i_ k t^ j_ k\), \(t^ i_ j t^ k_ j t^ i_ j= t^ k_ j t^ i_ j\), \(t^ i_ j t^ m_ n t^ i_ j= t^ m_ n t^ i_ j\), \(t^ i_ j t^ k_ j= t^ k_ j t^ i_ j\), \(t^ i_ j t^ m_ n= t^ m_ n t^ i_ j\), \(t^ k_ i t^ j_ k t^ i_ j= t^ i_ k t^ j_ i t^ k_ j t^ i_ k\), and \(t^ n_ i t^ k_ n t^ j_ k t^ i_ j= t^ i_ n t^ j_ i t^ n_ j t^ k_ n t^ i_ k\).
The paper also contains a characterization of the equations that are valid in all cylindric algebras and involve only substitutions. Several applications of these results to cylindric algebras are mentioned.
For the entire collection see [Zbl 0777.00048].
Reviewer: R.Maddux (Ames)

MSC:

03G15 Cylindric and polyadic algebras; relation algebras
20M05 Free semigroups, generators and relations, word problems
20M20 Semigroups of transformations, relations, partitions, etc.
03G99 Algebraic logic
PDFBibTeX XMLCite