# The Order of Generalized Hypersubstitutions of Typeτ=(2)

Authors: Wattapong Puninagool; Sorasak Leeratanavalee
Journal: International Journal of Mathematics and Mathematical Sciences
 (2008)

---

## Abstract

The order of hypersubstitutions, all idempotent elements on the monoid of all hypersubstitutions of typeτ=(2) were studied by K. Denecke and Sh. L. Wismath and all idempotent elements on the monoid of all hypersubstitutions of type τ=(2,2)
were studied by Th. Changpas and K. Denecke. We want to study similar problems for the monoid of all generalized hypersubstitutions
of type τ=(2). In this paper, we use similar methods to characterize idempotent generalized
hypersubstitutions of type τ=(2) and determine the order of each
generalized hypersubstitution of this type. The main result is
that the order is 1,2 or infinite.


---

## Body

## 1. Introduction

The concept of generalized hypersubstitutions was
introduced by  Leeratanavalee and  Denecke [1]. We use it as a tool to
study strong hyperidentities and use strong hyperidentities to classify
varieties into collections called strong hypervarieties. Varieties which are
closed under arbitrary application of generalized hypersubstitutions are called strongly solid.A generalized hypersubstitution of typeτ=(ni)i∈I,
for short, a generalized hypersubstitution is a mapping σ which maps each ni-ary operation symbol of type τ to the set Wτ(X) of all terms of type τ built up by operation symbols from {fi∣i∈I} where fi is ni-ary and variables from a countably infinite
alphabet of variables X:={x1,x2,x3,…} which does not necessarily preserve the arity.
We denote the set of all generalized hypersubstitutions of type τ by HypG(τ).
First, we define inductively the concept of generalized superposition of termsSm:Wτ(X)m+1→Wτ(X) by the following steps:(i)
ift=xj,1≤j≤m,
then Sm(xj,t1,…,tm):=tj;(ii)
ift=xj,m<j∈ℕ,
then Sm(xj,t1,…,tm):=xj;(iii)
ift=fi(s1,…,sni),
then (1.1)Sm(t,t1,…,tm):=fi(Sm(s1,t1,…,tm),…,Sm(sni,t1,…,tm)).We extend a generalized hypersubstitutionσ to a mapping σ^:Wτ(X)→Wτ(X) inductively defined as follows:(i)
σ^[x]:=x∈X;(ii)
σ^[fi(t1,…,tni)]:=Sni(σ(fi),σ^[t1],…,σ^[tni]),
for any ni-ary operation symbol fi supposed that σ^[tj], 1≤j≤ni are already defined.Then we define a binary operation∘G on HypG(τ) by σ1∘Gσ2:=σ^1∘σ2 where ∘ denotes the usual composition of mappings and σ1,σ2∈HypG(τ).
Let σid be the hypersubstitution which maps each ni-ary operation symbol fi to the term fi(x1,…,xni).
We proved the following propositions.Proposition 1.1 (see [1]).
For arbitrary termst,t1,…,tn∈Wτ(X) and for arbitrary generalized
hypersubstitutions σ,σ1,σ2 one has
(i)
Sn(σ^[t],σ^[t1],…,σ^[tn])=σ^[Sn(t,t1,…,tn)];(ii)
(σ^1∘σ2)^=σ^1∘σ^2.Proposition 1.2 (see [1]).
HypG(τ¯)=(HypG(τ);∘G,σid) is a monoid and the set of all
hypersubstitutions of type τ forms a submonoid of HypG(τ¯).The order of the elementa is defined as the order of the cyclic
subsemigroup 〈a〉.
The order of any hypersubstitution of type τ=(2) was determined in [2].Theorem 1.3 (see [2]).
Letτ=(2) be a type. The order of any hypersubstitution
of type τ is 1,2 or infinite.In Section4, we characterize the order of generalized
hypersubstitutions of type τ=(2).


## 2. Idempotent Elements inHypG(2)

