# The Depth of Generalized Full Terms and Generalized Full Hypersubstitutions

Authors: Sarawut Phuapong; Sorasak Leeratanavalee
Journal: Algebra
 (2013)

---

## Abstract

We generalize the concept of a full term which was introduced by Denecke and Changphas and the concept of the depth of a hypersubstitution which was introduced by  Denecke et al. to the depth of a generalized full term and the depth of a generalized full hypersubstitution and then derive the formular for its depth.


---

## Body

## 1. Introduction

Identities are used to classify algebras into collections called varieties. An important activity is to classify all varieties of algebras of a given typeτ. Such as for a type τ=(2), if the binary operation symbol satisfies the associative law, the algebras are semigroups. Hyperidentities are also used to classify varieties into collections called hypervarieties. Its generalization is called M-hyperidentities and M-solid varieties. The study of hyperidentities is a part of Universal Algebra and also a part of Model Theory of second-order language. The notions of hyperidentities and hypervarieties of a given type τ without nullary operations were originated by Aczél [1], Belousov [2], Neumann [3], and Taylor [4]. The main tool used to study hyperidentities and hypervarieties is the concept of a hypersubstitution which was introduced by Denecke et al. [5]. In 2000, Leeratanavalee and Denecke generalized the concept of hypersubstitution [6].LetX={x1,x2,x3,…} be a countably infinite set of symbols called variables. We often refer to these variables as letters, to X as an alphabet, and also refer to the set Xn={x1,x2,…,xn} as an n-element alphabet. Let (fi)i∈I be an indexed set which is disjoint from X. Each fi is called ni-ary operation symbol, where ni≥1 is a natural number. Let τ be a function which assigns to every fi the number ni as its arity. The function τ, on the values of τ written as (ni)i∈I is called a type.Ann-ary term of type, τ, or simply an n-ary term is defined inductively as follows:  (i)
the variablesx1,…,xn are n-ary terms.(ii)
Ift1,…,tni are n-ary terms, then fi(t1,…,tni) is an n-ary term.ByWτ(Xn) we mean the smallest set which contains x1,…,xn and is closed under finite application of (ii). It is clear that every n-ary term is also an m-ary term for all m≥n. The set Wτ(X):=⋃n=1∞‍Wτ(Xn) is the set of all terms of type τ over the alphabet X. This set can be used as the universe of an algebra of type τ. For every i∈I, an ni-ary operation fi¯ on Wτ(X) is defined by fi¯:Wτ(X)ni→Wτ(X) with (t1,…,tni)↦fi(t1,…,tni). The algebra ℱτ(X):=(Wτ(X);(fi¯)i∈I) is called the absolutely free algebra of typeτover the setX. The term algebra  ℱτ(X) is generated by the set X and has the property called absolute freeness, meaning that for every algebra 𝒜∈Alg(τ) and every mapping f:X→𝒜 there exists a unique homomorphism f^:ℱτ(X)→𝒜 which extends the mapping f and such that f^∘φ=f, where φ:X→ℱτ(X) is the embedding of X into ℱτ(X). This can be shown by Figure 1.Figure 1
The embedding ofX into ℱτ(X).It is clear that the absolutely free algebrasℱτ(X) and ℱτ(Y) are isomorphic if X and Y have the same cardinality. One can use trees instead of terms. Trees are connected graphs which have no cycles. It can be used to visualize the structure of computer programs. For applications, we can measure the complexity of a tree. Then the depth of a term (or the height of a tree) is defined. Let t∈Wτ(X), the depth of a term t which is denoted by depth(t) and is defined as follows:  (i)
ift=x∈X, then depth(t):=0,(ii)
ift=fi(t1,…,tni) where t1,…,tni∈Wτ(X), then depth(t):=max{depth(tj)∣1≤j≤ni}+1.A generalized hypersubstitution of typeτ is a mapping σ:{fi∣i∈I}→Wτ(X) which does not necessarily preserve the arity.We denoted the set of all generalized hypersubstitutions of typeτ by HypG(τ). To define a binary operation on HypG(τ), we need to define the concept of generalized superposition of terms Sm:Wτ(X)m+1→Wτ(X) by the following steps.For any termt∈Wτ(X),  (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)Sm(t,t1,…,tm):=fi(Sm(s1,t1,…,tm),…,Sm(sni,t1,…,tm)).Then the generalized hypersubstitutionσ can be extended to a mapping σ^:Wτ(X)→Wτ(X) by the following steps:  (i)
σ^[x]:=x∈X,(ii)
σ^[fi(t1,…,tni)]:=Sni(σ(fi),σ^[t1],…,σ^[tni]), for any ni-ary operation symbol fi where σ^[tj], 1≤j≤ni are already defined.We defined 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). In [6], it is proved that for arbitrary terms t,t1,…,tn∈Wτ(X) and for arbitrary generalized hypersubstitutions σ,σ1,σ2 we have  (i)
Sn(σ^[t],σ^[t1],…,σ^[tn])=σ^[Sn(t,t1,…,tn)],(ii)
(σ^1∘σ2)^=σ^1∘σ^2.It turns out that(HypG(τ);∘G,σid) is a monoid where σid is its identity element. The monoid (Hyp(τ);∘h,σid) of all arity preserving hypersubstitutions of type τ forms a submonoid of (HypG(τ);∘G,σid). In 2001, Denecke et al. introduced the concept of the depth of a hypersubstitution [7]. Also in 2002, Denecke and Changpas defined full terms and studied full hypersubstitutions [8]. In this paper we generalized these concepts to the depth of generalized full terms and generalized full hypersubstitutions.


