The combinatorial degrees of proofs and equations

DOI10.1007/BF01197185MaRDI QIDQ1918969zbMATH OpenOpenAlexFDO

Publication date 13 April 1997

Published in Algebra Universalis (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/bf01197185

Let \(I=(U_1,U_2)\) be an identity i.e. an unordered pair of words i.e. elements of the free semigroup \(F(n)\) generated by \(S_n=\{x_1,\dots,x_n\}\). When an identity \((U_1,U_2)\) implies another identity \((V_1,V_2)\), its proof is a sequence of equalities in some sense. The author combinatorically studies equations in terms of `degree' introduced by him applying it to several examples of equations. Let \(x_1,\dots,x_m\) be the symbols in \(U_1\) or \(U_2\). We write \(U_i(x_1,\dots,x_m)\), \(i=1,2\), but we assume that each symbol appearing in \(U_2\) appears at least as often in \(U_1\) and at least one symbol appears more often in \(U_1\) than in \(U_2\). Let \(W_1,\dots,W_m\) be elements of \(F(n)\). Define a binary relation \(\rho\) on \(F(n)\) as follows: let \(X,Y\in F(n)\). \(X\rho Y\) iff \(X=U_1(W_1,\dots,W_m)\) and \(Y=U_2(W_1,\dots,W_m)\) where \(U_i(W_1,\dots,W_m)\), \(i=1,2\), is the word obtained from \(U_i(x_1,\dots,x_m)\) by replacing \(x_j\) by \(W_j\) (\(j=1,\dots,m\)). The author denotes by \(\approx\) the congruence relation on \(F(n)\) generated by \(\rho\). Let \(F(I,n)=F(n)/ \approx\). The author's `adjacent relation' \(\sigma\) is the reflexive, symmetric, compatible relation generated by \(\rho\), and the transitive closure of \(\sigma\) equals \(\approx\). (In terms of operations, \(\sigma=\rho RSC\) and \(\approx=\sigma T=\rho RSCT\) [the reviewer, Bull. Am. Math. Soc. 70, 113-120 (1964; Zbl 0221.04001), Trans. Am. Math. Soc. 120, 343-358 (1966; Zbl 0145.02101)].) Let \(\ell(W)\) denote the length of a word \(W\). If \(A\sigma B\), then either \(\ell(A)<\ell(B)\) or \(\ell(B)<\ell(A)\). This is due to the assumption on \(I\). If \(\ell(A)<\ell(B)\), we write \(A\uparrow B\) or \(B\downarrow A\). The transitive closure of \(\uparrow\) is denoted by \(\Uparrow\), that is, if \(W_1\uparrow W_2\uparrow\dots\uparrow W_k\), we write \(W_1\Uparrow W_k\) or \(W_k\Downarrow W_1\). A sequence of the form \(A\uparrow B\downarrow C\) is called a peak and a sequence \(A\Uparrow B\Downarrow C\) is a mountain while \(A\downarrow B\uparrow C\) is a trough and \(A\Downarrow B\Uparrow C\) is a valley. By the degree of a proof we mean the number of peaks in the proof. If \(A\approx B\), \(d(A,B)\) denotes the minimal degree of all proofs of \(A\approx B\). (If \(A=B\) we say there is a proof of degree 0 of \(A\approx B\).) Define, \(d(I,n)\) to be the maximum of \(\{d(A,B):A,B\in S_n,\) \(A\approx B\}\) if exists, otherwise let \(d(I,n)=\infty\). \(d(I,n)\) is called the degree of the equation \(I\) on \(S_n\). The following are the main results of this paper. (1) An equation \(I\) has degree 0 on \(S_n\) if and only if each word in \(S_n\) has a unique minimal reduction with respect to \(I\). (2) The equation \((xyx,y)\) has degree 0 on \(S_1\) and degree 1 for \(n\geq 2\). (3) The equation \((xyxy,y^3x^3)\) has a finite degree on \(S_2\). (4) Let \(I=(x^ay^bx^c,x)\) where \(a,b,c>0\) and g.c.d.\((a+c,b-1)=1\). Then \(x\approx y\) is obtained from the equation \(I\) by a mountain proof. (5) Let \(I=(x^ay^b,yx)\). If \(a,b>0\) but not both 1, then \(I\) has degree 1 for \(n\geq 1\) except for the case when \(n=1\) and either \(a\) or \(b\) is 1. (6) The equation \((x^2,x)\) has degree 0 for \(n=1\) or \(n=2\) and degree 1 for \(n>2\). The importance of this paper is to study the situation of the congruence relation \(\approx\) on \(F(n)\) derived from an equation not through the structure of the semigroup \(F(I,n)\) even in the case when the semigroup-theoretical structure of \(F(I,n)\) is well known (namely in case (2) and (6), that is, (2) is an abelian group satisfying \(x^2=e\) for all \(x\), (6) is a semilattice of rectangular bands). In this sense this paper is very interesting.

Recommendations

Cites work

Cited in

(4)

This page was built for publication: The combinatorial degrees of proofs and equations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1918969)