In this
section, we consider especially the idempotent elements ofHypG(2).
We have only one binary operation symbol, say f.
The generalized hypersubstitution σ which maps f to the term t is denoted by σt.
For any term t∈W(2)(X),
the set of all variables occurring in t is denoted by var(t).
First, we will recall the definition of an idempotent element.Definition 2.1.
For any semigroupS,
an element e∈S is called idempotent if ee=e.
In general, by E(S) we denote the set of all idempotent elements
of S.Proposition 2.2.
An elementσt∈HypG(2) is idempotent if and only if σ^t[t]=t.Proof.
Assume thatσt is idempotent, that is, σt2=σt.
Then (2.1)σ^t[t]=σ^t[σt(f)]=σt2(f)=σt(f)=t.Conversely, let σ^t[t]=t.
We have (σt∘Gσt)(f)=σ^t[σt(f)]=σ^t[t]=t=σt(f). Thus σt2=σt.Proposition 2.3.
For
everyxi∈X, σxi and σid are idempotent.Proof.
Since for everyxi∈X, σ^xi[xi]=xi.
By Proposition 2.2 we have σxi is idempotent. σid is idempotent because it is a neutral
element.Proposition 2.4.
For everyi,j∈ℕ, the generalized hypersubstitutions σf(x1,xj) and σf(xi,x2) are idempotent.Proof.
Leti,j∈ℕ.
Then we have (2.2)σ^f(x1,xj)[f(x1,xj)]=S2(σf(x1,xj)(f),x1,xj)=S2(f(x1,xj),x1,xj)=f(x1,xj),σ^f(xi,x2)[f(xi,x2)]=S2(σf(xi,x2)(f),xi,x2)=S2(f(xi,x2),xi,x2)=f(xi,x2).
Note that for anyt∈W(2)(X)∖X and x1,x2∉var(t), σt is idempotent. Since there is nothing to
substitute in the term σ^t[t],
thus σ^t[t]=t.Proposition 2.5.
Lett∈W(2)(X)∖X.
Then the following propositions hold:
(i)
ifx2∉var(t),
then σf(x1,t) is idempotent;(ii)
ifx1∉var(t),
then σf(t,x2) is idempotent.Proof.
(i) Letx2∉var(t).
Then (2.3)σ^f(x1,t)[f(x1,t)]=S2(σf(x1,t)(f),x1,σ^f(x1,t)[t])=S2(f(x1,t),x1,σ^f(x1,t)[t])=f(x1,t).
(ii) Letx1∉var(t).
Then (2.4)σ^f(t,x2)[f(t,x2)]=S2(σf(t,x2)(f),σ^f(t,x2)[t],x2)=S2(f(t,x2),σ^f(t,x2)[t],x2)=f(t,x2).


## 3. Nonidempotent Elements ofHypG(2)

In this
section, we characterize all elements ofHypG(2) which are not idempotent.Proposition 3.1.
Ifi,j∈ℕ with i≠1 and j≠2,
then σf(x2,xj) and σf(xi,x1) are not idempotent.Proof.
Leti,j∈ℕ with i≠1 and j≠2.
Since j≠2, σ^f(x2,xj)[f(x2,xj)]=S2(f(x2,xj),x2,xj)≠f(x2,xj).
Since i≠1, σ^f(xi,x1)[f(xi,x1)]=S2(f(xi,x1),xi,x1)≠f(xi,x1).Proposition 3.2.
Lett∈W(2)(X)∖X.
Then the following propositions hold:
(i)
ifx2∈var(t),
then σf(x1,t) is not idempotent;(ii)
ifx1∈var(t),
then σf(t,x2) is not idempotent;(ii)
σf(t,x1) and σf(x2,t) are not idempotent;(iv)
ifx1∈var(t) or x2∈var(t),
then σf(xi,t) and σf(t,xi) are not idempotent for any i∈ℕ with i>2.Proof.
(i) Letx2∈var(t).
Then we have σ^f(x1,t)[f(x1,t)]=S2(f(x1,t),x1,σ^f(x1,t)[t]). Since x2∈var(t),
then we have to substitute x2 in the term t by σ^f(x1,t)[t]. S2(f(x1,t),x1,σ^f(x1,t)[t])≠f(x1,t).
The proofs of (ii), (iii), and (iv) are similar to
(i).Proposition 3.3.
Lett1,t2∈W(2)(X)∖X.
If x1∈var(t1)∪var(t2) or x2∈var(t1)∪var(t2),
then σf(t1,t2) is not idempotent.Proof.
The
proof is similar to that of Proposition3.2.By Sections2 and 3, we get PG(2)∪Ex1G∪Ex2G∪G∪{σid} is the set of all idempotent elements in HypG(2) where PG(2):={σxi∈HypG(2)∣i∈ℕ,xi∈X},Ex1G:={σf(x1,s)∈HypG(2)∣s∈W(2)(X),x2∉var(s)},Ex2G:={σf(s,x2)∈HypG(2)∣s∈W(2)(X),x1∉var(s)} and G:={σs∈HypG(2)∣s∈W(2)(X)∖X,x1,x2∉var(s)}.