## 2. Generalized Full Terms

We use standard terminology established in modern algebra; see [9–11]. In this section, we give the definition of a generalized full term of type τ, or simply a generalized full term, and describe the behavior of the depth of a generalized full term.Definition 1.
LetΩ be the set of operation symbols and f∈Ω with arity (f)=n:  (i)
ifs:{1,…,n}→{1,…,n} is a permutation, then f(xs(1),…,xs(n)) is a generalized full term,(ii)
ifj1,j2,…,jn are natural numbers greater than n, then f(xs′(j1),…,xs′(jn)) is a generalized full term where s′ is a permutation on {j1,…,jn},(iii)
ift1,…,tn are generalized full terms, then f(t1,…,tn) is a generalized full term.
LetW(n)GF(X) be the set of all generalized full terms and let Pn be the set of all permutations on {1,2,…,n}. By Definition 1, the set W(n)GF(X) is closed under finite application of (iii). Therefore (W(n)GF(X);(f-i)i∈I) is a subalgebra of ℱτ(X).Proposition 2.
Letp,p1,p2,…,pn∈W(n)GF(X). Then Sn(p,p1,…pn) is also a generalized full term.Proof.
We give a proof by induction on the complexity of a generalized full termp.
Ifp=f(xs(1),…,xs(n)) where s∈Pn, then:
(2)Sn(p,p1,…,pn)=Sn(fi(xs(1),…,xs(n)),p1,…,pn)=f(ps(1),…,ps(n))
which is a generalized full term.
Ifp=f(xs′(j1),…,xs′(jn)) where j1,…jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then
(3)Sn(p,p1,…,pn)=Sn(f(xs′(j1),…,xs′(jn)),p1,…,pn)=f(xs′(j1),…,xs′(jn))
which is a generalized full term.
Ifp=f(t1,…,tn) where t1,…,tn∈W(n)GF(X) and assume that Sn(tj,p1,…,pn) are generalized full terms for all 1≤j≤n, then
(4)Sn(p,p1,…,pn)=Sn(f(t1,…,tn),p1,…,pn)=f(Sn(t1,p1,…,pn),…,Sn(tn,p1,…,pn)).
By Definition 1(iii), Sn(p,p1,…,pn) is a generalized full term.Now we consider the algebracloneGF(n):=(W(n)GF(X);Sn) of type (n+1) with ℱGS(n)={f(xs(1),…,xs(n))∣s∈Pn}∪{f(xs′(j1),…,xs′(jn))∣j1,…,jn>n,s′ is a permutation on {j1,…,jn}} as a generating system. The algebra cloneGF(n) is called the clone of generalized full terms of type(n). Then we have the following.Proposition 3.
The algebracloneGF(n) satisfies the so-called superassociative law (C)(5)S~n(X0,S~n(Y1,X1,…,Xn),…,S~n(Yn,X1,…,Xn))≈S~n(S~n(X0,Y1,…,Yn),X1,…,Xn),
where S~n is an (n+1)-ary operation symbol and Xl,Yj are variables.Proof.
We give a proof by induction on the complexity of the generalized full term which is substituted forX0. Substituting for X0 a term of the form f(xs(1),…,xs(n)) for s∈Pn, then
(6)Sn(f(xs(1),…,xs(n)),Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn))=f(Sn(xs(1),Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn)),…,Sn(xs(n),Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn)))=f(Sn(ts(1),s1,…,sn),…,Sn(ts(n),s1,…,sn))=Sn(f(ts(1),…,ts(n)),s1,…,sn)=Sn(Sn(f(xs(1),…,xs(n)),t1,…,tn),s1,…,sn).
If we substitute for X0 a term t=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then
(7)Sn(f(xs′(j1),…,xs′(jn)),Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn){f(xs′(j1),…,xs′(jn))})=f(xs′(j1),…,xs′(jn))=Sn(f(xs′(j1),…,xs′(jn)),s1,…,sn)=Sn(f(Sn(xs′(j1),t1,…,tn),…,Sn(xs′(jn),t1,…,tn)),s1,…,sn)=Sn(Sn(f(xs′(j1),…,xs′(jn)),t1,…,tn),s1,…,sn).
If we substitute for X0 a term t=f(r1,…,rn) and assume that (C) is satisfied for r1,…,rn∈W(n)GF(X), then
(8)Sn(f(r1,…,rn),Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn))=f(Sn(r1,Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn)),…,Sn(rn,Sn(t1,s1,…,sn),…,Sn(tn,s1,…,sn)))=Sn(f(Sn(r1,t1,…,tn),…,Sn(rn,t1,…,tn)),s1,…,sn)=Sn(Sn(f(r1,…,rn),t1,…,tn),s1,…,sn).An algebra(M;Sn) of type (n+1) which satisfies the condition (C) is called a Menger algebra of rankn.Lemma 4.
Lett,t1,t2,…,tn∈W(n)GF(X). If depth(t)=1, then
(9)depth(Sn(t,t1,…,tn))=1ormax{depth(t1),…,depth(tn)}+1.Proof.
Assume thatdepth(t)=1. Then t=f(xs(1),…,xs(n)) where s∈Pn or t=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}:
ift=f(xs(1),…,xs(n)), then
(10)depth(Sn(t,t1,…,tn))=depth(Sn(f(xs(1),…,xs(n)),t1,…,tn))=depth(f(ts(1),…,ts(n)))=max{depth(ts(1)),…,depth(ts(n))}+1=max{depth(t1),…,depth(tn)}+1.
If t=f(xs′(j1),…,xs′(jn)), then
(11)depth(Sn(t,t1,…,tn))=depth(Sn(f(xs′(j1),…,xs′(jn)),t1,…,tn))=depth(f(xs′(j1),…,xs′(jn)))=1.Theorem 5.
Lett,t1,t2,…,tn∈W(n)GF(X). Then depth(Sn(t,t1,…,tn))=1 or max{depth(t1),…,depth(tn)}+depth(t).Proof.
We prove this fact by induction on the complexity ofdepth(t).
Ifdepth(t)=1, then by Lemma 4 we have depth(Sn(t,t1,…,tn))=1 or max{depth(t1),…,depth(tn)}+depth(t).
Ifdepth(t)>1, then we have t=f(s1,…,sn) and assume that the formula is satisfied for s1,…,sn∈W(n)GF(X) that is depth(Sn(sk,t1,…,tn))=1 or max{depth(t1),…,depth(tn)}+depth(sk) for all 1≤k≤n. Then we have
(12)depth(Sn(t,t1,…,tn))=depth(f(Sn(s1,t1,…,tn),…,Sn(sn,t1,…,tn)))=max{depth(Sn(s1,t1…,tn)),…,depth(Sn(sn,t1,…,tn))}+1=max{max{depth(t1),…,depth(tn)}+depth(s1),…,max{depth(t1),…,depth(tn)}+depth(sn)}+1=max{depth(t1),…,depth(tn)}+max{depth(s1),…,depth(sn)}+1=max{depth(t1),…,depth(tn)}+depth(t).


