KYUNGPOOK Math. J. 2019; 59(4): 617-629  
The Monoid of Linear Hypersubstitutions
Thawhat Changphas∗, Bundit Pibaljommee and Klaus Denecke
Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand
e-mail : thacha@kku.ac.th, banpib@kku.ac.th and klausdenecke@hotmail.com
* Corresponding Author.
Received: August 22, 2018; Revised: December 18, 2018; Accepted: December 19, 2018; Published online: December 23, 2019.
© Kyungpook Mathematical Journal. All rights reserved.

This is an Open Access article distributed under the terms of the Creative Commons Attribution Non-Commercial License (http://creativecommons.org/licenses/by-nc/3.0/) which permits unrestricted non-commercial use, distribution, and reproduction in any medium, provided the original work is properly cited.
Abstract

A term is called linear if each variable which occurs in the term, occurs only once. A hypersubstitution is said to be linear if it maps any operation symbol to a linear term of the same arity. Linear hypersubstitutions have some importance in Theoretical Computer Science since they preserve recognizability [7]. We show that the collection of all linear hypersubstitutions forms a monoid. Linear hypersubstitutions are used to define linear hyperidentities. The set of all linear term operations of a given algebra forms with respect to certain superposition operations a function algebra. Hypersubstitutions define endomorphisms on this function algebra.

Keywords: linear term, linear hypersubstitution, linear hyperidentity.
1. Introduction

The concept of a term is one of the fundamental concepts of algebra. To define terms one needs variables and operation symbols. Let (fi)iI be an indexed set of operation symbols. To every operation symbol fi there belongs an integer ni as its arity. The type of the formal language of terms is the indexed set τ = (ni)iI of these arities. Moreover, one needs variables from an alphabet X. Let Xn := {x1, …, xn} be a finite alphabet and let X := {x1, …, xn, …} be countably infinite. Then n-ary terms of type τ are defined as follows:

Let n ≥ 1.

(i) Every variable xjXn is an n-ary term (of type τ).

(ii) If t1, …, tni are n-ary terms and if fi is an ni-ary operation symbol, then fi(t1, …, tni) is an n-ary term (of type τ).

(iii) The set Wτ (Xn) of all n-ary terms is the smallest set which contains x1, …, xn and is closed under finite application of (ii).

The set of all terms of type τ over the countably infinite alphabet X is defined by Wτ(X):=n1Wτ(Xn).

On the set Wτ (X) of all terms of type τ an algebra ℱτ (X) of type τ can be defined if we consider the operation symbols fi as ni-ary operations i : Wτ (X)niWτ (X) with (t1, …, tni) ↦ i(t1, …, tni) := fi(t1, …, tni). This is possible by (ii) of the definition of terms. Then the pair ℱ(X) := (Wτ (X); (i)iI) is an algebra of type τ which is free with respect to the class Alg(τ) of all algebras of type τ, freely generated by X in the sense that for every algebra any mapping ϕ : XA can be extended to a homomorphism with A=(A;(fiA)iI). Here fiA:AniA are the ni-ary operations defined on A which correspond to the operation symbols fi.

A term in which each variable occurs at most once, is said to be linear. For a formal definition of n-ary linear terms we replace (ii) in the definition of terms by a slightly different condition.

Definition 1.1

An n-ary linear term of type τ is defined in the following inductive way:

(i) xjXn is for any j ∈ {1, …, n} an n-ary linear term (of type τ).

(ii) If t1, …, tni are n-ary linear terms and if var(tj) ∩ var(tk) = ∅︀ for all 1 ≤ j < kni, then fi(t1 …, tni) is an n-ary linear term.

(iii) The set Wτlin(Xn) of all n-ary linear terms is the smallest set which contains x1, …, xn and is closed under finite application of (ii).

The set of all linear terms of type τ over the countably infinite alphabet X is defined by Wτlin(X):=n1Wτlin(Xn).

The set Wτlin(X) is not closed under application of the i’s since fi(t1, …, tni) needs not to be linear if t1, …, tniare linear. But, if we define to every fi a partial operation i on Wτlin(X) by

f^i(t1,,fni):={fi(t1,,fni)if var(tj)var(tk)= for all1j<kni,not defined,otherwise,

then Fτlin(X):=(Wτlin(X);(f^i)1I) is a partial algebra of type τ. The domain of i consists of all ni-tuples (t1, …, tni) satisfying the condition var(tj) ∩ var(tk) = ∅︀, 1 ≤ j < kni.

Let PAlg(τ) be the class of all partial algebras of type τ. If, , then a mapping : AB is called a homomorphism from to ℬ if for all iI the following is satisfied:

if (a1,,ani)domfiA , then (h¯(a1),,h¯(ani))domfiB, and then

h¯(fiA(a1,ani))=fiB(h¯(a1),,h¯(ani)).

(Here domfiA is the domain of the function fiA). It is easy to see that Fτlin(X) is a free algebra w.r.t. PAlg(τ), freely generated by X, i.e. that for all any mapping h : XA can be extended to a homomorphism .

The set Wτ (X) of all terms of type τ is closed under composition, i.e. if t1, …, tn are m-ary terms of type τ and if fi(s1, …, sni) is an n-ary term of type τ, then the term

fi(s1(t1,,tn),,sni(t1,,tn))

obtained by replacing the variables x1, …, xn occurring in s1, …sni by the terms t1, …, tni is a new m-ary term of type τ. This is not true for linear terms.

Pairs of linear terms are said to be linear equations and if a linear equation is satisfied in an algebra or in a variety of algebras we speak of a linear identity. Linear identities are studied in many papers, see e.g. [1, 3, 9]. Let

Linτ(X):={sts,tWτlin(X)}=Wτlin(X)×Wτlin(X)=(Wτlin(X))2

be the set of all linear equations of type τ. It is well-known that the set (Wτ (X))2 of all equations of type τ forms a fully invariant congruence relation on the term algebra ℱτ (X).

Theorem 1.2

Linτ (X) is a congruence on the partial linear term algebra Fτlin(X)=(Wτlin(X);(f^i)iI).

Proof

Clearly, Lin(τ) is reflexive, symmetric and transitive. Assume that s1t1, …, snitniLin(τ), that (s1, …, sni) ∈ dom f̂i, i.e. var(sj)∩var(sk) = ∅︀, for all j, k ∈ {1, …, ni}, jk and that (t1, …, tni) ∈ dom f̂i, i.e. var(tj)∩var(tk) = ∅︀, for all j, k ∈ {1, …, ni}, jk. Then i(s1, …, sni) = fi(s1, …, sni) and i(t1, …, tni) = fi(t1, …, tni). Then from fi(s1, …, sni) ≈ fi(t1, …, tni) ∈ Wτ (X)2 (since Wτ (X) is a congruence on ℱτ (X)) there follows i(s1, …, sni) ≈ i(t1, …, tni) ∈ Linτ (X).

Since linearity of the terms on the left-hand side and the right-hand side of a linear identity can get lost under substitution, Lin(τ) is not fully invariant.

We consider the following example. Let τ = (2) with the binary operation symbol f. Then W(2)lin(X2)={x1,x2,f(x1,x2),f(x2,x1)} and thus Lin(2)(X2) = {x1x1, x1x2, x1f(x1, x2), x1f(x2, x1), x2x1, x2x2, x2f(x1, x2), x2f(x2, x1), f(x1, x2) ≈ x1, f(x1, x2) ≈ x2, f(x1, x2) ≈ f(x1, x2), f(x1, x2) ≈ f(x2, x1), f(x2, x1) ≈ x1, f(x2, x1) ≈ x2, f(x2, x1) ≈ f(x1, x2), f(x2, x1) ≈ f(x2, x1)}.

Substituting in x1f(x1, x2) for x1 the linear term f(x2, x1) we get f(x2, x1) ≈ f(f(x2, x1), x2) ∉ Lin(2)(X2).

We recall that st is satisfied as an identity in the algebra A=(A;(fiA)iI) of type τ if , i.e. if the induced term operations are equal. In this case we write . Let V be a variety of type τ, i.e. a model class of a set ∑ of equations:

V=ModΣ={AAlg(τ)stΣ(Ast)}.

Definition 1.3

A variety V is said to be linear, if there is a set ∑ ⊆ Linτ (X) of linear equations of type τ such that V = Mod∑.

Let Idlin(V) be the set of all linear identities in V. Using the fact that IdV is a fully invariant congruence on the term algebra ℱτ (X), in a similar way as in the proof of Theorem 1.2 we show that Idlin(V) is a congruence on the partial linear term algebra Fτlin(X). This fact gives a derivation concept for linear identities, similar to the derivation concept of identities and allows us to consider and to study a linear equational logic. Not every identity of a linear variety is linear. This means that by using the usual derivation concept of Universal Algebra from linear identities also non-linear identities can be derived.

For example, M = Mod{x1(x2x3) ≈ (x1x2)x3, x1x2x3x4x1x3x2x4}, the variety of medial semigroups, is linear, x12x2x3x4x12x3x2x4 is an identity in M, but not linear.

For the basic concepts on Universal Algebra see [5] and for partial algebras see [2].

2. Linear Hypersubstitutions and Linear Hyperidentities

A mapping σ : {fi | iI} → Wτ (X) which maps every ni-ary operation symbol fi to an ni-ary term of type τ is said to be a hypersubstitution (of type τ). The extension σ̂ : Wτ (X) → Wτ (X) is defined inductively by

(i) σ̂[x] := x for any variable xX and

(ii) σ̂[fi(t1, …, tni)] = σ(fi)(σ̂[t1], …, σ̂[tni]) assumed that the results σ̂[tj], 1 ≤ jni, are already defined. Here the right-hand side means the superposition of terms.

Then a product σ1h σ2 := σ̂1σ2 can be defined and the set Hyp(τ) of all hypersubstitutions of type τ becomes a monoid. Hypersubstitutions can be applied to identities and to algebras of type τ. Let A=(A;(fiA)iI) be an algebra of type τ. Then the identity st is said to be a hyperidentity satisfied in , if σ̂[s] ≈ σ̂[t] are satisfied as identities in for all σHyp(τ). We write if st is satisfied as an identity in and if st is satisfied as a hyperidentity in . The algebra σ[A]:=(A;(σ(fi))iIA) is said to be derived from by σ. There holds

Aσ^[s]σ^[t]σ(A)st.

(This equivalence is called the ‘conjugate property’). For more information on hyperidentities and hypersubstitutions see e.g. [5, 6, 8].

Now we consider hypersubstitutions mapping the operation symbols to linear terms.

Definition 2.1

A linear hypersubstitution of type τ is a hypersubstitution

σ:{fiiI}Wτlin(X).

Let Hyplin(τ) be the set of all linear hypersubstitutions of type τ.

Example 2.2

Let τ = (2) with the binary operation symbol f. Since W(2)(X2) = {x1, x2, f(x1, x2), f(x2, x1)} is the set of all binary linear terms of type (2), Hyplin(2) consists of four hypersubstitutions which can be written as σx1, σx2, σf(x1, x2) and σf(x2, x1). If we apply the multiplication ∘h on this set, we obtain a monoid where the operation ∘h can be described by the following table:

hσf(x1, x2)σf(x2, x1)σx1σx2
σf(x1, x2)σf(x1, x2)σf(x2, x1)σx1σx2
σf(x2, x1)σf(x2, x1)σf(x1, x2)σx1σx2
σx1σx1σx2σx1σx2
σx2σx2σx1σx1σx2.

Here σf(x1, x2) is the identity element of the monoid (Hyplin(2); ∘h, σid).

In the general case it is not clear whether or not the extension σ̂ of a linear hypersubstitution maps linear terms to linear terms and then it is also not clear whether or not the linear hypersubstitutions form a monoid. The first fact is well-known (see e. g. [5]).

Lemma 2.3

For any hypersubstitution σ and any term t we have

var(t)var(σ^[t]).
Proof

We give a proof by induction on the complexity of t. If t = xiX is a variable, then

var(t)=var(xi)={xi}=var(σ^[xi]).

Assume that t = fi(t1, …, tni) and that var(tj) ⊇ var(σ̂[tj]), j = 1, …, ni. Then

var(t)=j=1nivar(tj)j=1nivar(σ^[tj])var(σ(fi)(σ^[t1],,σ^[tni]))=var(σ^[t])

by properties of the superposition of terms.

Then we obtain:

Lemma 2.4

For any linear term t = fi(t1, …, tni) and any linear hypersubstitution σ we get

var(σ^[tj])var(σ^[tk])=

for all 1 ≤ j < kni.

Proof

The previous lemma gives var(tl) ⊇ var(σ̂[tl]) for any 1 ≤ lni and thus

=var(tj)var(tk)var(σ^[tj])var(σ^[tk])=.

Lemma 2.5

The extension of a linear hypersubstitution maps linear terms to linear terms.

Proof

Let tWτlin(X) and let σHyplin(τ). If t = xi, then σ̂[xi] = xi is linear. Otherwise, i.e. if t = fi(t1, …, tni), by the previous lemma we have var(σ̂[tj]) ∩ var(σ̂[tk]) = ∅︀ for all 1 ≤ j < kni. Inductively we may assume that σ̂[t1], …, σ̂[tni] are linear. Altogether, σ̂[t] = σ(fi)(σ̂[t1], …, σ̂[tni]) is linear.

One more consequence is

Theorem 2.6

(Hyplin(τ); ∘h, σid) is a submonoid of (Hyp(τ); ∘h, σid).

Proof

If σ1, σ2Hyplin(τ), we have to show that σ1h σ2Hyplin(τ). Indeed, (σ1h σ2)(fi) = σ̂1[σ2(fi)]. Since σ2(fi) is linear and since σ1 is linear, by the previous lemma σ̂1[σ2(fi)] is linear. The identity hypersubstitution σid is linear since σid(fi) = fi(x1, … xni) is linear.

Now we will give two more examples of linear hypersubstitions.

Example 2.7

Let τ = (4, 2) be the type with a quaternary operation symbol g and a binary operation symbol f. Let σ be the hypersubstitution which maps g to f(f(x1, x3), f(x2, x4)) and f to f(x1, x2). Then σHyplin(4, 2).

Example 2.8

Let τ = (4, 2, 1) be the type with a quaternary operation symbol g, a binary operation symbol f and a unary operation symbol h and let σ be the hypersubstitution which maps g to f(f(x1, x3), h(x4)), which maps f to f(x1, x2) and h to h(x1). Obviously, σHyplin(4, 2, 1).

The second example shows that there are linear hypersubstitutions which map ni-ary operation symbols to terms, which do not use all variables from {x1, …, xni}.

As for an arbitrary mapping also for the extension of a hypersubstitution one may consider the kernel of this mapping (see e.g. [8]). In particular, by Lemma 2.4, this can be done for a linear hypersubstitution σ since its extension σ̂ maps Wτlin(X) to Wτlin(X).

Definition 2.9

Let σHyplin(τ). Then for s,tWτlin(X)

Kerσ:={(s,t)σ^[s]=σ^[t]}

is said to be the kernel of the linear hypersubstitution σ.

For σHyp(τ) the kernel Kerσ is a fully invariant congruence on the absolutely free algebra ℱτ (X) = (Wτ (X); (i)iI). For linear hypersubstitutions we get

Proposition 2.10

Let σHyplin(τ). Then Kerσ is a congruence on the partial algebra Fτlin(X)=(Wτlin(X);(f^i)iI).

Proof

Kerσ is clearly an equivalence relation on Wτlin(X). For iI let (s1, t1) ∈ Kerσ, …, (sni, tni) ∈ Kerσ and thus

σ^[s1]=σ^[t1],,σ^[sni]=σ^[tni].

Assume that i(s1, …, sni) and i(t1, …, tni) exist. Then

f^i(s1,,sni)=fi(s1,,sni) and f^i(t1,,tni)=fi(t1,,tni)

and by Lemma 2.3, var(σ̂[sj]) ∩ var(σ̂[sk]) = ∅︀ and var(σ̂[tj]) ∩ var(σ̂[tk]) = ∅︀ for all 1 ≤ j < kni. Applying the linear term σ(fi) on (*) we obtain

σ(fi)(σ^[s1],,σ^[sni])=σ(fi)(σ^[t1],,σ^[tni]).

Both sides of this equation are linear terms and by the definition of the extension and we obtain

σ^[fi(s1,,sni)]=σ^[fi(t1,,tni)].

By (**) we have

σ^[f^i(s1,,sni)]=σ^[f^i(t1,,tni)]

and then

(f^i(s1,,sni),f^i(t1,,tni))Kerσ.

We remark that Theorem 2.6 has important consequences. Let ℳ be an arbitrary submonoid of ℋyp(τ) with the universe M. A variety V of algebras of type τ is said to be M-solid if for every stIdV and every σM, σ̂[s] ≈ σ̂[t] ∈ IdV. The collection of all M-solid varieties of type τ forms a complete sublattice of the lattice of all varieties of type τ. Since the set of all linear identities of a variety V is not closed under substitution of terms, i.e. is not an equational theory, we cannot apply the general theory of M-hyperidentities and M-solid varieties. Therefore, not all of our next definitions follow the general theory.

Definition 2.11

Let be an algebra and let K be a class of algebras, both of type τ. A linear identity st is said to be a linear hyperidentity in (respectively, in K) if (respectively, σ̂[s] ≈ σ̂[t] ∈ IdK) for every σHyplin(τ). In this case we write in the first, and Klin s t in the second case.

We define an operator χlinE by

χlinE[st]={σ^[s]σ^[t]σM}.

This extends, additively, to sets of identities, so that for any set ∑ of linear identities we set

χlinE[Σ]={χlinE[st]stΣ and st(Wτlin(X))2}.

Using derived algebras we define now an operator χlinA on the set Alg(τ), first on individual algebras and then on classes K of algebras, by

χlinA[A]={σ(A)σHyplin(τ)} and χlinA[K]={χlinA[A]AK}.

The identity hypersubstitution is linear. Using this, one shows that both operators are extensive, i.e. ΣχlinE[Σ] and KχlinA[K]. Monotonicity of both operators is a consequence of their definition and idempotency follows from the fact that Hyplin(τ) forms a monoid. By definition, both operators are additive. From the conjugate property there follows:

χlinA[A]stAχlinE[st].

Altogether, as for arbitrary monoids of hypersubstitutions, also for linear hypersubstitutions, we have:

Proposition 2.12

Let τ be a fixed type. The two operators χlinE and χlinA are additive closure operators and are conjugate with respect to the relation Alg(τ)×(Wτlin(X))2 of satisfaction.

The sets of all fixed points {KχlinA[K]=K, KAlg(τ)} and {ΣχlinK[Σ],ΣWτlin(X))2} form complete sublattices of the power set lattices ℘(Alg(τ)) and P((Wτlin(X))2), respectively.

The relation ⊨ of satisfaction of an equation as linear identity of an algebra defines the Galois connections (Id, Mod) and (Mod, Id).

The relation of linear hypersatisfaction induces a new Galois connection (HlinId, HlinMod), defined on classes K and sets ∑ of linear equations as follows:

HlinIdK={st(Wτlin(X))2st is a linear hyperidentity in A for all A in K},HlinModΣ={AAlg(τ)all identities in Σ are linear hyperidentities of A}.

Sets of equations of the form HlinIdK are called linear hyperequational theories and classes of algebras of the same type having the form HlinMod∑ are called linear hyperequational classes. As a property of a Galois connection, the combinations HlinIdHlinMod and HlinModHlinId are closure operators and their fixed points form two complete sublattices of the power set lattices ℘(Wτ (X))2 and ℘(Alg(τ)). Now we may apply the general theory of conjugate pairs of additive closure operators [11], (see [8]).

Theorem 2.13

For any variety V of type τ, the following conditions are equivalent:

(i) V = HlinModHlinIdV.

(ii) χlinA[V]=V.

(iii) IdV = HlinIdV.

(iv) χlinE[IdV]=IdV.

And dually, for any equational theoryof type τ, the following conditions are equivalent:

(i’) ∑ = HlinIdHlinMod∑.

(ii’) χlinE[Σ]=Σ.

(iii’) Mod= HlinMod∑.

(iv’) χlinA[ModΣ]=ModΣ.

From the general theory of conjugate pairs of additive closure operators for KAlg(τ) and Σ(Wτlin(X))2 one obtains also the following conditions:

(i) χlinA[K]ModIdKModIdK=HlinModHlinIdKχlinA[ModIdK]=ModIdK.

(ii) χlinE[Σ]IdModΣIdModΣ=HlinIdHlinModΣχlinE[IdModΣ]=IdModΣ.

The second proposition can be used if a variety V = Mod∑ is defined by a linear equational basis ∑. If we want to check, whether IdV is a fixed point under the operator χlinE, it is enough to apply all linear hypersubstitutions to the equational basis Σ:χlinE[IdV]=IdVχlinE[Σ]IdV if V = Mod∑.

For any subset of equations and for any monoid ℳ of hypersubstitutions we defined a variety V to be M-solid, if V is a fixed point under the corresponding operator χMA. Because of property (ii) we may define

Definition 2.14

A variety V of type τ is said to be linear-solid if it is linear and if the defining linear identities are linear hyperidentities.

Not every identity in a linear-solid variety V must be a linear hyperidentity. We consider the following example:

Example 2.15

Let τ = (2) and let M = Mod{x1(x2x3) ≈ (x1x2)x3, x1x2x3x4x1x3x2x4} be the variety of medial semigroups. If we apply the four linear hypersubstitutions σid, σx1, σx2, σf(x2, x1) to each of the both defining identities of variety M, we get identities satisfied in M. Therefore, M is linear-solid, but the equation x12x2x3x4x12x3x2x4 is an identity in M, but not linear, therefore it cannot be a linear hyperidentity since ℋyp(τ) as a monoid contains the identity hypersubstitution and thus each linear hyperidentity is a linear identity.

3. The Monoid of Linear Hypersubstitutions of Type τnI

In this section we consider monoids of linear hypersubstitutions when fi is n-ary, n ≥ 2, for every iI, i.e. if the type contains |I| operation symbols of the same arity n, n ≥ 2. Such types will be denoted by τnI, n ≥ 2. We recall that projection hypersubstitutions map each operation symbol to a variable.

To determine all linear hypersubstitutions of this type, we describe the form of n-ary terms. We denote the number of occurences of operation symbols in a term t by op(t), i.e. op(t) is defined inductively by

(i) op(t) = 0 if t = xiXn is a variable and

(ii) op(fi(t1,,tni))=j=1niop(tj)+1 if t = fi(t1, …, tni) is a composed n-ary term.

Proposition 3.1

Let t be an n-ary linear term of type τnI, n ≥ 2. Then op(t) ≤ 1.

Proof

If t = xiXn, then op(t) = 0. Let t = fi(t1, …, tn) be an n-ary linear term. If there were a number k, 1 ≤ kni with op(tk) = 1, then |var(tk)| ≥ 2 since the arity of all operation symbols in tk is greater than 1 and tk is linear. Assume that xmxlvar(tk). These variables cannot occur in another subterm of t. But in t there occur n − 1 pairwise different variables which are different from xm and xl. This contradiction shows that op(tk) = 0 for all 1 ≤ kni and thus op(t) = 1.

This observation allows us to describe the form of all n-ary linear terms and we obtain

WτnIlin(Xn)={fi(xs(1),,xs(n))iI and s is a permutation on{1,,n}}.

Then it is also clear that there are precisely |I|n! + n- many n-ary linear terms.

Since every linear hypersubstitution maps the operation symbol fi to an n-ary term we have a full description of Hyplin(τnI). Any linear hypersubstitution maps the operation symbol fi to a variable xjXn or to a term of the form fj(xs(1), …, xs(n)) where s is a permutation on {1, …, sn}.

For the product of two linear hypersubstitutions σ1 and σ2 there are precisely the following three possibilities:

1. σ2(fi) = xkXn: Then σ1hσ2=σ^1[σ2(fi)]=σ^1[xk]=xk=σxk(fi).

2. σ2(fi) = fj(xs(1), …, xs(n)) and σ1(fj) = xk. Then (σ1h σ2)(fi) = σ̂1[σ2(fi)] = σ̂1[fj(xs(1), …, xs(n))] = σ1(fj)(xs(1), …, xs(n)) = xs(k) = σxs(k) (fi).

3. σ2(fi) = fj(xs(1), …, xs(n)) and σ1(fj) = fk(xs′(1), …, xs′(n)). Then (σ1hσ2)(fi) = σ̂1[σ2(fi)] = σ̂1[fj(xs(1), …, xs(n))] = σ1(fj)(xs(1), …, xs(n)) = fk(xs′(1), …, xs′(n))(xs(1), …, xs(n)) = fk(x(ss′)(1), …, x(ss′)(n)).

4. Interpretation of Linear Hypersubstitutions on Single Algebras

Term operations induced by linear terms are defined in the usual way. Let A=(A;(fiA)iI) be an algebra of type τ and let Wτlin(X) be the set of all linear terms of type τ. Then the set (Wτlin(X))A of all linear term operations of is defined as follows:

(i) xiA:=ein,A,

(ii) if fi(t1,,tni)Wτlin(X) and assumed that t1A,,tniA are defined, then (fi(t1,,tni))A=fiA(t1A,,tniA).

Here the right-hand side is the superposition of fiA and t1A,,tniA.

Let be an algebra of type τ and let Wτ (X) be the set of all terms of type τ. Then the set of all term operations induced by terms of type τ is closed under some superposition operations. These operations can be defined on the set

Let O(A):=n1On(A) be the set of all operations on A. Here On(A) is the set of all n-ary operations defined on A. Then (Wτlin(X))AO(A). The set O(A) is closed under some superposition operations which were introduced by A. I. Mal’cev (see [10]). Here we will use Mal’cev’s original notation in spite of the fact that the letter τ was already used for the type of a language or an algebra.

Let fOn(A) and gOm(A). Then

(f*g)(x1,,xm+n1):=f(g(x1,,xlin),xm+1,,xm+n1),(τf)(x1,,xn):=f(x2,x1,x3,,xn),(ζf)(x1,,xn):=f(x2,x3,,xn,x1),(Δf)(x1,,xn1):=f(x1,x1,,xn1),(f)(x1,x2,,xn+1):=f(x2,,xn+1),if fOn(A)with n>1 and(τf)(x1)=(ζf)(x1)=(Δf)(x1)=(f)(x1)=f(x1)

if f is a unary function.

The algebra ( ; *, ζ, τ,Δ,∇, e12,A) is said to be the clone of term operations of the algebra .

Now we ask for the algebraic structure of ((Wτlin(X))A. The answer was given by Couceiro and Lehtonen in [4].

Theorem 4.1.([4])

Letbe an algebra of type τ and let (Wτlin(X))A be the set of all linear term operations induced on, i.e. term operations induced by linear terms on. Then (Wτlin(X))A is closed under the operations *, ζ, τ andand contains all projections.

Couceiro and Lehtonen proved in [4] also that the subalgebra (Wτlin(X))A; ζ, τ, ∇, *) of ; ζ, τ,∇, *) is generated by the set {fiAiI}JA, where JA is the set of all projections.

