Abstract
We give an abstract characterization of algebras of partial functions from A n to A endowed with the operations of the Menger superposition and the set-theoretic difference of functions as subsets of A n+1.
Similar content being viewed by others
Avoid common mistakes on your manuscript.
1. Let A n be the n-th Cartesian power of a set A. Any partial mapping from A n into A is called a partial n-place function. The set of all such mappings is denoted by \(\mathcal {F}(A^{n},A)\). On \(\mathcal{F}(A^{n},A)\) we define the Menger superposition (composition) of n-place functions O:(f,g 1,…,g n )↦f[g 1…g n ] as follows:
for all \(\bar{a}\in A^{n}\), \(\bar{b}=(b_{1},\ldots,b_{n})\in A^{n}\), c∈A.
Each subalgebra (Φ,O), where \(\varPhi\subset\mathcal{F}(A^{n},A)\), of the algebra \((\mathcal{F}(A^{n},A),\mathrm{O})\) is a Menger algebra of rank n in the sense of [2–4, 8]. Menger algebras of partial n-place functions are partially ordered by the set-theoretic inclusion, i.e., such algebras can be considered as algebras of the form (Φ,O,⊂). The first abstract characterization of such algebras was given in [9]. Later, in [10, 11] there have been found abstract characterizations of Menger algebras of n-place functions closed with respect to the set-theoretic intersection and union of functions, i.e., Menger algebras of the form (Φ,O,∩), (Φ,O,∪) and (Φ,O,∩,∪).
As is well known, the set-theoretic inclusion ⊂ and the operations ∩, ∪ can be expressed via the set-theoretic difference (subtraction) in the following way:
where A,B,C are arbitrary sets such that A⊂C and B⊂C.
Thus it makes sense to examine sets of functions closed with respect to the subtraction of functions. Such sets of functions are called difference semigroups, while their abstract analogs are called subtraction semigroups. Some properties of subtraction semigroups can bee found in [1]. The investigation of difference semigroups was initiated by Schein [7].
Below we present a generalization of Schein’s results to the case of Menger algebras of n-place functions, i.e., to the case of algebras (Φ,O,∖,∅), where \(\varPhi\subset\mathcal{F}(A^{n}, A)\), ∅∈Φ. Such algebras will be called difference Menger algebras.
2. A Menger algebra of rank n is a non-empty set G with one (n+1)-ary operation o(x,y 1,…,y n )=x[y 1…y n ] satisfying the identity:
A Menger algebra of rank 1 is a semigroup. A Menger algebra (G,o) of rank n is called unitary if it contains selectors, i.e., elements e 1,…,e n ∈G such that x[e 1…e n ]=x and e i [x 1…x n ]=x i for all x,x 1,…,x n ∈G, i=1,…,n. One can prove (see [2, 3]) that every Menger algebra (G,o) of rank n can be isomorphically embedded into a unitary Menger algebra (G ∗,o ∗) of the same rank with selectors e 1,…,e n ∉G such that G∪{e 1,…,e n } is a generating set of (G ∗,o ∗).
Let (G,o) be a Menger algebra of rank n. Consider the alphabet G∪{[ , ],x}, where the symbols [ , ],x do not belong to G, and construct the set T n (G) of polynomials over this alphabet by the following rules:
-
(a)
x∈T n (G);
-
(b)
if i∈{1,…,n}, a,b 1,…,b i−1,b i+1,…,b n ∈G, t∈T n (G), then a[b 1…b i−1 t b i+1,…b n ]∈T n (G);
-
(c)
T n (G) contains those and only those polynomials which are constructed by (a) and (b).
A binary relation ρ⊂G×G, where (G,o) is a Menger algebra of rank n, is
-
stable if for all x,y,x i ,y i ∈G, i=1,…,n
$$(x,y),(x_1,y_1),\ldots,(x_n,y_n)\in\rho\longrightarrow \bigl(x[x_1\ldots x_n],y[y_1\ldots y_n]\bigr)\in\rho;$$ -
l-regular, if for any x,y,z i ∈G, i=1,…,n
$$(x,y)\in\rho\longrightarrow\bigl(x[z_1\ldots z_n],y[z_1\ldots z_n]\bigr)\in\rho;$$ -
v-regular, if for all x i ,y i ,z∈G, i=1,…,n
$$(x_1,y_1),\ldots,(x_n,y_n)\in \rho\longrightarrow\bigl(z[x_1\ldots x_n],z[y_1\ldots y_n]\bigr)\in\rho;$$ -
i-regular (1≤i≤n), if for all u,x,y∈G, \(\bar{w}\in G^{n}\)
$$(x,y)\in\rho\longrightarrow\bigl(u[\bar{w}|_ix], u[\bar{w}|_iy]\bigr)\in\rho;$$ -
weakly steady if for all x,y,z∈G, t 1,t 2∈T n (G)
$$(x,y),\bigl(z,t_1(x)\bigr),\bigl(z,t_2(y)\bigr)\in\rho \longrightarrow \bigl(z,t_2(x)\bigr)\in\rho,$$
where \(\bar{w}=(w_{1},\ldots,w_{n})\) and \(u[\bar{w}|_{i}\,x]=u[w_{1}\ldots w_{i-1}xw_{i+1}\ldots w_{n}]\). It is clear that a quasiorderFootnote 1 on a Menger algebra is v-regular if and only if it is i-regular for every i=1,…,n. A quasiorder is stable if and only if it is both v-regular and l-regular.
A subset H of a Menger algebra (G,o) is called
-
stable if
$$g,g_1,\ldots,g_n\in H\longrightarrow g[g_1\ldots g_n]\in H;$$ -
an l-ideal, if for all x,h 1,…,h n ∈G
$$(h_1,\ldots,h_n)\in G^n \setminus(G\setminus H)^n \longrightarrow x [h_1\ldots h_n]\in H;$$ -
an i-ideal (1≤i≤n), if for all h,u∈G, \(\bar{w}\in G^{n} \)
$$h\in H\longrightarrow u[\bar{w}|_i h]\in H.$$
Clearly, H is an l-ideal if and only if it is an i-ideal for every i=1,…,n.
An algebra (G,−,0) of type (2,0) is called a subtraction algebra if it satisfies the following identities:
(Abbott [1])
Every subtraction algebra satisfies the identity
Below we give a short proof of this identity:
as required. □
From (7), by using (3), we obtain the following two identities:
Similarly, from (4), (5), (7) and (8) we can deduce the identities
Thus, subtraction algebras are implicative BCK-algebras (cf. [5, 6]).
An algebra (G,o,−,0) of type (n+1,2,0) is called a subtraction Menger algebra of rank n, if (G,o) is a Menger algebra of rank n, (G,−,0) is a subtraction algebra and the conditions
hold for all x,y,z,u,z 1,…,z n ∈G, \(\bar{w}\in G^{n}\), i=1,…,n and t 1,t 2∈T n (G).
By putting n=1 in the above definition we obtain the notion of a weak subtraction semigroup Footnote 2 studied by Schein (cf. [7]). Such semigroups are isomorphic to some subtraction semigroups of the form (Φ,∘,∖).
3. Now we can present the first result of our paper.
Each difference Menger algebra of n-place functions is a subtraction Menger algebra of rank n.
FormalPara ProofLet (Φ,O,∖,∅) be a difference Menger algebra of n-place functions defined on A. Since, as it is proved in [2], the superposition O satisfies (2), the algebra (Φ,O) is a Menger algebra of rank n. From the results proved in [1] it follows that the operation ∖ satisfies (3), (4) and (5). Hence (Φ,∖,∅) is a subtraction algebra. Thus, (Φ,O,∖,∅) will be a subtraction Menger algebra if (11), (12) and (13) will be satisfied.
To verify (11) observe that for each \((\bar{a},c)\in(f\setminus g)[h_{1}\ldots h_{n}]\), where f,g,h 1,…,h n ∈Φ, \(\bar{a}\in A^{n}\), c∈A there exists \(\bar{b}=(b_{1},\ldots,b_{n})\in A^{n}\) such that \((\bar{b},c)\in f \setminus g\) and \((\bar{a},b_{i})\in h_{i}\) for each i=1,…,n. Consequently, \((\bar{b},c)\in f\) and \((\bar{b},c)\notin g\). Thus, \((\bar{a},c)\in f[h_{1}\ldots h_{n}]\). If \((\bar{a},c)\in g[h_{1}\ldots h_{n}]\), then there exists \(\bar {d}=(d_{1},\ldots, d_{n})\in A^{n}\) such that \((\bar{d},c)\in g\) and \((\bar {a},d_{i})\in h_{i}\) for every i=1,…,n. Since h 1,…,h n are functions, we obtain b i =d i for all i=1,…,n. Thus \(\bar{b}=\bar{d}\). Therefore \((\bar{b},c)\in g\), which is impossible. Hence \((\bar {a},c)\notin g[h_{1}\ldots h_{n}]\). This means that \((\bar{a},c)\in f[h_{1}\ldots h_{n}]\setminus g[h_{1}\ldots h_{n}]\). So, the following implication
is valid for any \(\bar{a}\in A^{n}\), c∈A, i.e., (f∖g)[h 1…h n ]⊂f[h 1…h n ]∖g[h 1…h n ].
Conversely, let \((\bar{a},c)\in f[h_{1}\ldots h_{n}]\setminus g[h_{1}\ldots h_{n}]\). Then \((\bar{a},c)\in f[h_{1}\ldots h_{n}]\) and \((\bar{a},c)\notin g [h_{1}\ldots h_{n}]\). Thus, there exists \(\bar{b}=(b_{1},\ldots,b_{n})\in A^{n}\) such that \((\bar{b},c)\in f\), \((\bar{b},c)\notin g\) and \((\bar{a},b_{i})\in h_{i}\) for each i=1,…,n. Hence, \((\bar{b},c)\in f \setminus g\) and \((\bar{a},c)\in(f \setminus g)[h_{1}\ldots h_{n}]\). So,
for any \(\bar{a}\in A^{n}\), c∈A, i.e., f[h 1…h n ]∖g[h 1…h n ]⊂(f∖g)[h 1…h n ]. Thus,
which proves (11).
Now, let \((\bar{a},c)\in u[\bar{\omega}|_{i}(f \setminus(f \setminus g))] =u[\bar{\omega}|_{i}(f\cap g)]\), where f,g,u∈Φ, \(\bar{\omega}\in\varPhi^{n}\), \(\bar{a}\in A^{n}\), c∈A. Then there exists \(\bar{b}=(b_{1},\ldots,b_{n})\in A^{n}\) such that \((\bar{a},b_{i})\in f\cap g\), \((\bar{a},b_{j})\in\omega_{j}\), j∈{1,…,n}∖{i} and \((\bar{b},c)\in u\). Since \((\bar{a},b_{i})\in f\cap g\) implies \((\bar{a},b_{i})\notin f \setminus g\), we have \((\bar{a},c)\in u[\bar {\omega}|_{i}f]\) and \((\bar{a},c)\notin u[\bar{\omega}|_{i}(f \setminus g)]\). Therefore \((\bar{a},c)\in u[\bar{\omega}|_{i}f]\setminus u[\bar {\omega}|_{i}(f \setminus g)]\). Thus, we have shown that for any \(\bar{a}\in A^{n}\), c∈A holds the implication
which is equivalent to the inclusion \(u[\bar{\omega}|_{i}(f \setminus(f \setminus g))]\subset u[\bar{\omega}|_{i}f]\setminus u[\bar{\omega}|_{i}(f \setminus g)]\).
Conversely, let \((\bar{a},c)\in u[\bar{\omega}|_{i}f]\setminus u[\bar {\omega}|_{i}(f \setminus g)]\). Then \((\bar{a},c)\in u[\bar{\omega}|_{i}f]\) and \((\bar{a},c)\notin u[\bar{\omega}|_{i}(f \setminus g)]\). The first of these two conditions means that there exists \(\bar{b}=(b_{1},\ldots,b_{n})\in A^{n}\) such that \((\bar{a},b_{i})\in f\), \((\bar {a},b_{j})\in\omega_{j}\) for each j∈{1,…,n}∖{i} and \((\bar{b},c)\in u\). It is easy to see that the second condition \((\bar{a},c)\notin u[\bar{\omega}|_{i}(f \setminus g)]\) is equivalent to the implication
where \(\bar{d}=(d_{1},\ldots,d_{n})\in A^{n}\). From this implication for \(\bar{d}=\bar{b}\), we obtain
which gives \((\bar{a},b_{i})\in g\). Therefore \((\bar{a},b_{i})\in f\cap g=f \setminus(f \setminus g)\). This means that \((\bar{a},c)\in u[\bar{\omega}|_{i}(f \setminus(f \setminus g))]\). So, the implication
is valid for all \(\bar{a}\in A^{n}\), c∈A. Hence \(u[\bar{\omega}|_{i}f]\setminus u[\bar{\omega}|_{i}(f \setminus g)]\subset u[\bar{\omega}|_{i}(f \setminus(f \setminus g))]\). Thus
This proves (12).
To prove (13) suppose that for some f,g,h∈Φ and t 1,t 2∈T n (Φ) we have f∖g=∅, h∖t 1(f)=∅ and h∖t 2(g)=∅. Then f⊂g, h⊂t 1(f) and h⊂t 2(g). Hence \(f=g\circ\Delta_{{\operatorname {pr_{1}}}f}\) and \(\operatorname {pr_{1}}h\subset \operatorname {pr_{1}}f\), where \(\operatorname {pr_{1}}f\) denotes the domain of f and \(\Delta_{{\operatorname {pr_{1}}}f}\) is the identity binary relation on \(\operatorname {pr_{1}}f\).
From the inclusion h⊂t 2(g) we obtain
which means that (13) is also satisfied. This completes the proof that (Φ,O,∖,∅) is a subtraction Menger algebra of rank n. □
To prove the converse statement, we should first consider a number of properties of subtraction Menger algebras of rank n, introduce some definitions and prove a few auxiliary propositions.
4. Let (G,o,−,0) be a subtraction Menger algebra of rank n.
In every subtraction Menger algebra of rank n we have
for all x,x 1,…,x n ∈G, i=1,…,n.
FormalPara ProofIndeed, using (7) and (11) we obtain
Similarly, applying (12) and (7) we get
which was to show. □
Let ω be a binary relation defined on (G,o,−,0) in the following way:
Using (7), (8) and (9) it is easy to see that this is an order, i.e., a reflexive, transitive and antisymmetric relation. In connection with this fact we will sometimes write x≤y instead of (x,y)∈ω. Using this notation it is not difficult to verify that
holds for all x,y,z,u,v∈G.
Moreover, in a subtraction algebra the following two identities
The relation ω on the algebra (G,o,−,0) is stable and weakly steady.
FormalPara ProofLet x≤y for some x,y∈G. Then x−y=0 and
for all z 1,…,z n ∈G. This, by (11), implies
i.e., x[z 1…z n ]≤y[z 1…z n ]. Thus, ω is l-regular.
Moreover, from x≤y, using (8), we obtain x−(x−y)=x, which together with (4), gives y−(y−x)=x. Consequently, for any u∈G, \(\bar{w}\in G^{n} \) we have \(u[\bar {w}|_{i}(y-(y-x))]=u[\bar{w}|_{i}\,x]\). This and (11) give \(u[\bar{w}|_{i}\,y]-u[\bar{w}|_{i}(y-x)]=u[\bar{w}|_{i}\,x]\). Hence, according to (15), we obtain \(u[\bar{w}|_{i}\,x]\leq u[\bar{w}|_{i}\,y]\). Thus, ω is i-regular for every i=1,…,n. Since ω is a quasiorder, this means that ω is v-regular. But ω also is l-regular, hence it is stable.
It is clear that ω is weakly steady if and only if it satisfies (13).Footnote 3 □
FormalPara Proposition 4The axiom (12) is equivalent to each of the following conditions:
for all x,y,u∈G, \(\bar{w}\in G^{n}\), i=1,…,n, t∈T n (G).
FormalPara Proof(12)→(22). Suppose that the condition (12) is satisfied and x≤y for some x,y∈G. Then, according to (16), we have x−(x−y)=x. Hence, by (4), we obtain y−(y−x)=x. Thus, y−x=y−(y−(y−x)), which, in view of (12), gives \(u[\bar{w}|_{i}\,(y-x)]=u[\bar{w}|_{i}\,(y-(y-(y-x)))]=u[\bar{w}|_{i}y]-u[\bar {w}|_{i}(y-(y-x))]=u[\bar{w}|_{i}y]-u[\bar{w}|_{i}x]\). This means that (12) implies (22).
(22)→(23). From (22) it follows that for x≤y and all polynomials t∈T n (G) of the form \(t(x)=u[\bar{w}|_{i}x]\) the condition (23) is satisfied. To prove that (23) is satisfied by an arbitrary polynomial from T n (G) suppose that it is satisfied by some t′∈T n (G). Since the relation ω is stable on the algebra (G,o,−,0), from x≤y it follows t′(x)≤t′(y), which in view of (22), implies
But according to the assumption on t′ for x≤y we have t′(y)−t′(x)=t′(y−x), so the above equation can be written as
Thus, (23) is satisfied by polynomials of the form \(t(x)=u[\bar{w}|_{i}t'(x)]\).
From the construction of T n (G) it follows that (23) is satisfied by all polynomials t∈T n (G). Therefore (22) implies (23).
(23)→(24). Since, by (15), x−y≤x holds for all x,y∈G, from (23) it follows t(x−(x−y))=t(x)−t(x−y) for any polynomial t∈T n (G). Thus, (23) implies (24).
(24)→(12). By putting \(t(x)=u[\bar{w}|_{i}\,x]\) we obtain (12). □
On a subtraction Menger algebra (G,o,−,0) of rank n we can define a binary operation ⋏ by putting:
By using this operation the conditions (11), (16), (24) can be written in a more useful form:
where x,y,u∈G, \(\bar{w}\in G^{n}\), i=1,…,n, t∈T n (G). Moreover, from (11) and (25), we can deduce the identity:
The algebra (G,⋏) is a lower semilattice. Directly from the conditions (3)–(10) we obtain (cf. [1]) the following properties:
for all x,y,z∈G.
In a subtraction Menger algebra (G,o,−,0) of rank n the following conditions
are valid for each t∈T n (G) and x,y∈G.
FormalPara ProofFrom (35) we obtain t(x−y)=t(x−(x⋏y)) for every t∈T n (G). (25) and (15) imply x⋏y≤x, which together with (23) gives t(x−(x⋏y))=t(x)−t(x⋏y). Hence, t(x−y)=t(x)−t(x⋏y). This proves (39).
Since x⋏y≤y, the stability of ω implies t(x⋏y)≤t(y) for every t∈T n (G). From this, by applying (15) and (18), we obtain t(x)−t(y)≤t(x)−t(x⋏y)=t(x−y), which proves (40). □
By [0,a] we denote the initial segment of the algebra (G,−,0), i.e., the set of all x∈G such that 0≤x≤a. According to [7], on any [0,a] we can define a binary operation ⋎ by putting:
for all x,y∈[0,a]. It is not difficult to see that this operation is idempotent and commutative, and 0 is its neutral element, i.e., x⋎x=x, x⋎y=y⋎x, x⋎0=x for all x,y∈[0,a].
For any x,y∈[0,b]⊂[0,a], where a,b∈G, we have
Note first that b=b⋏a because b≤a. Moreover, from x≤b and y≤b, according to (18), we obtain a−b≤a−x and a−b≤a−y. This together with (30) gives a−b≤(a−x)⋏(a−y). Thus, (a−b)−((a−x)⋏(a−y))=0.
By (15) we have b−((a−x)⋏(a−y))≤b, which implies
Obviously b=b⋏b=b⋏a, x=b⋏x, y=b⋏y. Therefore:Footnote 4
which completes the proof. □
FormalPara Corollary 1The condition (42) is valid for all x,y∈[0,a]∩[0,b].
FormalPara ProofSince [0,a]∩[0,b]=[0,a⋏b]⊂[0,a]∪[0,b], by Proposition 6, for all x,y∈[0,a]∩[0,b] we have:
This implies (42). □
From the above corollary it follows that the value of x⋎y, if it exists, does not depend on the choice of the interval [0,a] containing the elements x and y. In [1] it is proved that for x,y,z∈[0,a] we have:
From (44) it follows x≤x⋎y.
If for some x,y∈G there exists x⋎y, then for all u∈G, \(\bar{z},\bar{w}\in G^{n}\), i=1,…,n there are also elements \(x[\bar{z}]\curlyvee y[\bar{z}]\) and \(u[\bar{w}|_{i}\,x]\curlyvee u[\bar{w}|_{i}\,y]\), and the following identities are satisfied:
Suppose that the element x⋎y exists. Then x≤a and y≤a for some a∈G, which, by the l-regularity of the relation ω, implies \(x[\bar{z}]\leq a[\bar{z}]\) and \(y[\bar{z}]\leq a[\bar{z}]\) for any \(\bar{z}\in G^{n}\). This means that \(x[\bar{z}]\curlyvee y[\bar{z}]\) exists and
This proves (54).
Further, from x≤a, y≤a and the i-regularity of ω we obtain \(u[\bar{w}|_{i}\,x]\leq u[\bar{w}|_{i}\,a]\) and \(u[\bar{w}|_{i}\,y]\leq u[\bar{w}|_{i}\,a]\). Hence, the element \(u[\bar {w}|_{i}\,x]\curlyvee u[\bar{w}|_{i}\,y]\) exists. Since x≤x⋎y and y≤x⋎y, we also have \(u[\bar {w}|_{i}\,x]\leq u[\bar{w}|_{i}(x\curlyvee y)]\) and \(u[\bar{w}|_{i}\,y]\leq u[\bar{w}|_{i}(x\curlyvee y)]\), which, according to (50), gives
On the other side, the existence of \(u[\bar{w}|_{i}\,x]\curlyvee u[\bar {w}|_{i}\,y]\) implies
Moreover,
Consequently,
But y−x≤y, so, \(u[\bar{w}|_{i}(y-x)]\leq u[\bar{w}|_{i}\,y]\) and
This and (57) guarantee the existence of the element
such that
Since \(u[\bar{w}|_{i}(y-x)]\leq u[\bar{w}|_{i}\,y]\leq u[\bar{w}|_{i}(x\curlyvee y)]\), the last inequality and (51) imply
which together with (58) gives
Comparing this inequality with (56) we obtain (55). □
FormalPara Corollary 2If for some x,y∈G an element x⋎y exists, then for any polynomial t∈T n (G) an element t(x)⋎t(y) also exists and t(x⋎y)=t(x)⋎t(y).
FormalPara Proposition 8For all x,y∈G and all polynomials t 1,t 2∈T n (G) we have:
Let t 1(x⋏y)⋏t 2(x−y)=h. Obviously h≤t 1(x⋏y) and h≤t 2(x−y). Since t 2(x−y)≤t 2(x), we have h≤t 2(x). Thus, x⋏y≤x, h≤t 1(x⋏y) and h≤t 2(x). This, in view of Proposition 3 and (13), gives h≤t 2(x⋏y). Consequently,
Further,
Therefore,
which together with (59) implies h≤0. Hence h=0. This completes the proof. □
FormalPara Proposition 9For all x,y,z,g∈G and all polynomials t 1,t 2∈T n (G) the following conditions are valid:
To prove (60) observe first that for z=t 1(x⋏y)⋏t 2(y) we have z≤t 1(x⋏y) and z≤t 2(y). Since the relation ω is weakly steady and x⋏y≤y, from the above we conclude z≤t 2(x⋏y), i.e., t 1(x⋏y)⋏t 2(y)≤t 2(x⋏y). This, by (31), implies t 1(x⋏y)⋏t 2(y)≤t 1(x⋏y)⋏t 2(x⋏y).
On the other side, the stability of ω and x⋏y≤y imply t 2(x⋏y)≤t 2(y) for every t 2∈T n (G). Hence, t 1(x⋏y)⋏t 2(x⋏y)≤t 1(x⋏y)⋏t 2(y) by (31). This completes the proof of (60).
Further: \(t_{1}(x\curlywedge y\curlywedge z)\curlywedge t_{2}(y)=t_{1}((x\curlywedge z)\curlywedge y)\curlywedge t_{2}(y)\stackrel{\mbox{\mbox{\scriptsize(60)}}}{=}t_{1}((x\curlywedge z)\curlywedge y)\curlywedge t_{2}((x\curlywedge z)\curlywedge y)\leq t_{1}(x\curlywedge y)\curlywedge t_{2}(y\curlywedge z)\) proves (61).
Finally, let g≤t 1(x⋏y) and g≤t 2(y⋏z). Then
This proves (62) and completes the proof of our proposition. □
FormalPara Corollary 3For all x,y,z∈G and all polynomials t 1,t 2∈T n (G) we have:
We have t 1(x⋏y)⋏t 2(y⋏z)≤t 1(x⋏y) and t 1(x⋏y)⋏t 2(y⋏z)≤t 2(y⋏z), so by (62) we obtain t 1(x⋏y)⋏t 2(y⋏z)≤t 1(x⋏y⋏z). Considering now that t 1(x⋏y)⋏t 2(y⋏z)≤t 2(y⋏z)≤t 2(y), by (30), we get t 1(x⋏y)⋏t 2(y⋏z)≤t 1(x⋏y⋏z)⋏t 2(y). Taking now into account the condition (61) we obtain (63). □
5. Let (G,o,−,0) be a subtraction Menger algebra of rank n.
By a determining pair of a subtraction Menger algebra (G,o,−,0) of rank n we mean an ordered pair (ε ∗,W), where ε is a v-regular equivalence relation defined on (G,o), ε ∗=ε∪{(e 1,e 1),…,(e n ,e n )}, e 1,…,e n are the selectors of the unitary extension (G ∗,o ∗) of (G,o) and W is the empty set or an l-ideal of (G,o) which is an ε-class.
FormalPara Definition 4A non-empty subset F of a subtraction Menger algebra (G,o,−,0) of rank n is called a filter if:
-
(1)
0∉F;
-
(2)
x∈F∧x≤y⟶y∈F;
-
(3)
x∈F∧y∈F⟶x⋏y∈F
for all x,y∈G.
If a,b∈G and a≰b, then [ a)={x∈G | a≤x} is a filter with a∈[ a) and b∉[ a). By Zorn’s Lemma the collection of filters which contain an element a, but do not contain an element b, has a maximal element which is denoted by F a,b . Using this filter we define the following three sets:
For any a,b∈G, the pair \((\varepsilon^{*}_{a,b},W_{a,b})\) is the determining pair of the algebra (G,o,−,0).
FormalPara ProofFirst we show that ε a,b is an equivalence relation on G. It is clear that this relation is reflexive and symmetric. To prove its transitivity let (x,y),(y,z)∈ε a,b . We have four possibilities:
-
(a)
x⋏y∉W a,b ∧ y⋏z∉W a,b ,
-
(b)
x⋏y∉W a,b ∧ y,z∈W a,b ,
-
(c)
x,y∈W a,b ∧ y⋏z∉W a,b ,
-
(d)
x,y∈W a,b ∧ y,z∈W a,b .
In the case (a) we have t 1(x⋏y),t 2(y⋏z)∈F a,b for some t 1,t 2∈T n (G). Since F a,b is a filter, then, obviously, t 1(x⋏y)⋏t 2(y⋏z)∈F a,b . This, according to (63), implies t 1(x⋏y⋏z)⋏t 2(y)∈F a,b . But t 1(x⋏y⋏z)⋏t 2(y)≤t 1(x⋏z), hence also t 1(x⋏z)∈F a,b , i.e., x⋏z∉W a,b . Thus, (x,z)∈ε a,b .
In the case (b) from x⋏y∉W a,b it follows t(x⋏y)∈F a,b for some polynomial t∈T n (G). But x⋏y≤y, and consequently t(x⋏y)≤t(y). Thus t(y)∈F a,b , i.e., y∉W a,b , which is a contradiction. Hence the case (b) is impossible. Analogously we can show that also the case (c) is impossible. The case (d) is obvious, because in this case x,z∈W a,b which means that (x,z)∈ε a,b . This completes the proof that ε a,b is transitive.
Moreover, if x∈W a,b , then t(x)∉F a,b for every t∈T n (G). In particular, for all \(t(x)=t'(u[\bar{w}|_{i}\,x])\in T_{n}(G)\) we have \(t'(u[\bar{w}|_{i}\,x])\notin F_{a,b}\). Thus, \(u[\bar {w}|_{i}\,x]\in W_{a,b}\) for every i=1,…,n. Hence, W a,b is an i-ideal of (G,o), and consequently, an l-ideal. It is clear that W a,b is an ε a,b -class.
Next, we prove that the relation ε a,b is v-regular. Let x≡y(ε a,b ). Then x⋏y∉W a,b or x,y∈W a,b . In the case x,y∈W a,b we obtain \(u[\bar{w}|_{i}\,x],u[\bar{w}|_{i}\,y]\in W_{a,b}\) because W a,b is an l-ideal of (G,o). Thus, \(u[\bar{w}|_{i}\,x]\equiv u[\bar{w}|_{i}\,y](\varepsilon_{a,b})\). In the case x⋏y∉W a,b elements \(u[\bar{w}|_{i}\,x]\), \(u[\bar{w}|_{i}\,y]\) belong or not belong to W a,b simultaneously. Indeed, if \(u[\bar{w}|_{i}\,x]\), \(u[\bar{w}|_{i}\,y]\in W_{a,b}\), then obviously \(u[\bar{w}|_{i}\,x]\equiv u[\bar{w}|_{i}\,y](\varepsilon_{a,b})\). Now, if \(u[\bar{w}|_{i}\,x]\notin W_{a,b}\), then \(t(u[\bar{w}|_{i}\,x])\in F_{a,b}\) for some t∈T n (G). Since x⋏y∉W a,b , then also t 1(x⋏y)∈F a,b for some t 1∈T n (G). Thus \(t_{1}(x\curlywedge y)\curlywedge t(u[\bar{w}|_{i}\,x])\in F_{a,b}\), which, by (60), implies \(t_{1}(x\curlywedge y)\curlywedge t(u[\bar{w}|_{i}(x\curlywedge y)])\in F_{a,b}\). But \(t_{1}(x\curlywedge y)\curlywedge t(u[\bar{w}|_{i}(x\curlywedge y)]) \leq t(u[\bar{w}|_{i}\,y])\), hence \(t(u[\bar{w}|_{i}\,y])\in F_{a,b}\), i.e., \(u[\bar{w}|_{i}\,y]\notin W_{a,b}\). So, we have shown that x⋏y∉W a,b and \(u[\bar{w}|_{i}\,x]\notin W_{a,b}\) imply \(u[\bar{w}|_{i}\,y]\notin W_{a,b}\). Similarly we can show that x⋏y∉W a,b and \(u[\bar{w}|_{i}\,y]\notin W_{a,b}\) imply \(u[\bar{w}|_{i}\,x]\notin W_{a,b}\). Therefore, we have proved that in the case x⋏y∉W a,b elements \(u[\bar{w}|_{i}\,x]\), \(u[\bar{w}|_{i}\,y]\) belong or not belong to W a,b simultaneously.
So, if for x⋏y∉W a,b we have \(u[\bar{w}|_{i}\,x],u[\bar{w}|_{i}\,y]\in W_{a,b}\), then clearly \(u[\bar{w}|_{i}\,x]\equiv u[\bar{w}|_{i}\,y](\varepsilon_{a,b})\). Therefore assume that \(u[\bar {w}|_{i}\,x]\notin W_{a,b}\) (hence \(u[\bar{w}|_{i}\,y]\notin W_{a,b}\)). Thus, x⋏y∉W a,b , \(u[\bar{w}|_{i}\,x]\notin W_{a,b}\), i.e., t(x⋏y)∈F a,b , \(t_{1}(u[\bar{w}|_{i}\,x])\in F_{a,b}\) for some t,t 1∈T n (G). Hence, \(t(y\curlywedge x\curlywedge y)\curlywedge t_{1}(u[\bar{w}|_{i}\,x])\in F_{a,b}\). From this, according to (63), we obtain \(t(y\curlywedge x)\curlywedge t_{1}(u[\bar{w}|_{i}(x\curlywedge y)])\in F_{a,b}\). This implies \(t_{1}(u[\bar{w}|_{i}(x\curlywedge y)])\in F_{a,b}\). Since \(u[\bar {w}|_{i}(x\curlywedge y)]\leq u[\bar{w}|_{i}\,x]\) and \(u[\bar{w}|_{i}(x\curlywedge y)]\leq u[\bar{w}|_{i}\,y]\), we have \(u[\bar{w}|_{i}(x\curlywedge y)]\leq u[\bar{w}|_{i}\,x]\curlywedge u[\bar{w}|_{i}\,y]\), which, by the stability of ω gives \(t_{1}(u[\bar {w}|_{i}(x\curlywedge y)]) \leq t_{1}(u[\bar{w}|_{i}\,x]\curlywedge u[\bar{w}|_{i}\,y])\). Consequently, \(t_{1}(u[\bar{w}|_{i}\,x]\curlywedge u[\bar{w}|_{i}\,y])\in F_{a,b}\), so \(u[\bar{w}|_{i}\,x]\curlywedge u[\bar{w}|_{i}\,y]\notin W_{a,b}\), i.e., \(u[\bar{w}|_{i}\,x]\equiv u[\bar {w}|_{i}\,y](\varepsilon_{a,b})\). In this way we have proved that the relation ε a,b is i-regular for every i=1,…,n. Thus it is v-regular. □
FormalPara Proposition 11All equivalence classes of ε a,b , except of W a,b , are filters.
FormalPara ProofIndeed, let H≠W a,b be an arbitrary class of ε a,b . If x∈H and x≤y, then x⋏y=x∉W a,b , consequently, (x,y)∈ε a,b . Hence, y∈H. Further, let x,y∈H, then (x,y)∈ε a,b . Thus x⋏y∉W a,b , i.e., t(x⋏y)∈F a,b for some t∈T n (G). But x⋏y=x⋏(x⋏y), hence, t(x⋏(x⋏y))∈F a,b and x⋏(x⋏y)∉W a,b . So x≡x⋏y(ε a,b ). This implies x⋏y∈H. Thus, we have shown that H is a filter. □
FormalPara Proposition 12If x⋎y exists for some x,y∈W a,b , then x⋎y∈W a,b .
FormalPara ProofLet x⋎y exists for some x,y∈W a,b . If x⋎y∉W a,b , then t(x⋎y)∈F a,b for some t∈T n (G), and, according to Corollary 2, t(x⋎y)=t(x)⋎t(y). If t(x)∉F a,b , then F a,b is a proper subset of the set
because t(x)∈U.
We show that U is a filter. 0∉U because, by (15), we have 0≤z⋏t(x) for any z∈F a,b . Let s∈U and s≤r. Then z⋏t(x)≤s for some z∈F a,b . Consequently, z⋏t(x)≤r, so r∈U. Now let s∈U and r∈U, i.e., z 1⋏t(x)≤s and z 2⋏t(x)≤r for some z 1,z 2∈F a,b . Since F a,b is a filter, we have z 1⋏z 2∈F a,b . Hence, (z 1⋏z 2)⋏t(x)≤s⋏r, which implies s⋏r∈U. Thus U is a filter. But by assumption F a,b ⊂U is a maximal filter, which does not contain b, so b∈U. Consequently, z 1⋏t(x)≤b for some z 1∈F a,b . Similarly, if t(y)∉F a,b , then z 2⋏t(y)≤b for some z 2∈F a,b . This implies z⋏t(x)≤b and z⋏t(y)≤b for z=z 1⋏z 2. Hence (z⋏t(x))⋎(z⋏t(y)) exists and
by (47). But by (50) we have (z⋏t(x))⋎(z⋏t(y))≤b, so z⋏t(x⋎y)≤b. Since z⋏t(x⋎y)∈F a,b , then, obviously, b∈F a,b , which is impossible. So, t(x)∈F a,b or t(y)∈F a,b , hence x∉W a,b or y∉W a,b , contrary to the assumption that x,y∈W a,b . Thus, the assumption that x⋎y∉W a,b is incorrect. Therefore x⋎y∈W a,b . □
6. Each homomorphism of a Menger algebra (G,o) of rank n into a Menger algebra \((\mathcal{F}(A^{n},A),\mathrm{O})\) is called a representation by n-place functions. Thus, \(P:G\to \mathcal{F}(A^{n},A)\) is a representation, if
for all x,y 1,…,y n ∈G. A representation which is an isomorphism is called faithful (cf. [2–4, 8]). A representation P of (G,o) is a representation of (G,o,−,0) if
for all x,y∈G.
Let (P i ) i∈I be the family of representations of a subtraction Menger algebra (G,o,−,0) of rank n by n-place functions defined on pairwise disjoint sets (A i ) i∈I . By the sum of the family (P i ) i∈I we mean the map P:g↦P(g), denoted by ∑ i∈I P i , where P(g) is an n-place function on A=⋃ i∈I A i defined by P(g)=⋃ i∈I P i (g). It is clear (cf. [2, 3]) that P is a representation of (G,o,−,0).
Similarly as in [2, 3] with each determining pair (ε ∗,W) we can associate the so-called simplest representation \(P_{(\varepsilon^{*},W)}\) of (G,o) which assigns to each element g∈G the n-place function \(P_{(\varepsilon^{*},W)}(g)\) defined on \(\mathcal{H}=\mathcal{H}_{0}\cup\{\{e_{1}\},\ldots,\{e_{n}\}\}\), where \(\mathcal{H}_{0}\) is the set of all ε-classes of G different from W such that
for \((H_{1},\ldots,H_{n})\in\mathcal{H}^{n}_{0}\cup \{(\{e_{1}\},\ldots,\{e_{n}\})\}\) and \(H\in\mathcal{H}\).
Each subtraction Menger algebra of rank n is isomorphic to some difference Menger algebra of n-place functions.
FormalPara ProofLet (G,o,−,0) be a subtraction Menger algebra of rank n. Then the sum
of the family \((P_{(\varepsilon^{*}_{a,b},W_{a,b})} )_{a,b\in G,\,a\nleq b}\) of simplest representations of (G,o) is a representation of (G,o).
Now we show that P is a representation of (G,o,−,0). Let \(\mathcal {H}_{0}\) be the set of all ε a,b -classes of G different from W a,b . Consider \(H_{1},\ldots,H_{n},H\in\mathcal{H}\), where \(\mathcal{H}=\mathcal{H}_{0}\cup\{\{e_{1}\},\ldots,\{e_{n}\}\}\), such that \((H_{1},\ldots,H_{n},H)\in P_{(\varepsilon^{*}_{a,b},W_{a,b})}(g_{1}-g_{2})\) for some g 1,g 2∈G. Then, obviously, (g 1−g 2)[H 1…H n ]⊂H≠W a,b . Thus \((g_{1}-g_{2})[\bar{x}]\in H\) for each \(\bar{x}\in H_{1}\times\cdots\times H_{n}\), which, by (11), gives \(g_{1}[\bar{x}]-g_{2}[\bar{x}]\in H\). But \(g_{1}[\bar{x}]-g_{2}[\bar {x}]\leq g_{1}[\bar{x}]\) and H is a filter (Proposition 11), hence \(g_{1}[\bar{x}]\in H\). Thus \((g_{1}[\bar{x}]-g_{2}[\bar{x}])\curlywedge g_{2}[\bar{x}]=0\), by (33). Consequently, \((g_{1}[\bar{x}]-g_{2}[\bar{x}])\curlywedge g_{2}[\bar{x}]\in W_{a,b}\), because the other ε a,b -classes as filters do not contain 0. This means that \(g_{1}[\bar{x}]-g_{2}[\bar{x}]\not\equiv g_{2}[\bar {x}](\varepsilon_{a,b})\). Hence, \(g_{2}[\bar{x}]\notin H\). Therefore g 1[H 1…H n ]⊂H and g 2[h 1…H n ]∩H=∅, which implies
In this way, we have proved the inclusion
To show the reverse inclusion let
Then \((H_{1},\ldots,H_{n},H)\in P_{(\varepsilon^{*}_{a,b},W_{a,b})}(g_{1})\) and \((H_{1},\ldots,H_{n},H)\notin P_{(\varepsilon^{*}_{a,b},W_{a,b})}(g_{2})\), i.e., g 1[H 1…H n ]⊂H and g 2[H 1…H n ]∩H=∅. Thus \(g_{1}[\bar{x}]\in H\) and \(g_{2}[\bar{x}]\notin H\) for all \(\bar{x}\in H_{1}\times\cdots\times H_{n}\). Since from \(g_{1}[\bar {x}]\curlywedge g_{2}[\bar{x}]\notin W_{a,b}\), it follows \(g_{1}[\bar {x}]\equiv g_{2}[\bar{x}](\varepsilon_{a,b})\) and \(g_{2}[\bar{x}]\in H\), which is a contradiction, we conclude that \(g_{1}[\bar{x}]\curlywedge g_{2}[\bar{x}]\in W_{a,b}\).
If \(g_{1}[\bar{x}]-g_{2}[\bar{x}]\in W_{a,b}\), then, by (53) and Proposition 12, we obtain \(g_{1}[\bar{x}]=(g_{1}[\bar{x}]\curlywedge g_{2}[\bar{x}])\curlyvee(g_{1}[\bar {x}]-g_{2}[\bar{x}])\in W_{a,b}\). Consequently, \(g_{1}[\bar{x}]\in W_{a,b}\), which is impossible because \(g_{1}[\bar{x}]\in H\). Thus, \((g_{1}[\bar{x}]-g_{2}[\bar{x}])\curlywedge g_{1}[\bar{x}]=g_{1}[\bar{x}]-g_{2}[\bar{x}]\notin W_{a,b}\). Hence, \(g_{1}[\bar {x}]-g_{2}[\bar{x}]\equiv g_{1}[\bar{x}](\varepsilon_{a,b})\). This implies \((g_{1}-g_{2})[\bar{x}]=g_{1}[\bar{x}]-g_{2}[\bar{x}]\in H\). Therefore, (g 1−g 2)[H 1…H n ]⊂H, i.e., \((H_{1},\ldots,H_{n},H)\in P_{(\varepsilon^{*}_{a,b},W_{a,b})}(g_{1}-g_{2})\). So, we have proved
This together with (64) proves
which means that P(g 1−g 2)=P(g 1)∖P(g 2) for g 1,g 2∈G. Further, P(0)=P(0−0)=P(0)∖P(0)=∅. So, P is a representation of (G,o,−,0) by n-place functions.
We show that this representation is faithful. Let P(g 1)=P(g 2) for some g 1,g 2∈G. If g 1≠g 2, then both inequalities g 1≤g 2 and g 2≤g 1 at the same time are impossible. Suppose that g 1≰g 2. Then \(g_{1}\in F_{g_{1},g_{2}}\) and, consequently,
Since \(P_{(\varepsilon^{*}_{g_{1},g_{2}},W_{g_{1},g_{2}})}(g_{1})=P_{(\varepsilon ^{*}_{g_{1},g_{2}},W_{g_{1},g_{2}})}(g_{2})\), then, obviously,
Thus \(\{g_{2}\}=g_{2}[\{e_{1}\}\ldots\{e_{n}\}]\subset F_{g_{1},g_{2}}\), hence \(g_{2}\in F_{g_{1},g_{2}}\). This is a contradiction because \(F_{g_{1},g_{2}}\) is a filter containing g 1 but not containing g 2. The case g 2≰g 1 is analogous. So, the supposition g 1≠g 2 is not true. Hence g 1=g 2 and P is a faithful representation. The theorem is proved. □
Notes
Recall that a quasiorder is a reflexive and transitive binary relation.
In the case of semigroups the fact that ω is weakly steady can be deduced directly from the axioms of a weak subtraction semigroup (cf. [7]).
To reduce the number of brackets we will write x⋏y−z instead of (x⋏y)−z.
References
Abbott, J.C.: Sets, Lattices and Boolean Algebras. Allyn & Bacon, Boston (1969)
Dudek, W.A., Trokhimenko, V.S.: Menger Algebras of Multiplace Functions. Centrul Ed. USM, Chişinǎu (2006) (Russian)
Dudek, W.A., Trokhimenko, V.S.: Algebras of Multiplace Functions. De Gruyter/Versita, Berlin/London (2010)
Dudek, W.A., Trokhimenko, V.S.: Menger algebras of n-place functions. In: Proc. Intern. Confer. Algebra 2010. Advances in Algebraic Structures, pp. 198–218. World Scientific, Singapore (2011)
Iséki, K.: On implicative BCK-algebras. Math. Semin. Notes, Kobe Univ. 4, 9–10 (1976)
Kim, Y.H., Kim, H.S.: Subtraction algebras and BCK-algebras. Math. Bohem. 1, 21–24 (2003)
Schein, B.M.: Difference semigroups. Commun. Algebra 20, 2153–2169 (1992)
Schein, B.M., Trohimenko, V.S.: Algebras of multiplace functions. Semigroup Forum 17, 1–64 (1979)
Trokhimenko, V.S.: Ordered algebras of multiplace functions. Izv. Vysš. Učebn. Zaved., Mat. 104, 90–98 (1971) (Russian)
Trokhimenko, V.S.: A characterization of \(\mathcal{P}\)-algebras of multiplace functions. Sib. Math. J. 16, 461–470 (1976). Translation from Sibirsk. Mat. Zh. 16, 599–611 (1975)
Trokhimenko, V.S., Schein, B.M.: Compatible algebras of multiplace functions. Teor. Polugrupp Prilozh. 4, 89–98 (1978) (Izdat. Saratov. Gos. Univ.) (Russian)
Open Access
This article is distributed under the terms of the Creative Commons Attribution License which permits any use, distribution, and reproduction in any medium, provided the original author(s) and the source are credited.
Author information
Authors and Affiliations
Corresponding author
Additional information
Communicated by Mikhail Volkov.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 2.0 International License (https://creativecommons.org/licenses/by/2.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
About this article
Cite this article
Dudek, W.A., Trokhimenko, V.S. Subtraction Menger algebras. Semigroup Forum 85, 111–128 (2012). https://doi.org/10.1007/s00233-012-9396-0
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00233-012-9396-0