# The Order of Hypersubstitutions of Type (2,1)

Authors: Tawhat Changphas; Wonlop Hemvong
Journal: International Journal of Mathematics and Mathematical Sciences
 (2011)

---

## Abstract

Hypersubstitutions are mappings which map operation symbols to terms of the corresponding arities. They were introduced as a way of making precise the concept of a hyperidentity and generalizations toM-hyperidentities. A variety in which every identity is satisfied as a hyperidentity is called solid. If every identity is an M-hyperidentity for a subset M of the set of all hypersubstitutions, the variety is called M-solid. There is a Galois connection
between monoids of hypersubstitutions and sublattices of the lattice of all varieties of algebras of a given type. Therefore, it is interesting and useful to know how semigroup or monoid properties of monoids of hypersubstitutions transfer under this Galois connection to properties of the corresponding lattices of M-solid varieties. In this paper, we study the order of each
hypersubstitution of type (2,1), that is, the order of the cyclic subsemigroup of the monoid of all hypersubstitutions of type (2,1) generated by that hypersubstitution.


---

## Body

## 1. Preliminaries

Letℕ denote the set of all positive integers. Let τ={(fi,ni)∣i∈I} be a type. Let X={x1,x2,x3,…} be a countably infinite alphabet of variables such that the sequence of the operation symbols (fi)i∈I is disjoint with X, and let Xn={x1,x2,…,xn} be an n-element alphabet where n∈ℕ. Here, fi is ni-ary for a natural number ni≥1. An n-ary (n≥1) term of type τ is inductively defined as follows: (i)
every variablexj∈Xn is an n-ary term,(ii)
ift1,…,tni are n-ary terms and fi is an ni-ary operation symbol, then fi(t1,…,tni) is an n-ary term.LetWτ(Xn) be the smallest set containing x1,…,xn and being closed under finite application of (ii). The set of all terms of type τ over the alphabet X is defined as the disjoint union Wτ(X)∶=⋃n=1∞Wτ(Xn).Any mappingσ:{fi:i∈I}→Wτ(X) is called a hypersubstitution of type τ if σ(fi) is an ni-ary term of type τ for every i∈I. Any hypersubstitution σ of type τ can be uniquely extended to a map σ̂ on Wτ(X) as follows: (i)
σ̂[t]∶=t if t∈X,(ii)
σ̂[t]∶=σ(fi)(σ̂[t1],…,σ̂[tni]) if t=fi(t1,…,tni).A binary operation∘h is defined on the set Hyp(τ) of all hypersubstitutions of type τ by (1.1)(σ1∘hσ2)(fi)∶=σ̂1[σ2(fi)],
for all ni-ary operation symbols fi. This binary associative operation makes Hyp(τ) into a monoid, with the identity hypersubstitution σid which maps every fi to fi(x1,…,xni) as an identity element. For a submonoid M of Hyp(τ) an identity s≈t of a variety V of type (τ) is called an M-hyperidentity of V if for every hypersubstitution σ∈M, the equation σ̂[s]≈σ̂[t] holds in V. A variety V is called M-solid if every identity of V is an M-hyperidentity of V. If M is a submonoid of Hyp(τ), then the collection of all M-solid varieties of type τ is a complete sublattice of the lattice of all varieties of type τ [1].Letσ∈Hyp(τ) and let 〈σ〉∶={σn∣n∈ℕ} be the cyclic subsemigroup of Hyp(τ) generated by σ. The order of σ∈Hyp(τ) is defined as the order of the semigroup 〈σ〉. If 〈σ〉 is finite, then the order of the hypersubstition σ is finite, otherwise the order of σ is infinite. The hypersubstitution σ is idempotent if and only if the order of σ is 1.The order of a hypersubstitution of type (2) is 1, 2, or infinite [2]. The order of a hypersubstitution of type (3) is 1, 2, 3, or infinite [3]. The order of a hypersubstitution of type (2,2) is 1, 2, 3, 4, or infinite [4]. We are interested in type (2,1). The main result is as followsMain Theorem.
Any hypersubstitution of type(2,1) has order either infinite or less than or equal to 3.Throughout this paper, letf and g be the binary operation symbols and the unary operation symbols of type τ=(2,1), respectively. For a binary term a and an unary term b of type τ, the hypersubstitution which maps the operation symbol f to the term a and the operation symbol g to the term b will be denoted by σa,b.For a binary termt∈W(2,1)(X2), we introduce the following notations:leftmost(t)—the first variable (from the left) occurring in t,rightmost(t)—the last variable occurring in t,var(t)—the set of all variable occurring in t,op(t)—the total number of all operation symbols occurring in t,ops(t)—the set of all operation symbols occurring in t,firstops(t)—the first operation symbol (from the left) occurring in t.Fort∈W(2,1)(X2), let Lp(t) denote the left path from the root to the leaf which is labelled by the leftmost variable in t and Rp(t) denote the right path from the root to the leaf which is labelled by the rightmost variable in t. The operation symbols occurring in Lp(t) and Rp(t) will be denoted by ops(Lp(t)) and ops(Rp(t)), respectively. If t∈W(2,1)(X2) such that var(t)={x1} or var(t)={x2}, we define t1=t and (1.2)tn=tn-1(t,t),ifn≥1.Fora and b of the hypersubstitution σa,b, we break our analysis into the following six cases, which cover all possibilities for a and b: (I)
op(a)≤1 and op(b)≤1,(II)
op(a)>1 and op(b)>1,(III)
op(a)=1 and op(b)>1,(IV)
op(a)>1 and op(b)=1,(V)
op(a)>1 and op(b)=0,(VI)
op(a)=0 and op(b)>1.In case (I), we have terma∈{x1,x2,f(x1,x1),f(x1,x2),f(x2,x1),f(x2,x2),g(x1), g(x2)} and b∈{x1,g(x1),f(x1,x1)}. For σa,b we have twenty-four cases, for which the orders can be verified by simple calculations. The case a=g(x2) and b=f(x1,x1) gives order 3, six other cases give order 2, and the remaining 17 cases give order 1.