## 3. The Depth of Generalized Full Terms with respect tok

In this section, we generalize the concept of the depth of a full termt with respect to k which were studied by Denecke et al. [7] to the depth of a generalized full term t with respect to k.Definition 6.
Lett∈W(n)GF(X) and let k be a fixed element of {1,2,…,n} and var(t) be the set of all variables occurring in t. For each variable xk, the depth of a generalized full term t with respect to k denoted by depthk(t) is defined inductively as follows:  (i)
ift=f(xs(1),…,xs(n)) where s∈Pn, then depthk(t)=1,(ii)
ift=f(xs′(j1),…,xs′(jn)) where j1,j2,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then  depthk(t)=0,(iii)
ift=f(t1,…,tn) and assume that  depthk(tj),1≤j≤n are already defined, then
(13)depthk(t)={0,ifxk∉var(t);max{depthk(tj)∣1≤j≤n;xk∈var(tj)}+1.otherwiseTheorem 7.
Lett,t1,t2,…,tn∈W(n)GF(X). Then
(14)depth(Sn(t,t1,…,tn))≥max{depthj(t)+depth(tj)∣1≤j≤n;xj∈var(t)}.Proof.
We prove this fact by induction on the complexity ofdepth(t). Suppose that depth(t)=1. Then t=f(xs(1),…,xs(n)) where s∈Pn or t=f(xs′(j1),…,xs′(jn)) where j1,j2,…,jn are natural numbers greater than n, and s′ is a permutation on {j1,…,jn}.
Ift=f(xs(1),…,xs(n)), then Sn(t,t1,…,tn)=Sn(f(xs(1),…,xs(n)),t1,…,tn)=f(ts(1),…,ts(n)). Therefore,
(15)depth(Sn(t,t1,…,tn))=depth(f(ts(1),…,ts(n)))=max{depth(ts(1)),…,depth(ts(n))}+1,max{depthj(t)+depth(tj)∣1≤j≤n;xj∈var(t)}=max{1+depth(t1),…,1+depth(tn)}=max{depth(ts(1)),…,depth(ts(n))}+1.
If t=f(xs′(j1),…,xs′(jn)), then Sn(t,t1,…,tn)=Sn(f(xs′(j1),…,xs′(jn)),t1,…,tn)=f(xs′(j1),…,xs′(jn)). Therefore,
(16)depth(Sn(t,t1,…,tn))=depth(f(xs′(j1),…,xs′(jn)))=1,max{depthj(t)+depth(tj)∣1≤j≤n;xj∈var(t)}=0.
If depth(t)>1, then t=f(p1,…,pn) where p1,…,pn∈W(n)GF(X) and assume that the formula is satisfied for p1,…,pn. Thus
(17)Sn(t,t1,…,tn)=Sn(f(p1,…,pn),t1,…,tn)=f(Sn(p1,t1,…,tn),…,Sn(pn,t1,…,tn)),depth(Sn(t,t1,…,tn))=max{depth(Sn(p1,t1,…,tn)),…,depth(Sn(pn,t1,…,tn))}+1≥max{max{depthj(p1)+depth(tj)∣1≤j≤n;xj∈var(p1)},…,max{depthj(pn)+depth(tj)∣1≤j≤n;xj∈var(pn)}}+1=max{max{depthj(pk)∣1≤j≤n,1≤k≤n;xj∈var(pk)}+1+depth(tj)∣1≤j≤n,xj∈∪{var(pk)∣1≤k≤n}}=max{max{depthj(pk)∣1≤j≤n,1≤k≤n;xj∈var(pk)}+1+depth(tj)∣1≤j≤n;xj∈var(t)}}=max{depthj(t)+depth(tj)∣1≤j≤n;xj∈var(t)}.Example 8.
Letτ=(3) be a type; that is, we have only one ternary operation symbol, say f. Let t,t1,t2∈W(3)GF(X) where t=f(f(x2,x1,x3),f(x7,x4,x5),f(x3,x2,x1)), t1=f(x9,x5,x4), t2=f(f(x2,x3,x1),f(x2,x3,x1),f(x2,x3,x1)) and t3=f(x6,x4,x5). Then we have depth(t)=2, depth(t1)=1, depth(t2)=2, and depth(t3)=1. Thus depth(S3(t,t1,t2,t3))=4. Consider max{depth1(t)+depth(t1),depth2(t)+depth(t2),anddepth3(t)+depth(t3)}=max{2+1,2+2,2+1}=4.