## 4. The Order of Generalized Hypersubstitutions of Typeτ=(2)

In this section, we characterize the order of
generalized hypersubstitutions of typeτ=(2).
First, we introduce some notations. For s,f(c,d)∈W(2)(X),xi,xj∈X,i,j∈ℕ we denotevb(s):= the total number of variables occurring in
the term s;leftmost(s):=  the first variable (from the left) that
occurs in s;rightmost(s):= the last variable that occurs in s;W(2)G({x1}):={s∈W(2)(X)∣x1∈var(s),x2∉var(s)},W(2)G({x2}):={s∈W(2)(X)∣x2∈var(s),x1∉var(s)},f(c,d)¯ :=
the term obtained from f(c,d) by interchanging all occurrences of the
letters x1 and x2,
that is, f(c,d)¯=S2(f(c,d),x2,x1) and f(c,d)=S2(f(c,d)¯,x2,x1);f(c,d)′:= the term defined inductively by xi'=xi and f(c,d)′=f(d′,c′);Cxi[f(c,d)]:= the term obtained from f(c,d) by replacing each of the occurrences of the
letter x1 by xi,
that is, Cxi[f(c,d)]=S2(f(c,d),xi,x2);Cxi[f(c,d)]:=
the term obtained from f(c,d) by replacing each of the occurrences of the
letter x2 by xi, that is, Cxi[f(c,d)]=S2(f(c,d),x1,xi);Cxjxi[f(c,d)]:=
the term obtained from f(c,d) by replacing each of the occurrences of the
letter x1 by xi and the letter x2 by xj, that is, Cxjxi[f(c,d)]=S2(f(c,d),xi,xj).An elementa in a semigroup S is idempotent if and only if the order of a is 1. Then we consider only the order of
generalized hypersubstitutions of type τ=(2) which are not idempotent. We have the
following lemmas and propositions.Lemma 4.1.
Letf(c,d),f(u,v)∈W(2)(X) and σf(c,d)∘Gσf(u,v)=σw.
Then vb(w)>vb(f(c,d)) unless f(c,d) and f(u,v) match one of the following 16 possibilities:
E(1)
σf(c,d)∘Gσf(u,v)=σf(c,d) where σf(c,d)∈G;E(2)
σf(c,d)∘Gσf(x1,x1)=σCx1[f(c,d)];E(3)
σf(c,d)∘Gσf(x2,x2)=σCx2[f(c,d)];E(4)
σf(c,d)∘Gσid=σf(c,d);E(5)
σf(c,d)∘Gσf(x1,xi)=σCxi[f(c,d)] where xi∈X, i>2;E(6)
σf(c,d)∘Gσf(x2,x1)=σf(c,d)¯;E(7)
σf(c,d)∘Gσf(x2,xi)=σCxix2[f(c,d)] where xi∈X, i>2;E(8)
σf(c,d)∘Gσf(xi,x1)=σCx1xi[f(c,d)]  where xi∈X, i>2;E(9)
σf(c,d)∘Gσf(xi,x2)=σCxi[f(c,d)]  where xi∈X, i>2;E(10)
σf(c,d)∘Gσf(xi,xj)=σCxjxi[f(c,d)]  where xi,xj∈X, i,j>2;E(11)
σf(c,d)∘Gσf(x1,v)=σf(c,d) where v∉X, f(c,d)∈W(2)G({x1});E(12)
σf(c,d)∘Gσf(x2,v)=σf(c,d)¯ where v∉X, f(c,d)∈W(2)G({x1});E(13)
σf(c,d)∘Gσf(xi,v)=σCxi[f(c,d)] where xi∈X, i>2, v∉X, f(c,d)∈W(2)G({x1});E(14)
σf(c,d)∘Gσf(u,x1)=σf(c,d)¯ where u∉X, f(c,d)∈W(2)G({x2});E(15)
σf(c,d)∘Gσf(u,x2)=σf(c,d) where u∉X, f(c,d)∈W(2)G({x2});E(16)
σf(c,d)∘Gσf(u,xi)=σCxi[f(c,d)] where xi∈X, i>2, u∉X, f(c,d)∈W(2)G({x2}).Proof.
Assume
thatf(c,d),f(u,v)∈W(2)(X) and σf(c,d)∘Gσf(u,v)=σw.
We want to compare vb(w) with vb(f(c,d)).
From σf(c,d)∘Gσf(u,v)=σw,
it follows that w=S2(f(c,d),σ^f(c,d)[u],σ^f(c,d)[v]).
If σf(c,d)∈G,
then w=f(c,d) and we have E(1). Assume that σf(c,d)∉G.
Then x1∈var(f(c,d)) or x2∈var(f(c,d)).
We will consider the following cases.
Case 1.
Ifu,v∈X,
then σ^f(c,d)[u]=u and σ^f(c,d)[v]=v.
This gives 9 possible subcases:
(1)
u=v=x1:
then we have σf(c,d)∘Gσf(x1,x1)=σCx1[f(c,d)],
which is E(2);(2)
u=v=x2:
then we have σf(c,d)∘Gσf(x2,x2)=σC[f(c,d)]x2,
which is E(3);(3)
u=x1,v=x2:
then we have σf(c,d)∘Gσid=σf(c,d),
which is E(4);(4)
u=x1,v=xi,i>2:
then we have σf(c,d)∘Gσf(x1,xi)=σCxi[f(c,d)],
which is E(5);(5)
u=x2,v=x1:
then we have σf(c,d)∘Gσf(x2,x1)=σf(c,d)¯,
which is E(6);(6)
u=x2,v=xi,i>2: then
we have σf(c,d)∘Gσf(x2,xi)=σCxi[f(c,d)]x2,
which is E(7);(7)
u=xi,v=x1,i>2:
then we have σf(c,d)∘Gσf(xi,x1)=σCx1[f(c,d)]xi,
which is E(8);(8)
u=xi,v=x2,i>2:
then we have σf(c,d)∘Gσf(xi,x2)=σC[f(c,d)]xi,
which is E(9);(9)
u=xi,v=xj,i,j>2:
then we have σf(c,d)∘Gσf(xi,xj)=σCxj[f(c,d)]xi,
which is E(10).Case 2.
Ifu=x1 and v∉X,
then w=S2(f(c,d),x1,σ^f(c,d)[v]).
If f(c,d)∈W(2)G({x1}),
then w=f(c,d),
as in E(11). Assume that x2∈var(f(c,d)).
Since vb(σ^f(c,d)[v])>1 and we have to substitute x2 in f(c,d) by σ^f(c,d)[v],
we get vb(w)>vb(f(c,d)).Case 3.
u=x2 and v∉X.
In this case we get E(12) or vb(w)>vb(f(c,d)).Case 4.
u=xi,i>2 and v∉X.
In this case we get E(13) or vb(w)>vb(f(c,d)).Case 5.
u∉X and v=x1.
In this case we get E(14) or vb(w)>vb(f(c,d)).Case 6.
u∉X and v=x2.
In this case we get E(15) or vb(w)>vb(f(c,d)).Case 7.
u∉X and v=xi,i>2.
In this case we get E(16) or vb(w)>vb(f(c,d)).Case 8.
Ifu,v∉X,
then vb(σ^f(c,d)[u])>1 and vb(σ^f(c,d)[v])>1.
Since vb(σ^f(c,d)[u])>1, vb(σ^f(c,d)[v])>1 and we have to substitute x1 in f(c,d) by σ^f(c,d)[u] or x2 in f(c,d) by σ^f(c,d)[v],
we get vb(w)>vb(f(c,d)).Lemma 4.2.
Lets∈W(2)(X)∖X,x1,x2∈var(s),t∈W(2)(X) and xi∈X where i∈ℕ.
If xi∈var(t),
then xi∈var(σ^s[t]).Proof.
Ift∈X,
then t=xi.
So σ^s[t]=xi and thus xi∈var(σ^s[t]).
Assume that t=f(t1,t2) for some t1,t2∈W(2)(X).
Then xi∈var(t1) or xi∈var(t2).
Assume that xi∈var(t1) and xi∈var(σ^s[t1]).
Consider σ^s[t]=σ^s[f(t1,t2)]=S2(s,σ^s[t1],σ^s[t2]).
Since x1∈var(s) and xi∈var(σ^s[t1]),
we get xi∈var(σ^s[t]).
By the same way, we can show that if xi∈var(t2),
then xi∈var(σ^s[t]).Lemma 4.3.
Lets∈W(2)(X)∖X.
If x1,x2∈var(s),
then x1,x2∈var(σsn(f)) for all n∈ℕ.Proof.
Assume thats=f(s1,s2) for some s1,s2∈W(2)(X).
For n=1, σs1(f)=σs(f)=s.
So x1,x2∈var(σs1(f)).
Assume that x1,x2∈var(σsn(f)).
Consider σsn+1(f)=(σsn∘Gσs)(f)=σ^sn[σs(f)]=σ^sn[s]=σ^sn[f(s1,s2)]=S2(σsn(f),σ^sn[s1],σ^sn[s2]).
If x1,x2∈var(s1),
then by Lemma 4.2 we get x1,x2∈var(σ^sn[s1]).
Since x1∈var(σsn(f)) and x1,x2∈var(σ^sn[s1]),
we get x1,x2∈var(σsn+1(f)).
If s1∈W(2)G({x1}),
then x2∈var(s2).
By Lemma 4.2, we get x1∈var(σ^sn[s1]) and x2∈var(σ^sn[s2]).
Since x1,x2∈var(σsn(f)),
we get x1,x2∈var(σsn+1(f)).
If s1∈W(2)G({x2}),
then by the same proof as for the case s1∈W(2)G({x1}) we get x1,x2∈var(σsn+1(f)).
If x1,x2∉var(s1),
then x1,x2∈var(s2). By the same proof as for the case x1,x2∈var(s1), we get x1,x2∈var(σsn+1(f)).Lemma 4.4.
Lets∈W(2)(X)∖X and s∈W(2)G({x1}).
If leftmost(s)=xi where xi∈X,i>2,
then x1,x2∉var(σs2(f)).Proof.
Assume thats=f(s1,s2) for some s1,s2∈W(2)(X).
Consider σs2(f)=(σs∘Gσs)(f)=σ^s[σs(f)]=σ^s[s]=σ^s[f(s1,s2)]=S2(s,σ^s[s1],σ^s[s2]).
If s1∈X,
then s1 is the leftmost variable of s,
so s1=xi.
Thus σ^s[s1]=xi.
Since s∈W(2)G({x1}), x1,x2∉var(σ^s[s1]) and σs2(f)=S2(s,σ^s[s1],σ^s[s2]),
we get x1,x2∉var(σs2(f)).
Assume that s1=f(s3,s4) for some s3,s4∈W(2)(X).
Consider  σ^s[s1]=σ^s[f(s3,s4)]=S2(s,σ^s[s3],σ^s[s4]).
If s3∈X,
then s3 is the leftmost variable of s,
so s3=xi.
Thus σ^s[s3]=xi.
Since s∈W(2)G({x1}), x1,x2∉var(σ^s[s3]) and σ^s[s1]=S2(s,σ^s[s3],σ^s[s4]),
we get x1,x2∉var(σ^s[s1]).
This implies x1,x2∉var(σs2(f)).
This procedure stops after finitely many steps at leftmost(s)=xi.Lemma 4.5.
Lets∈W(2)(X)∖X.
If leftmost(s)=x1,
then leftmost(σsn(f))=x1 for all n∈ℕ.Proof.
Assume thats=f(s1,s2) for some s1,s2∈W(2)(X).
For n=1, σs1(f)=σs(f)=s.
So leftmost(σs1(f))=x1.
Assume that leftmost(σsn(f))=x1.
Consider σsn+1(f)=(σsn∘Gσs)(f)=σ^sn[σs(f)]=σ^sn[s]=σ^sn[f(s1,s2)]=S2(σsn(f),σ^sn[s1],σ^sn[s2]).
If s1∈X,
then s1 is the leftmost variable of s,
so s1=x1.
Thus σ^sn[s1]=x1.
Since σsn+1(f)=S2(σsn(f),σ^sn[s1],σ^sn[s2]), leftmost(σsn(f))=x1 and σ^sn[s1]=x1,
we get leftmost(σsn+1(f))=x1.
Assume that s1=f(s3,s4) for some s3,s4∈W(2)(X).
Consider σ^sn[s1]=σ^sn[f(s3,s4)]=S2(σsn(f),σ^sn[s3],σ^sn[s4]).
If s3∈X,
then s3 is the leftmost variable of s,
so s3=x1.
Thus σ^sn[s3]=x1.
Since σ^sn[s1]=S2(σsn(f),σ^sn[s3],σ^sn[s4]), leftmost(σsn(f))=x1 and σ^sn[s3]=x1,
we get leftmost(σ^sn[s1])=x1.
This implies leftmost(σsn+1(f))=x1.
This procedure stops after finitely many steps at leftmost(s)=x1.Lemma 4.6.
Lets∈W(2)(X)∖X and s∈W(2)G({x2}).
If rightmost(s)=xi where xi∈X,i>2,
then x1,x2∉var(σs2(f)).Proof.
The proof is similar to the proof of Lemma4.4.Lemma 4.7.
Lets∈W(2)(X)∖X.
If rightmost(s)=x2,
then rightmost(σsn(f))=x2 for all n∈ℕ.Proof.
The proof is similar to the proof of Lemma4.5.Note that{σf(x2,x1)n∣n∈ℕ}={σid,σf(x2,x1)},
and that the order of σf(x2,x1) is 2.Proposition 4.8.
Lets∈W(2)(X), x1,x2∈var(s), σs be not idempotent and not equal to σf(x2,x1).
Then the order of σs is infinite.Proof.
Letn∈ℕ.
Let σsn(f)=w.
By Lemma 4.3, we get x1,x2∈var(w).
Then the equation σsn+1=σsn∘Gσs does not fit any of E(1) to E(16), so by Lemma
4.1, we have that the term for σsn+1 is longer than w.
This implies the order of σs is infinite.Proposition 4.9.
Lets∈W(2)G({x1}),
and σs be not idempotent. If leftmost(s)=x1,
then the order of σs is infinite.Proof.
Letn∈ℕ.
Let σsn(f)=w.
By Lemma 4.5, we get leftmost(w)=x1.
Then the equation σsn+1=σsn∘Gσs does not fit any of E(1) to E(16), so by Lemma
4.1 we have that the term for σsn+1 is longer than w.
This implies the order of σs is infinite.Proposition 4.10.
Lets∈W(2)G({x1}) and σs be not idempotent. If leftmost(s)=xi where xi∈X, i>2,
then the order of σs is 2.Proof.
Letσs2(f)=w.
By Lemma 4.4, we get x1,x2∉var(w).
This implies σsn=σs2 for all n∈ℕ where n≥2.
So the order of σs is 2.Proposition 4.11.
Lets∈W(2)G({x2}) and σs be not idempotent. If rightmost(s)=x2,
then the order of σs is infinite.Proof.
The proof is similar to the proof
of Proposition4.9.Proposition 4.12.
Lets∈W(2)G({x2}) and σs be not idempotent. If rightmost(s)=xi where xi∈X, i>2,
then the order of σs is 2.Proof.
The proof is similar to the proof of Proposition4.10.Now we have the main result.Theorem 4.13.
The
order of any generalized hypersubstitution of typeτ=(2) is 1,2 or infinite.Proof.
Letσt∈HypG(2).
If σt is idempotent, then the order of σt is 1. If σt is not idempotent, then x1∈var(t) or x2∈var(t).
Assume that x1,x2∈var(t).
If σt=σf(x2,x1),
then the order of σt is 2. If σt≠σf(x2,x1),
then by Proposition 4.8 we get the order of σt is infinite. Assume that x1∈var(t) and x2∉var(t).
If leftmost(t)=x1,
then by Proposition 4.9 we get the order of σt is infinite. If leftmost(t)=xi where i>2,
then by Proposition 4.10 we get the order of σt is 2. By the same way we can show that if x2∈var(t) and x1∉var(t),
then the order of σt is 2 or infinite.



---

*Source: 263541-2009-02-10.xml*