## 2. Case II:op(a)>1 and op(b)>1

In this section, we consider the order of a hypersubstitutionσa,b where op(a)>1 and op(b)>1. We consider three subcases of Case II: (II-1)
var(a)={x1,x2}, var(b)={x1},(II-2)
var(a)={x1}, var(b)={x1},(II-3)
var(a)={x2}, var(b)={x1}.The following formula for the operation symbol count of the compound terms(t1,…,tn) for some s,t1,…,tn∈Wτ(X) was proved in [5]: (2.1)op(s(t1,…,tn))=∑j=1nvbj(s)op(tj)+op(s),s,t1,…,tn∈W(τ)(X),
where vbj(s) = the number of occurrences of variable xj in the term  s.Using the facts (see [5]) that op(σ̂[t])>op(t) for all t∈Wτ(X) if σ∈Hyp(τ) is regular, that is, var(σ(fi))=Xn, for all i∈I, and the formula above, we obtain the following theorem.Theorem 2.1.
Leta∈W(2,1)(X2), b∈W(2,1)(X1). If op(a)>1, op(b)>1, var(a)={x1,x2}, var(b)={x1}, then the order of σa,b is infinite.Proof.
Sinceσa,b is regular, by induction we obtain op(σa,bk(f))<op(σa,bk+1(f)). Then, the order of σa,b is infinite.The following lemmas are easy to prove.Lemma 2.2.
Leta,t∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)≥1, op(b)≥1. If t∉X2, then σ̂a,bn[t] is not a variable for all n∈ℕ.Lemma 2.3.
Leta,t∈W(2,1)(X2), b∈W(2,1)(X1). If var(t)={xi} for some i∈{1,2}, then var(σ̂a,bn[t])={xi} for all n∈ℕ.Lemma 2.4.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)≥1, op(b)≥1, and a=f(a1,a2), b=g(b1) for some a1,a2∈W(2,1)(X2), b1∈W(2,1)(X1). Then, the following hold: (i)
ifvar(a)={x1} and a1≠x1, then the order of σa,b is infinite;(ii)
ifvar(b)={x1} and b1≠x1, then the order of σa,b is infinite.Proof.
(i) Assumevar(a)={x1} and a1≠x1. Then, a1∉X2. Let n∈ℕ. By Lemma 2.2, σ̂a,bn+1[a1]∉X2. Since var(a)={x1}, by Lemma 2.3, var(σ̂a,bn[a])={x1}. Now,
(2.2)op(σ̂a,bn+1[a])=op(σ̂a,bn[σ̂a,b[f(a1,a2)]])=op(σ̂a,bn[σa,b(f)(σ̂a,b[a1],σ̂a,b[a2])])=op(σ̂a,bn[a(σ̂a,b[a1],σ̂a,b[a2])])=op(σ̂a,bn[a](σ̂a,bn+1[a1],σ̂a,bn+1[a2]))>op(σ̂a,bn[a]).
This shows that op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) for all n∈ℕ. Hence, the order of σa,b is infinite.
(ii) Assumevar(b)={x1} and b1≠x1, then b1∉X1. Let n∈ℕ. By Lemma 2.2, σ̂a,bn+1[b1]∉X1. Since var(b)={x1}, by Lemma 2.3  var(σ̂a,bn[b])={x1} for all n∈ℕ. Then,
(2.3)op(σ̂a,bn+1[b])=op(σ̂a,bn[σ̂a,b[g(b1)]])=op(σ̂a,bn[b](σ̂a,bn+1[b1]))>op(σ̂a,bn[b]).
Therefore, op(σ̂a,bn+1[b])>op(σ̂a,bn[b]) for all n∈ℕ. Hence we have the claim.Throughout the rest of this paper, we assume that whena is not a variable term it has the form f(a1,a2) or g(a1), for some terms a1, a2 and that when b is not a variable term it has the form f(b1,b2) or g(b1), for some terms b1, b2.In Case (II-2), we havevar(a)={x1}, var(b)={x1}. We consider the following four subcases: (2.1)
firstops(a)=f, firstops(b)=f;(2.2)
firstops(a)=g, firstops(b)=g;(2.3)
firstops(a)=f, firstops(b)=g;(2.4)
firstops(a)=g, firstops(b)=f.In Case (2.1), we can separate into four subcases:(2.1.1)
a1∉X2;(2.1.2)
a1=x1, b1=x1;(2.1.3)
a1=x1, b1∉X1, ops(Lp(b))={f};(2.1.4)
a1=x1, b1∉X1, ops(Lp(b))≠{f}.Theorem 2.5.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x1}=var(b), and a=f(a1,a2), b=f(b1,b2) for some a1,a2∈W(2,1)(X2), b1,b2∈W(2,1)(X1). Then, the following hold: (i)
ifa and b satisfy (2.1.1) or (2.1.4), then σa,b has infinite order;(ii)
ifa and b satisfy (2.1.2) or (2.1.3), then the order of σa,b is less than or equal to 3.Proof.
(i) Assumea and b satisfy (2.1.1). By Lemma 2.2, we have σ̂a,bn[a1]∉X2 for all n∈ℕ. Since var(σ̂a,b[a])={x1}, by Lemma 2.3  var(σ̂a,bn[a])={x1} for all n∈ℕ. Therefore,
(2.4)op(σ̂a,bk+1[a])=op(σ̂a,bk[a(σ̂a,b[a1],σ̂a,b[a2])])=op(σ̂a,bk[a](σ̂a,bk+1[a1],σ̂a,bk+1[a2]))>op(σ̂a,bk[a]).
This shows that op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) for all n∈ℕ. Hence, σa,b has infinite order.
Assumea and b satisfy (2.1.4). Since var(σ̂a,b[a])={x1}, σ̂a,bn[a]=σ̂a,b[a] for all n∈ℕ. Since g∈ops(Lp(b)), we have op(σ̂a,bn+1[b])>op(σ̂a,bn[b]) for all n∈ℕ. Hence, the order of σa,b is infinite.
(ii) Assumea and b satisfy (2.1.2). Since var(σ̂a,b[a])={x1}, a1=x1 and firstops(a)=f, we obtain σ̂a,b[a]=a. This gives
(2.5)σ̂a,b3[f]=σ̂a,b2[a]=σ̂a,b[a]=σ̂a,b2[f].
Since b1=x1, var(σ̂a,b[a])={x1} and firstops(b)=f, we have σ̂a,b[b])=a. So,
(2.6)σ̂a,b3[g]=σ̂a,b2[b]=σ̂a,b[a]=a=σ̂a,b[b]=σ̂a,b2[g].
Hence, σa,b2=σa,b3. This shows that the order of σa,b is less than or equal to 2.
Assumea and b satisfy (2.1.3). Because of (2.1.2), we have σ̂a,b[a]=a, which implies σ̂a,b3[f])=σ̂a,b2[f]. Since ops(Lp(b))={f}, we have
(2.7)σ̂a,b[b]=a1′(a2′(⋯am-1′(am′(x1,x1),σ̂a,b[tm-1′]),…,σ̂a,b[t2′]),σ̂a,b[t1′]),
for some t1′,…,tm-1′∈W(2,1)(X1) with m=op(Lp(b)) and a1′=a2′=⋯=am′=a. It follows that σ̂a,b2[b]=(σ̂a,b[a])m. Since σ̂a,b[a]=a, we obtain
(2.8)σ̂a,b4[g]=σ̂a,b3[b]=σ̂a,b[(σ̂a,b[a])m]=(σ̂a,b2[a])m=(σ̂a,b[σ̂a,b[a]])m=(σ̂a,b[a])m=σ̂a,b2[b]=σ̂a,b3[g].
Thus, σa,b3=σa,b4. Hence, the order of σa,b is less than or equal to 3.In Case (2.2), we havefirstops(a)=g and firstops(b)=g. Since op(a)>1 and op(b)>1, a1∉X2 and b1∉X1. Then, we obtain the following.Theorem 2.6.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x1}, a=g(a1) and b=g(b1) for some a1∈W(2,1)(X2), b1∈W(2,1)(X1). Then, σa,b has infinite order.Proof.
Assume thata=g(a1), b=g(b1), op(a)>1, op(b)>1, var(a)={x1}. Then, a1∉X2, b1∉X1. It can be proved, as in the proof of Theorem 2.5(i), that the order of σa,b is infinite.In Case (2.3), we havefirstops(a)=f and firstops(b)=g. Since op(b)>1, b1∉X1. Then, we obtain the following.Theorem 2.7.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x1}, a=f(a1,a2) and b=g(b1) for some a1,a2∈W(2,1)(X2), b1∈W(2,1)(X1)∖X1. Then, σa,b has infinite order.Proof.
Byop(b)>1, b1∉X1. Since firstops(b)=g, var(b)={x1} and Lemma 2.4(ii), we have σa,b has infinite order.In Case (2.4), we havefirstops(a)=g and firstops(b)=f. Since op(a)>1 and op(b)>1, a1∉X2 and b1∉X1 or b2∉X1. We consider the following three subcases: (2.4.1)
b1∉X1;(2.4.2)
b1=x1, op(a1)={g};(2.4.3)
b1=x1, op(a1)≠{g}.Theorem 2.8.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x1}, var(b)={x1}, and a=g(a1), b=f(b1,b2) for some a1∈W(2,1)(X2), b1,b2∈W(2,1)(X1). Then, the following hold: (i)
ifa and b satisfy (2.4.1) or (2.4.3), then σa,b has infinite order;(ii)
ifa and b satisfy (2.4.2), then the order of σa,b is less than or equal to 2.Proof.
(i) Assume thata and b satisfy (2.4.1). By Lemma 2.2, we have σ̂a,bn[a1]∉X2 for all n∈ℕ. Since var(σ̂a,b[a])={x1}, by Lemma 2.3  var(σ̂a,bn[a])={x1} for all n∈ℕ. Therefore,
(2.9)op(σ̂a,bk+1[a])=op(σ̂a,bk[a(σ̂a,b[a1],σ̂a,b[a2])])=op(σ̂a,bk[a](σ̂a,bk+1[a1],σ̂a,bk+1[a2]))>op(σ̂a,bk[a]).
This shows that op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) for all n∈ℕ. Hence, σa,b has infinite order.
Assume thata and b satisfy (2.4.3). This case can be proved as in (2.4.1).
(ii) Assume thata and b satisfy (2.4.2). Then, σ̂a,b[a]=b and σ̂a,b[b]=a. We have σa,b3=σa,b and σa,b4=σa,b2. Hence, the order of σa,b is less than or equal to 3.In Case (II-3), we havevar(a)={x2}, var(b)={x1}. We consider the following four subcases: (3.1)
firstops(a)=f, firstops(b)=f;(3.2)
firstops(a)=g, firstops(b)=g;(3.3)
firstops(a)=f, firstops(b)=g;(3.4)
firstops(a)=g, firstops(b)=f.In Case (3.1), we can separate into four subcases:(3.1.1)
a2∉X2;(3.1.2)
a2=x2, b2=x1;(3.1.3)
a2=x2, b2∉X1, ops(Rp(b))={f};(3.1.4)
a2=x2,b2∉X1, ops(Rp(b))≠{f}.Theorem 2.9.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x2}, var(b)={x1}, and a=f(a1,a2), b=f(b1,b2) for some a1,a2∈W(2,1)(X2), b1,b2∈W(2,1)(X1). Then, the following hold: (i)
ifa and b satisfy (3.1.1) or (3.1.4), then σa,b has infinite order;(ii)
ifa and b satisfy (3.1.2) or (2.1.3), then the order of σa,b is less than or equal to 2.Proof.
(i) Assume thata and b satisfy (3.1.1). By Lemma 2.2, we have σ̂a,bn[a1]∉X2 for all n  inℕ. Since var(σ̂a,b[a])={x2}, by Lemma 2.3  var(σ̂a,bn[a])={x2} for all n∈ℕ. Therefore,
(2.10)op(σ̂a,bk+1[a])=op(σ̂a,bk[a(σ̂a,b[a1],σ̂a,b[a2])])=op(σ̂a,bk[a](σ̂a,bk+1[a1],σ̂a,bk+1[a2]))>op(σ̂a,bk[a]).
This shows that op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) for all n∈ℕ. Hence, σa,b has infinite order.
Assume thata and b satisfy (3.1.4). Then, σ̂a,bn[a]=σ̂a,b[a] for all n∈ℕ. Since var(σ̂a,b[a])={x2} and b2∉X1, we have
(2.11)op(σ̂a,bk+1[b])=op(σ̂a,bk[b(σ̂a,b[b1],σ̂a,b[b2])])=op(σ̂a,bk[b](σ̂a,bk+1[b1],σ̂a,bk+1[b2]))>op(σ̂a,bk[b]).
This implies that op(σ̂a,bn+1[b])>op(σ̂a,bn[b]) for all n∈ℕ. Hence, the order of σa,b is infinite.
(ii) Assume thata and b satisfy (3.1.2). Then, we get σ̂a,b[a]=a, σ̂a,b2[b]=σ̂a,b[b] or σ̂a,b[a]=a, σ̂a,b[b]=b. In the first, the order of σa,b is equal to 2. For the latter, σa,b is idempotent.
Assume thata and b satisfy (3.1.3). Then, σ̂a,b[a]=a, σ̂a,b2[b]=σ̂a,b[b], which can be proved the same way as the first case of (ii).In Case (3.2), we havefirstops(a)=g and firstops(b)=g. Since op(a)>1 and op(b)>1, a1∉X2 and b1∉X1. Then, we obtain the following.Theorem 2.10.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x2}, a=g(a1) and b=g(b1) for some a1∈W(2,1)(X2)∖X2, b1∈W(2,1)(X1)∖X1. Then σa,b has infinite order.Proof.
Sincevar(a)={x2} and b1∉X1, we have
(2.12)op(σ̂a,bk+1[b])=op(σ̂a,bk[b(σ̂a,b[b1],σ̂a,b[b2])])=op(σ̂a,bk[b](σ̂a,bk+1[b1],σ̂a,bk+1[b2]))>op(σ̂a,bk[b]).
Hence, the order of σa,b is infinite.In Case (3.3), we havefirstops(a)=f and firstops(b)=g. Since op(b)>1, b1∉X1. Then, we obtain the following.Theorem 2.11.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x2}, a=f(a1,a2) and b=g(b1) for some a1,a2∈W(2,1)(X2), b1∈W(2,1)(X1)∖X1. Then σa,b has infinite order.Proof.
Sinceb1∉X1  firstops(b)=g and Lemma 2.4(ii), we have σa,b has infinite order.In Case (3.4), we havefirstops(a)=g and firstops(b)=f. Since op(a)>1 and op(b)>1, a1∉X2 and b1∉X1. We have the following result.Theorem 2.12.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)>1, var(a)={x2}, var(b)={x1}, and a=g(a1), b=f(b1,b2) for some a1∈W(2,1)(X2), b1,b2∈W(2,1)(X1). Then, σa,b has infinite order.Proof.
Sinceop(a)>1, a1∉X2. We have, by Lemma 2.2, σ̂a,bn[a1]∉X2 for all  ninℕ. Since var(σ̂a,b[a])={x2}, by Lemma 2.3  var(σ̂a,bn[a])={x2} for all n∈ℕ. We obtain
(2.13)op(σ̂a,bk+1[a])=op(σ̂a,bk[a(σ̂a,b[a1],σ̂a,b[a2])])=op(σ̂a,bk[a](σ̂a,bk+1[a1],σ̂a,bk+1[a2]))>op(σ̂a,bk[a]).
Hence, σa,b has infinite order.


