Green’s relations on the seminearring of full hypersubstitutions of type (n)

Hypersubstitutions are mappings which are used to define hyperidentities and solid varieties. In this paper we will show that the set of all hypersubstitutions of a given type forms a seminearring. We will give a full characterization of Green’s relation R on a sub-seminearring of the seminearri...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2003
Hauptverfasser:	Changphas, Th., Denecke, K.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2003
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/154666
Tags:	Tag hinzufügen Keine Tags, Fügen Sie den ersten Tag hinzu!
Назва журналу:	Digital Library of Periodicals of National Academy of Sciences of Ukraine
Zitieren:	Green’s relations on the seminearring of full hypersubstitutions of type (n) / Th. Changphas, K. Denecke // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 6–19. — Бібліогр.: 9 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-154666
record_format	dspace
spelling	irk-123456789-1546662019-06-16T01:31:54Z Green’s relations on the seminearring of full hypersubstitutions of type (n) Changphas, Th. Denecke, K. Hypersubstitutions are mappings which are used to define hyperidentities and solid varieties. In this paper we will show that the set of all hypersubstitutions of a given type forms a seminearring. We will give a full characterization of Green’s relation R on a sub-seminearring of the seminearring Hyp(n) of all hypersubstitutions of type (n). 2003 Article Green’s relations on the seminearring of full hypersubstitutions of type (n) / Th. Changphas, K. Denecke // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 6–19. — Бібліогр.: 9 назв. — англ. 1726-3255 2001 Mathematics Subject Classification: 08B15. http://dspace.nbuv.gov.ua/handle/123456789/154666 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	Hypersubstitutions are mappings which are used to define hyperidentities and solid varieties. In this paper we will show that the set of all hypersubstitutions of a given type forms a seminearring. We will give a full characterization of Green’s relation R on a sub-seminearring of the seminearring Hyp(n) of all hypersubstitutions of type (n).
format	Article
author	Changphas, Th. Denecke, K.
spellingShingle	Changphas, Th. Denecke, K. Green’s relations on the seminearring of full hypersubstitutions of type (n) Algebra and Discrete Mathematics
author_facet	Changphas, Th. Denecke, K.
author_sort	Changphas, Th.
title	Green’s relations on the seminearring of full hypersubstitutions of type (n)
title_short	Green’s relations on the seminearring of full hypersubstitutions of type (n)
title_full	Green’s relations on the seminearring of full hypersubstitutions of type (n)
title_fullStr	Green’s relations on the seminearring of full hypersubstitutions of type (n)
title_full_unstemmed	Green’s relations on the seminearring of full hypersubstitutions of type (n)
title_sort	green’s relations on the seminearring of full hypersubstitutions of type (n)
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2003
url	http://dspace.nbuv.gov.ua/handle/123456789/154666
citation_txt	Green’s relations on the seminearring of full hypersubstitutions of type (n) / Th. Changphas, K. Denecke // Algebra and Discrete Mathematics. — 2003. — Vol. 2, № 1. — С. 6–19. — Бібліогр.: 9 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT changphasth greensrelationsontheseminearringoffullhypersubstitutionsoftypen AT deneckek greensrelationsontheseminearringoffullhypersubstitutionsoftypen
first_indexed	2025-07-14T06:42:00Z
last_indexed	2025-07-14T06:42:00Z
_version_	1837603562110058496
fulltext	Jo ur na l A lg eb ra D is cr et e M at h.Algebra and Discrete Mathematics RESEARCH ARTICLE Number 2. (2003). pp. 6–19 c© Journal “Algebra and Discrete Mathematics” Green’s relations on the seminearring of full hypersubstitutions of type (n) Th. Changphas, K. Denecke Communicated by V. M. Usenko Abstract. Hypersubstitutions are mappings which are used to define hyperidentities and solid varieties. In this paper we will show that the set of all hypersubstitutions of a given type forms a seminearring. We will give a full characterization of Green’s relation R on a sub-seminearring of the seminearring Hyp(n) of all hypersubstitutions of type (n). 1. Introduction Hypersubstitutions were introduced to make precise the concept of a hyperidentity and generalizations to M -hyperidentities. Let τ = (ni)i∈I be a type indexed by a set I, with operation symbols fi of arity ni ∈ N. Let X = {x1, x2, . . .} be a countably infinite set of variables and let Xn = {x1, . . . , xn} be a finite set. We denote by Wτ (Xn) the set of all n-ary terms of type τ over the alphabet Xn and by Wτ (X) the set of all terms of type τ . An identity s ≈ t, s, t ∈ Wτ (X), of type τ is called a hyperidentity of a variety V of type τ if for every substitution of n-ary terms for the n-ary operation symbols in s ≈ t, the resulting identity holds in V . This shows that we are interested in mappings which associate to every operation symbol fi of a given type τ a term σ(fi) of type τ of the same arity as fi. Any such map is called a hypersubstitution of type τ . 2001 Mathematics Subject Classification: 08B15. Key words and phrases: full hypersubstitutions, seminearring, Green’s rela- tions. Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 7 Hypersubstitutions can be uniquely extended to mappings σ̂ : Wτ (X) → Wτ (X) which are inductively defined by the following steps: (i) σ̂[x] := x if x ∈ X, (ii) σ̂[t] := σ(fi)(σ̂[t1], . . . , σ̂[tni ]) if t = fi(t1, . . . , tni ). Using this extension we can define a binary operation ◦h on the set Hyp(τ) of all hypersubstitutions of type τ by σ1 ◦h σ2 := σ̂1 ◦ σ2, where ◦ is the usual composition of operations. By σid we denote the iden- tity hypersubstitution, mapping each operation symbol fi to the term fi(x1, . . . xni ). This gives the monoid (Hyp(τ); ◦h, σid). If M is any submonoid of the monoid Hyp(τ), then an identity u ≈ v of a variety V is called an M -hyperidentity of V if for every σ ∈ M the equation σ̂[u] ≈ σ̂[v] holds in V . A variety V is called M -solid if every identity of V is an M -hyperidentity in V . The collection of all M -solid varieties of type τ forms a complete sublattice of the lattice of all varieties of type τ . Actually, there is a Galois connection between submonoids of Hyp(τ) and complete sublattices of the lattice of all varieties of type τ . For more background see [3]. This shows the importance of study- ing the properties of the monoid Hyp(τ) and its submonoids. In [2] the authors started to investigate the semigroup properties of the monoid Hyp(2) of all hypersubstitutions of type τ = (2), especially Green’s rela- tions on Hyp(2). We want to continue these investigations with Hyp(n), the monoid of all hypersubstitutions of type τ = (n), and a particular submonoid of Hyp(n), the monoid of all so-called full hypersubstitutions. It turns out that one can define a second binary operation on Hyp(τ) such that Hyp(τ) forms a seminearring. By (σ1 + σ2)(fi) := σ2(fi)(σ1(fi), . . . , σ1(fi)) we define a hypersubstitution which maps the ni-ary operation symbol fi to the ni-ary term σ2(fi)(σ1(fi), . . . , σ1(fi)) for every i ∈ I. The term σ2(fi)(σ1(fi), . . . , σ1(fi)) is ni-ary. Therefore σ1 + σ2 is a hypersubstitu- tion of Hyp(τ). We show that the operation + is associative. Indeed, we have ((σ1 + σ2) + σ3)(fi) = σ3(fi)((σ1 + σ2)(fi), . . . , (σ1 + σ2)(fi)) = = σ3(fi)(σ2(fi)(σ1(fi), . . . , σ1(fi)), . . . , σ2(fi)(σ1(fi), . . . , σ1(fi))) = = σ3(fi)(σ2(fi), . . . , σ2(fi))(σ1(fi), . . . , σ1(fi)) = = (σ2 + σ3)(fi)(σ1(fi), . . . , σ1(fi)) = (σ1 + (σ2 + σ3))(fi). Here we used properties of the superposition of terms. In a similar way we prove that σ ◦h (σ1 + σ2) = (σ ◦h σ1) + (σ ◦h σ2). Jo ur na l A lg eb ra D is cr et e M at h.8 Green’s relations on the seminearring... Indeed, we have (σ ◦h (σ1 + σ2))(fi) = σ̂[(σ1 + σ2)(fi)] = = σ̂[σ2(fi)(σ1(fi), . . . , σ1(fi))] = = σ̂[σ2(fi)](σ̂[σ1(fi)], . . . , σ̂[σ1(fi)]) = = (σ ◦h σ2)(fi)((σ ◦h σ1)(fi), . . . , (σ ◦h σ1)(fi)) ((σ ◦h σ1) + (σ ◦h σ2))(fi) if we use that hypersubstitution and superposition are permutable. This shows the left distributivity. The following counterexample shows that the right distributive identity is not satisfied. Assume that τ = (2), with a binary operation symbol f , and that σ1, σ2, σ3 are defined by σ1(f) = f(x, y), σ2(f) = f(y, x), σ3(f) = f(x, f(y, y)). Then (σ1 + σ2)(f) = f(f(x, y), f(x, y)), ((σ1 + σ2) ◦h σ3)(f) = (σ1 + σ2)ˆ[f(x, f(y, y))], = f(f(x, f(f(y, y), f(y, y))), f(x, f(f(y, y), f(y, y)))), (σ1 ◦h σ3)(f) = f(x, f(y, y)), (σ2 ◦h σ3)(f) = f(f(y, y), x), ((σ1 ◦h σ3) + (σ2 ◦h σ3))(f) = (σ2 ◦h σ3)(f)((σ1 ◦h σ3)(f), (σ1 ◦h σ3)(f)) = f(f(y, y), x)(f(x, f(y, y)), f(x, f(y, y))) = f(f(f(x, f(y, y)), f(x, f(y, y))), f(x, f(y, y))). On the set Hyp(τ) not only operations, but also relations can be defined. Let σ1, σ2 ∈ Hyp(τ). Then we define σ1 ¹R σ2 if and only if there is a hypersubstitution σ such that σ1 = σ2 ◦h σ. Since Hyp(τ) is a monoid, ¹R is reflexive and transitive, i.e. a quasiorder. Similarly, we define σ1 ¹L σ2 if and only if there is a hypersubstitution σ such that σ1 = σ ◦h σ2. The relation ¹L is also a quasiorder. Then it is easy to see (and well-known) that R =¹R ∩ ¹−1 R and L =¹L ∩ ¹−1 L are equivalence relations and are called Green’s relations R and L. The relations ¹L and ¹R induce partial order relations on the quotient sets Hyp(τ)/R and Hyp(τ)/L, respectively. Green’s relations H and D are defined by H := R ∩ L and D := R ◦ L and J is defined by σ1J σ2 :⇔ ∃σ, σ′, γ, γ′ ∈ Hyp(τ) (σ1 = σ ◦h σ2 ◦h σ′, σ2 = γ ◦h σ1 ◦h γ′). We recall the following properties of Green’s relations R and L: Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 9 Proposition 1.1. ([7]) (i) R ◦ L = L ◦ R, (ii) R is a left congruence on Hyp(τ), (iii) L is a right congruence on Hyp(τ). In [5] we considered special submonoids of Hyp(τ). The images of the hypersubstitutions from these submonoids are called full terms and strongly full terms and are inductively defined as follows: Definition 1.2. Let fi, i ∈ I, be an ni-ary operation symbol and let s : {1, . . . , ni} → {1, . . . , ni} be a permutation, then (i) fi(xs(1), . . . , xs(ni)) is a full term and (ii) if fj , j ∈ J , is an nj-ary operation symbol and if t1, . . . , tnj are full terms, then fj(t1, . . . , tnj ) is a full term. Let W f τ (X) be the set of all full terms of type τ . Strongly full terms are defined as follows: Definition 1.3. (i) For every ni-ary operation symbol fi, i ∈ I the term fi(x1, . . . , xni ) is strongly full, (ii) if t1, . . . , tni are strongly full and if fi, i ∈ I, is an ni-ary operation symbol, then fi(t1, . . . , tni ) is strongly full. We denote by W sf τ (X) the set of all strongly full terms of type τ . Definition 1.4. A hypersubstitution σ is called full if σ(fi) ∈ W f τ (Xni ) for all i ∈ I and strongly full if for all i ∈ I the images of the operation symbols fi belong to W sf τ (Xni ). By Hypf (τ) and Hypsf (τ), respectively, we denote the set of all full and the set of all strongly full hypersubstitu- tions of type τ . Then in [5] it was proved: Lemma 1.5. The sets Hypf (τ) and Hypsf (τ) form submonoids of the monoid Hyp(τ). Jo ur na l A lg eb ra D is cr et e M at h.10 Green’s relations on the seminearring... 2. Green’s Relations and the Complexity of a Hypersub- stitutions There are different ways to measure the complexity of a term. If vb(t) denotes the number of variables occurring in the term t, then vb is an example for a complexity measure of terms. The most commonly used measurement of the complexity of terms of type τ is the usual depth of a term which is defined inductively by the following steps: (i) If t = x ∈ X, then depth(t) = 0. (ii) If t = fi(t1, . . . , tni ), then depth(t) = max{depth(t1), . . . , depth(tni )} + 1. To decribe some more complexity functions we often identify a term with the tree diagram used to represent it. For instance, the term f(f(x1, x2), f(f(x1, x2), f(x1, x2))) can be described by the diagram: u u u u u u u u u u u x1 x2 x1 x2 x1 x2 f f f f f Then the depth of a term t is the length of the longest path from the root to a vertex labelled by a variable (a leaf) in the tree. Instead of depth(t) one can also speak of the maxdepth(t). The minimum depth of a term t, denoted by mindepth(t), is the length of the shortest path from the root to a leaf in the tree and is defined inductively by (i) If t is a variable,then mindepth(t) = 0. Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 11 (ii) If t = fi(t1, . . . , tni ),then mindepth(t) = min{mindepth(t1), . . . , mindepth(tni )} + 1. Using the depth and the mindepth we can define another kind of terms. Definition 2.1. Let t ∈ Wτ (Xn) be an n-ary term of type τ . Then t is called path-regular (for short a pr-term) if mindepth(t) = depth(t). Let W pr τ (Xn) be the set of all n-ary pr-terms of type τ . A hypersubstitution is called path-regular, if the terms σ(fi) are path-regular for every i ∈ I. Let Hyppr(τ) be the set of all path-regular hypersubstitutions. In [5] it was proved: Proposition 2.2. Hyppr(τ) forms a submonoid of Hyp(τ). All these complexity measures are particular cases of the following valuation of terms: Definition 2.3. Let Fτ (X) = (Wτ (X); (f̄i)i∈I) with f̄i : {t1, . . . , tni } 7→ fi(t1, . . . , tni ) be the absolutely free term algebra of type τ on a countable set X, and let Nτ = (N; (fN i )i∈I) be an algebra of type τ defined on the set of all natural numbers. Then a mapping v : X → Nτ is called a valuation of terms of type τ into Nτ if the following conditions are satisfied: (i) v(x) = a if x ∈ X and a ∈ N. (ii) v(t) ≥ v(x) for every variable x and every term t (see [6]). From the freeness of Fτ (X) we obtain a uniquely determined ho- momorphism v̂ : Fτ (X) → Nτ which extends v. For short, we denote this homomorphism also by v and will call it valuation of terms. In the case of depth(t) the operations fN i are defined by fN i (a1, . . . , ani ) = max{a1, . . . , ani } + 1 and for mindepth(t) we have fN i (a1, . . . , ani ) = min{a1, . . . , ani } + 1. Both kinds of operations are monotone with re- spect to the usual order ≤ on N. So, in many case the mapping v satisfies the following condition (OC) If aj ≤ bj for 1 ≤ j ≤ ni and fi is an ni-ary opera- tion symbol of type τ then for the corresponding operations fN i we have fN i (a1, . . . , ani ) ≤ fN i (b1, . . . , bni ) Here we denote by ≤ the usual order on the set of natural numbers. For more background on valuation of terms see [6]. This can be applied to hypersubstitutions as follows: Jo ur na l A lg eb ra D is cr et e M at h.12 Green’s relations on the seminearring... Definition 2.4. Let σ be a hypersubstitution of type τ . Then depth(σ) := min{depth(σ(fi)) \| i ∈ I} v(σ) := min{v(σ(fi)) \| i ∈ I}. For the type τ = (n) and for full terms in [4] it was proved: Proposition 2.5. Let τ = (n), n ≥ 1 and let t ∈ W f τ (X) be a full term. Then depth(σ̂[t]) = depth(σ(f))depth(t). As a consequence we obtain: Proposition 2.6. Assume that τ = (n). The mapping depth : Hypf (n) → N + defined by σ 7→ depth(σ) is a homomorphism of (Hypf (n); ◦h, σid) onto the monoid (N+; ·, 1) of all positive integers. Proof. The mapping depth is well-defined and for every natural number n ≥ 1 there is a full hypersubstitution σ with depth(σ) = n. Therefore depth is surjective. Further we have depth(σ1 ◦h σ2) = depth((σ1 ◦h σ2)(f)) = depth(σ̂1[σ2(f)]) = depth(σ1(f))depth(σ2(f)) = depth(σ1)depth(σ2) by Proposition 2.5 and depth(σid) = depth(σid(f)) = depth(f(x1, . . . , xn)) = 1. By the homomorphism theorem (N+; ·, 1) is isomorphic to the quo- tient monoid Hypf (n)/kerdepth with kerdepth = {(σ1, σ2) \| σ1, σ2 ∈ Hypf (n), depth(σ1) = depth(σ2)}. Proposition 2.5 has some consequences for Green’s relations. First of all, if σ1 = σ2 ◦h σ3, then by Proposition 2.5 depth(σ2) divides depth(σ1) and depth(σ3) divides depth(σ1). One more consequence of Proposition 2.5 is that the monoid (Hypf (n); ◦h, σid) is not finitely generated. The homomorphism depth maps any generating system of Hypf (n) onto a generating system of (N+; ·, 1). Every generating system of (N; ·, 1) con- tains the infinite set of all prime numbers. This shows that there is no finite generating system of (Hypf (n); ◦h, σid). The homomorphism depth preserves also the quasiorders ¹R and ¹L on Hyp(τ) since σ1 ¹R σ2 ⇒ ∃ρ ∈ Hyp(τ)(σ1 = σ2 ◦h ρ) ⇒ ⇒ depth(σ2)\|depth(σ1) ⇒ depth(σ2) ≤ depth(σ1) (Here ≤ denotes the usual order on N). Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 13 Corollary 2.7. Let σ1, σ2 ∈ Hypf (n) and let K ∈ {R,L,H,D,J }, then σ1Kσ2 implies depth(σ1) = depth(σ2). Proof. For K = R we have σ1Rσ2 =⇒ ∃ρ, ρ′ ∈ Hyp(τ) (σ1 = σ2 ◦h ρ ∧ σ2 = σ1 ◦h ρ′) =⇒ depth(σ2) ≤ depth(σ1) ∧ depth(σ1) ≤ depth(σ2) =⇒ depth(σ1) = depth(σ2). For the relation L we conclude in a similar way. For H we have: σ1Hσ2 =⇒ σ1(R∩L)σ2 =⇒ σ1Rσ2 ∧ σ1Lσ2 =⇒ depth(σ1) = depth(σ2). Considering D we obtain: σ1Dσ2 =⇒ σ1(R ◦ L)σ2 =⇒ ∃σ ∈ Hyp(τ)(σ1Lσ ∧ σRσ2) =⇒ depth(σ1) = depth(σ) ∧ depth(σ) = depth(σ2). Finally, for J we get σ1J σ2 ⇒ ∃σ, σ′, γ, γ′ ∈ Hyp(τ) (σ1 = σ ◦h σ2 ◦h σ′ ∧ σ2 = γ ◦h σ1 ◦h γ′) ⇒ depth(σ1)\|depth(σ2) ∧ depth(σ2)\|depth(σ1) ⇒ depth(σ1) = depth(σ2). For the depth of the hypersubstitutions ρ, ρ′, γ, γ′ which are needed in the definitions of R, L and J we have depth(ρ) = depth(ρ′) = depth(γ) = depth(γ′) = 1. Further we have Corollary 2.8. σ ∈ Hypf (n) is invertible if and only if depth(σ) = 1 and idempotent if and only if σ = σid. Proof. If σ is invertible, then there exists a hypersubstitution σ′ such that σ ◦σ′ = σ′ ◦σ = σid. Now from Proposition 2.5 we obtain depth(σ) · depth(σ′) = 1 and then depth(σ) = 1. If conversely depth(σ) = 1, then there is a permutation s on the set {1, . . . , n} such that σ(f) = f(xs(1), . . . , xs(n)), but then the hypersubstitution σ′ with σ′(f) = = f(xs−1(1), . . . , xs−1(n)) satisfies (σ ◦h σ′)(f) = f(x(s◦s−1)(1), . . . , x(s◦s−1)(n)) = f(x1, . . . , xn) = = σid(f) = f(x(s−1◦s)(1), . . . , x(s−1◦s)(n)) = (σ′ ◦ σ)(f). Jo ur na l A lg eb ra D is cr et e M at h.14 Green’s relations on the seminearring... Therefore σ is invertible. The second proposition follows from σ2 = σ ⇒ depth(σ2) = depth(σ) ⇒ depth(σ) = 1 ⇒ ⇒ ∃s ∈ Sn(σ(f) = f(xs(1), . . . , xs(n))) ⇒ s = σid. Clearly, the set of all invertible elements of (Hypf (n); ◦h, σid) is the maximal subgroup of (Hypf (n); ◦h, σid) and is isomorphic to the full symmetric group Sn of all permutations on {1, . . . , n}. Assume that σ1, σ2 are full hypersubstitutions. In [4] it was proved that the superposition of full terms is full. Therefore σ1 + σ2 is a full hypersubstitution and we have: Theorem 2.9. (Hypf (n); ◦h, +, σid) is a left-seminearring with identity and the function depth is a homomorphism onto the semiring (N+; ·, +, 1) of natural numbers with identity. Proof. We proved already that all defining identities of a left- seminearring are satisfied. By Definition 2.4 we have depth(σ1 + σ2) = depth(σ1 + σ2)(f) = depth(σ2(f)(σ1(f), . . . , σ1(f))) = depth(σ1) + depth(σ2). The rest follows from Proposition 2.5. Seminearrings were considered in [8] and [9]. Further we have Proposition 2.10. The structures (Hypsf (n); ◦h, +, σid) and (Hyppr(n); ◦h, +, σid) are left-seminearrings and (Hypsf (n); ◦h, +, σid) is a sub-left-seminearring of the left-seminearring (Hypf (n); ◦h, +, σid). Proof. (Hypsf (n); ◦h, σid) is a submonoid of (Hypf (n); ◦h, +, σid). As- sume that σ1, σ2 ∈ Hypf (n). Then σ2(f)(σ1(f), . . . , σ1(f)). If we sub- stitute for x1 the strongly full term σ1(f), etc., and finally for xn the strongly full term σ1(f), then by the inductive definition of strongly full terms the resulting term σ2(f)(σ1(f)), . . . , σ1(f)) is strongly full and σ1 + σ2 ∈ Hypsf (n). Assume now that σ1, σ2 ∈ Hyppr(n), i.e. mindepth(σ2(f)) = depth(σj(f)), j = 1, 2. Then we have also mindepth((σ1 + σ2)(f)) = mindepth(σ2(f)(σ1(f), . . . , σ1(f))) = mindepth(σ1(f)) + mindepth(σ2(f)) Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 15 and thus mindepth(σ1 + σ2) = mindepth(σ1) + mindepth(σ2) = = depth(σ1) + depth(σ2) = depth(σ1 + σ2) and then σ1 + σ2 ∈ Hyppr(n). Further we have Proposition 2.11. (Hypsf (n); ◦h, +) ∩ (Hyppr(n); ◦h, +) is the left- seminearring generated by σid. Proof. The one-element set σid is closed under the multiplication. There- fore, since the addition of hypersubstitutions is associative, every ele- ment of the left-seminearring generated by σid can be written as nσid for some natural number n. We show by induction on n that every hy- persubstitution of the form nσid belongs to Hypsf (n) and to Hyppr(n) and therefore to the intersection. This is clear for σid. Assume that nσid ∈ Hypsf (n) ∩ Hyppr(n), then (n + 1)σid(f) = nσid + σid(f) = σid(f)(nσid(f), . . . , nσid(f)) = f(nσid(f), . . . , nσid(f)) and by the def- inition of strongly full and of path-regular hypersubstitutions we have (n + 1)σid ∈ Hypsf (n) ∩ Hyppr(n). Conversely, assume that σ ∈ Hypsf (n) ∩ Hyppr(n). Since σ is full, there are terms t1, . . . , tn such that σ(f) = f(t1, . . . , tn). We give a proof by depth(σ). If depth(σ) = 1, i.e. depth(σ(f)) = 1, then σ(f) = f(x1, . . . , xn) = σid(f) and thus σ ∈ 〈σid〉. Assume that every σ with depth(σ) = n belongs to 〈σid〉 and let σ′ be a hypersubstitution with depth(σ′) = n + 1. Thus σ′(f) = f(t1, . . . , tn) where t1, . . . , tn are full and path-regular terms. Consider the hypersubstitutions σ1, . . . , σn with σi(f) = ti. Since depth(σi) = n, we have σi ∈ 〈σid〉. If there numbers ni such that σj = niσid, ni 6= nj for i 6= j, then min{mindepth(n1σid), . . . , mindepth(nnσid)} = = max{depth(n1σid), . . . , depth(nnσid)}. Therefore for every i = 1, . . . , n we have σi = nσid and therefore σ′ = (n + 1)σid ∈ 〈σid〉. This shows that 〈σid〉 = Hypsf (n) ∩ Hyppr(n). We remark that the set of all hypersubstitutions of arbitrary type τ is also closed under our addition and is called a left-seminearring since the proof of the associativity and left distributivity did not use the type Jo ur na l A lg eb ra D is cr et e M at h.16 Green’s relations on the seminearring... (n). Then a consequence of Proposition 2.10 is that the left- semin- earring (Hypf (n); ◦h, +, σid) has no finite sub-left-seminearring and that every left-seminearring of hypersubstitutions contains the infinite left- seminearring 〈σid〉 = Hypsf (n). Remark further that the mapping nσid 7→ n defines an isomorphism between 〈σid〉 and (N; +, ·, 1). This show that 〈σid〉 is a semiring with can- cellation rules for both operations, and with commutative addition. Fur- thermore 〈σid〉 has no zero-divisors. Now we want to generalize Corollary 2.7 to the valuation of terms of type τ into Nτ introduced in Definition 2.3. We mention the following Fact which was proved in [6]: Fact: Let v be a valuation of terms into Nτ which satisfies the con- dition (OC). Then for any n-ary terms t1, . . . , tm and for an arbitrary m-ary term t we have v(t(t1, . . . , tm)) ≥ v(t). Now we prove: Proposition 2.12. Let σ1, σ2 ∈ Hypf (n). If σ1Rσ2, then for every valuation which satisfies (OC) we have v(σ1) = v(σ2). Proof. If σ1Rσ2, then there exist hypersubstitutions σ, σ′ ∈ Hypf (n) such that σ1 = σ2 ◦h σ and σ2 = σ1 ◦h σ′ and therefore from σ1(f) = (σ2 ◦h σ)(f) follows σ1(f) = σ̂2[σ(f)] and σ2(f) = σ̂1[σ ′(f)]. Since τ = n and since σ ∈ Hypf (n), the term σ(f) has the form f(t1, . . . , tn) and then σ̂2[σ(f)] has the form σ2(f)(σ̂2[t1], . . . , σ̂2[tn]). Applying the Fact we see that v((σ2◦σ)(f)) ≥ v(σ2(f)) and then v(σ1) ≥ v(σ2). Using σ2 = σ1◦hσ′ we get v(σ2) ≥ v(σ1). Altogether, we have v(σ1) = v(σ2). Clearly, if σ1Hσ2 and if v satisfies (OC) we have also v(σ1) = v(σ2). Because of (σ1 + σ2)(f) = σ2(f)(σ1(f), . . . , σ1(f)) from the fact follows that v(σ1 + σ2) ≤ v(σ2), while v(σ1 ◦h σ2) ≤ v(σ1). 3. A Characterization of Green’s relation R The condition depth(σ) = depth(σ′) turns out to be necessary, but not sufficient for σ1Rσ2. Indeed, if σ1, σ2 ∈ Hypf (2) and σ1 6= σ2 then σ1Rσ2 implies σ1 = σ2 ◦h σx1x2 or σ2 = σ1 ◦h σx2x1 . For instance, for type τ = (2) the hypersubstitutions σ1 with σ1(f) = f(f(x1, x2), f(f(x1, x2), f(x2, x1))) Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 17 and σ2 with σ2(f) = f(f(f(x1, x2), f(x2, x1)), f(x1, x2)) satisfy depth(σ1) = depth(σ2), but σ1 and σ2 are not R-related. There- fore we need some more conditions. For any n-ary term t we denote by Sn,x n (t) the term arising from t if we substitute for each variable the variable x. Then we get: Proposition 3.1. Assume that σ1, σ2 ∈ Hypf (n). If σ1Rσ2, then Sn,x n (σ1(f)) = Sn,x n (σ2(f)). Proof. If σ1Rσ2 then there are hypersubstitutions σ and σ′ such that σ1 = σ2 ◦h σ and σ2 = σ1 ◦h σ′ and then σ1 = σ1 ◦h (σ ◦h σ′). By Propo- sition 2.5 we get depth(σ1) = depth(σ1)depth(σ)depth(σ′). From this we obtain depth(σ) = depth(σ′) = 1. Since σ and σ′ are full hypersubstitu- tions, we have σ(f) = f(xs(1), . . . , xs(n)), σ′(f) = f(xs′(1), . . . , xs′(n)) for permutations s,s′ on {1, . . . , n}. From this there follows Sn,x n (σ1(f)) = Sn,x n ((σ2 ◦h σ)(f)) = Sn,x n (σ̂2[σ(f)]) = Sn,x n (σ̂2[f(xs(1), . . . , xs(n))]) = Sn,x n (σ̂2[f(xs′(1), . . . , xs′(n))]) = Sn,x n (σ2(f)). Every full term t ∈ W f n (Xn) contains subterms of the form f(xsj(1), . . . , xsj(n)) for permutations sj on {1, . . . , n}. Considering the tree of the term t by P (t) we denote the sequence of all permutations on {1, . . . , n} which are needed in t, written from the left to the right, i.e., P (t) := {(s1, . . . , sm) \| f(xsi(1), . . . , xsi(n)) is a subterm of t for 1 ≤ i ≤ m and where these subterms are ordered in the tree of t from the left to the right}. Example: Consider for τ = (3) the term t = f(f(x2, x1, x3), f(f(x1, x2, x3), f(x2, x1, x3), f(x3, x2, x1)), f(x3, x1, x2)). Then P (t) = ((12), (1), (12), (13), (132)) if we write the permutations which are needed as cycles. Clearly, two terms t1, t2 ∈ W f (n)(Xn) are equal if and only if Sn,x n (t1) = Sn,x n (t2) and P (t1) = P (t2). Now we have Jo ur na l A lg eb ra D is cr et e M at h.18 Green’s relations on the seminearring... Proposition 3.2. Let σ1, σ2 ∈ Hypf (n) and assume that P (σ1(f)) = (u1, . . . , um) and P (σ2(f)) = (v1, . . . , vl). If σ1Rσ2 then m = l and u1v −1 1 = · · · = umv−1 m . Proof. Assume that σ1Rσ2. There are hypersubstitutions σ, σ′ such that σ1 = σ2 ◦h σ and σ2 = σ1 ◦h σ′ and therefore depth(σ) = depth(σ′) = 1. It follows that there are permutations s, s′ : {1, . . . , n} → {1, . . . , n} such that σ1(f) = σ̂2[f(xs(1), . . . , xs(n))] and σ2(f) = σ̂1[f(xs′(1), . . . , xs′(n))]. Then P (σ1(f)) = P (σ̂2[f(xs(1), . . . , xs(n)]) = = P (σ2(f)(xs(1), . . . , xs(n))) = (s ◦ v1, . . . , s ◦ vl). Similarly, we get P (σ2(f)) = P (σ̂1[f(xs′(1), . . . , xs′(n)]) = = P (σ1(f)(xs′(1), . . . , xs′(n))) = (s′ ◦ u1, . . . , s ′ ◦ um). By Proposition 3.1 from σ1Rσ2 there follows Sn,x n (σ1(f)) = Sn,x n (σ2(f)). Since the trees of Sn,x n (σ1(f)) and σ1(f) differ only in the labeling of the leaves, the structure of the tree of σ1(f) and of σ2(f) is equal and therefore the number of permutations s occurring in σ1(f) and σ2(f) is equal, i.e. we have m = l and then (s◦v1, . . . , s◦vm) = (s′◦u1, . . . , s ′◦um) implies s◦vj = s′ ◦uj for every 1 ≤ j ≤ m. From this equation we obtain uj ◦ v−1 j = s ◦ s′−1 for every 1 ≤ j ≤ m and this means u1 ◦ v−1 1 = · · · = um ◦ v−1 m . It turns out that both conditions, Proposition 3.1 and Proposition 3.2 together, characterize Green’s relation R. Theorem 3.3. Let σ1, σ2 ∈ Hypf (n). Then the following conditions are equivalent: (i) σ1Rσ2, (ii) Sn,x n (σ1(f)) = Sn,x n (σ2(f)) and u1 ◦ v−1 1 = · · · = um ◦ v−1 m where P (σ1(f)) = (u1, . . . , um) and P (σ2(f)) = (v1, . . . , vm). Proof. (i) ⇒ (ii) was already proved. (ii) ⇒ (i): We form s = u1 ◦ v−1 1 , s−1 = v1 ◦ u−1 1 and consider σ, σ′ ∈ Hypf (n) defined by σ(f) = f(xs(1), . . . , xs(n)) and σ′(f) = f(xs−1(1), . . . , xs−1(n)). Clearly, σ′ = σ−1. Now we prove that σ1 = σ2 ◦h σ using the Jo ur na l A lg eb ra D is cr et e M at h.Th. Changphas, K. Denecke 19 remark before Proposition 3.2 and showing that Sn,x n (σ1(f)) = Sn,x n ((σ2◦ σ)(f)) and P (σ1(f)) = P ((σ2 ◦h σ)(f)). Indeed, we have Sn,x n ((σ2 ◦ σ)(f)) = Sn,x n (σ̂2[σ(f)]) = Sn,x n (σ̂2[f(xs(1), . . . , xs(n))]) = = Sn,x n (σ2(f)(xs(1), . . . , xs(n))) = Sn,x n (σ2(f)). Further P ((σ2 ◦h σ)(f)) = P (σ2(f)(xs(1), . . . , xs(n))) = (s ◦ v1, . . . , s ◦ vm) = (u1, . . . , um) = P (σ1(f)). Since the inverse of σ exists, we get σ2 = σ1 ◦ σ−1 and altogether we have σ1Rσ2. References [1] K. Denecke, J. Koppitz, R. MarszaÃlek, Derived varieties and derived equational theories, International Journal of Algebra and Computation, Vol. 8, No. 2 (1998), 153 -169. [2] K. Denecke, S.L. Wismath, The monoid of hypersubstitutions of type τ = (2), Contributions to General Algebra, 10, Klagenfurth, (1998), 109-127. [3] K. Denecke, S. L. Wismath, Hyperidentities and Clones, Gordon and Breach Science Publishers, 2000. [4] K. Denecke, J. Koppitz, Sl. Shtrakov, The Depth of a hypersubstitution, Journal of Automata, Languages and Combinatorics, 6 (2001)3, 253-262. [5] K. Denecke, Th. Changphas, Full hypersubstitutions and Fully Solid Varieties of Semigroups, preprint 2002. [6] K. Denecke, S.L. Wismath, Valuations of Terms, preprint, 2002. [7] J. M. Howie, Fundamentals of Semigroups, Academic Press,1995. [8] G. Pilz, Nearrings, North-Holland Publ. Comp., 1977. [9] H. J. Weinert, Semirings, Seminearfields and their Semigroup-theoretical Back- ground, Semigroup Forum,Vol. 24 (1982),231-254. Contact information Th. Changphas Universität Potsdam, Institut für Mathe- matik, D-14415 Potsdam (Germany), PF 601553 E-Mail: thacha@kku.ac.th K. Denecke Universität Potsdam, Institut für Mathe- matik, D-14415 Potsdam (Germany), PF 601553 E-Mail: kdenecke@rz.uni-potsdam.de Received by the editors: 23.09.2002.

Green’s relations on the seminearring of full hypersubstitutions of type (n)

Institution

Ähnliche Einträge