## 4. Generalized Full Hypersubstitutions and Substitutions ofcloneGF(n)

In this section, we will generalize the concept of full hypersubstitution. For any generalized full termt, we define the generalized full term ts arising from t by mapping all variables corresponding to a permutation s∈Pn inductively by the following steps:  (i)
ift=f(xr(1),…,xr(n)) where r∈Pn, then ts=f(xs(r(1)),…,xs(r(n))),(ii)
ift=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then ts=f(xs′(j1),…,xs′(jn)),(iii)
ift=f(t1,…,tn) where t1,…,tn∈W(n)GF(X), then ts=f((t1)s,…,(tn)s).It is clear thatts is a generalized full term for any generalized full term t and for any s∈Pn.Definition 9.
A mappingσ:Ω→W(n)GF(X) is called a  generalized full hypersubstitution.ByHypGF(n) we denote the set of all generalized full hypersubstitutions of type (n). Every generalized full hypersubstitution σ can be extended to a map σ^ defined on W(n)GF(X) as follows:  (i)
σ^[f(xs(1),…,xs(n))]:=σ(f)s,(ii)
σ^[f(xs′(j1),…,xs′(jn))]:=Sn(σ(f),xs′(j1),…,xs′(jn)),(iii)
σ^[fi(t1,…,tn)]:=Sn(σ(f),σ^[t1],…,σ^[tn]).We define a binary operation∘GF on HypGF(n) by σ1∘GFσ2:=σ^1∘σ2, where ∘ denotes the usual composition of functions. Together with the hypersubstitution σid defined by σid(f):=f(x1,…,xn), one has a monoid (HypGF(n);∘GF,σid). Then we have the following.Lemma 10.
Lett∈W(n)GF(X), s∈Pn, and σ∈HypGF(n). Then
(18)Sn(t,σ^[ts(1)],…,σ^[ts(n)])=Sn(ts,σ^[t1],…,σ^[tn]).Proof.
We give a proof by induction on the complexity of a generalized full termt.
Ift=f(xr(1),…,xr(n)) where r∈Pn, then
(19)Sn(t,σ^[ts(1)],…,σ^[ts(n)])=Sn(f(xr(1),…,xr(n)),σ^[ts(1)],…,σ^[ts(n)])=f(σ^[ts(r(1))],…,σ^[ts(r(n))]),Sn(ts,σ^[t1],…,σ^[tn])=Sn(f(xr(1),…,xr(n))s,σ^[t1],…,σ^[tn])=Sn(f(xs(r(1)),…,xs(r(n))),σ^[t1],…,σ^[tn])=f(σ^[ts(r(1))],…,σ^[ts(r(n))]).
If t=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then
(20)Sn(t,σ^[ts(1)],…,σ^[ts(n)])=Sn(f(xs′(j1),…,xs′(jn)),σ^[ts(1)],…,σ^[ts(n)])=f(xs′(j1),…,xs′(jn)),Sn(ts,σ^[t1],…,σ^[tn])=Sn((f(xs′(j1),…,xs′(jn))s,σ^[t1],…,σ^[tn])=f(xs′(j1),…,xs′(jn)).
If t=f(t1′,…,tn′) where t1′,…,tn′∈W(n)GF(X) and assume that the formula is satisfied for t1′,…,tn′, then
(21)Sn(t,σ^[ts(1)],…,σ^[ts(n)])=Sn(f(t1′,…,tn′)),σ^[ts(1)],…,σ^[ts(n)])=f(Sn(t1′,σ^[ts(1)],…,σ^[ts(n)]),…,Sn(tn′,σ^[ts(1)],…,σ^[ts(n)]))=f(Sn((t1′)s,σ^[t1],…,σ^[tn]),…,Sn((tn′)s,σ^[t1],…,σ^[tn]))=Sn(f((t1′)s,…,(tn′)s),σ^[t1],…,σ^[tn])=Sn((f(t1′,…,tn′))s,σ^[t1],…,σ^[tn])=Sn(ts,σ^[t1],…,σ^[tn]).Lemma 11.
Letσ∈HypGF(n) and p be a generalized full term. Then σ^[p] is also a generalized full term.Proof.
We give a proof by induction on the complexity of a generalized full termp.
Ifp=f(xs(1),…,xs(n)) where s∈Pn, then σ^[p]=σ(f)s. Since σ(f)s is a generalized full term, σ^[p] is also a generalized full term.
Ifp=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then σ^[p]=σ^[f(xs′(j1),…,xs′(jn))]=Sn(σ(f),xs′(j1),…,xs′(jn)). Since Sn(σ(f),xs′(j1),…,xs′(jn)) is a generalized full term, σ^[p] is also a generalized full term.
Ifp=f(p1,…,pn) where pj are generalized full terms for all 1≤j≤n and assume that σ^[pj] are generalized full terms for all 1≤j≤n, then σ^[p]=Sn(σ(fi),σ^[p1],…,σ^[pn]) is also a generalized full term.Lemma 12.
H
y
p
G
F
(
n
)
_ forms a submonoid of the monoid HypG(n)_ of all generalized hypersubstitutions.Proof.
Sinceσid(f)=f(x1,…,xn) is a generalized full term, the identity-generalized hypersubstitution is a generalized full hypersubstitution.
Assume thatσ1,σ2∈HypGF(n). Since (σ1∘GFσ2)(f)=σ^1[σ2(f)] and σ1(f),σ2(f) are generalized full terms, then by Lemma 11 we have that  (σ1∘GFσ2)(f) is a generalized full term. Hence σ1∘GFσ2∈HypGF(n) and therefore HypGF(n)_ forms a submonoid of HypG(n)_.Definition 13.
Letσ be a generalized full hypersubstitution of type (n), and then we define
(22)depth(σ)=max{depth(σ(f))∣f∈Ω}.Corollary 14.
Letp=f(p1,…,pn)∈W(n)GF(X), σ∈HypGF(n). Then
(23)depth(σ^[p])=depth(σ(f))depth(p).Proof.
We give a proof by induction ondepth(p).
Ifdepth(p)=1, then p=f(xs(1),…,xs(n)) where s∈Pn or p=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}.
Ifp=f(xs(1),…,xs(n)), then
(24)depth(σ^[p])=depth(σ^[f(xs(1),…,xs(n))])=depth(σ(f)s)=depth(σ(f))=depth(σ(f))depth(p).
If p=f(xs′(j1),…,xs′(jn)), then
(25)depth(σ^[p])=depth(σ^[f(xs′(j1),…,xs′(jn))])=depth(Sn(σ(f),xs′(j1),…,xs′(jn)))=max{depth(xs′(j1)),…,depth(xs′(jn))}+depth(σ(f))=0+depth(σ(f))=depth(σ(f))=depth(σ(f))depth(p).
Assume that the depth(σ^[pk])=depth(σ(f))depth(pk) for all 1≤k≤n and p=f(p1,…,pn). Then
(26)depth(σ^[p])=depth(Sn(σ(f),σ^[p1],…,σ^[pn]))=depth(σ(f))+max{depth(σ^[pk])∣1≤k≤n}=depth(σ(f))+max{depth(σ(f))depth(pk)∣1≤k≤n}=depth(σ(f))+depth(σ(f))max{depth(pk)∣1≤k≤n}=depth(σ(f))(1+max{depth(pk)∣1≤k≤n})=depth(σ(f))depth(p).Corollary 15.
The functiondepthGF:HypGF(n)→ℕ+ with σ↦depth(σ) is a homomorphism from the monoid (HypGF(n);∘GF,σid) onto the monoid (ℕ+;·,1).Proof.
The mappingdepthGF is well defined and surjective since for every n∈ℕ+ there exists a generalized full term p with depth(p)=n. Furthermore, we have depthGF(σid)=depth(σid(f))=depth(f(x1,…,xn))=1 and
(27)depth((σ1∘GFσ2)(f))=depth(σ^1[σ2(f)])=depth(σ1(f))depth(σ2(f))=depthGF(σ1)depthGF(σ2).Proposition 16.
Letσ∈HypGF(n). Then σ^ is an endomorphism on the algebra (W(n)GF(X);Sn).Proof.
Indeedσ^:(W(n)GF(X);Sn)→(W(n)GF(X);Sn) is a function. Now we give a proof by induction on the complexity of a term t0 that, for any t1,…,tn∈W(n)GF(X),
(28)σ^[Sn(t0,t1,…,tn)]=Sn(σ^[t0],…,σ^[tn]).
First consider the case that t0=f(xs(1),…,xs(n)) where i∈I and s∈Pn. Then
(29)σ^[Sn(t0,t1,…,tn)]=σ^[Sn(f(xs(1),…,xs(n)),t1,…,tn)]=σ^[f(ts(1),…,ts(n))]=Sn(σ(f),σ^[ts(1)],…,σ^[ts(n)])=Sn(σ(f)s,σ^[t1],…,σ^[tn])=Sn(σ^[t0],σ^[t1],…,σ^[tn]).
If t0=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then
(30)σ^[Sn(t0,t1,…,tn)]=σ^[Sn(f(xs′(j1),…,xs′(jn)),t1,…,tn)]=σ^[f(xs′(j1),…,xs′(jn))]=Sn(σ(f),xs′(j1),…,xs′(jn))=Sn(σ(f),σ^[Sn(xs′(j1),t1,…,tn)],…,σ^[Sn(xs′(jn),t1,…,tn)])=Sn(Sn(σ(f),xs′(j1),…,xs′(jn)),σ^[t1],…,σ^[tn])=Sn(σ^[f(xs′(j1),…,xs′(jn))],σ^[t1],…,σ^[tn])=Sn(σ^[t0],σ^[t1],…,σ^[tn]).
If t0=f(r1,…,rn) where r1,…,rn∈W(n)GF(X) and assume that the formula is satisfied for r1,…,rn, then
(31)σ^[Sn(t0,t1,…,tn)]=σ^[Sn(f(r1,…,rn),t1,…,tn])=σ^[f(Sn(r1,t1,…,tn),…,Sn(rn,t1,…,tn))]=Sn(σ(f),σ^[Sn(r1,t1,…,tn)],…,σ^[Sn(rn,t1,…,tn)])=Sn(σ(f),Sn(σ^[r1],σ^[t1],…,σ^[tn]),…,Sn(σ^[rn],σ^[t1],…,σ^[tn]))=Sn(Sn(σ(f),σ^[r1],…,σ^[rn]),σ^[t1],…,σ^[tn])=Sn(σ^[t0],σ^[t1],…,σ^[tn]).Since the free algebracloneGF(n) is generated by the set
(32){f(xs(1),…,xs(n))s∈Pn}∪{f(xs′(j1),…,xs′(jn))∣j1,…,jn>n,s′isapermutationon{j1,…,jn}{(xs′(j1),…,xs′(jn))}},therefore any mappingη from ℱGS(n) into W(n)GF(X) can be uniquely extended to an endomorphism η- of cloneGF(n). These mappings are called generalized full clone substitutions. We denote the set of all generalized full clone substitutions by SubstGFC. The set SubstGFC with a binary operation ⊙ is defined by η1⊙η2:=η-1∘η2, where ∘ is the usual composition of functions, and, together with idℱGS(n), the identity mapping on ℱGS(n) is a monoid. Then we have the following proposition.Proposition 17.
The monoid(HypGF(n);∘GF,σid) can be embedded into the monoid (SubstGFC;⊙,idℱGS(n)).Proof.
Letσ∈HypGF(n). Then by Proposition 16, σ^ is an endomorphism on the algebra cloneGF(n). Since ℱGS(n)={f(xs(1),…,xs(n))∣s∈Pn}∪{f(xs′(j1),…,xs′(jn))∣j1,…,jn>n,s′ is a permutation on {j1,…,jn}} is a generating set of cloneGF(n), the mapping σ^∣ℱGS(n) is a substitution with σ^∣ℱGS(n)¯=σ^. We define the mapping ψ:HypGF(n)→SubstGFC by ψ(σ)=σ^∣ℱGS(n). Injectivity of ψ is clear. We show that ψ is a homomorphism. Let σ1,σ2∈HypGF(n). Then ψ(σ1∘GFσ2)=(σ^1∘σ2)∣^ℱGS(n)=(σ^1∘σ^2)∣ℱGS(n)=σ^1∘σ^2∣ℱGS(n)=σ^1∣ℱGS(n)-∘σ^2∣ℱGS(n)=ψ(σ1)¯∘ψ(σ2)=ψ(σ1)⊙ψ(σ2). Clearly, the mapping ψ preserves the identity element.