## 3. Case III:op(a)=1 and op(b)>1

We consider three subcases:(III-1)
var(a)=X2, var(b)={x1};(III-2)
var(a)={x1}, var(b)={x1};(III-3)
var(a)={x2}, var(b)={x1}.In Case (III-1), we separate into the following subcases:(1)
a=f(x1,x2),firstops(b)=f;(2)
a=f(x1,x2),firstops(b)=g;(3)
a=f(x2,x1),firstops(b)=f;(4)
a=f(x2,x1),firstops(b)=g.We have the following results. Subcases (2) and (4) give infinite order, by Lemma2.4(ii). The next proposition deal with subcases (1) and (3).Proposition 3.1.
Letb=f(b1,b2) for some b1,b2∈W(2,1)(X1) be such that var(b)={x1} and op(b)>1. Then, the following hold: (i)
ifa=f(x1,x2), then the order of σa,b is equal to 1 or is infinite;(ii)
ifa=f(x2,x1), then the order of σa,b is less than or equal to 3 or infinite.Proof.
(i) Assume thata=f(x1,x2). Then, σa,b[a]=a. We consider the following.
(i′) Ifops(b)={f}, then σa,b[b]=b. We get that σa,b is idempotent.
(i′′) Ifg∈ops(b), suppose that g∈ops(b1). Let k∈ℕ. Then op(σ̂a,bk+1[b1])≥op(σ̂a,bk[b1]).
Now,(3.1)op(σ̂a,bk+1[b])=op(σ̂a,bk[σ̂a,b[b]])=op(σ̂a,bk[σa,b(f)(σ̂a,b[b1],σ̂a,b[b2])])=op(σa,bk(σa,b(f))(σ̂a,bk+1[b1],σ̂a,bk+1[b2]))>op(σa,bk(f)(σ̂a,bk[b1],σ̂a,bk[b2]))=op(σ̂a,bk[b]).
A similar argument works for g∈ops(b2). This shows that the order of σa,b is infinite.
(ii) Ifops(b)={f}, then σ̂a,b1[a]=σ̂a,b3[a] and σ̂a,b[b]=σ̂a,b3[b]. This gives σ̂a,b4=σ̂a,b2. Then, the order of σa,b is less than or equal to 3. If g∈ops(b), then it can be proved as in (i′′) that the order is infinite.In Case (III-2), we havevar(a)={x1}, var(b)={x1}. We consider the following subcases: (3.2.1)
a=f(x1,x1), firstops(b)=f;
(3.2.1.1)
b1=x1;(3.2.1.2)
b1≠x1, g∈ops(Lp(b));(3.2.1.3)
b1≠x1, g∉ops(Lp(b));(3.2.2)
a=g(x1), firstops(b)=g, then b1∉X1;(3.2.3)
a=f(x1,x1), firstops(b)=g, then b1∉X1;(3.2.4)
a=g(x1), firstops(b)=f;
(3.2.4.1)
b1=x1;(3.2.4.2)
b1≠x1.Proposition 3.2.
Leta=f(x1,x1), firstops(b)=f, op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (3.2.1.1) or (3.2.1.3), then the order of σa,b is less than or equal to 2;(ii)
ifb satisfies (3.2.1.2), then the order of σa,b is infinite.Proof.
(i) Ifa and b satisfy (3.2.1.1), then σ̂a,b[a]=a=σ̂a,b[b]. Assume that a and b satisfy (3.2.1.3). Since a=f(x1,x1) and g∉σ̂a,b[b], we have σ̂a,b2[b]=σ̂a,b[b]. Clearly, σ̂a,b2[a]=a. Then, σa,b3=σa,b2. Hence, the order of σa,b is less than or equal to 2.
(ii) Assume thata and b satisfy (3.2.1.2). Since a=f(x1,x1), firstops(b)=f and g∈ops(Lp(b)), it follows that σ̂a,b[b]=f(x1,x1)(b(v),b(v′)) for some v,v′∈W(2,1)(X1). For n∈ℕ, we have
(3.2)op(σ̂a,bn+1[b])=op(σ̂n[σ̂a,b[b]])=op(σ̂a,bn[f(x1,x1)(b(v),b(v′))])=op(f(x1,x1)(σ̂a,bn[b](σ̂a,bn[v]),σ̂a,bn[b](σ̂a,bn[v′])))>op(σ̂a,bn[b]).
Hence, the order of σa,b is infinite.Proposition 3.3.
Leta=g(x1) or a=f(x1,x1), firstops(b)=g, op(b)>1, and var(b)={x1}. Then, the order of σa,b is infinite.Proof.
Assume thata=g(x1). Since firstops(b)=g, a=g(x1), σ̂a,b[b]=b(g(x1)). For any natural number n, op(σ̂a,bn+1[b])>op(σ̂a,bn[b]) makes σa,b have infinite order.
Assume thata=f(x1,x1). Since firstops(b)=g, a=f(x1,x1), σ̂a,b[b]=b(f(x1,x1)). For n∈ℕ, a similar proof to those above gives op(σ̂a,bn+1[b])>op(σ̂a,bn[b]). Hence, the order of σa,b is infinite.Proposition 3.4.
Leta=g(x1), firstops(b)=f, op(b)>1 and var(b)={x1}. Then the following hold: (i)
ifb satisfies (3.2.4.1), then the order of σa,b is equal to 2;(ii)
ifb satisfies (3.2.4.2), then the order of σa,b is infinite.Proof.
(i) Ifa and b satisfy (3.2.4.1), then σ̂a,b[a]=b and σ̂a,b[b]=a. Hence, the order of σa,b is equal to 2.
(ii) Assume thata and b satisfy (3.2.4.2). Since a=g(x1), firstops(b)=f, it follows that σ̂a,b[b]=g(x1)b. For n∈ℕ. As in the proof of Proposition 3.3, we have op(σ̂a,bn+1[b])>op(σ̂a,bn[b]). Hence, the order of σa,b is infinite.In Case (III-3), we have var(a)={x2}, var(b)={x1}. We consider the following subcases: (3.3.1)
a=f(x2,x2), firstops(b)=f;
(3.3.1.1)
b2=x1;(3.3.1.2)
b2≠x1;(3.3.2)
a=g(x2), firstops(b)=g.(3.3.3)
a=f(x2,x2),firstops(b)=g.(3.3.4)
a=g(x2),firstops(b)=f;
(3.3.4.1)
b2=x1;(3.3.4.2)
b2≠x1.Proposition 3.5.
Leta=f(x2,x2), firstops(b)=f, op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (3.3.1.1), then the order of σa,b is equal to 2;(ii)
ifb satisfies (3.3.1.2), then the order of σa,b is infinite.Proof.
(i) Ifa and b satisfy (3.3.1.1), then σ̂a,b[a]=a and σ̂a,b2[b]=σ̂a,b[b]. Hence the order of σa,b is equal to 2.
(ii) This can be proved in the same way as Proposition3.2 (ii).Proposition 3.6.
Leta=g(x2) or a=f(x2,x2), firstops(b)=g, op(b)>1, and var(b)={x1}. Then, the order of σa,b is infinite.Proof.
Assume thata=g(x2). Since firstops(b)=g, a=g(x2), σ̂a,b[b]=b(g(x2)). The same argument works as in Proposition 3.3. Hence, the order of σa,b is infinite. The case that a=f(x2,x2) can be proved similarly.Proposition 3.7.
Leta=g(x2), firstops(b)=f, op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (3.3.4.1), then the order of σa,b is equal to 2;(ii)
ifb satisfies (3.3.4.2), then the order of σa,b is infinite.Proof.
(i) Ifa and b satisfy (3.3.4.1), then σ̂a,b2[a]=a and σ̂a,b2[b]=b. Hence, the order of σa,b is equal to 2.
(ii) Assumea and b satisfy (3.3.4.2), Since b=g(x2), firstops(b)=f, b2∉X2. By Lemma 2.2, we have σ̂a,bn[b1]∉X2. Then,
(3.3)op(σ̂a,b[b])=op(σ̂a,b[f(b1,b2)])=op(σa,b(f)(σ̂a,b[b1],σ̂a,b[b2]))>op(f(b1,b2))=op(b).
This shows that, op(σ̂a,b[b])>op(b) for all a∈W(2,1)(X1)∖X1. Consequently, op(σ̂a,bk+1[b])=op(σ̂a,b[σ̂a,bk[b]]) for all k∈ℕ. Then, order of σa,b is infinite.


