On mappings of terms determined by hypersubstitutions

The extensions of hypersubstitutions are mappings on the set of all terms. In the present paper we characterize all hypersubstitutions which provide bijections on the set of all terms. The set of all such hypersubstitutions forms a monoid. On the other hand, one can modify each hypersubstitution...

Ausführliche Beschreibung

Gespeichert in:

Bibliographische Detailangaben
Datum:	2005
Hauptverfasser:	Koppitz, J., Shtrakov, S.
Format:	Artikel
Sprache:	English
Veröffentlicht:	Інститут прикладної математики і механіки НАН України 2005
Schriftenreihe:	Algebra and Discrete Mathematics
Online Zugang:	http://dspace.nbuv.gov.ua/handle/123456789/157195
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:	On mappings of terms determined by hypersubstitutions / J. Koppitz, S. Shtrakov // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 3. — С. 18–29. — Бібліогр.: 6 назв. — англ.

Institution

Digital Library of Periodicals of National Academy of Sciences of Ukraine

id	irk-123456789-157195
record_format	dspace
spelling	irk-123456789-1571952019-06-20T01:29:25Z On mappings of terms determined by hypersubstitutions Koppitz, J. Shtrakov, S. The extensions of hypersubstitutions are mappings on the set of all terms. In the present paper we characterize all hypersubstitutions which provide bijections on the set of all terms. The set of all such hypersubstitutions forms a monoid. On the other hand, one can modify each hypersubstitution to any mapping on the set of terms. For this we can consider mappings ρ from the set of all hypersubstitutions into the set of all mappings on the set of all terms. If for each hypersubstitution σ the application of ρ(σ) to any identity in a given variety V is again an identity in V , so that variety is called ρ-solid. The concept of a ρ-solid variety generalizes the concept of a solid variety. In the present paper, we determine all ρ-solid varieties of semigroups for particular mappings ρ. 2005 Article On mappings of terms determined by hypersubstitutions / J. Koppitz, S. Shtrakov // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 3. — С. 18–29. — Бібліогр.: 6 назв. — англ. 1726-3255 2000 Mathematics Subject Classification: 20M14, 20M07. http://dspace.nbuv.gov.ua/handle/123456789/157195 en Algebra and Discrete Mathematics Інститут прикладної математики і механіки НАН України
institution	Digital Library of Periodicals of National Academy of Sciences of Ukraine
collection	DSpace DC
language	English
description	The extensions of hypersubstitutions are mappings on the set of all terms. In the present paper we characterize all hypersubstitutions which provide bijections on the set of all terms. The set of all such hypersubstitutions forms a monoid. On the other hand, one can modify each hypersubstitution to any mapping on the set of terms. For this we can consider mappings ρ from the set of all hypersubstitutions into the set of all mappings on the set of all terms. If for each hypersubstitution σ the application of ρ(σ) to any identity in a given variety V is again an identity in V , so that variety is called ρ-solid. The concept of a ρ-solid variety generalizes the concept of a solid variety. In the present paper, we determine all ρ-solid varieties of semigroups for particular mappings ρ.
format	Article
author	Koppitz, J. Shtrakov, S.
spellingShingle	Koppitz, J. Shtrakov, S. On mappings of terms determined by hypersubstitutions Algebra and Discrete Mathematics
author_facet	Koppitz, J. Shtrakov, S.
author_sort	Koppitz, J.
title	On mappings of terms determined by hypersubstitutions
title_short	On mappings of terms determined by hypersubstitutions
title_full	On mappings of terms determined by hypersubstitutions
title_fullStr	On mappings of terms determined by hypersubstitutions
title_full_unstemmed	On mappings of terms determined by hypersubstitutions
title_sort	on mappings of terms determined by hypersubstitutions
publisher	Інститут прикладної математики і механіки НАН України
publishDate	2005
url	http://dspace.nbuv.gov.ua/handle/123456789/157195
citation_txt	On mappings of terms determined by hypersubstitutions / J. Koppitz, S. Shtrakov // Algebra and Discrete Mathematics. — 2005. — Vol. 4, № 3. — С. 18–29. — Бібліогр.: 6 назв. — англ.
series	Algebra and Discrete Mathematics
work_keys_str_mv	AT koppitzj onmappingsoftermsdeterminedbyhypersubstitutions AT shtrakovs onmappingsoftermsdeterminedbyhypersubstitutions
first_indexed	2025-07-14T09:35:06Z
last_indexed	2025-07-14T09:35:06Z
_version_	1837614453719302144
fulltext	Jo u rn al A lg eb ra D is cr et e M at h . Algebra and Discrete Mathematics RESEARCH ARTICLE Number 3. (2005). pp. 18 – 29 c© Journal “Algebra and Discrete Mathematics” On mappings of terms determined by hypersubstitutions Jörg Koppitz, Slavcho Shtrakov Communicated by V. M. Usenko December 14, 2004 Abstract. The extensions of hypersubstitutions are map- pings on the set of all terms. In the present paper we characterize all hypersubstitutions which provide bijections on the set of all terms. The set of all such hypersubstitutions forms a monoid. On the other hand, one can modify each hypersubstitution to any mapping on the set of terms. For this we can consider map- pings ρ from the set of all hypersubstitutions into the set of all mappings on the set of all terms. If for each hypersubstitution σ the application of ρ(σ) to any identity in a given variety V is again an identity in V , so that variety is called ρ-solid. The concept of a ρ-solid variety generalizes the concept of a solid variety. In the present paper, we determine all ρ-solid varieties of semigroups for particular mappings ρ. 1. Basic Definitions and Notations We fix a type τ = (ni)i∈I , ni > 0 for all i ∈ I, and a set of operation symbols Ω := {fi \| i ∈ I} where fi is ni-ary. Let Wτ (X) be the set of all terms of type τ over some fixed alphabet X = {x1, x2, . . .}. Terms in Wτ (Xn) with Xn = {x1, . . . , xn}, n ≥ 1, are called n-ary. For natural numbers m, n ≥ 1 we define a mapping Sn m : Wτ (Xn) × Wτ (Xm)n → Wτ (Xm) in the following way: For (t1, . . . , tn) ∈ Wτ (Xm)n we put: 2000 Mathematics Subject Classification: 20M14, 20M07. Key words and phrases: ρ-solid, hypersubstitution, bijection. Jo u rn al A lg eb ra D is cr et e M at h .J. Koppitz, S. Shtrakov 19 (i) Sn m(xi, t1, . . . , tn) := ti for 1 ≤ i ≤ n; (ii) Sn m(fi(s1, . . . , sni ), t1, . . . , tn) := fi(S n m(s1, t1, . . . , tn), . . . , Sn m(sni , t1, . . . , tn)) for i ∈ I, s1, . . . , sni ∈ Wτ (Xn) where Sn m(s1, t1, . . . , tn), . . . , Sn m(sni , t1, . . . , tn) will be assumed to be already defined. If it is obvious what m is, we write Sn. For t ∈ Wτ (X) we define the depth of t in the following inductive way: (i) depth(t) := 0 for t ∈ X; (ii) depth(t) := max{depth(t1), . . . , depth(tni )} + 1 for t = fi(t1, . . . , tni )with i ∈ I, t1, . . . , tni ∈ Wτ (X) where depth(t1), . . . , depth(tni ) will be assumed to be already defined. By c(t) we denote the length of a term t (i.e. the number of the variables occurring in t), var(t) denotes the set of all variables occurring in t and cv(t) means the number of elements in the set var(t). Instead of x1, x2, x3, . . . we write also x, y, z, . . .. The concept of a hypersubstitution was introduced in [2]. Definition 1. A mapping σ : Ω → Wτ (X) which assigns to every ni-ary operation symbol fi, i ∈ I, an ni-ary term is called a hypersubstitution of type τ (shortly hypersubstitution). The set of all hypersubstitutions of type τ will be denoted by Hyp(τ). To each hypersubstitution σ there belongs a mapping from the set of all terms of the form fi(x1, . . . , xni ) to the terms σ(fi). It follows that every hypersubstitution of type τ then induces a mapping σ̂ : Wτ (X) → Wτ (X) as follows: (i) σ̂[w] := w for w ∈ X; (ii) σ̂[fi(t1, . . . , tni )] := Sn(σ(fi), σ̂[t1], . . . , σ̂[tni ]) for i ∈ I, t1, . . . , tni ∈ Wτ (X) where σ̂[t1], . . . , σ̂[tni ] will be assumed to be already defined. By σ1 ◦h σ2 := σ̂1 ◦ σ2 is defined an associative operation on Hyp(τ) where ◦ denotes the usual composition of mappings. By ε we denote the hypersubstitution with ε(fi) = fi(x1, . . . , xni ) for i ∈ I, where ε deals as identity element. Then (Hyp(τ); ◦h, ε) forms a monoid, denoted by Hyp(τ). 2. Bijections on Wτ (X) By Bij(τ) we denote the set of all σ ∈ Hyp(τ) such that σ̂ : Wτ (X) → Wτ (X) is a bijection on Wτ (X). Such hypersubstitutions have a high importance in computer science. The product of two bijections is again a bijection. Further, for two hypersubstitutions σ1 and σ2 we have (σ1 ◦h σ2)̂ = σ̂1 ◦ σ̂2 Jo u rn al A lg eb ra D is cr et e M at h .20 On mappings of terms determined by hypersubstitutions (see [3]). So we have the following result. Proposition 1. (Bij(τ); ◦h, ε) forms a submonoid of Hyp(τ). For the characterization of Bij(τ) we need the following notations: (i) B denotes the set of all bijections on Ω preserving the arity. (ii) Let Sn be the set of all permutations of the set {1, . . . , n} for 1 ≤ n ∈ N. (iii) A := ⋃ 1≤n∈N Sn. (iv) P := {p ∈ AI \| p(i) ∈ Sni for i ∈ I}. The following theorem characterizes Bij(τ) for any type τ . Theorem 1. Let τ = (ni)i∈I , ni > 0 for all i ∈ I, be any type. For each σ ∈ Hyp(τ) the following statements are equivalent: (i) σ ∈ Bij(τ). (ii) There are h ∈ B and p ∈ P such that σ(fi) = h(fi)(xp(i)(1), . . . , xp(i)(ni)) for all i ∈ I. Proof. (ii) ⇒ (i) : We show by induction that σ̂ is injective and surjective. Injectivity: Let s, t ∈ Wτ (X) with σ̂[s] = σ̂[t]. Suppose that the depth(s) = 0. Then depth(t) = 0 and s, t are vari- ables with s = σ̂[s] = σ̂[t] = t. Suppose that from σ̂[s‘] = σ̂[t‘] there follows s‘ = t‘ for any s‘, t‘ ∈ Wτ (X) with depth(s‘) ≤ n. Let depth(s) = n + 1. Then depth(t) ≥ 1 and there are i, j ∈ I with s = fi(s1, . . . , sni ) and t = fj(t1, . . . , tnj ). Now we have σ̂[s] = Sni(h(fi)(xp(i)(1), . . . , xp(i)(ni)), σ̂[s1], . . . , σ̂[sni ]) and σ̂[t] = Snj (h(fj)(xp(j)(1), . . . , xp(j)(nj)), σ̂[t1], . . . , σ̂[tnj ]). From σ̂[s] = σ̂[t] it follows that h(fi) = h(fj) and thus fi = fj , i.e. i = j, since h is a bijection. Hence Sni(h(fi)(xp(i)(1), . . . , xp(i)(ni)), σ̂[s1], . . . , σ̂[sni ]) = Sni(h(fi)(xp(i)(1), . . . , xp(i)(ni)), σ̂[t1], . . . , σ̂[tnj ]) and, consequently, σ̂[sk] = σ̂[tk] for 1 ≤ k ≤ ni. By our hypothesis we get sk = tk for 1 ≤ k ≤ ni. Consequently, s = fi(s1, . . . , sni ) = fj(t1, . . . , tnj ) = t. Surjectivity: For w ∈ X we have σ̂[w] = w. Suppose that for any s ∈ Wτ (X) with depth(s) ≤ n there is an s̃ ∈ Wτ (X) with σ̂[s̃] = s. Let now t ∈ Wτ (X) be a term with depth(t) = n + 1. Then there is an i ∈ I with t = fi(t1, . . . , tni ) and by our hypothesis there are t̃1, . . . , t̃ni ∈ Wτ (X) such that σ̂[t̃k] = tk for 1 ≤ k ≤ ni. Further there is a j ∈ I with h(fj) = fi and ni = nj . Now we consider the term Jo u rn al A lg eb ra D is cr et e M at h .J. Koppitz, S. Shtrakov 21 t̃ := fj(t̃p(j)−1(1), . . . , t̃p(j)−1(ni)). There holds σ̂[t̃] = Sni(h(fj)(xp(j)(1), . . . , xp(j)(nj)), σ̂[t̃p(j)−1(1)], . . . , σ̂[t̃p(j)−1(ni)]) = = Sni(fi(xp(j)(1), . . . , xp(j)(ni)), tp(j)−1(1), . . . , tp(j)−1(ni)) (by hypothesis) = fi(t1, . . . , tni ) = t. (i) ⇒ (ii) : Since σ̂ is surjective for each j ∈ I there is an sj ∈ Wτ (X) with σ̂[sj ] = fj(x1, . . . , xnj ) which is minimal with respect to the depth. Obviously, the case depth(sj) = 0 is impossible. Thus there are a k ∈ I and r1, . . . , rnk ∈ Wτ (X) with sj = fk(r1, . . . , rnk ). So σ̂[sj ] = σ̂[fk(r1, . . . , rnk )] = Snk(σ(fk), σ̂[r1], . . . , σ̂[rnk ]) = fj(x1, . . . , xnj ). This is only possible if σ(fk) ∈ X or σ(fk) = fj(a1, . . . , anj ) with a1, . . . , anj ∈ {x1, . . . , xnk }, \| {a1, . . . , anj } \|= nj , and thus nk ≥ nj . But the case σ(fk) ∈ X is impossible. Otherwise there is an i ∈ {1, . . . , nk} with σ(fk) = xi and σ̂[sj ] = σ̂[ri] where depth(sj) > depth(ri), this contradicts the minimallity of sj . This shows that for all j ∈ I there are a k(j) ∈ I with nk(j) ≥ nj and a1, . . . , anj ∈ Xnk(j) with \| {a1, . . . , anj } \|= nj such that σ(fk(j)) = fj(a1, . . . , anj ). Assume that nk(j) > nj for some j ∈ I. Then there is an x ∈ Xnk(j) \ var(σ(fk(j))), i.e. x is not essential in σ(fk(j)) and thus σ̂ is not a bijection on Wτ (X) (see [1], [6]), a contradiction. Thus nk(j) = nj and σ(fk(j)) = fj(xπj(1), . . . , xπj(nj)) for some πj ∈ Snj . Assume that there are j, l ∈ I with l 6= k(j) such that fj is the first operation symbol in σ(fl). We put t := σ̂[fl(x1, . . . , xnl )]. Then t = fj(t1, . . . , tnj ) for some t1, . . . , tnj ∈ Wτ (X). Since σ̂ is surjective, there are s1, . . . , snj ∈ Wτ (X) with σ̂[si] = ti for 1 ≤ i ≤ nj . Then σ̂[fk(j)(sπ−1 j (1), . . . , sπ−1 j (nj) )] = Snj (σ(fk(j)), σ̂[s π−1 j (1)], . . . , σ̂[s π−1 j (nj) ]) = Snj (fj(xπj(1), . . . , xπj(nj)), tπ−1 j (1), . . . , tπ−1 j (nj) ) = fj(t1, . . . , tnj ). Since fk(j)(sπ−1 j (1), . . . , sπ−1 j (nj) ) 6= fl(x1, . . . , xnl ), σ̂ is no injective, a contradiction. Altogether this shows that the mapping h : Ω → Ω where h(f) is the first operation symbol in σ(f) is a bijection on Ω preserving the arity. Further, let p ∈ AI with p(i) := πi for i ∈ I. Then p ∈ P. Consequently, we have σ(fi) = h(fi)(xp(i)(1), . . . , xp(i)(ni)) for all i ∈ I. Let us give the following examples. Jo u rn al A lg eb ra D is cr et e M at h .22 On mappings of terms determined by hypersubstitutions Example 1. Let 2 ≤ n ∈ N. We consider the type τn = (n), where f denotes the n-ary operation symbol. For π ∈ Sn we define: σπ : f 7→ f(xπ(1), . . . , xπ(n)). These hypersubstitutions are precisely the bijections, i.e. Bij(τn) = {σπ \| π ∈ Sn}. In particular, if n = 2 then Bij(τ2) = {ε, σd} where σd is defined by σd : f 7→ f(x2, x1). Example 2. Let now τ = (2, 2) where f and g are the both binary op- eration symbols. Then we define the following eight hypersubstitutions σ1, . . . , σ8 by: f 7→ g 7→ σ1 : f(x1, x2) g(x1, x2) σ2 : f(x1, x2) g(x2, x1) σ3 : f(x2, x1) g(x1, x2) σ4 : f(x2, x1) g(x2, x1) σ5 : g(x1, x2) f(x1, x2) σ6 : g(x1, x2) f(x2, x1) σ7 : g(x2, x1) f(x1, x2) σ8 : g(x2, x1) f(x2, x1) These hypersubstitutions are precisely the bijections, so Bij(τ) = {σ1, . . . , σ8}. 3. ρ-solid varieties In Section 1, we mentioned that any hypersubstitution σ can be uniquely extended to a mapping σ̂ : Wτ (X) → Wτ (X) (σ̂ ∈ Wτ (X)Wτ (X)). Thus a mapping ρ : Hyp(τ) → Wτ (X)Wτ (X) is defined by setting ρ(σ) = σ̂ for all σ ∈ Hyp(τ). In [4], the concept of a solid variety was introduced. By Birkhoff, a variety V is a class of algebras of type τ satisfying a set Σ of identities, i.e. V = ModΣ. For a variety V of type τ we denote by IdV the set of all identities in V . The variety V is said to be solid iff σ̂[s] ≈ σ̂[t] ∈ IdV for all s ≈ t ∈ IdV and all σ ∈ Hyp(τ). For a submonoid M of Hyp(τ), the variety V is said to be M -solid iff σ̂[s] ≈ σ̂[t] ∈ IdV for all s ≈ t ∈ IdV and all σ ∈ M (see [3]). If M = Hyp(τ) then we have solid varieties. In this section we will study mappings ρ : Hyp(τ) → Wτ (X)Wτ (X) and generalize the concept of an M -solid variety to the concept of an M -ρ-solid variety. For convenience, we put σρ := ρ(σ) for σ ∈ Hyp(τ). Jo u rn al A lg eb ra D is cr et e M at h .J. Koppitz, S. Shtrakov 23 Definition 2. Let ρ : Hyp(τ) → Wτ (X)Wτ (X) be a mapping and V be a variety of type τ and M be a submonoid of Hyp(τ). V is called M -ρ-solid iff σρ(s) ≈ σρ(t) ∈ IdV for all s ≈ t ∈ IdV and all σ ∈ M . If M = Hyp(τ) then V is said to be ρ-solid. Example 3. Let ρ : Hyp(τ) → Wτ (X)Wτ (X) be defined by ρ(σ) = σ̂ for all σ ∈ Hyp(τ). Then the ρ-solid varieties are exactly the solid varieties, which is clear by the appropriate definitions. L. Polák has determined all solid varieties of semigroups in [5]. Besides the trivial variety, exactly the self-dual varieties in the interval between the normalization Z∨RB of the variety of all rectangular bands and the variety defined by the identities x2 ≈ x4, x2y2z ≈ x2yx2yz, xy2z2 ≈ xyz2yz2, and xyzyx ≈ xyxzxyx as well as the varieties RB of all rectangular, NB of all normal, and RegB of all regular bands are solid. In Section 2 we have checked that Bij(τ) forms a monoid. For par- ticular mappings ρ : Hyp(τ) → Wτ (X)Wτ (X) the Bij(τ)-ρ-solid varieties are of special interest, in particular for type τ = (2) and semigroup vari- eties. They realize substitutions of operations in terms which are useful in some calculational aspects of computer algebra systems. In the following we will consider such mappings ρ : Hyp(τ) → Wτ (X)Wτ (X). Definition 3. Let fa : Hyp(τ) → Wτ (X)Wτ (X) and sa : Hyp(τ) → Wτ (X)Wτ (X) be the following mappings: For σ ∈ Hyp(τ) we put (i) σfa(x) := σsa(x) := x for x ∈ X; (ii) σfa(fi(t1, . . . , tni )) := Sni(σ(fi), σ sa(t1), . . . , σ sa(tni )) and σsa(fi(t1, . . . , tni )) := fi(σ fa(t1), . . . , σ fa(tni )) for i ∈ I and t1, . . . , tni ∈ Wτ (X) where σsa(t1), . . . , σ sa(tni ), σfa(t1), . . . , σfa(tni )will be assumed to be already defined. If we consider M -ρ-solid varieties of semigroups we have the type τ = (2) and thus ρ : Hyp(2) → W(2)(X)W(2)(X) (where Hyp(2) := Hyp((2))). If one considers semigroup identities, we have the associative law and we can renounce of the operation symbol f and the brackets, i.e. we write semigroup words only as sequences of variables. Theorem 2. The trivial variety TR and the variety Z of all zero semi- groups (defined by xy ≈ zt) are the only sa-solid varieties of semigroups. Proof. Clearly, TR is sa-solid. We show that for any σ ∈ Hyp(2) and any t ∈ W(2)(X) there holds σsa(t) ≈ t ∈ IdZ. Jo u rn al A lg eb ra D is cr et e M at h .24 On mappings of terms determined by hypersubstitutions If t ∈ X then σsa(t) = t. If t /∈ X then t = f(t1, t2) for some t1, t2 ∈ W(2)(X). Thus c(t) ≥ 2 and t ≈ xy ∈ IdZ. Further, there holds σsa(t) = f(σfa(t1), σ fa(t2)) ≈ xy ∈ IdZ. Consequently, σsa(t) ≈ t ∈ IdZ. This shows that σsa(s) ≈ s ≈ t ≈ σsa(t) holds in Z for all s ≈ t ∈ IdZ and all σ ∈ Hyp(2), i.e. Z is sa-solid. Conversely, let V be an sa-solid variety of semigroups. By σx (σy) we will denote the hypersubstitution which maps the binary operation sym- bol f to the term x1 (x2). Then σsa x (f(f(x, y), z)) ≈ σsa x (f(x, f(y, z))) ∈ IdV . This provides xz ≈ xy ∈ IdV . From σsa y (f(f(x, y), z)) ≈ σsa y (f(x, f(y, z))) ∈ IdV it follows yz ≈ xz ∈ IdV . Both identities xz ≈ xy and yz ≈ xz provide yz ≈ xt, i.e. V ⊆ Z. But TR and Z are the only subvarieties of Z. Proposition 2. A variety V of semigroups is Bij(2)-sa-solid iff (i) V ⊆ Mod{x(yz) ≈ (xy)z, xyz ≈ zxy} and (ii) V ⊆ Mod{x(yz) ≈ (xy)z, xyz ≈ xzy ≈ zxy} if there is an identity s ≈ t ∈ IdV with cv(s) = c(s) = 3 and c(t) 6= 3 or cv(t) 6= 3 or var(t) 6= var(s). Proof. We have already mentioned that Bij(2) = {ε, σd}. Suppose that V is Bij(2)-sa-solid. Then σsa d (f(f(x, y), z)) ≈ σsa d (f(x, f(y, z))) ∈ IdV , so yxz ≈ xzy ∈ IdV . Let now s ≈ t ∈ IdV with cv(s) = c(s) = 3. If c(t) ≤ 2 then σsa d (t) = t. If c(t) ≥ 4 then σsa d (t) ≈ t ∈ IdV is easy to check using yxz ≈ xzy ∈ IdV . If c(t) = 3 and cv(t) = 1 then σsa d (t) ≈ t ∈ IdV is obvious. If c(t) = 3 and cv(t) = 2 then there are w1, w2 ∈ X such that t = (w1w2)w2 or t = (w2w1)w2 or t = (w2w2)w1 or t = w1(w2w2) or t = w2(w1w2) or t = w2(w2w1). Using yxz ≈ xzy ∈ IdV we get that w1w2w2 ≈ w2w1w2 ≈ w2w2w1 in V . This shows that σsa d (t) ≈ t ∈ IdV . From cv(s) = c(s) = 3 it follows s = (w1w2)w3 or s = w1(w2w3) for some w1, w2, w3 ∈ X. Without loss of generality let s = w1(w2w3), so σsa d (s) = w1w3w2. If c(t) 6= 3 or cv(t) 6= 3, from σsa d (s) ≈ σsa d (t) ∈ IdV it follows w1w3w2 ≈ t ∈ IdV . Consequently, w1w3w2 ≈ w1w2w3 ∈ IdV . If cv(t) = c(t) = 3 and var(t) 6= var(s) then there is a w ∈ var(t) \ var(s). Substituting w by w2 we get s ≈ r ∈ IdV from s ≈ t ∈ IdV where c(r) = 4. Then we get xyz ≈ zxy ∈ IdV as above. Suppose that (i) and (ii) are satisfied. Let s ≈ t ∈ IdV . Then εsa(s) ≈ εsa(t) ∈ IdV . We have to show that σsa d (s) ≈ σsa d (t) ∈ IdV and consider the following cases: Jo u rn al A lg eb ra D is cr et e M at h .J. Koppitz, S. Shtrakov 25 1) If c(s) 6= 3 or cv(s) 6= 3 and c(t) 6= 3 or cv(t) 6= 3 then we have σsa d (s) ≈ s ∈ IdV and σsa d (t) ≈ t ∈ IdV as we have shown already. This provides σsa d (s) ≈ σsa d (t) ∈ IdV . 2.1) If cv(s) = c(s) = 3 and c(t) 6= 3 or cv(t) 6= 3 or var(t) 6= var(s) then xyz ≈ xzy ≈ zxy holds in V (by (ii)) and it is easy to see that σsa d (s) ≈ s ∈ IdV and σsa d (t) ≈ t ∈ IdV , so σsa d (s) ≈ σsa d (t) ∈ IdV . 2.2) If cv(s) = c(s) = 3 and c(t) = 3 and cv(t) = 3 and var(t) = var(s) then there are w1, w2, w3 ∈ X such that s, t ∈ {r1, . . . , r12} where r1 = w2(w1w3) r2 = (w2w1)w3 r3 = w3(w2w1) r4 = (w3w2)w1 r5 = w1(w3w2) r6 = (w1w3)w2 r7 = w2(w3w1) r8 = (w2w3)w1 r9 = w3(w1w2) r10 = (w3w1)w2 r11 = w1(w2w3) r12 = (w1w2)w3. Then σsa d (r1) = r7, σsa d (r2) = r12, σsa d (r3) = r9, σsa d (r4) = r8, σsa d (r5) = r11, σsa d (r6) = r10, σsa d (r7) = r1, σsa d (r8) = r4, σsa d (r9) = r3, σsa d (r10) = r6, σsa d (r11) = r5, and σsa d (r12) = r2. This shows that σsa d (ri) ≈ σsa d (rj) ∈ IdV for 1 ≤ i, j ≤ 6 or 7 ≤ i, j ≤ 12 by xyz ≈ zxy ∈ IdV . If ri ≈ rj ∈ IdV with 1 ≤ i ≤ 6 or 7 ≤ j ≤ 12 or conversely, then xyz ≈ xzy ∈ IdV . Together with xyz ≈ zxy ∈ IdV it is easy to check that then σsa d (ri) ≈ ri ∈ IdV and σsa d (rj) ≈ rj ∈ IdV , i.e. σsa d (ri) ≈ σsa d (rj) ∈ IdV . Altogether this shows that σsa d (s) ≈ σsa d (t) ∈ IdV . 3) If cv(t) = c(t) = 3 then we get dually σsa d (s) ≈ σsa d (t) ∈ IdV . Theorem 3. TR is the only fa-solid variety of semigroups. Proof. Clearly, TR is fa-solid. Let V be an fa-solid variety of semi- groups. From σfa x (f(f(x, y), z)) ≈ σfa x (f(x, f(y, z))) ∈ IdV it follows xy ≈ x ∈ IdV . Moreover, σfa y (f(f(x, y), z)) ≈ σfa y (f(x, f(y, z))) ∈ IdV provides z ≈ yz ∈ IdV . Both identities xy ≈ x and z ≈ yz give z ≈ y, i.e. V = TR. Proposition 3. A variety V of semigroups is Bij(2)-fa-solid iff (i) V ⊆ Mod{x(yz) ≈ (xy)z, xyz ≈ zxy} and (ii) V is a variety of commutative semigroups if there is an identity s ≈ t ∈ IdV with cv(s) = c(s) = 2 and c(t) 6= 2 or cv(t) 6= 2 or var(t) 6= var(s). Proof. We have already mentioned that Bij(2) = {ε, σd}. Suppose that V is Bij(2)-fa-solid. Then σfa d (f(f(x, y), z)) ≈ σfa d (f(x, f(y, z))) ∈ IdV , so zxy ≈ yzx ∈ IdV . Let now s ≈ t ∈ IdV with cv(s) = c(s) = 2. If c(t) = 1 then σfa d (t) = t. If c(t) ≥ 3 then σfa d (t) ≈ t ∈ IdV is easy to check using zxy ≈ yzx ∈ IdV . If c(t) = 2 and cv(t) = 1 then σfa d (t) ≈ t ∈ IdV is obvious. Jo u rn al A lg eb ra D is cr et e M at h .26 On mappings of terms determined by hypersubstitutions From cv(s) = c(s) = 2 it follows s = w1w2, so σfa d (s) = w2w1. If c(t) 6= 2 or cv(t) 6= 2 from σfa d (s) ≈ σfa d (t) ∈ IdV it follows w2w1 ≈ t ∈ IdV and, consequently, w1w2 ≈ w2w1 ∈ IdV . If cv(t) = c(t) = 2 and var(t) 6= var(s) then there is a w ∈ var(t) \ var(s). Substituting w by w2 we get s ≈ r ∈ IdV from s ≈ t ∈ IdV where c(r) = 3. Then we get xy ≈ yx ∈ IdV as above. Suppose that (i) and (ii) are satisfied. Let s ≈ t ∈ IdV . Then εfa(s) ≈ εfa(t) ∈ IdV . We have to show that σfa d (s) ≈ σfa d (t) ∈ IdV and consider the following cases: 1) If c(s) 6= 2 or cv(s) 6= 2 and c(t) 6= 2 or cv(t) 6= 2 then we have σfa d (s) ≈ s ∈ IdV and σfa d (t) ≈ t ∈ IdV as we have shown already. This provides σfa d (s) ≈ σfa d (t) ∈ IdV . 2.1) If cv(s) = c(s) = 2 and c(t) 6= 2 or cv(t) 6= 2 or var(t) 6= var(s) then V is a variety of commutative semigroups (by (ii)) and it is easy to see that σfa d (s) ≈ s ∈ IdV and σfa d (t) ≈ t ∈ IdV , so σfa d (s) ≈ σfa d (t) ∈ IdV . 2.2) If cv(s) = c(s) = 2 and c(t) = cv(t) = 2 and var(t) = var(s) then there are w1, w2 ∈ X such that s = w1w2 or s = w2w1 and t = w1w2 or t = w2w1. If s = t then σfa d (s) = σfa d (t). If s 6= t then s ≈ t is the commutative law and we have σfa d (s) ≈ σfa d (t) ∈ IdV . 3) If cv(t) = c(t) = 2 then we get dually σfa d (s) ≈ σfa d (t) ∈ IdV . Definition 4. We define a mapping γn : Hyp(τ) → Wτ (X)Wτ (X) for each natural number n as follows: For σ ∈ Hyp(τ) we put (i) σγ0 := σ̂; (ii) σγn(x) := x for x ∈ X and 1 ≤ n ∈ N; (iii) σγn(fi(t1, . . . , tni )) := fi(σ γn−1(t1), . . . , σ γn−1(tni )) for 1 ≤ n ∈ N, i ∈ I, and t1, . . . , tni ∈ Wτ (X). We put Hyp(n)(τ) := {σγn \| σ ∈ Hyp(τ)} for n ∈ N. For the hypersubstitution ε ∈ Hyp(τ) (the identity element in Hyp(τ)) there holds εγn = ε̂ for all n ∈ N. This becomes clear by the following considerations: We have εγ0 = ε̂ and suppose that εγn = ε̂ for some natural number n then there holds εγn+1(x) = x = ε̂[x] and εγn+1(fi(t1, . . . , tni )) = fi(ε γn(t1), . . . , ε γn(tni )) = fi(ε̂[t1], . . . , ε̂[tni ]) = fi(t1, . . . , tni ) = ε̂[fi(t1, . . . , tni )]. Jo u rn al A lg eb ra D is cr et e M at h .J. Koppitz, S. Shtrakov 27 Proposition 4. The monoids (Hyp(n)(τ); ◦, ε̂) and Hyp(τ) are isomor- phic for each natural number n. Proof. Let n be a natural number. We define a mapping h : Hyp(τ) → Hyp(n)(τ) by h(σ) := σγn for σ ∈ Hyp(τ). We show that h is injective. For this let σ1, σ2 ∈ Hyp(τ) with σγn 1 = σγn 2 . Assume that σ1 6= σ2. Then there is an i ∈ I with σ1(fi) 6= σ2(fi) and we have σ̂1[fi(x1, . . . , xni )] 6= σ̂2[fi(x1, . . . , xni )]. Then we define: (i) t0 := fi(x1, . . . , xni ); (ii) tp+1 := fi(tp, x2, . . . , xni ) for p ∈ N. It is easy to check that σγn 1 (tn) 6= σγn 2 (tn) because of σ̂1[t0] 6= σ̂2[t0], which contradicts σγn 1 = σγn 2 . This shows that h is injective. Clearly, h is surjective. Consequently, h is a bijective mapping. It is left to show that h satisfies the homomorphic property. We will show by induction on n that h(σ1◦hσ2) = h(σ1)◦h(σ2), i.e. (σ1◦hσ2) γn = σγn 1 ◦ σγn 2 . If n = 0 then we have σγ0 1 ◦ σγ0 2 = σ̂1 ◦ σ̂2 = (σ1 ◦h σ2)̂ = (σ1 ◦h σ2) γ0 (see [3]). For n = m we suppose that σγm 1 ◦ σγm 2 = (σ1 ◦h σ2) γm . Let now n = m + 1. Obviously, we have (σ γm+1 1 ◦ σ γm+1 2 )(x) = x = (σ1 ◦h σ2) γm+1(x). Let i ∈ I and t1, . . . , tni ∈ Wτ (X). Then there holds (σ γm+1 1 ◦ σ γm+1 2 )(fi(t1, . . . , tni )) = σ γm+1 1 (fi(σ γm 2 (t1), . . . , σ γm 2 (tni ))) = fi((σ γm 1 ◦ σγm 2 )(t1), . . . , (σ γm 1 ◦ σγm 2 )(tni )) = fi((σ1 ◦h σ2) γm(t1), . . . , (σ1 ◦h σ2) γm(tni )) (by hypothesis) = (σ1 ◦h σ2) γm+1 (fi(t1, . . . , tni )). Altogether, this shows that σ γm+1 1 ◦ σ γm+1 2 = (σ1 ◦h σ2) γm+1 . By definition, a variety V of type τ is M -γ0-solid iff V is M -solid. The class of all solid varieties of semigroups was determined in [5]. We will now characterize the γn-solid varieties of semigroups for 1 ≤ n ∈ N. Here we need some else notations. For a fixed variable w ∈ X we put: F0 := {f(f(x, y), z) ≈ f(x, f(y, z))} and Fm+1 := {f(s, w) ≈ f(t, w) \| s ≈ t ∈ Fm} ∪ {f(w, s) ≈ f(w, t) \| s ≈ t ∈ Fm} for m ∈ N. Theorem 4. Let 1 ≤ n ∈ N and V be a variety of semigroups. Then V is γn-solid iff x1 . . . xn+1 ≈ y1 . . . yn+1 ∈ IdV . Proof. Suppose that V is γn-solid. Jo u rn al A lg eb ra D is cr et e M at h .28 On mappings of terms determined by hypersubstitutions Since the associative law is satisfied in V there holds Fn−1 ⊆ IdV . Since V is γn-solid the application of σγn x to the identities of Fn−1 gives again identities in V : I1 := {waxzwb ≈ waxywb \| a, b ∈ N, a + b = n − 1} ⊆ IdV . The application of σγn y to the identities of Fn−1 provides I2 := {wayzwb ≈ waxzwb \| a, b ∈ N, a + b = n − 1} ⊆ IdV . It is easy to check that one can derive x1 . . . xn+1 ≈ y1 . . . yn+1 from I1 ∪ I2. Thus x1 . . . xn+1 ≈ y1 . . . yn+1 ∈ IdV . Suppose now that x1 . . . xn+1 ≈ y1 . . . yn+1 ∈ IdV . We show that for any σ ∈ Hyp(2) and any t ∈ W(2)(X) there holds σγn(t) ≈ t ∈ IdV. If t contains at most n operation symbols then σγn(t) = t by definition of the mapping σγn . If t contains more than n operation symbols then c(t) ≥ n + 1 and t ≈ x1 . . . xn+1 ∈ IdV because of x1 . . . xn+1 ≈ y1 . . . yn+1 ∈ IdV. Since t contains more than n operation symbols, by definition of the mapping σγn , the term σγn(t) contains at least n operation symbols and thus c(σγn(t)) ≥ n + 1. Using x1 . . . xn+1 ≈ y1 . . . yn+1 ∈ IdV we get σγn(t) ≈ x1 . . . xn+1 ∈ IdV . Consequently, σγn(t) ≈ t ∈ IdV . This shows that σγn(s) ≈ s ≈ t ≈ σγn(t) holds in V for s ≈ t ∈ IdV and σ ∈ Hyp(2), i.e. V is γn-solid. Corollary 1. TR and Z are the only γ1-solid varieties of semigroups. Proof. By Theorem 4, a variety V of semigroups is γ1-solid iff x1x2 ≈ y1y2 ∈ IdV, i.e. V ⊆ Z. But TR and Z are the only subvarieties of Z. References [1] Denecke, K., Koppitz, J., Essential variables in Hypersubstitutions, Algebra Uni- versalis 46(2001), 443-454. [2] Denecke, K., Lau, D., Pöschel, R., Schweigert, D., Hyperidentities, hyperequa- tional classes, and clone congruences, Contributions to General Algebra 7, Verlag Hölder-Pichler-Tempsky, Wien 1991, 97-118. [3] Denecke, K., Wismath, S.L., Hyperidentities and clones, Gordon and Breach Sci- entific Publisher, 2000. [4] Graczýnska, E., Schweigert, D., Hypervarieties of a given type, Algebra Universalis 27(1990), 111-127. [5] Polák, L., All solid varieties of semigroups, J. of Algebra 219 (1999), 421-436. [6] Shtrakov, Sl., Denecke, K., Essential variables and separable sets in Universal Algebra, Multiple-Valued Logic in Eastern Europe, Multiple-Valued Logic 8(2002), no 2, 165-181. Jo u rn al A lg eb ra D is cr et e M at h .J. Koppitz, S. Shtrakov 29 Contact information Jörg Koppitz University of Potsdam Institute of Mathematics Postfach 601553 14415 Potsdam, Germany E-Mail: koppitz@rz.uni-potsdam.de Slavcho Shtrakov South-West-University Blagoevgrad Faculty of Mathematics and Natural Sci- ences 2700 Blagoevgrad, Bulgaria E-Mail: shtrakov@aix.swu.bg Received by the editors: 26.05.2005 and final form in 22.07.2005.

On mappings of terms determined by hypersubstitutions

Institution

Ähnliche Einträge