## 5. Full Strong Hyperidentities and Identities incloneGF(n)

LetV be the variety of type (n) and let IdGFV:=W(n)GF(X)2∩IdV be the set of all identities of V consisting of generalized full terms. Then we have the following.Proposition 18.
I
d
G
F
V is a congruence on cloneGF(n).Proof.
We will prove that ifr≈t, rk≈tk∈IdGFV,k=1,2,…,n, then Sn(r,r1,…,rn)≈Sn(t,t1,…,tn)∈IdGFV. Firstly, we give a proof by induction on the complexity of a term t∈W(n)GF(X) that, for every n∈ℕ+ from tk≈rk∈IdGFV,k=1,2,…,n, there follows Sn(t,t1,…,tn)≈Sn(t,r1,…,rn)∈IdGFV.
Ift=f(xs(1),…,xs(n)) and s∈Pn, then
(33)Sn(f(xs(1),…,xs(n)),t1,…,tn)=f(ts(1),…,ts(n))≈f(rs(1),…,rs(n))=Sn(f(xs(1),…,xs(n)),r1,…,rn)∈IdGFV,
where IdV is compatible with the operation f¯ of the absolutely free algebra ℱ(n)(X) and by the definition of generalized full terms.
Ift=f(xs′(j1),…,xs′(jn)) where j1,…,jn are natural numbers greater than n and s′ is a permutation on {j1,…,jn}, then
(34)Sn(f(xs′(j1),…,xs′(jn)),t1,…,tn)=f(xs′(j1),…,xs′(jn))=Sn(f(xs′(j1),…,xs′(jn)),r1,…,rn)∈IdGFV.
Assume now that t=f(l1,…,ln)∈W(n)GF(X) and, for lj,1≤j≤n, we have already
(35)Sn(lj,t1,…,tn)≈Sn(lj,r1,…,rn)∈IdGFV.
Then
(36)Sn(f(l1,…,ln),t1,…,tn)=f(Sn(l1,t1,…,tn),…,Sn(ln,t1,…,tn))≈f(Sn(l1,r1,…,rn),…,Sn(ln,r1,…,rn))=Sn(f(l1,…,ln),r1,…,rn)∈IdGFV.
Now we prove the implication
(37)t≈r∈IdGFV⟹Sn(t,r1,…,rn)≈Sn(r,r1,…,rn)∈IdGFV.
This is a consequence of the fully invariance of IdV as a congruence on the absolutely free algebra ℱ(n)(X) and the definition of a generalized full term. Assume now that t≈r,tk≈rk∈IdGFV. Then
(38)Sn(t,t1,…,tn)≈Sn(r,t1,…,tn)≈Sn(r,r1,…,rn)∈IdGFV.Definition 19.
LetV be a variety of type (n) and let IdGFV be the set of all identities of V consisting of generalized full terms. Then s≈t∈IdGFV is called an Ω-GF-hyperidentity inV if σ^[s]≈σ^[t]∈IdGFV for every σ∈HypGF(n). If every identity in IdGFV is satisfied as an Ω-GF-hyperidentity, the variety V is called Ω-GF-solid.Proposition 20.
IfIdGFV is a fully invariant congruence relation on cloneGF(n), then the variety V is Ω-GF-solid.Proof.
Lets≈t∈IdGFV and let σ∈HypGF(n) be a generalized full hypersubstitution. Since by Proposition 16 the extension σ^ of σ is an endomorphism of cloneGF(n), we have σ^[s]≈σ^[t]∈IdGFV.By Proposition18 we can form a quotient algebra:
(39)cloneGFV:=cloneGF(n)/IdGFV
which belongs to a variety of a Menger algebra of rank n. There is the following connection between clone identities and Ω-GF-hyperidentities in V.Proposition 21.
LetV be the variety of type (n) and let s≈t∈IdGFV. If s≈t is an identity in cloneGF(n), then it is an Ω-GF-hyperidentity in V.Proof.
Lets≈t∈IdGFV be an identity in cloneGF(n) and let σ∈HypGF(n). Then σ^∈End(cloneGFτ) the set of all endomorphisms of cloneGF(n) and σ^∣ℱGS(n)∈SubstGFC with σ^∣ℱGS(n)¯=σ^. By the natural mapping natIdGFV we have
(40)natIdGFV∘σ^∣ℱGS(n):ℱGS(n)⟶cloneGF(n),
and this is a valuation mapping with
(41)natIdGFV∘σ^∣ℱGS(n)¯=natIdGFV∘σ^.
Then
(42)s≈t∈Id(cloneGFV)⟹natIdGFV∘σ^∣ℱGS(n)¯(s)=natIdGFV∘σ^∣ℱGS(n)¯(t)⟹natIdGFV∘σ^(s)=natIdGFV∘σ^(t)⟹[σ^[s]]IdGFV=[σ^[t]]IdGFV⟹σ^[s]≈σ^[t]∈IdGFV.
This means that s≈t is satisfied as an Ω-GF-hyperidentity in V.



---

*Source: 396464-2013-06-26.xml*