## 4. Case IV:op(a)>1 and op(b)=1

We consider three subcases:(IV-1)
var(a)=X2, var(b)={x1};(IV-2)
var(a)={x1}, var(b)={x1};(IV-3)
var(a)={x2}, var(b)={x1}.In Case (IV-1), we separate into four cases:(4.1.1)
b=f(x1,x1), firstops(a)=f;(4.1.2)
b=f(x1,x1), firstops(a)=g;(4.1.3)
b=g(x1), firstops(a)=f;(4.1.4)
b=g(x1), firstops(a)=g.Theorem 4.1.
Leta∈W(2,1)(X2), b∈W(2,1)(X1) be such that op(a)>1, op(b)=1, var(a)={x1,x2}, var(b)={x1}. Then, the following hold: (i)
ifb satisfies (4.1.1) or (4.1.2) or (4.1.3), then the order of σa,b is infinite;(ii)
ifb satisfies (4.1.4), then the order of σa,b is equal to 1 or is infinite.Proof.
(i) Ifa and b satisfy (4.1.1), then we let a=f(a1,a2) for some a1,a2∈W(2,1)(X2). Since op(a)>1, we may assume that a1∉X2. By Lemma 2.2, we have σ̂a,bn[a1]∉X2. For any natural number n, op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) makes σa,b have infinite order. Cases (4.1.2) and (4.1.3) can be proved similarly.
(ii) Assume thata and b satisfy (4.1.4). If ops(a1)={g}, then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent. The case that op(a1)≠{g} can be proved as in (i).In Case (IV-2), we havevar(a)={x1}, var(b)={x1}. If a=g(a1) for some term a1, then op(a)>1 means that a1 is not variable.Proposition 4.2.
Letb=f(x1,x1) or b=g(x1), op(a)>1, a=g(a1) for some a1 and var(a)={x1}=var(b). Then, the order of σa,b is infinite.Proof.
Assumeop(a)>1, a=g(a1) for some a1 and var(a)={x1}=var(b). Since a1∉X2. By Lemma 2.2 we have σ̂a,bn[a1]∉X2. It can be proved, as in the proof of Theorem 4.1(i), that the order of σa,b is infinite.In Case (IV-3), we havevar(a)={x2}, var(b)={x1}. If firstops(a)=g, then a2∉X2. We consider the following cases: (4.3.1)
a2∉X2, b=f(x1,x1);(4.3.2)
a2∉X2, b=g(x1).Proposition 4.3.
Letb=f(x1,x1), op(a)>1, and var(a)={x2}, var(b)={x1}. If a and b satisfy (4.3.1), then the order of σa,b is infinite.Proof.
The case (4.3.1) can be verified as in Proposition4.2.Proposition 4.4.
Letb=g(x1), op(a)>1, and var(a)={x2}, var(b)={x1}. If a and b satisfy (4.3.2), then the order of σa,b is equal to 1 or is infinite.Proof.
Assume thata and b satisfy (4.3.2). If b=g(x1), firstops(a)=g, and ops(a2)={g}, then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent. Assume that a2∉X2. This case can be proved as in Proposition 4.3.


