HARJU and KARHUMÄKI

3 . ON THE RANK OF A SYSTEM OF EQUATIONS

In this section we develop a generalization of the defect theorem in order to be able to determine an upper bound for the rank of a system of equations.

Let X be a finite set of variables, x,,...,x , and let Q be a set of equations

U^ ( x^ , . . . ,x^) = V^(x^,...,x^), i € I,

in these variables. The rank of a solution (s,,...,s ) E

- - - - - - - - - - - - - - - - - - - I n

F is defined to be the rank of the free envelope of the F-semigroup [s,,...,s ] and the rank of the system Q is the maximum of the ranks of all the solutions of Q, [ll]. By definition we let rank(Q) equal to zero if Q has no solutions. The defect theorem says that rank(Q) < n since each solution gives rise to a nonfree F-semigroup.

Define a relation Rp^ 9 SxS for the F-semigroup S by

( s , s * ) e Rq iff sS n s*S ;^ 0,

and denote by R the transitive closure of R^.. The relation R is an equivalence relation, in fact, a left congruence,

with s*, s" in S. Then (s*,s) £ R and each equivalence

class clasSü(s) contains an element from the finite base

2 S \ S . Hence we have ind^R S rank(S). The right ence L ^ SxS can be defined symmetrically.

From these definitions it readily follows that S is free if and only if rank(S) = ind^R = ind^^L. The link with the defect theorem is given by

THEOREM 5. For each F-semigroup S we_ have rank(S) < indç^R < rank(S), and if S is_ not free then ind<^R < rank(S) - 1.

Proof . The second inequality and the second ment were already mentioned above. To prove rank(S) < ^ indç,R it is sufficient to show, by Lemma 4, that for

209