Thompson, Richard J. 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) Cited in 1 ReviewCited in 5 Documents 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 Keywords:replacement; substitutions; semigroups of finite non-permutational transformations; cylindric algebras PDFBibTeX XMLCite \textit{R. J. Thompson}, Banach Cent. Publ. 28, 327--342 (1993; Zbl 0797.03062)