## 5. Case V:op(a)>1 and op(b)=0

In this case, we havea=f(a1,a2) or a=g(a1), b=x1. We consider three subcases: (V-1)
var(a)=X2, b=x1;(V-2)
var(a)={x1}, b=x1;(V-3)
var(a)={x2}, b=x1.In Case (V-1), we separate into the following subcases:(5.1.1)
firstops(a)=f, a1∉X2, ops(Lp(a))≠{g};(5.1.2)
firstops(a)=f, a1∉X2, ops(Lp(a))={g};(5.1.3)
firstops(a)=f, a1∈X2, ops(Rp(a))≠{g};(5.1.4)
firstops(a)=f, a1∈X2, ops(Rp(a))={g};(5.1.5)
firstops(a)=g, ops(a1)={g};(5.1.6)
firstops(a)=g, ops(a1)≠{g}.Proposition 5.1.
Leta=f(a1,a2), op(a)>1, op(b)=0, var(a)={x1,x2}, and b=x1. Then, the following hold: (i)
ifa satisfies (5.1.1) or (5.1.3), then the order of σa,b is infinite;(ii)
ifa satisfies (5.1.2) or (5.1.4), then the order of σa,b is less than or equal to 2.Proof.
(i) Assumea and b satisfy (5.1.1). Then, firstops(a)=f, var(a)={x1,x2}, and f∈ops(Lp(a)). Then, op(a)<op(σ̂a,b[a]). For any natural number n, op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) makes σa,b have infinite order. A similar argument works for (5.1.3).
(ii) Assumea and b satisfy (5.1.2). Then, firstops(a)=f, var(a)={x1,x2}, and ops(Lp(a))={g}. If leftmost(a1)=x1, then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent. If leftmost(a1)=x2, then σ̂a,b2[a]=σ̂a,b[a] and σ̂a,b[b]=b. Hence, the order of σa,b is equal to 2.
Assumea and b satisfy (5.1.4). Then, firstops(a)=f, var(a)={x1,x2} and ops(Rp(a))={g}. If rightmost(a2)=x2, then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent. If leftmost(a2)=x1, then σ̂a,b2[a]=σ̂a,b[a] and σ̂a,b[b]=b. Hence, the order of σa,b is equal to 2.Proposition 5.2.
Leta=g(a1), op(a)>1, op(b)=0, var(a)={x1,x2}, and b=x1. If a satisfies (5.1.5) or (5.1.6), then, the order of σa,b is less than or equal to 2.Proof.
Assume thata and b satisfy (5.1.5). Then, firstops(a1)=g and ops(a1)={g}. If leftmost(a1)=x1, then σ̂a,b[a]=b and σ̂a,b[b]=b. Hence, the order of σa,b is equal to 2. If leftmost(a1)=x2, then σ̂a,b2[a]=σ̂a,b[a] and σ̂a,b[b]=b. Again, the order of σa,b is equal to 2.
Assume thata and b satisfy (5.1.6). Then firstops(a1)=f and f∈ops(a1). If leftmost(a1)=x1, then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent. If leftmost(a1)=x2, then σ̂a,b2[a]=σ̂a,b[a] and σ̂a,b[b]=b. Hence, the order of σa,b is equal to 2.In Case (V-2), we havevar(a)={x1}, var(b)={x1}. We separate this case into following subcases: (5.2.1)
firstops(a)=f, a1=x1;(5.2.2)
firstops(a)=f, a1∉X2, ops(Lp(a))={g};(5.2.3)
firstops(a)=f, a1∉X2, ops(Lp(a))≠{g};(5.2.4)
firstops(a)=g, ops(a1)={g};(5.2.5)
firstops(a)=g, ops(a1)≠{g}.Proposition 5.3.
Leta=f(a1,a2), op(a)>1, op(b)=0, var(a)={x1}, and b=x1. Then, the following hold: (i)
ifa satisfies (5.2.1) or (5.2.2), then the order of σa,b is equal to 1;(ii)
ifa satisfies (5.2.3), then the order of σa,b is infinite.Proof.
(i) Assume thata and b satisfy (5.2.1). Since firstops(a1)=f and var(a)={x1}, we have σ̂a,b[a]=a. Since b=x1, σ̂a,b[b]=b. Hence, σa,b is idempotent.
Assumea and b satisfy (5.2.2). Since ops(a1)=g and var(a)={x1}, we have σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent.
(ii) Assumea and b satisfy (5.2.3). Since firstops(a1)=f and var(a)={x1}, we have op(σ̂a,bk+1[a1])≥op(σ̂a,bk[a1]) for all k∈ℕ. For any natural number n, op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) makes σa,b have infinite order.Proposition 5.4.
Leta=g(a1), op(a)>1, op(b)=0, var(a)={x1}, and b=x1. Then, the following hold: (i)
ifa satisfies (5.2.4), then the order of σa,b is equal to 2;(ii)
ifa satisfies (5.2.5), then the order of σa,b is equal to 1 or is infinite.Proof.
(i) Assumea and b satisfy (5.2.4). Then, σ̂a,b[a]=b=σ̂a,b[b]. Hence, the order of σa,b is equal to 2.
(ii) Assumea and b satisfy (5.2.5). If there is only one f∈ops(a1), then σ̂a,b[a]=x1(x1(⋯(a)))=a and σ̂a,b[b]=b. Hence, σa,b is idempotent.
Assume that the symbolf occurs more than twice in term a1. Then, op(σ̂a,bk+1[a1])≥op(σ̂a,bk[a1]) for all k∈ℕ. For any natural number n, op(σ̂a,bn+1[a])>op(σ̂a,bn[a]) makes σa,b have infinite order.In Case (V-3), we havevar(a)={x2}, b=x1. We separate into the following subcases: (5.3.1)
firstops(a)=f, a2=x2;(5.3.2)
firstops(a)=f, a2∉X2, ops(a2)={g};(5.3.3)
firstops(a)=f, a2∉X2, ops(a2)≠{g};(5.3.4)
firstops(a)=g, ops(a1)={g};(5.3.5)
firstops(a)=g, ops(a1)≠{g}.Proposition 5.5.
Leta=f(a1,a2), op(a)>1, op(b)=0, var(a)={x2}, and b=x1. Then, the following hold: (i)
ifa satisfies (5.3.1) or (5.3.2), then the order of σa,b is equal to 1;(ii)
ifa satisfies (5.3.3), then the order of σa,b is infinite.Proof.
This can be proved similarly to the proof of Proposition5.3.Proposition 5.6.
Leta=g(a1), op(a)>1, op(b)=0, var(a)={x2}, and b=x1. Then, the following hold: (i)
ifa satisfies (5.3.4), then the order of σa,b is equal to 2;(ii)
ifa satisfies (5.3.5), then the order of σa,b is equal to 1 or is infinite.Proof.
This can be proved similarly to the proof of Proposition5.4.