Theorem 4.2

Letbe any algebra of type τ. If σHyplin(τ) satisfies. Then

Φ:(Wτlin(X))A(Wτlin(X))AdefinedbytA(σ^[t])A

is an endomorphism of ((Wτlin(X))A; *, ζ, τ,∇).

Proof

1. Φ is well-defined: assume that t1A=t2A, t1, t2(Wτlin(X))A There follows t1t2IdA(Wτlin(X))2 and then

σ^[t1]σ^[t2]σ^[IdA(Wτlin(X))2]=σ^[IdlinA].

This means .

2. Now we show the compatibility of Φ with the operations ζ and τ. Let tA(Wτlin(X))A, then and

Φ(ζ(tA))=(σ^[t(x2,x3,,xn,x1)])A=(σ^[t](x2,x3,,xn,x1))A.

On the other hand we have Φ(tA)=(σ^[t])A and ζ(Φ(tA))=(σ^[t](x2,x3,,xn,x1))A.

This shows . In the same way we obtain .

3. and

Φ((tA))=(σ^[t(x2,x3,,xn+1)])A=(σ^[t](x2,x3,,xn+1))A=(Φ(tA)).

4. For the binary operation * we get

Φ(tA*sA)=Φ(t(s,xm+1,,xm+n1)A))=(σ^[t(s,xm+1,,xm+n1)])A))=(σ^[t](σ^[s],xm+1,,xm+n1))A=(σ^[t])A*(σ^[s])A=Φ(tA)*Φ(sA).
References
  1. MN. Bleicher, H. Schneider, and RL. Wilson. Permanence of identities on algebras. Algebra Universalis., 3(1973), 72-93.
    CrossRef
  2. P. Burmeister. A model theoretic oriented approach to partial algebras. Introduction to theory and application of partial algebras Part I, Mathematical Research, 32, Akademie-Verlag, Berlin, 1986.
  3. I. Chajda, G. Czédli, and R. Halaš. Tolerances as images of congruences in varieties defined by linear identities. Algebra Universalis., 69(2013), 167-169.
    CrossRef
  4. M. Couceiro, and E. Lehtonen. Galois theory for sets of operations closed under permutation, cylindrification and composition. Algebra Universalis., 67(2012), 273-297.
    CrossRef
  5. K. Denecke, and SL. Wismath. Hyperidentities and clones, , Gordon and Breach Science Publishers, Amsterdam, 2000.
  6. SL. Wismath. The monoid of hypersubstitutions of type (n). Southeast Asian Bull Math., 24(1)(2000), 115-128.
    CrossRef
  7. F. Gécseg, and M. Steinby. Tree automata, , Akadémiai Kiadó, Budapest, 1984.
  8. J. Koppitz, and K. Denecke. M-solid Varieties of algebras. Advances in Mathematics, 10, Springer, New York, 2006.
  9. A. Pilitowska. Linear identities in graph algebras. Comment Math Univ Carolin., 50(2009), 11-24.
  10. AI. Mal’cev. Iterative Algebras and Post’s Varieties. Algebra Logic., 5(2)(1966), 5-24.
  11. Reichel. M. Bihomomorphisms and hyperidentities, Dissertation, Universität Potsdam, 1994.


This Article

Social Network Service

e-submission

Archives

Indexed/Covered by