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₁, …, x_n} be a finite alphabet and let X := {x₁, …, 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₁, …, t_ni are n-ary terms and if f_i is an n_i-ary operation symbol, then f_i(t₁, …, t_ni) 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₁, …, 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τ(X):=∪n≥1Wτ(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 f_i as n_i-ary operations f̄_i : W_τ (X)^n_i → W_τ (X) with (t₁, …, t_ni) ↦ f̄_i(t₁, …, t_ni) := f_i(t₁, …, t_ni). 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 A=(A;(fiA)i∈I). Here fiA:Ani→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₁, …, t_ni are n-ary linear terms and if var(t_j) ∩ var(t_k) = ∅︀ for all 1 ≤ j < k ≤ n_i, then f_i(t₁ …, t_ni) is an n-ary linear term.

(iii) The set Wτlin(Xn) of all n-ary linear terms is the smallest set which contains x₁, …, 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τlin(X):=∪n≥1Wτlin(Xn).

The set Wτlin(X) is not closed under application of the f̄_i’s since f_i(t₁, …, t_ni) needs not to be linear if t₁, …, t_niare linear. But, if we define to every f_i a partial operation f̂_i on Wτlin(X) by

then Fτlin(X):=(Wτlin(X);(f^i)1∈I) is a partial algebra of type τ. The domain of f̂_i consists of all n_i-tuples (t₁, …, t_ni) 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 (a1,…,ani)∈dom fiA , then (h¯(a1),…,h¯(ani))∈domfiB, and then

(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 : 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₁, …, t_n are m-ary terms of type τ and if f_i(s₁, …, s_ni) is an n-ary term of type τ, then the term

obtained by replacing the variables x₁, …, x_n occurring in s₁, …s_ni by the terms t₁, …, t_ni 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))² 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)i∈I).

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 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 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{x₁(x₂x₃) ≈ (x₁x₂)x₃, x₁x₂x₃x₄ ≈ x₁x₃x₂x₄}, the variety of medial semigroups, is linear, x12x2x3x4≈x12x3x2x4 is an identity in M, but not linear.

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

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₁, …, t_ni)] = σ(f_i)(σ̂[t₁], …, σ̂[t_ni]) 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 σ₁ ∘_h σ₂ := σ̂₁ ∘ σ₂ 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)i∈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 σ[A]:=(A;(σ(fi))i∈IA) is said to be derived from by σ. There holds

(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

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₍₂₎(X₂) = {x₁, x₂, f(x₁, x₂), f(x₂, x₁)} is the set of all binary linear terms of type (2), Hyp^lin(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:

Here σ_{f(x1, x2)} 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

Lemma 2.4

For any linear term t = f_i(t₁, …, t_ni) and any linear hypersubstitution σ we get

for all 1 ≤ j < k ≤ n_i.

Lemma 2.5

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

Theorem 2.6

(Hyp^lin(τ); ∘_h, σ_id) is a submonoid of (Hyp(τ); ∘_h, σ_id).

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₁, x₃), f(x₂, x₄)) and f to f(x₁, x₂). 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₁, x₃), h(x₄)), which maps f to f(x₁, x₂) and h to h(x₁). 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₁, …, x_ni}.

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 σ ∈ Hyp^lin(τ). Then for s,t∈Wτ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 Fτlin(X)=(Wτlin(X);(f^i)i∈I).

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.

We define an operator χlinE by

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

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

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 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 χ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, K ⊆ Alg(τ)} 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 (H_linId, H_linMod), defined on classes K and sets ∑ of linear equations as follows:

Sets of equations of the form H_linIdK are called linear hyperequational theories and classes of algebras of the same type having the form H_linMod∑ are called linear hyperequational classes. As a property of a Galois connection, the combinations H_linIdH_linMod and H_linModH_linId are closure operators and their fixed points form two complete sublattices of the power set lattices ℘(W_τ (X))² 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_linModH_linIdV.

(ii) χlinA[V]=V.

(iii) IdV = H_linIdV.

(iv) χlinE[IdV]=IdV.

And dually, for any equational theory ∑ of type τ, the following conditions are equivalent:

(i’) ∑ = H_linIdH_linMod∑.

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

(iii’) Mod∑ = H_linMod∑.

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

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

(i) χlinA[K]⊆ModIdK⇔ModIdK=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{x₁(x₂x₃) ≈ (x₁x₂)x₃, x₁x₂x₃x₄ ≈ x₁x₃x₂x₄} 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 x12x2x3x4≈x12x3x2x4 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.

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 τn∣I∣, 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(fi(t1,…,tni))=∑j=1niop(tj)+1 if t = f_i(t₁, …, t_ni) is a composed n-ary term.

Proposition 3.1

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

Term operations induced by linear terms are defined in the usual way. Let A=(A;(fiA)i∈I) 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):=∪n≥1On(A) be the set of all operations on A. Here Oⁿ(A) is the set of all n-ary operations defined on A. Then (Wτlin(X))A⊂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.

Let f ∈ Oⁿ(A) and g ∈ O^m(A). Then

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 *, ζ, τ and ∇ and contains all projections.

Couceiro and Lehtonen proved in [4] also that the subalgebra (Wτlin(X))A; ζ, τ, ∇, *) of ; ζ, τ,∇, *) is generated by the set {fiA∣i∈I}∪JA, 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τlin(X))A; *, ζ, τ,∇).