## 6. Case VI:op(a)=0 and op(b)>1

In this case, we consider the following cases:(6.1)
a=x1;
(6.1.1)
firstops(b)=f, b1=x1;(6.1.2)
firstops(b)=f, b1∉X1, ops(Lp(b))={f};(6.1.3)
firstops(b)=f, b1∉X1, ops(Lp(b))≠{f};(6.1.4)
firstops(b)=g, ops(b1)={f};(6.1.5)
firstops(b)=g, ops(b1)≠{f};(6.2)
a=x2;
(6.2.1)
firstops(b)=f, b2=x1;(6.2.2)
firstops(b)=f, b2∉X1, ops(Rp(b))={f};(6.2.3)
firstops(b)=f, b2∉X1, ops(Rp(b))≠{f};(6.2.4)
firstops(b)=g, ops(b1)={f};(6.2.5)
firstops(b)=g, ops(b1)≠{f}.Proposition 6.1.
Leta=x1, b=f(b1,b2), op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (6.1.1) or (6.1.2), then the order of σa,b is equal to 2;(ii)
ifb satisfies (6.1.3), then the order of σa,b is equal to 1 or is infinite.Proof.
(i) Ifa and b satisfy (6.1.1) or (6.1.2), then σ̂a,b[a]=a and σ̂a,b[b]=a. Hence, the order of σa,b is equal to 2.
(ii) Assumea and b satisfy (6.1.3). If there is only one occurrence of g in b1, then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent.
Assume thatg occurs more than twice in b1. Then, op(σ̂a,bk+1[b1])≥op(σ̂a,bk[b1]) for all k∈ℕ. Then,
(6.1)op(σ̂a,bk+1[b])=op(σ̂a,bk[σ̂a,b[b]])=op(σ̂a,bk[σa,b(f)(σ̂a,b[b1],σ̂a,b[b2])])=op(σa,bk(σa,b(f))(σ̂a,bk+1[b1],σ̂a,bk+1[b2]))>op(σa,bk(f)(σ̂a,bk[b1],σ̂a,bk[b2]))=op(σ̂a,bk[b]).
This shows that the order of σa,b is infinite.Proposition 6.2.
Leta=x1, b=g(b1), op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (6.1.4), then the order of σa,b is equal to 1;(ii)
ifb satisfies (6.1.5), then the order of σa,b is infinite.Proof.
(i) Ifa and b satisfy (6.1.4), then σ̂a,b[a]=a and σ̂a,b[b]=b. Hence, σa,b is idempotent.
(ii) Assumea and b satisfy (6.1.5). Then, op(σ̂a,bk+1[b1])≥op(σ̂a,bk[b1]) for all k∈ℕ. Then,
(6.2)op(σ̂a,bk+1[b])=op(σ̂a,bk[σ̂a,b[b]])=op(σ̂a,bk[σa,b(g)(σ̂a,b[b1])])=op(σa,bk(σa,b(g))(σ̂a,bk+1[b1]))>op(σa,bk(g)(σ̂a,bk[b1]))=op(σ̂a,bk[b]).
This shows that the order of σa,b is infinite.Proposition 6.3.
Leta=x2, b=f(b1,b2), op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (6.2.1) or (6.2.2), then the order of σa,b is equal to 2;(ii)
ifb satisfies (6.2.3), then the order of σa,b is equal to 1 or is infinite.Proof.
(i) Ifa and b satisfy (6.2.1) or (6.2.2), then σ̂a,b[a]=a and σ̂a,b2[b]=σ̂a,b[b]. Hence the order of σa,b is equal to 2.
(ii) This case can be proved similarly to the proof of Proposition6.1(ii).Proposition 6.4.
Leta=x2, b=g(b1), op(b)>1, and var(b)={x1}. Then, the following hold: (i)
ifb satisfies (6.2.4), then the order of σa,b is equal to 1;(ii)
ifb satisfies (6.2.5), then the order of σa,b is infinite.Proof.
The proofs follow those of Proposition6.2 (i) and (ii), respectively.



---

*Source: 615014-2011-05-31.xml*