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 (f_{i})_{i}_{∈}_{I} be an indexed set of operation symbols. To every operation symbol f_{i} there belongs an integer n_{i} as its arity. The type of the formal language of terms is the indexed set τ = (n_{i})_{i}_{∈}_{I} of these arities. Moreover, one needs variables from an alphabet X. Let X_{n} := {x_{1}, …, x_{n}} be a finite alphabet and let X := {x_{1}, …, x_{n}, …} be countably infinite. Then n-ary terms of type τ are defined as follows:
Let n ≥ 1.
(i) Every variable x_{j} ∈ X_{n} is an n-ary term (of type τ).
(ii) If t_{1}, …, t_{n}_{i} are n-ary terms and if f_{i} is an n_{i}-ary operation symbol, then f_{i}(t_{1}, …, t_{n}_{i}) is an n-ary term (of type τ).
(iii) The set W_{τ} (X_{n}) of all n-ary terms is the smallest set which contains x_{1}, …, x_{n} 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}_{\tau}(X):={\displaystyle \underset{n\ge 1}{\cup}{W}_{\tau}({X}_{n})}$.
On the set W_{τ} (X) of all terms of type τ an algebra ℱ_{τ} (X) of type τ can be defined if we consider the operation symbols f_{i} as n_{i}-ary operations f̄_{i} : W_{τ} (X)^{ni} → W_{τ} (X) with (t_{1}, …, t_{n}_{i}) ↦ f̄_{i}(t_{1}, …, t_{n}_{i}) := f_{i}(t_{1}, …, t_{n}_{i}). This is possible by (ii) of the definition of terms. Then the pair ℱ(X) := (W_{τ} (X); (f̄_{i})_{i}_{∈}_{I}) 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 ϕ : X → A can be extended to a homomorphism with $\mathcal{A}=(A;{({f}_{i}^{\mathcal{A}})}_{i\in I})$. Here ${f}_{i}^{\mathcal{A}}:{A}^{{n}_{i}}\to A$ are the n_{i}-ary operations defined on A which correspond to the operation symbols f_{i}.
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) x_{j} ∈ X_{n} is for any j ∈ {1, …, n} an n-ary linear term (of type τ).
(ii) If t_{1}, …, t_{n}_{i} are n-ary linear terms and if var(t_{j}) ∩ var(t_{k}) = ∅︀ for all 1 ≤ j < k ≤ n_{i}, then f_{i}(t_{1} …, t_{n}_{i}) is an n-ary linear term.
(iii) The set ${W}_{\tau}^{lin}({X}_{n})$ of all n-ary linear terms is the smallest set which contains x_{1}, …, x_{n} 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}_{\tau}^{lin}(X):={\displaystyle \underset{n\ge 1}{\cup}{W}_{\tau}^{lin}({X}_{n})}$.
The set ${W}_{\tau}^{lin}(X)$ is not closed under application of the f̄_{i}’s since f_{i}(t_{1}, …, t_{n}_{i}) needs not to be linear if t_{1}, …, t_{n}_{i}are linear. But, if we define to every f_{i} a partial operation f̂_{i} on ${W}_{\tau}^{lin}(X)$ by
then ${\mathcal{F}}_{\tau}^{lin}(X):=({W}_{\tau}^{lin}(X);{({\widehat{f}}_{i})}_{1\in I})$ is a partial algebra of type τ. The domain of f̂_{i} consists of all n_{i}-tuples (t_{1}, …, t_{n}_{i}) satisfying the condition var(t_{j}) ∩ var(t_{k}) = ∅︀, 1 ≤ j < k ≤ n_{i}.
Let PAlg(τ) be the class of all partial algebras of type τ. If, , then a mapping h̄ : A → B is called a homomorphism from to ℬ if for all i ∈ I the following is satisfied:
if $({a}_{1},\dots ,{a}_{{n}_{i}})\in dom\text{\hspace{0.17em}}{f}_{i}^{\mathcal{A}}$ , then $(\overline{h}({a}_{1}),\dots ,\overline{h}({a}_{{n}_{i}}))\in dom{f}_{i}^{\mathcal{B}}$, and then
(Here $dom{f}_{i}^{\mathcal{A}}$ is the domain of the function ${f}_{i}^{\mathcal{A}}$). It is easy to see that ${\mathcal{F}}_{\tau}^{lin}(X)$ is a free algebra w.r.t. PAlg(τ), freely generated by X, i.e. that for all any mapping h : X → A can be extended to a homomorphism h̄.
The set W_{τ} (X) of all terms of type τ is closed under composition, i.e. if t_{1}, …, t_{n} are m-ary terms of type τ and if f_{i}(s_{1}, …, s_{n}_{i}) is an n-ary term of type τ, then the term
obtained by replacing the variables x_{1}, …, x_{n} occurring in s_{1}, …s_{n}_{i} by the terms t_{1}, …, t_{n}_{i} 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
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 ${\mathcal{F}}_{\tau}^{lin}(X)=({W}_{\tau}^{lin}(X);{({\widehat{f}}_{i})}_{i\in I})$.
Proof
Clearly, Lin(τ) is reflexive, symmetric and transitive. Assume that s_{1} ≈ t_{1}, …, s_{n}_{i} ≈ t_{n}_{i} ∈ Lin(τ), that (s_{1}, …, s_{n}_{i}) ∈ dom f̂_{i}, i.e. var(s_{j})∩var(s_{k}) = ∅︀, for all j, k ∈ {1, …, n_{i}}, j ≠ k and that (t_{1}, …, t_{n}_{i}) ∈ dom f̂_{i}, i.e. var(t_{j})∩var(t_{k}) = ∅︀, for all j, k ∈ {1, …, n_{i}}, j ≠ k. Then f̂_{i}(s_{1}, …, s_{n}_{i}) = f_{i}(s_{1}, …, s_{n}_{i}) and f̂_{i}(t_{1}, …, t_{n}_{i}) = f_{i}(t_{1}, …, t_{n}_{i}). Then from f_{i}(s_{1}, …, s_{n}_{i}) ≈ f_{i}(t_{1}, …, t_{n}_{i}) ∈ W_{τ} (X)^{2} (since W_{τ} (X) is a congruence on ℱ_{τ} (X)) there follows f̂_{i}(s_{1}, …, s_{n}_{i}) ≈ f̂_{i}(t_{1}, …, t_{n}_{i}) ∈ 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}({X}_{2})=\{{x}_{1},{x}_{2},f({x}_{1},{x}_{2}),f({x}_{2},{x}_{1})\}$ and thus Lin_{(2)}(X_{2}) = {x_{1} ≈ x_{1}, x_{1} ≈ x_{2}, x_{1} ≈ f(x_{1}, x_{2}), x_{1} ≈ f(x_{2}, x_{1}), x_{2} ≈ x_{1}, x_{2} ≈ x_{2}, x_{2} ≈ f(x_{1}, x_{2}), x_{2} ≈ f(x_{2}, x_{1}), f(x_{1}, x_{2}) ≈ x_{1}, f(x_{1}, x_{2}) ≈ x_{2}, f(x_{1}, x_{2}) ≈ f(x_{1}, x_{2}), f(x_{1}, x_{2}) ≈ f(x_{2}, x_{1}), f(x_{2}, x_{1}) ≈ x_{1}, f(x_{2}, x_{1}) ≈ x_{2}, f(x_{2}, x_{1}) ≈ f(x_{1}, x_{2}), f(x_{2}, x_{1}) ≈ f(x_{2}, x_{1})}.
Substituting in x_{1} ≈ f(x_{1}, x_{2}) for x_{1} the linear term f(x_{2}, x_{1}) we get f(x_{2}, x_{1}) ≈ f(f(x_{2}, x_{1}), x_{2}) ∉ Lin_{(2)}(X_{2}).
We recall that s ≈ t is satisfied as an identity in the algebra $\mathcal{A}=(A;{({f}_{i}^{\mathcal{A}})}_{i\in I})$ 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:
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 Id^{lin}(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 Id^{lin}(V) is a congruence on the partial linear term algebra ${\mathcal{F}}_{\tau}^{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{x_{1}(x_{2}x_{3}) ≈ (x_{1}x_{2})x_{3}, x_{1}x_{2}x_{3}x_{4} ≈ x_{1}x_{3}x_{2}x_{4}}, the variety of medial semigroups, is linear, ${x}_{1}^{2}{x}_{2}{x}_{3}{x}_{4}\approx {x}_{1}^{2}{x}_{3}{x}_{2}{x}_{4}$ 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 σ : {f_{i} | i ∈ I} → W_{τ} (X) which maps every n_{i}-ary operation symbol f_{i} to an n_{i}-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 x ∈ X and
(ii) σ̂[f_{i}(t_{1}, …, t_{n}_{i})] = σ(f_{i})(σ̂[t_{1}], …, σ̂[t_{n}_{i}]) assumed that the results σ̂[t_{j}], 1 ≤ j ≤ n_{i}, are already defined. Here the right-hand side means the superposition of terms.
Then a product σ_{1} ∘_{h} σ_{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 $\mathcal{A}=(A;{({f}_{i}^{\mathcal{A}})}_{i\in I})$ be an algebra of type τ. Then the identity s ≈ t is said to be a hyperidentity satisfied in , if σ̂[s] ≈ σ̂[t] are satisfied as identities in for all σ ∈ Hyp(τ). We write if s ≈ t is satisfied as an identity in and if s ≈ t is satisfied as a hyperidentity in . The algebra $\sigma [\mathcal{A}]:=(A;{(\sigma ({f}_{i}))}_{i\in I}^{\mathcal{A}})$ is said to be derived from by σ. There holds
Let Hyp^{lin}(τ) be the set of all linear hypersubstitutions of type τ.
Example 2.2
Let τ = (2) with the binary operation symbol f. Since W_{(2)}(X_{2}) = {x_{1}, x_{2}, f(x_{1}, x_{2}), f(x_{2}, x_{1})} is the set of all binary linear terms of type (2), Hyp^{lin}(2) consists of four hypersubstitutions which can be written as σ_{x}_{1}, σ_{x}_{2}, σ_{f}_{(}_{x}_{1, }_{x}_{2)} and σ_{f}_{(}_{x}_{2, }_{x}_{1)}. 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}_{(}_{x}_{1, }_{x}_{2)}
σ_{f}_{(}_{x}_{2, }_{x}_{1)}
σ_{x}_{1}
σ_{x}_{2}
σ_{f}_{(}_{x}_{1, }_{x}_{2)}
σ_{f}_{(}_{x}_{1, }_{x}_{2)}
σ_{f}_{(}_{x}_{2, }_{x}_{1)}
σ_{x}_{1}
σ_{x}_{2}
σ_{f}_{(}_{x}_{2, }_{x}_{1)}
σ_{f}_{(}_{x}_{2, }_{x}_{1)}
σ_{f}_{(}_{x}_{1, }_{x}_{2)}
σ_{x}_{1}
σ_{x}_{2}
σ_{x}_{1}
σ_{x}_{1}
σ_{x}_{2}
σ_{x}_{1}
σ_{x}_{2}
σ_{x}_{2}
σ_{x}_{2}
σ_{x}_{1}
σ_{x}_{1}
σ_{x}_{2}.
Here σ_{f}_{(}_{x}_{1, }_{x}_{2)} is the identity element of the monoid (Hyp^{lin}(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)\supseteq var(\widehat{\sigma}[t]).$$
Proof
We give a proof by induction on the complexity of t. If t = x_{i} ∈ X is a variable, then
The extension of a linear hypersubstitution maps linear terms to linear terms.
Proof
Let $t\in {W}_{\tau}^{lin}(X)$ and let σ ∈ Hyp^{lin}(τ). If t = x_{i}, then σ̂[x_{i}] = x_{i} is linear. Otherwise, i.e. if t = f_{i}(t_{1}, …, t_{n}_{i}), by the previous lemma we have var(σ̂[t_{j}]) ∩ var(σ̂[t_{k}]) = ∅︀ for all 1 ≤ j < k ≤ n_{i}. Inductively we may assume that σ̂[t_{1}], …, σ̂[t_{n}_{i}] are linear. Altogether, σ̂[t] = σ(f_{i})(σ̂[t_{1}], …, σ̂[t_{n}_{i}]) is linear.
One more consequence is
Theorem 2.6
(Hyp^{lin}(τ); ∘_{h}, σ_{id}) is a submonoid of (Hyp(τ); ∘_{h}, σ_{id}).
Proof
If σ_{1}, σ_{2} ∈ Hyp^{lin}(τ), we have to show that σ_{1} ∘_{h} σ_{2} ∈ Hyp^{lin}(τ). Indeed, (σ_{1} ∘_{h} σ_{2})(f_{i}) = σ̂_{1}[σ_{2}(f_{i})]. Since σ_{2}(f_{i}) is linear and since σ_{1} is linear, by the previous lemma σ̂_{1}[σ_{2}(f_{i})] is linear. The identity hypersubstitution σ_{id} is linear since σ_{id}(f_{i}) = f_{i}(x_{1}, … x_{n}_{i}) 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(x_{1}, x_{3}), f(x_{2}, x_{4})) and f to f(x_{1}, x_{2}). Then σ ∈ Hyp^{lin}(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(x_{1}, x_{3}), h(x_{4})), which maps f to f(x_{1}, x_{2}) and h to h(x_{1}). Obviously, σ ∈ Hyp^{lin}(4, 2, 1).
The second example shows that there are linear hypersubstitutions which map n_{i}-ary operation symbols to terms, which do not use all variables from {x_{1}, …, x_{n}_{i}}.
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}_{\tau}^{lin}(X)$ to ${W}_{\tau}^{lin}(X)$.
Definition 2.9
Let σ ∈ Hyp^{lin}(τ). Then for s,$t\in {W}_{\tau}^{lin}(X)$
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); (f̄_{i})_{i}_{∈}_{I}). For linear hypersubstitutions we get
Proposition 2.10
Let σ ∈ Hyp^{lin}(τ). Then Kerσ is a congruence on the partial algebra ${\mathcal{F}}_{\tau}^{lin}(X)=({W}_{\tau}^{lin}(X);{({\widehat{f}}_{i})}_{i\in I})$.
Proof
Kerσ is clearly an equivalence relation on ${W}_{\tau}^{lin}(X)$. For i ∈ I let (s_{1}, t_{1}) ∈ Kerσ, …, (s_{n}_{i}, t_{n}_{i}) ∈ Kerσ and thus
and by Lemma 2.3, var(σ̂[s_{j}]) ∩ var(σ̂[s_{k}]) = ∅︀ and var(σ̂[t_{j}]) ∩ var(σ̂[t_{k}]) = ∅︀ for all 1 ≤ j < k ≤ n_{i}. Applying the linear term σ(f_{i}) on (*) we obtain
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 s ≈ t ∈ IdV 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 s ≈ t is said to be a linear hyperidentity in (respectively, in K) if (respectively, σ̂[s] ≈ σ̂[t] ∈ IdK) for every σ ∈ Hyp^{lin}(τ). In this case we write in the first, and K ⊨_{lin} s ≈ t in the second case.
Using derived algebras we define now an operator ${\chi}_{lin}^{A}$ on the set Alg(τ), first on individual algebras and then on classes K of algebras, by
The identity hypersubstitution is linear. Using this, one shows that both operators are extensive, i.e. $\mathrm{\Sigma}\subseteq {\chi}_{lin}^{E}[\mathrm{\Sigma}]$ and $K\subseteq {\chi}_{lin}^{A}[K]$. Monotonicity of both operators is a consequence of their definition and idempotency follows from the fact that Hyp^{lin}(τ) forms a monoid. By definition, both operators are additive. From the conjugate property there follows:
Altogether, as for arbitrary monoids of hypersubstitutions, also for linear hypersubstitutions, we have:
Proposition 2.12
Let τ be a fixed type. The two operators ${\chi}_{lin}^{E}$ and ${\chi}_{lin}^{A}$ are additive closure operators and are conjugate with respect to the relation $\models \subseteq Alg(\tau )\times {({W}_{\tau}^{lin}(X))}^{2}$ of satisfaction.
The sets of all fixed points {$K\mid {\chi}_{lin}^{A}[K]=K$, K ⊆ Alg(τ)} and {$\mathrm{\Sigma}\mid {\chi}_{lin}^{K}[\mathrm{\Sigma}],\mathrm{\Sigma}\subseteq {W}_{\tau}^{lin}{(X))}^{2}$} form complete sublattices of the power set lattices ℘(Alg(τ)) and $\mathcal{P}({({W}_{\tau}^{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 (H_{lin}Id, H_{lin}Mod), defined on classes K and sets ∑ of linear equations as follows:
Sets of equations of the form H_{lin}IdK are called linear hyperequational theories and classes of algebras of the same type having the form H_{lin}Mod∑ are called linear hyperequational classes. As a property of a Galois connection, the combinations H_{lin}IdH_{lin}Mod and H_{lin}ModH_{lin}Id 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 = H_{lin}ModH_{lin}IdV.
(ii) ${\chi}_{lin}^{A}[V]=V$.
(iii) IdV = H_{lin}IdV.
(iv) ${\chi}_{lin}^{E}[IdV]=IdV$.
And dually, for any equational theory ∑ of type τ, the following conditions are equivalent:
From the general theory of conjugate pairs of additive closure operators for K ⊆ Alg(τ) and $\mathrm{\Sigma}\subseteq {({W}_{\tau}^{lin}(X))}^{2}$ one obtains also the following conditions:
(ii) ${\chi}_{lin}^{E}[\mathrm{\Sigma}]\subseteq IdMod\mathrm{\Sigma}\iff IdMod\mathrm{\Sigma}={H}_{lin}Id{H}_{lin}Mod\mathrm{\Sigma}\iff {\chi}_{lin}^{E}[IdMod\mathrm{\Sigma}]=IdMod\mathrm{\Sigma}$.
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 ${\chi}_{lin}^{E}$, it is enough to apply all linear hypersubstitutions to the equational basis $\mathrm{\Sigma}:{\chi}_{lin}^{E}[IdV]=IdV\iff {\chi}_{lin}^{E}[\mathrm{\Sigma}]\subseteq 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 ${\chi}_{M}^{A}$. 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{x_{1}(x_{2}x_{3}) ≈ (x_{1}x_{2})x_{3}, x_{1}x_{2}x_{3}x_{4} ≈ x_{1}x_{3}x_{2}x_{4}} be the variety of medial semigroups. If we apply the four linear hypersubstitutions σ_{id}, σ_{x}_{1}, σ_{x}_{2}, σ_{f}_{(}_{x}_{2, }_{x}_{1)} to each of the both defining identities of variety M, we get identities satisfied in M. Therefore, M is linear-solid, but the equation ${x}_{1}^{2}{x}_{2}{x}_{3}{x}_{4}\approx {x}_{1}^{2}{x}_{3}{x}_{2}{x}_{4}$ 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 ${\tau}_{n}^{\mid I\mid}$
In this section we consider monoids of linear hypersubstitutions when f_{i} is n-ary, n ≥ 2, for every i ∈ I, i.e. if the type contains |I| operation symbols of the same arity n, n ≥ 2. Such types will be denoted by ${\tau}_{n}^{\mid I\mid}$, 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 = x_{i} ∈ X_{n} is a variable and
(ii) $op({f}_{i}({t}_{1},\dots ,{t}_{{n}_{i}}))={\displaystyle \sum _{j=1}^{{n}_{i}}op({t}_{j})}+1$ if t = f_{i}(t_{1}, …, t_{n}_{i}) is a composed n-ary term.
Proposition 3.1
Let t be an n-ary linear term of type ${\tau}_{n}^{\mid I\mid}$, n ≥ 2. Then op(t) ≤ 1.
Proof
If t = x_{i} ∈ X_{n}, then op(t) = 0. Let t = f_{i}(t_{1}, …, t_{n}) be an n-ary linear term. If there were a number k, 1 ≤ k ≤ n_{i} with op(t_{k}) = 1, then |var(t_{k})| ≥ 2 since the arity of all operation symbols in t_{k} is greater than 1 and t_{k} is linear. Assume that x_{m} ≠ x_{l} ∈ var(t_{k}). These variables cannot occur in another subterm of t. But in t there occur n − 1 pairwise different variables which are different from x_{m} and x_{l}. This contradiction shows that op(t_{k}) = 0 for all 1 ≤ k ≤ n_{i} and thus op(t) = 1.
This observation allows us to describe the form of all n-ary linear terms and we obtain
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 f_{i} to an n-ary term we have a full description of $Hy{p}^{lin}({\tau}_{n}^{\mid I\mid})$. Any linear hypersubstitution maps the operation symbol f_{i} to a variable x_{j} ∈ X_{n} or to a term of the form f_{j}(x_{s}_{(1)}, …, x_{s}_{(}_{n}_{)}) where s is a permutation on {1, …, s_{n}}.
For the product of two linear hypersubstitutions σ_{1} and σ_{2} there are precisely the following three possibilities:
1. σ_{2}(f_{i}) = x_{k} ∈ X_{n}: Then $${\sigma}_{1}{\circ}_{h}{\sigma}_{2}={\widehat{\sigma}}_{1}[{\sigma}_{2}({f}_{i})]={\widehat{\sigma}}_{1}[{x}_{k}]={x}_{k}={\sigma}_{{x}_{k}}({f}_{i}).$$
4. Interpretation of Linear Hypersubstitutions on Single Algebras
Term operations induced by linear terms are defined in the usual way. Let $\mathcal{A}=(A;{({f}_{i}^{\mathcal{A}})}_{i\in I})$ be an algebra of type τ and let ${W}_{\tau}^{lin}(X)$ be the set of all linear terms of type τ. Then the set ${({W}_{\tau}^{lin}(X))}^{\mathcal{A}}$ of all linear term operations of is defined as follows:
(ii) if ${f}_{i}({t}_{1},\dots ,{t}_{{n}_{i}})\in {W}_{\tau}^{lin}(X)$ and assumed that ${t}_{1}^{\mathcal{A}},\dots ,{t}_{{n}_{i}}^{\mathcal{A}}$ are defined, then $${({f}_{i}({t}_{1},\dots ,{t}_{{n}_{i}}))}^{\mathcal{A}}={f}_{i}^{\mathcal{A}}({t}_{1}^{\mathcal{A}},\dots ,{t}_{{n}_{i}}^{\mathcal{A}}).$$
Here the right-hand side is the superposition of ${f}_{i}^{\mathcal{A}}$ and ${t}_{1}^{\mathcal{A}},\dots ,{t}_{{n}_{i}}^{\mathcal{A}}$.
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):={\displaystyle \underset{n\ge 1}{\cup}{O}^{n}(A)}$ be the set of all operations on A. Here O^{n}(A) is the set of all n-ary operations defined on A. Then ${({W}_{\tau}^{lin}(X))}^{\mathcal{A}}\subset O(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.
Letbe an algebra of type τ and let ${({W}_{\tau}^{lin}(X))}^{\mathcal{A}}$ be the set of all linear term operations induced on, i.e. term operations induced by linear terms on. Then ${({W}_{\tau}^{lin}(X))}^{\mathcal{A}}$ is closed under the operations *, ζ, τ and ∇ and contains all projections.
Couceiro and Lehtonen proved in [4] also that the subalgebra ${({W}_{\tau}^{lin}(X))}^{\mathcal{A}}$; ζ, τ, ∇, *) of ; ζ, τ,∇, *) is generated by the set $\{{f}_{i}^{\mathcal{A}}\mid i\in I\}\cup {J}_{A}$, where J_{A} is the set of all projections.
Theorem 4.2
Letbe any algebra of type τ. If σ ∈ Hyp^{lin}(τ) satisfies. Then
is an endomorphism of ${(({W}_{\tau}^{lin}(X))}^{\mathcal{A}}$; *, ζ, τ,∇).
Proof
1. Φ is well-defined: assume that ${t}_{1}^{\mathcal{A}}={t}_{2}^{\mathcal{A}}$, t_{1}, ${t}_{2}\in {({W}_{\tau}^{lin}(X))}^{\mathcal{A}}$ There follows ${t}_{1}\approx {t}_{2}\in Id\mathcal{A}\cap {({W}_{\tau}^{lin}(X))}^{2}$ and then
On the other hand we have $$\mathrm{\Phi}({t}^{\mathcal{A}})={(\widehat{\sigma}[t])}^{\mathcal{A}}\text{\hspace{0.17em}and\hspace{0.17em}}\zeta (\mathrm{\Phi}({t}^{\mathcal{A}}))={(\widehat{\sigma}[t]({x}_{2},{x}_{3},\dots ,{x}_{n},{x}_{1}))}^{\mathcal{A}}.$$
MN. Bleicher, H. Schneider, and RL. Wilson. Permanence of identities on algebras. Algebra Universalis., 3(1973), 72-93.
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.
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.
M. Couceiro, and E. Lehtonen. Galois theory for sets of operations closed under permutation, cylindrification and composition. Algebra Universalis., 67(2012), 273-297.
K. Denecke, and SL. Wismath. Hyperidentities and clones, , Gordon and Breach Science Publishers, Amsterdam, 2000.
SL. Wismath. The monoid of hypersubstitutions of type (n). Southeast Asian Bull Math., 24(1)(2000), 115-128.
F. Gécseg, and M. Steinby. Tree automata, , Akadémiai Kiadó, Budapest, 1984.
J. Koppitz, and K. Denecke. M-solid Varieties of algebras. Advances in Mathematics, 10, Springer, New York, 2006.
A. Pilitowska. Linear identities in graph algebras. Comment Math Univ Carolin., 50(2009), 11-24.