Pro jection representable relations on Menger ( 2 , n ) -semigroups 2000 Mathematics Sub ject Classification: 20N15, 08N05. Keywords: n -place function, algebra of functions, Menger algebra, ( 2 , n ) -semigroup. , , November 27, 2006

1 Introduction

Investigation of partial multiplace functions by algebraic methods plays an important role in modern mathematics where we consider various operations on sets of functions which are naturally defined. The basic operation for

n

-place functions is a superposition (composition)

O

n + 1

such functions, but there are some other naturally defined operations, which are also worth considering. In this paper we consider binary Mann's compositions

\oplus 1, \dots, \oplus n

for partial

n

-place functions introduced in [2] , which have many important applications for the studies of binary and

n

-ary operations. Algebras of

n

-place functions closed with respect to these compositions were investigated, for example, in [8] and [12] .

2 Preliminaries and notations

Let

A^{n}

be the

n

-th Cartesian product 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

ℱ (A^{n}, A)

. On

ℱ (A^{n}, A)

we define the superposition (composition) of

n

-place functions

O : (f, g_{1}, \dots, g_{n}) \mapsto f [g_{1} \dots g_{n}]

and

n

binary compositions

\oplus 1, \dots, \oplus n

putting

\begin{matrix} f [g_{1} \dots g_{n}] (a_{1}, \dots, a_{n}) = f (g_{1} (a_{1}, \dots, a_{n}), \dots, g_{n} (a_{1}, \dots, a_{n})), \end{matrix}

(1)

\begin{matrix} (f \oplus i g) (a_{1}, \dots, a_{n}) = f (a_{1}, \dots, a_{i - 1}, g (a_{1}, \dots, a_{n}), a_{i + 1}, \dots, a_{n}), \end{matrix}

(2)

for all

f, g, g_{1}, \dots, g_{n} \in ℱ (A^{n}, A)

and

(a_{1}, \dots, a_{n}) \in A^{n}

, where left and right side of (1 ) and (2 ) are defined or not defined simultaneously.

Since, as it is not difficult to verify, each composition

\oplus i

is an associative operation, algebras of the form

(Φ; \oplus 1, \dots, \oplus n)

and

(Φ; O, \oplus 1, \dots, \oplus n)

, where

Φ \subset ℱ (A^{n}, A)

, are called respectively

(2, n)

-semigroups and Menger

(2, n)

-semigroups of

n

-place functions.

According to the general convention used in the theory of

n

-ary systems, the sequence

x_{i}, x_{i + 1}, \dots, x_{j}

, where

i ⩽ j

, can be written as

x_{i}^{j}

(for

i > j

it is the empty symbol). In this convention (1 ) and (2 ) can be written as

\begin{matrix} f [g_{1}^{n}] (a_{1}^{n}) = f (g_{1} (a_{1}^{n}), \dots, g_{n} (a_{1}^{n})), \end{matrix}

\begin{matrix} (f \oplus i g) (a_{1}^{n}) = f (a_{1}^{i - 1}, g (a_{1}^{n}), a_{i + 1}^{n}) . \end{matrix}

An algebra

(G; o)

with one

(n + 1)

-ary operation

o

satisfying the identity

o (o (x_{0}^{n}), y_{1}^{n}) = o (x_{0}, o (x_{1}, y_{1}^{n}), \dots, o (x_{n}, y_{1}^{n}))

is called a Menger algebra of rank

n

(cf. [1] , [7] ). Such operation is called superassociative and by many authors is written as

o (x_{0}^{n}) = x_{0} [x_{1}^{n}]

. In this convention the above identity has the form

\begin{matrix} x_{0} [x_{1}^{n}] [y_{1}^{n}] = x_{0} [x_{1} [y_{1}^{n}] \dots x_{n} [y_{1}^{n}]] . \end{matrix}

(3)

It is clear that a Menger algebra of rank

1

is an arbitrary semigroup.

Let

{\oplus 1, \dots, \oplus n}

be a collection of associative binary operations defined on

G

. According to [8] and [12] , an algebra

(G; \oplus 1, \dots, \oplus n)

is called a

(2, n)

-semigroup. By a Menger

(2, n)

-semigroup we mean an algebra

(G; o, \oplus 1, \dots, \oplus n)

, where

(G; o)

is a Menger algebra of rank

n

and

(G; \oplus 1, \dots, \oplus n)

is a

(2, n)

-semigroup. Any homomorphism of a (Menger)

(2, n)

-semigroup onto some (Menger)

(2, n)

-semigroup of

n

-place functions is called a representation by

n

-place functions. A representation is faithful if it is an isomorphism.

The symbol

μ_{i} (\oplus i_{s} i_{1} x_{1}^{s})

, where

x_{1}, \dots, x_{s} \in G

and

\oplus i_{1}, \dots, \oplus i_{s}

are binary operations defined on

G

, denotes an element

x_{i_{k}} \oplus i_{s} i_{k + 1} x_{k + 1}^{s}

i = i_{k}

and

i \neq i_{p}

for all

p < k ⩽ s

. If

i \neq i_{p}

for all

i_{p} \in {i_{1}, \dots, i_{s}}

this symbol is empty. For example,

μ_{1} (\oplus 2 x \oplus 1 y \oplus 3 z) = y \oplus 3 z

μ_{2} (\oplus 2 x \oplus 1 y \oplus 3 z) = x \oplus 1 y \oplus 3 z

μ_{3} (\oplus 2 x \oplus 1 y \oplus 3 z) = z

. The symbol

μ_{4} (\oplus 2 x \oplus 1 y \oplus 3 z)

is empty.

In [8] it is proved that a

(2, n)

-semigroup

(G; \oplus 1, \dots, \oplus n)

has a faithful representation by

n

-place functions if and only if it satisfies the implication

\begin{matrix} ⋀_{i = 1}^{n} (μ_{i} (\oplus i_{s} i_{1} x_{1}^{s}) = μ_{i} (\oplus j_{k} j_{1} y_{1}^{k})) ⟶ g \oplus i_{s} i_{1} x_{1}^{s} = g \oplus j_{k} j_{1} y_{1}^{k} . \end{matrix}

(4)

For Menger

(2, n)

-semigroups the following identities must be satisfied additionally

\begin{matrix} (x \oplus i y) [z_{1}^{n}] = x [z_{1}^{i - 1} y [z_{1}^{n}] z_{i + 1}^{n}], \end{matrix}

(5)

\begin{matrix} x [y_{1}^{n}] \oplus i z = x [y_{1} \oplus i z \dots y_{n} \oplus i z], \end{matrix}

(6)

\begin{matrix} x \oplus i_{s} i_{1} y_{1}^{s} = x [μ_{1} (\oplus i_{s} i_{1} y_{1}^{s}) \dots μ_{n} (\oplus i_{s} i_{1} y_{1}^{s})], \end{matrix}

(7)

where

{i_{1}, \dots, i_{s}} = {1, \dots, n}

and

i = 1, \dots, n

. In the sequel, any (Menger)

(2, n)

-semigroup satisfying the condition (4 ) (respectively, (4 ), (5 ), (6 ) and (7 )) will be called representable.

Let

Φ

be some set of

n

-place functions, i.e.

Φ \subset ℱ (A^{n}, A)

. Consider the following three binary relations on

Φ

\begin{matrix} χ_{Φ} = {(f, g) \in Φ \times Φ | pr 1 f \subset pr 1 g}, \end{matrix}

\begin{matrix} γ_{Φ} = {(f, g) \in Φ \times Φ | pr 1 f \cap pr 1 g \neq \emptyset}, \end{matrix}

\begin{matrix} π_{Φ} = {(f, g) \in Φ \times Φ | pr 1 f = pr 1 g}, \end{matrix}

where

pr 1 f

is the domain of

f

, called respectively: inclusion of domains, co-definability and equality of domains.

Abstract characterizations of such relations for semigroups of transformations were studied in [4] , [5] , [6] and for Menger algebras of

n

-place functions in [9] , [10] , [11] . In this paper these relations will be characterized in

(2, n)

-semigroups and Menger

(2, n)

-semigroups of

n

-place functions.

Consider a representable (Menger)

(2, n)

-semigroup

(G; \oplus 1, \dots, \oplus n)

(respectively,

(G; o, \oplus 1, \dots, \oplus n)

) and its representation

P

n

-place functions. On the set

G

we define the following three binary relations:

\begin{matrix} χ_{P} = {(g_{1}, g_{2}) | pr 1 P (g_{1}) \subset pr 1 P (g_{2})}, \end{matrix}

\begin{matrix} γ_{P} = {(g_{1}, g_{2}) | pr 1 P (g_{1}) \cap pr 1 P (g_{2}) \neq \emptyset}, \end{matrix}

\begin{matrix} π_{P} = {(g_{1}, g_{2}) | pr 1 P (g_{1}) = pr 1 P (g_{2})} . \end{matrix}

It is not difficult to see that

χ_{P}

is a quasi-order and

π_{P}

is an equivalence such that

π_{P} = χ_{P} \cap χ_{P}^{- 1}

, where

χ_{P}^{- 1} = {(b, a) | (a, b) \in χ_{P}}

Let

(P_{i})_{i \in I}

be a family of representations of a representable

(2, n)

-semigroup

(G; \oplus 1, \dots, \oplus n)

(respectively, representable Menger

(2, n)

-semigroup

(G; o, \oplus 1, \dots, \oplus n)

) by

n

-place functions defined on sets

(A_{i})_{i \in I}

respectively, where the sets

A_{i}

are pairwise disjoint. The sum of

(P_{i})_{i \in I}

is the mapping

P : g \mapsto P (g)

, denoted by

\sum_{i \in I} P_{i}

, where

P (g)

is an

n

-place function on

A = \cup_{i \in I} A_{i}

such that

P (g) = \cup_{i \in I} P_{i} (g)

for every

g \in G

. The sum of a family of representations by

n

-place functions is also a representation by

n

-place functions and

\begin{matrix} χ_{P} = ⋂_{i \in I} χ_{P_{i}}, γ_{P} = ⋃_{i \in I} γ_{P_{i}}, π_{P} = ⋂_{i \in I} π_{P_{i}} . \end{matrix}

(8)

Let

0

be a zero of a

(2, n)

-semigroup

(G; \oplus 1, \dots, \oplus n)

(respectively, Menger

(2, n)

-semigroup

(G; o, \oplus 1, \dots, \oplus n)

), i.e.

0 \oplus i g = g \oplus i 0 = 0

(respectively,

0 \oplus i g = g \oplus i 0 = 0

and

0 [g_{1}^{n}] = g [g_{1}^{i - 1} 0 g_{i + 1}^{n}] = 0

) for all

i = 1, \dots, n

and

g, g_{1}, \dots, g_{n} \in G

. We say that a binary relation

ρ \subset G \times G

0

-reflexive, if

(g, g) \in ρ

for all

g \in G \ {0}

. A symmetric relation

ρ

which is reflexive if

0 \in pr 1 ρ

, and

0

-reflexive if

0 \notin pr 1 ρ

, is called a

0

-quasi-equivalence.

A binary relation

Δ

on a Menger

(2, n)

-semigroup

(G; o, \oplus 1, \dots, \oplus n)

is called:

∙ $l$ -regular, if
$\begin{matrix} x Δ y ⟶ x [z_{1}^{n}] Δ y [z_{1}^{n}], \end{matrix}$ (9)

$\begin{matrix} x Δ y ⟶ x \oplus i z Δ y \oplus i z \end{matrix}$ (10)
for all $i = 1, \dots, n$ and $x, y, z, z_{1}, \dots, z_{n} \in G$ ,
∙ $l$ -cancellative, if
$\begin{matrix} x [z_{1}^{n}] Δ y [z_{1}^{n}] ⟶ x Δ y, \end{matrix}$ (11)

$\begin{matrix} x \oplus i z Δ y \oplus i z ⟶ x Δ y \end{matrix}$ (12)
for all $i = 1, \dots, n$ and $x, y, z, z_{1}, \dots, z_{n} \in G$ ,

∙

v

-negative, if

\begin{matrix} x [y_{1}^{n}] Δ y_{i}, i = 1, \dots, n, \end{matrix}

(13)

\begin{matrix} x \oplus i_{s} i_{1} y_{1}^{s} Δ μ_{j} (\oplus i_{s} i_{1} y_{1}^{s}) \end{matrix}

(14)

for all

x, y_{1}, \dots, y_{k} \in G

k = m a x {n, s}

and

j \in {i_{1}, \dots, i_{s}}

In the case of

(2, n)

-semigroups these relations are defined only by (10 ), (12 ) and (14 ), respectively.

3 Pro jection representable relations on Menger $(2, n)$ -semigroups

Let

G = (G; o, \oplus 1, \dots, \oplus n)

be a representable Menger

(2, n)

-semigroup,

χ

γ

π

– binary relations on

G

. We say that the triplet

(χ, γ, π)

is (faithful) projection representable for

G

, if there exists such (faithful) representation

P

G

n

-place functions for which

χ = χ_{P}

γ = γ_{P}

and

π = π_{P}

Analogously we define projection representable pairs and separate relations.

In the sequel, instead of

(g_{1}, g_{2}) \in χ

(g_{1}, g_{2}) \in γ

and

(g_{1}, g_{2}) \in π

we will write

g_{1} ⊏ g_{2}

g_{1} ⊤ g_{2}

and

g_{1} \equiv g_{2}

, respectively.

Theorem 1. A triplet

(χ, γ, π)

of binary relations on

G

is projection representable for a representable Menger

(2, n)

-semigroup

G

if and only if the following conditions are satisfied:

(a)

χ

is an

l

-regular and

v

-negative quasi-order,

(b)

γ

is an

l

-cancellative

0

-quasi-equivalence,

(c)

π = χ \cap χ^{- 1}

and

\begin{matrix} h_{1} ⊤ h_{2} \land h_{1} ⊏ g_{1} \land h_{2} ⊏ g_{2} ⟶ g_{1} ⊤ g_{2} \end{matrix}

(15)

for all

h_{1}, h_{2}, g_{1}, g_{2} \in G

Proof. Necessity. Let $(Φ; O, \oplus 1, \dots, \oplus n)$ be a Menger $(2, n)$ -semigroup of $n$ -place functions determined on the set $A$ . Let us show that the triplet $(χ_{Φ}, γ_{Φ}, π_{Φ})$ satisfies all the conditions of the theorem.
At first we prove the condition $(a)$ . The relation $χ_{Φ}$ is obviously a quasi-order. Let $f, g, h_{1}, \dots, h_{n} \in Φ$ and $(f, g) \in χ_{Φ}$ , i.e. $pr 1 f \subset pr 1 g$ .
Suppose that $\bar{a} \in pr 1 f [h_{1}^{n}]$ for some $\bar{a} \in A^{n}$ . Then ${f [h_{1}^{n}] (\bar{a})} \neq \emptyset$ , i.e.
${f (h_{1} (\bar{a}), \dots h_{n} (\bar{a}))} \neq \emptyset$ . Thus $(h_{1} (\bar{a}), \dots h_{n} (\bar{a})) \in pr 1 f$ and, in the consequence, $(h_{1} (\bar{a}), \dots h_{n} (\bar{a})) \in pr 1 g$ . Therefore ${g (h_{1} (\bar{a}), \dots h_{n} (\bar{a}))} \neq \emptyset$ , whence ${g [h_{1}^{n}] (\bar{a})} \neq \emptyset$ , i.e. $\bar{a} \in pr 1 g [h_{1}^{n}]$ . So, $pr 1 f [h_{1}^{n}] \subset pr 1 g [h_{1}^{n}]$ , which implies $(f [h_{1}^{n}], g [h_{1}^{n}]) \in χ_{Φ}$ . Similarly we can prove that for all $f, g, h \in Φ$ and $i = 1, \dots, n$ , from $(f, g) \in χ_{Φ}$ it follows $(f \oplus i h, g \oplus i h) \in χ_{Φ}$ . This means that the relation $χ_{Φ}$ is $l$ -regular. The proof of the $v$ -negativity is analogous.
To prove $(b)$ let $Θ$ be a zero of a Menger $(2, n)$ -semigroup $(Φ; O, \oplus 1, \dots, \oplus n)$ . If $Θ \neq \emptyset$ , then $pr 1 Θ \neq \emptyset$ , whence $(Θ, Θ) \in γ_{Φ}$ .
Thus $Θ \in pr 1 γ_{Φ}$ . So, in this case $γ_{Φ}$ is reflexive. For $Θ = \emptyset$ we have $pr 1 Θ = \emptyset$ . Therefore $Θ \notin pr 1 γ_{Φ}$ , i.e. $(f, f) \in γ_{Φ}$ for every $f \neq Θ$ . Hence $γ_{Φ}$ is $Θ$ -reflexive. Since $γ_{Φ}$ is symmetric, the above means that $γ_{Φ}$ is a $Θ$ -quasi-equivalence.
Suppose now that $(f [h_{1}^{n}], g [h_{1}^{n}]) \in γ_{Φ}$ for some $f, g \in Φ$ , $h_{1}^{n} \in Φ^{n}$ . Then $pr 1 f [h_{1}^{n}] \cap pr 1 g [h_{1}^{n}] \neq \emptyset$ , i.e. there exists $\bar{a} \in A^{n}$ such that $\bar{a} \in pr 1 f [h_{1}^{n}]$ and $\bar{a} \in pr 1 g [h_{1}^{n}]$ . Therefore ${f [h_{1}^{n}] (\bar{a})} \neq \emptyset$ and ${g [h_{1}^{n}] (\bar{a})} \neq \emptyset$ . Thus ${f (h_{1} (\bar{a}), \dots h_{n} (\bar{a}))} \neq \emptyset$ and ${g (h_{1} (\bar{a}), \dots h_{n} (\bar{a}))} \neq \emptyset$ , which shows that $(h_{1} (\bar{a}), \dots, h_{n} (\bar{a})) \in pr 1 f \cap pr 1 g$ . So, $(f, g) \in γ_{Φ}$ . Analogously, for $f, g, h \in Φ$ , $i = 1, \dots, n$ , from $(f \oplus i h, g \oplus i h) \in γ_{Φ}$ it follows $(f, g) \in γ_{Φ}$ . So, $γ_{Φ}$ is $l$ -cancellative.
Since in $(c)$ the first condition is obvious, we prove $(15)$ only. For this let $(h_{1}, h_{2}) \in γ_{Φ}$ , $(h_{1}, g_{1}) \in χ_{Φ}$ and $(h_{2}, g_{2}) \in χ_{Φ}$ for some $h_{1}, h_{2}, g_{1}, g_{2} \in Φ$ .
Then $pr 1 h_{1} \cap pr 1 h_{2} \neq \emptyset$ , $pr 1 h_{1} \subset pr 1 g_{1}$ and $pr 1 h_{2} \subset pr 1 g_{2}$ , whence $\emptyset \neq pr 1 h_{1} \cap pr 1 h_{2} \subset pr 1 g_{1} \cap pr 1 g_{2}$ . Thus $pr 1 g_{1} \cap pr 1 g_{2} \neq \emptyset$ , i.e. $(g_{1}, g_{2}) \in γ_{Φ}$ , which proves (15 ) and completes the proof of the necessity of the conditions formulated in the theorem.

To prove the sufficiency of these conditions we must introduce some additional constructions. Consider the triplet

(χ, γ, π)

of binary relations on a representable Menger

(2, n)

-semigroup

G = (G; o, \oplus 1, \dots, \oplus n)

satisfying all the conditions of the theorem. Let

e_{1}, \dots, e_{n}

be pairwise different elements not belonging to

G

. For all

x_{1}, \dots, x_{s} \in G

i = 1, \dots, n

, and operations

\oplus i_{1}, \dots, \oplus i_{s}

defined on

G

μ_{i}^{*} (\oplus i_{s} i_{1} x_{1}^{s})

we denote an element of

G^{*} = G \cup {e_{1}, \dots, e_{n}}

such that

μ_{i}^{*} (\oplus i_{s} i_{1} x_{1}^{s}) = {\begin{matrix} μ_{i} (\oplus i_{s} i_{1} x_{1}^{s}), & if i \in {i_{1}, \dots, i_{s}}, \\ e_{i}, & if i \notin {i_{1}, \dots, i_{s}} . \end{matrix}

Consider the set

A^{*} = G^{n} \cup A_{0} \cup {(e_{1}, \dots, e_{n})}

, where

A_{0}

is the collection of all

n

-tuples

(x_{1}, \dots, x_{n}) \in (G^{*})^{n}

for which there exists

y_{1}, \dots, y_{s} \in G

and

i_{1}, \dots, i_{n} \in {1, \dots, n}

such that

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

. Let

(h_{1}, h_{2}) \in G^{2}

be fixed. For each

g \in G

we define a partial

n

-place function

P_{(h_{1}, h_{2})} (g) : A^{*} \to G

such that

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g) ⟷ {\begin{matrix} h_{1} ⊏ g [x_{1}^{n}] \lor h_{2} ⊏ g [x_{1}^{n}] & if x_{1}^{n} \in G^{n}, \\ h_{1} ⊏ g \lor h_{2} ⊏ g & if x_{1}^{n} = e_{1}^{n}, \\ h_{1} ⊏ g \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g \oplus i_{s} i_{1} y_{1}^{s} & if x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s}), \\ i = 1, \dots, n, for \\ some y_{1}^{s} \in G^{s} and \\ i_{1} \dots, i_{s} \in {1, \dots, n} . \end{matrix}

For

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g)

we put

\begin{matrix} P_{(h_{1}, h_{2})} (g) (x_{1}^{n}) = {\begin{matrix} g [x_{1}^{n}] & if x_{1}^{n} \in G^{n}, \\ g & if x_{1}^{n} = e_{1}^{n}, \\ g \oplus i_{s} i_{1} y_{1}^{s} & if x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s}), \\ i = 1, \dots, n, for \\ some y_{1}^{s} \in G^{s} and \\ i_{1} \dots, i_{s} \in {1, \dots, n} . \end{matrix} \end{matrix}

(16)

Let us show that

P_{(h_{1}, h_{2})}

is a representation of

G

n

-place functions.

Proposition 1. The function

P_{(h_{1}, h_{2})} (g)

is single-valued.

Proof. Let $x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g)$ , where $g, h_{1}, h_{2} \in G$ are fixed. Since for $x_{1}^{n} \in G^{n}$ and $x_{1}^{n} = e_{1}^{n}$ the value of $P_{(h_{1}, h_{2})} (g) (x_{1}^{n})$ is uniquely determined, we verify only the case when $x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})$ , $i = 1, \dots, n$ , for some $y_{1}^{s} \in G^{s}$ . If for some $z_{1}^{k} \in G^{k}$ and $j_{1}, \dots, j_{k} \in {1, \dots, n}$ we have also $x_{i} = μ_{i}^{*} (\oplus j_{k} j_{1} z_{1}^{k})$ , $i = 1, \dots, n$ , then $μ_{i} (\oplus i_{s} i_{1} y_{1}^{s}) = μ_{i} (\oplus j_{k} j_{1} z_{1}^{k})$ for every $i = 1, \dots, n$ , which, according to (4 ), implies $g \oplus i_{s} i_{1} y_{1}^{s} = g \oplus j_{k} j_{1} z_{1}^{k}$ . This means that also in this case $P_{(h_{1}, h_{2})} (g) (x_{1}^{n})$ is uniquely determined. Thus, the function $P_{(h_{1}, h_{2})} (g)$ is single-valued.

Proposition 2. For all

g, g_{1}, \dots, g_{n}, h_{1}, h_{2} \in G

we have

P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) = P_{(h_{1}, h_{2})} (g) [P_{(h_{1}, h_{2})} (g_{1}) \dots P_{(h_{1}, h_{2})} (g_{n})] .

Proof. Let

g, g_{1}, \dots, g_{n} \in G

and

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}])

. If

x_{1}^{n} \in G^{n}

, then

h_{1} ⊏ g [g_{1}^{n}] [x_{1}^{n}] \lor h_{2} ⊏ g [g_{1}^{n}] [x_{1}^{n}],

whence, applying the superassociativity (3 ), we obtain

\begin{matrix} h_{1} ⊏ g [g_{1} [x_{1}^{n}] \dots g_{n} [x_{1}^{n}]] \lor h_{2} ⊏ g [g_{1} [x_{1}^{n}] \dots g_{n} [x_{1}^{n}]] . \end{matrix}

(17)

This together with the

v

-negativity of

χ

implies

\begin{matrix} h_{1} ⊏ g_{i} [x_{1}^{n}] \lor h_{2} ⊏ g_{i} [x_{1}^{n}], i = 1, \dots, n . \end{matrix}

(18)

From (17 ) it follows that

(g_{1} [x_{1}^{n}], \dots, g_{n} [x_{1}^{n}]) \in pr 1 P_{(h_{1}, h_{2})} (g)

, from (18 ) that

x_{1}^{n} \in P_{(h_{1}, h_{2})} (g_{i})

i = 1, \dots, n

. So, if

x_{1}^{n} \in G^{n}

, then

\begin{matrix} x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) ⟷ {\begin{matrix} (g_{1} [x_{1}^{n}], \dots, g_{n} [x_{1}^{n}]) \in pr 1 P_{(h_{1}, h_{2})} (g), \\ \land_{i = 1}^{n} x_{1}^{n} \in P_{(h_{1}, h_{2})} (g_{i}) . \end{matrix} \end{matrix}

(19)

Analogously we can verify that

\begin{matrix} e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) ⟷ {\begin{matrix} (g_{1}, \dots, g_{n}) \in pr 1 P_{(h_{1}, h_{2})} (g), \\ \land_{i = 1}^{n} e_{1}^{n} \in P_{(h_{1}, h_{2})} (g_{i}) . \end{matrix} \end{matrix}

(20)

Now let

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

, for some

i_{1}, \dots, i_{s} \in {1, \dots, n}

and

y_{1}^{s} \in G^{s}

. Then

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}])

implies

h_{1} ⊏ g [g_{1}^{n}] \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g [g_{1}^{n}] \oplus i_{s} i_{1} y_{1}^{s},

which, by (6 ), is equivalent to

\begin{matrix} h_{1} ⊏ g [g_{1} \oplus i_{s} i_{1} y_{1}^{s} \dots g_{n} \oplus i_{s} i_{1} y_{1}^{s}] \lor h_{2} ⊏ g [g_{1} \oplus i_{s} i_{1} y_{1}^{s} \dots g_{n} \oplus i_{s} i_{1} y_{1}^{s}] . \end{matrix}

(21)

From this, applying the

v

-negativity of

χ

, we obtain

\begin{matrix} h_{1} ⊏ g_{i} \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g_{i} \oplus i_{s} i_{1} y_{1}^{s} \end{matrix}

(22)

for every

i = 1, \dots, n

The condition (21 ) is equivalent to

(g_{1} \oplus i_{s} i_{1} y_{1}^{s}, \dots, g_{n} \oplus i_{s} i_{1} y_{1}^{s}) \in pr 1 P_{(h_{1}, h_{2})} (g)

. The condition (22 ) shows that

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{i})

for every

i = 1, \dots, n

, where

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

. So,

\begin{matrix} x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) ⟷ {\begin{matrix} (g_{1} \oplus i_{s} i_{1} y_{1}^{s}, \dots, g_{n} \oplus i_{s} i_{1} y_{1}^{s}) \in pr 1 P_{(h_{1}, h_{2})} (g), \\ \land_{i = 1}^{n} x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{i}), \end{matrix} \end{matrix}

(23)

where

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

Let

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}])

. If

x_{1}^{n} \in G^{n}

, then, according to (16 ) and (19 ), we have

\begin{matrix} P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) (x_{1}^{n}) & = g [g_{1}^{n}] [x_{1}^{n}] = g [g_{1} [x_{1}^{n}] \dots g_{n} [x_{1}^{n}]] \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g) (g_{1} [x_{1}^{n}], \dots, g_{n} [x_{1}^{n}]) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g) (P_{(h_{1}, h_{2})} (g_{1}) (x_{1}^{n}), \dots, P_{(h_{1}, h_{2})} (g_{n}) (x_{1}^{n})) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g) [P_{(h_{1}, h_{2})} (g_{1}) \dots P_{(h_{1}, h_{2})} (g_{n})] (x_{1}^{n}) . \end{matrix}

Similarly, we can prove that

P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) (e_{1}^{n}) = [P_{(h_{1}, h_{2})} (g_{1}) \dots P_{(h_{1}, h_{2})} (g_{n})] (e_{1}^{n})

for

e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}])

. If

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g [g_{1}^{n}])

, where

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

, for some

y_{1}^{s} \in G^{s}

i_{1}, \dots, i_{s} \in {1, \dots, n}

, then, according to (16 ) and (23 ), we obtain

\begin{matrix} P_{(h_{1}, h_{2})} (g [g_{1}^{n}]) (x_{1}^{n}) & = g [g_{1}^{n}] \oplus i_{s} i_{1} y_{1}^{s} = g [g_{1} \oplus i_{s} i_{1} y_{1}^{s} \dots g_{n} \oplus i_{s} i_{1} y_{1}^{s}] \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g) (g_{1} \oplus i_{s} i_{1} y_{1}^{s}, \dots, g_{n} \oplus i_{s} i_{1} y_{1}^{s}) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g) (P_{(h_{1}, h_{2})} (g_{1}) (x_{1}^{n}), \dots, P_{(h_{1}, h_{2})} (g_{n}) (x_{1}^{n})) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g) [P_{(h_{1}, h_{2})} (g_{1}) \dots P_{(h_{1}, h_{2})} (g_{n})] (x_{1}^{n}) . \end{matrix}

The proof is complete.

Proposition 3. For all

g_{1}, g_{2}, h_{1}, h_{2} \in G

and

i = 1, \dots, n

we have

P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) = P_{(h_{1}, h_{2})} (g_{1}) \oplus i P_{(h_{1}, h_{2})} (g_{2}) .

Proof. Let

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2})

. If

x_{1}^{n} \in G^{n}

, then

h_{1} ⊏ (g_{1} \oplus i g_{2}) [x_{1}^{n}] \lor h_{2} ⊏ (g_{1} \oplus i g_{2}) [x_{1}^{n}],

which, by (5 ), is equivalent to

\begin{matrix} h_{1} ⊏ g_{1} [x_{1}^{i - 1} g_{2} [x_{1}^{n}] x_{i + 1}^{n}] \lor h_{2} ⊏ g_{1} [x_{1}^{i - 1} g_{2} [x_{1}^{n}] x_{i + 1}^{n}] . \end{matrix}

(24)

This, according to the

v

-negativity of

χ

, implies

\begin{matrix} h_{1} ⊏ g_{2} [x_{1}^{n}] \lor h_{2} ⊏ g_{2} [x_{1}^{n}] . \end{matrix}

(25)

The condition (24 ) means that

(x_{1}^{i - 1}, g_{2} [x_{1}^{n}], x_{i + 1}^{n}) \in pr 1 P_{(h_{1}, h_{2})} (g_{1})

. From (25 ) we obtain

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})

. So, for

x_{1}^{n} \in G^{n}

we have

\begin{matrix} x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) ⟷ {\begin{matrix} (x_{1}^{i - 1}, g_{2} [x_{1}^{n}], x_{i + 1}^{n}) \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) \\ x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2}) . \end{matrix} \end{matrix}

(26)

Consider now the case when

x_{1}^{n} = e_{1}^{n}

. In this case

e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2})

means, by (17 ), that

\begin{matrix} h_{1} ⊏ g_{1} \oplus i g_{2} \lor h_{2} ⊏ g_{1} \oplus i g_{2} . \end{matrix}

(27)

Because

g_{1} \oplus i g_{2} ⊏ μ_{i} (\oplus i g_{2}) = g_{2}

, by the

v

-negativity of

χ

, the above condition gives

\begin{matrix} h_{1} ⊏ g_{2} \lor h_{2} ⊏ g_{2} . \end{matrix}

(28)

But

μ_{i}^{*} (\oplus i g_{2}) = μ_{i} (\oplus i g_{2}) = g_{2}

and

μ_{k}^{*} (\oplus i g_{2}) = e_{k}

for

k \in {1, \dots, n} \ {i}

, so, (27 ) implies

(e_{1}^{i - 1}, g_{2}, e_{i + 1}^{n}) \in pr 1 P_{(h_{1}, h_{2})} (g_{1})

. On the other hand, from (28 ) it follows

e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})

. Therefore

\begin{matrix} e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) ⟷ {\begin{matrix} (e_{1}^{i - 1}, g_{2}, e_{i + 1}^{n}) \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) \\ e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2}) . \end{matrix} \end{matrix}

(29)

In the third case when

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

, for some

y_{1}^{s} \in G^{s}

i_{1}, \dots, i_{s} \in {1, \dots, n}

, from

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2})

we conclude

\begin{matrix} h_{1} ⊏ (g_{1} \oplus i g_{2}) \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ (g_{1} \oplus i g_{2}) \oplus i_{s} i_{1} y_{1}^{s} . \end{matrix}

(30)

Since

χ

v

-negative, we have

(g_{1} \oplus i g_{2}) \oplus i_{s} i_{1} y_{1}^{s} ⊏ μ_{i} (\oplus i g_{2} \oplus i_{s} i_{1} y_{1}^{s}) = g_{2} \oplus i_{s} i_{1} y_{1}^{s}

, which means that (30 ) can be written in the form

\begin{matrix} h_{1} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s} . \end{matrix}

(31)

But

μ_{i}^{*} (\oplus i g_{2} \oplus i_{s} i_{1} y_{1}^{s}) = μ_{i} (\oplus i g_{2} \oplus i_{s} i_{1} y_{1}^{s}) = g_{2} \oplus i_{s} i_{1} y_{1}^{s}

and

μ_{k}^{*} (\oplus i g_{2} \oplus i_{s} i_{1} y_{1}^{s}) = μ_{k}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

for

k \in {1, \dots, n} \ {i}

. This, together with the condition (30 ), proves

(x_{1}^{i - 1}, g_{2} \oplus i_{s} i_{1} y_{1}^{s}, x_{i + 1}^{n}) \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) .

Similarly, from (31 ) we can deduce

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2}) .

Therefore

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) ⟷ {\begin{matrix} (x_{1}^{i - 1}, g_{2} \oplus i_{s} i_{1} y_{1}^{s}, x_{i + 1}^{n}) \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) \\ x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2}), \end{matrix}

where

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

Let

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2})

. If

x_{1}^{n} \in G^{n}

, then, according to (16 ) and (26 ), we have

\begin{matrix} P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) (x_{1}^{n}) & = (g_{1} \oplus i g_{2}) [x_{1}^{n}] = g_{1} [x_{1}^{i - 1} g_{2} [x_{1}^{n}] x_{i + 1}^{n}] \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g_{1}) (x_{1}^{i - 1}, g_{2} [x_{1}^{n}], x_{i + 1}^{n}) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g_{1}) (x_{1}^{i - 1}, P_{(h_{1}, h_{2})} (g_{2}) (x_{1}^{n}), x_{i + 1}^{n}) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g_{1}) \oplus i P_{(h_{1}, h_{2})} (g_{2}) (x_{1}^{n}) . \end{matrix}

x_{1}^{n} = e_{1}^{n},

then, analogously as in the previous case, using (16 ) and (29 ) we obtain

P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) (e_{1}^{n}) = P_{(h_{1}, h_{2})} (g_{1}) \oplus i P_{(h_{1}, h_{2})} (g_{2}) (e_{1}^{n}) .

Similarly, in the case when

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

, for some

y_{1}^{s} \in G^{s}

i_{1}, \dots, i_{s} \in {1, \dots, n}

, we have

\begin{matrix} P_{(h_{1}, h_{2})} (g_{1} \oplus i g_{2}) (x_{1}^{n}) & = (g_{1} \oplus i g_{2}) \oplus i_{s} i_{1} y_{1}^{s} \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g_{1}) (x_{1}^{i - 1}, g_{2} \oplus i_{s} i_{1} y_{1}^{s}, x_{i + 1}^{n}) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g_{1}) (x_{1}^{i - 1}, P_{(h_{1}, h_{2})} (g_{2}) (x_{1}^{n}), x_{i + 1}^{n}) \end{matrix}

\begin{matrix} = P_{(h_{1}, h_{2})} (g_{1}) \oplus i P_{(h_{1}, h_{2})} (g_{2}) (x_{1}^{n}) . \end{matrix}

This completes our proof.

Basing on these propositions we are able to prove the sufficiency of the conditions of Theorem 1 .

Sufficiency. Let the triplet

(χ, γ, π)

of binary relations on a representable Menger

(2, n)

-semigroup

G = (G; o, \oplus 1, \dots, \oplus n)

satisfies all the conditions of the theorem. Then, as it follows from Propositions 1 –3 , for all

h_{1}, h_{2} \in G

, the mapping

P_{(h_{1}, h_{2})}

is a representation of

G

n

-place functions. Consider the family of representations

P_{(h_{1}, h_{2})}

such that

(h_{1}, h_{2}) \in γ

. Let

P

be the sum of this family, i.e.

P = \sum_{(h_{1}, h_{2}) \in γ} P_{(h_{1}, h_{2})}

. Of course,

P

is a representation of

G

n

-place functions. Let us show that

χ = χ_{P}

γ = γ_{P}

and

π = π_{P}

Let

(g_{1}, g_{2}) \in χ_{P}

. Then, according to (8 ), we have

(g_{1}, g_{2}) \in χ_{(h_{1}, h_{2})}

^$1$ for all

(h_{1}, h_{2}) \in γ

, i.e.

(\forall (h_{1}, h_{2}) \in γ) (pr 1 P_{(h_{1}, h_{2})} (g_{1}) \subset pr 1 P_{(h_{1}, h_{2})} (g_{2})),

which is equivalent to

(\forall (h_{1}, h_{2}) \in γ) (\forall x_{1}^{n}) (x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) ⟶ x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})) .

From this, for

x_{1}^{n} = e_{1}^{n}

, we obtain

(\forall (h_{1}, h_{2}) \in γ) (e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) ⟶ e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})),

which means that

(\forall (h_{1}, h_{2}) \in γ) (h_{1} ⊏ g_{1} \lor h_{2} ⊏ g_{1} ⟶ h_{1} ⊏ g_{2} \lor h_{2} ⊏ g_{2}) .

Let

g_{1} \neq 0

. Then

g_{1} ⊤ g_{1}

and the above implication gives

g_{1} ⊏ g_{1} ⟶ g_{1} ⊏ g_{2}

. This proves

(g_{1}, g_{2}) \in χ

because

χ

is reflexive. If

g_{1} = 0

, then

0 = 0 [g_{2} \dots g_{2}] ⊏ g_{2}

, by the

v

-negativity of

χ

. Hence

(0, g_{2}) \in χ

. So,

(g_{1}, g_{2}) \in χ

, i.e.

χ_{P} \subset χ

Conversely, let

(g_{1}, g_{2}) \in χ

(h_{1}, h_{2}) \in γ

and

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1})

. If

x_{1}^{n} \in G^{n}

, then

h_{1} ⊏ g_{1} [x_{1}^{n}] \lor h_{2} ⊏ g_{1} [x_{1}^{n}]

. Since the

l

-regularity of

χ

together with

g_{1} ⊏ g_{2}

implies

g_{1} [x_{1}^{n}] ⊏ g_{2} [x_{1}^{n}]

, from the above we conclude

h_{1} ⊏ g_{2} [x_{1}^{n}] \lor h_{2} ⊏ g_{2} [x_{1}^{n}]

, i.e.

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})

. Similarly, in the case

x_{1}^{n} = e_{1}^{n}

, from

e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1})

it follows

e_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})

. In the case when

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

, for some

y_{1}^{s} \in G^{s}

i_{1}, \dots, i_{s} \in {1, \dots, n}

, applying the

l

-regularity of

χ

g_{1} ⊏ g_{2}

, we obtain

g_{1} \oplus i_{s} i_{1} y_{1}^{s} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s}

, whence, in view of

h_{1} ⊏ g_{1} \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g_{1} \oplus i_{s} i_{1} y_{1}^{s}

, we obtain

h_{1} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s}

. Therefore

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})

, which proves

pr 1 P_{(h_{1}, h_{2})} (g_{1}) \subset pr 1 P_{(h_{1}, h_{2})} (g_{2})

for all

(h_{1}, h_{2}) \in γ

. Thus

(g_{1}, g_{2}) \in χ_{P}

, i.e.

χ \subset χ_{P}

. Consequently,

χ = χ_{P}

. This, together with the condition

(c)

formulated in the theorem, gives

π = χ \cap χ^{- 1} = χ_{P} \cap χ_{P}^{- 1} = π_{P}

. So,

π = π_{P}

Now let

(g_{1}, g_{2}) \in γ_{P}

. Then, according to (8 ), we have

(g_{1}, g_{2}) \in γ_{(h_{1}, h_{2})}

for some

(h_{1}, h_{2}) \in γ

, i.e.

(\exists (h_{1}, h_{2}) \in γ) (pr 1 P_{(h_{1}, h_{2})} (g_{1}) \cap pr 1 P_{(h_{1}, h_{2})} (g_{2}) \neq \emptyset),

which is equivalent to

(\exists (h_{1}, h_{2}) \in γ) (\exists x_{1}^{n}) (x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{1}) \land x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})} (g_{2})) .

This, for

x_{1}^{n} \in G^{n}

implies

h_{1} ⊏ g_{1} [x_{1}^{n}] \lor h_{2} ⊏ g_{1} [x_{1}^{n}]

and

h_{1} ⊏ g_{2} [x_{1}^{n}] \lor h_{2} ⊏ g_{2} [x_{1}^{n}]

. From the above, in view of

h_{1} ⊤ h_{2}

and (15 ), we obtain

g_{1} [x_{1}^{n}] ⊤ g_{2} [x_{1}^{n}]

, whence, applying the

l

-cancellativity of

γ

, we get

g_{1} ⊤ g_{2}

, i.e.

(g_{1}, g_{2}) \in γ

In the similar way, we can see that in the case

x_{1}^{n} = e_{1}^{n}

the condition

(g_{1}, g_{2}) \in γ

also holds.

x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s})

i = 1, \dots, n

, for some

y_{1}^{s} \in G^{s},

i_{1}, \dots, i_{s} \in {1, \dots, n}

, then

h_{1} ⊏ g_{1} \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g_{1} \oplus i_{s} i_{1} y_{1}^{s}

and

h_{1} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g_{2} \oplus i_{s} i_{1} y_{1}^{s}

, whence, by

h_{1} ⊤ h_{2}

and (15 ), we obtain

g_{1} \oplus i_{s} i_{1} y_{1}^{s} ⊤ g_{2} \oplus i_{s} i_{1} y_{1}^{s}

. This gives

g_{1} ⊤ g_{2}

because

γ

l

-cancellative. In this way we have proved that in any case

γ_{P} \subset γ

Conversely, let

(g_{1}, g_{2}) \in γ

. Since

χ

is reflexive,

g_{1} ⊏ g_{1}

and

g_{2} ⊏ g_{2}

, whence

g_{1} ⊏ g_{1} \lor g_{2} ⊏ g_{1}

and

g_{1} ⊏ g_{2} \lor g_{2} ⊏ g_{2}

. Consequently,

e_{1}^{n} \in pr 1 P_{(g_{1}, g_{2})} (g_{1})

and

e_{1}^{n} \in pr 1 P_{(g_{1}, g_{2})} (g_{2})

. Thus

(g_{1}, g_{2}) \in γ_{(g_{1}, g_{2})} \subset γ_{P}

, i.e.

γ \subset γ_{P}

. So,

γ = γ_{P}

This completes the proof of the theorem.

□

Problem 1. Find the necessary and sufficient conditions under which the triplet

(χ, γ, π)

of binary relations will be faithful projection representable for a representable Menger

(2, n)

-semigroup. Deleting from Theorem 1 the equality

π = χ \cap χ^{- 1}

we obtain the necessary and sufficient conditions under which the pair

(χ, γ)

of binary relations is projection representable for a representable Menger

(2, n)

-semigroup. Furthermore, all parts of the proof of this theorem connected with these two relations are valid. So, we have the following

Theorem 2. A pair

(χ, π)

of binary relations on

G

is projection representable for a representable Menger

(2, n)

-semigroup

G

if and only if

χ

is an

l

-regular and

v

-negative quasi-order,

γ

is an

l

-cancellative

0

-quasi-equivalence and the implication

(15)

is satisfied.

Problem 2. Find the necessary and sufficient conditions under which the pair

(χ, γ)

of binary relations will be faithful projection representable for a representable Menger

(2, n)

-semigroup.

Let

G = (G; o, \oplus 1, \dots, \oplus n)

be a representable Menger

(2, n)

-semigroup.

Let us consider on

G

the set

T_{n} (G)

of mappings

t : x \mapsto t (x)

defined as follows:

(a) $x \in T_{n} (G)$ , i.e. $T_{n} (G)$ contains the identity transformation of $G$ ,
(b) if $i \in {1, \dots, n}$ , $a, b_{1}, \dots, b_{i - 1}, b_{i + 1}, \dots, b_{n} \in G$ and $t (x) \in T_{n}$ , then $a [b_{1}^{i - 1} t (x) b_{i + 1}^{n}] \in T_{n}$ ,
(c) $T_{n}$ contains those and only those mappings which are defined by (a) and (b).

Let us consider on

G

two binary relations

δ_{1}

and

δ_{2}

defined in the following way:

1. $(g_{1}, g_{2}) \in δ_{1} ⟷ g_{1} = t (g_{2})$ for some $t \in T_{n}$ ,
2. $(g_{1}, g_{2}) \in δ_{2} ⟷ {\begin{matrix} g_{1} = (x \oplus i_{s} i_{1} y_{1}^{s}) [\bar{z}] a n d g_{2} = μ_{i} (\oplus i_{s} i_{1} y_{1}^{s}) [\bar{z}] f o r s o m e \\ x \in G, y_{1}^{s} \in G^{s}, \bar{z} \in G^{n}, i, i_{1}, \dots, i_{s} \in {1, \dots, n}, \\ w h e r e t h e s y m b o l [\bar{z}] c a n b e e m p t y . \end{matrix}$

It is not difficult to see that

δ_{1}

and

δ_{2}

are

l

-regular relations, additionally

δ_{1}

is a quasi-order. Moreover, a binary relation

ρ \subset G \times G

v

-negative if and only if it contains

δ_{1}

and

δ_{2}

Let

π

be an

l

-regular equivalence on a representable Menger

(2, n)

-semigroup

G

. Denote by

χ (π)

the binary relation

f_{t} (f_{R} (δ_{2}) \circ δ_{1} \circ π)

, where

f_{R}

and

f_{t}

are respectively reflexive and transitive closure operations (cf. [3] ), and

\circ

is a composition of relations, ^$2$ i.e.

\begin{matrix} χ (π) = f_{t} (f_{R} (δ_{2}) \circ δ_{1} \circ π) = ⋃_{n = 1}^{\infty} {((δ_{2} \cup △_{G}) \circ δ_{1} \circ π)}^{n} . \end{matrix}

(32)

Since

π

δ_{1}

and

f_{R} (δ_{2})

are reflexive

l

-regular relations,

χ (π)

is an

l

-regular quasi-order containing

π

δ_{1}

and

δ_{2}

. So,

χ (π)

is a

v

-negative quasi-order.

Proposition 4.

χ (π)

is the least

l

-regular and

v

-negative quasi-order containing

π

Proof. Let $χ$ be an arbitrary $l$ -regular and $v$ -negative quasi-order containing $π$ . Then $δ_{1} \subset χ$ and $δ_{2} \subset χ$ , because $χ$ is $v$ -negative. Thus, $π \subset χ$ , $δ_{1} \subset χ$ and $f_{R} (δ_{2}) \subset χ$ , whence $f_{R} (δ_{2}) \circ δ_{1} \circ π \subset χ^{3} \subset χ$ . From this, applying the transitivity of $χ$ , we obtain $(f_{R} (δ_{2}) \circ δ_{1} \circ π)^{n} \subset χ^{n} \subset χ$ for every natural $n$ .
Therefore $\cup_{n = 1}^{\infty} {((δ_{2} \cup △_{G}) \circ δ_{1} \circ π)}^{n} \subset χ$ , i.e. $χ (π) \subset χ$ .

Theorem 3. A pair

(γ, π)

of binary relations on a representable Menger

(2, n)

-semigroup

G

is projection representable if and only if

(a)

γ

is an

l

-cancellative

0

-quasi-equivalence,

(b)

π

is an

l

-regular equivalence such that

χ (π) \cap (χ (π))^{- 1} \subset π

(c)

the following condition

\begin{matrix} h_{1} ⊤ h_{2} \land h_{1} ⊏_{π} g_{1} \land h_{2} ⊏_{π} g_{2} ⟶ g_{1} ⊤ g_{2}, \end{matrix}

(33)

where

h ⊏_{π} g

means

(h, g) \in χ (π)

, is satisfied for all

g_{1}, g_{2}, h_{1}, h_{2} \in G

Proof. Let $P$ be such representation on a representable Menger $(2, n)$ -semigroup $G$ for which $γ = γ_{P}$ and $π = π_{P}$ . Then, by Proposition 3 , we have $χ (π) \subset χ_{P}$ , whence $χ (π) \cap (χ (π))^{- 1} \subset χ_{P} \cap χ_{P}^{- 1} = π_{P} = π$ .
Assume now that the premise of (33 ) is satisfied. Then $(h_{1}, h_{2}) \in γ$ , $(h_{1}, g_{1}) \in χ (π)$ and $(h_{2}, g_{2}) \in χ (π)$ . Consequently, $(h_{1}, h_{2}) \in γ_{P}$ , $(h_{1}, g_{1}) \in χ_{P}$ and $(h_{2}, g_{2}) \in χ_{P}$ , i.e. $pr 1 P (h_{1}) \cap pr 1 P (h_{2}) \neq \emptyset$ , $pr 1 P (h_{1}) \subset pr 1 P (g_{1})$ and $pr 1 P (h_{2}) \subset pr 1 P (g_{2})$ , whence $pr 1 P (g_{1}) \cap pr 1 P (g_{2}) \neq \emptyset$ . So, $(g_{1}, g_{2}) \in γ_{P} = γ$ , which means that the condition (33 ) is valid. The necessity is proved. To prove the sufficiency, assume that the pair $(γ, π)$ of binary relations satisfies all the conditions of the theorem and consider the triplet $(χ (π), γ, π)$ .
Then $π = π^{- 1} \subset (χ (π))^{- 1}$ , because $π \subset χ (π)$ . Therefore $π \subset χ (π) \cap (χ (π))^{- 1}$ , which, together with the condition $(b)$ , gives $π = χ (π) \cap (χ (π))^{- 1}$ .
This means that the triplet $(χ (π), γ, π)$ satisfies all the conditions of Theorem 1 . So, $(χ (π), γ, π)$ , and in the consequence, $(γ, π)$ is projection representable. The sufficiency is proved.

Problem 3. Find the necessary and sufficient conditions under which the pair

(γ, π)

of binary relations will be faithful projection representable.

Applying the method of mathematical induction to (32 ) we can prove the following proposition.

Proposition 5. The condition

(g_{1}, g_{2}) \in χ (π)

, where

g_{1}, g_{2} \in G

, means that the system of conditions

\begin{matrix} \begin{matrix} g_{1} = x_{0} \land g_{2} = x_{n}, \\ \land_{i = 0}^{n - 1} ((\begin{matrix} x_{i} \equiv t_{i} ((y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}]), \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}] \end{matrix}) \lor x_{i} \equiv t_{i} (x_{i + 1})) \end{matrix}} \end{matrix}

(34)

is valid for some

n \in N

x_{i}, y_{i}, z_{i} \in G

{\bar{w}}_{i} \in G^{n}

t_{i} \in T_{n}

k_{i} \in {1, \dots, n}

In the sequel the formula

⋀_{i = m}^{n} ((\begin{matrix} x_{i} \equiv t_{i} ((y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}]), \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}] \end{matrix}) \lor x_{i} \equiv t_{i} (x_{i + 1}))

will be denoted by

M (m, n)

The inclusion

χ (π) \cap (χ (π))^{- 1} \subset π

means that for all

g_{1}, g_{2} \in G

we have

(g_{1}, g_{2}) \in χ (π) \land (g_{2}, g_{1}) \in χ (π) ⟶ g_{1} \equiv g_{2},

which, according to Proposition 5 , can be written as the system of conditions

(A_{n, m})_{n, m \in N}

, where

A_{n, m} : M (0, n - 1) \land M (n + 1, n + m) \land x_{0} = x_{n + m} ⟶ x_{0} \equiv x_{n} .

The system

(A_{n, m})_{n, m \in N}

is equivalent to the system

(A_{n})_{n \in N}

, where

A_{n} : M (0, n - 1) \land x_{0} = x_{n} ⟶ x_{0} \equiv x_{1} .

Consider now the implication (33 ). According to (34 ) the condition

(h_{1}, g_{1}) \in χ (π)

means that

\begin{matrix} h_{1} = x_{0} \land M (0, n - 1) \land x_{n} = g_{1} \end{matrix}

(35)

for some

x_{i}, y_{i}, z_{k_{i}}, t_{i}, k_{i}, {\bar{w}}_{i}

. Similarly, the condition

(h_{2}, g_{2}) \in χ (π)

means that

\begin{matrix} h_{2} = x_{n + 1} \land M (n + 1, n + m) \land x_{n + m + 1} = g_{2} \end{matrix}

(36)

for some

x_{i}, y_{i}, z_{k_{i}}, t_{i}, k_{i}, {\bar{w}}_{i}

. So, (33 ) can be written as the system

(B_{n, m})_{n, m \in N}

of conditions

B_{n, m} : x_{0} ⊤ x_{n + 1} \land M (0, n - 1) \land M (n + 1, n + m) ⟶ x_{n} ⊤ x_{n + m + 1} .

In this way we have proved

Theorem 4. A pair

(γ, π)

of binary relations on a representable Menger

(2, n)

-semigroup

G

is projection representable if and only if

(a)

γ

is an

l

-cancellative

0

-quasi-equivalence,

(b)

π

is an

l

-regular equivalence,

(c)

the systems of conditions

(A_{n})_{n \in N}

and

(B_{n, m})_{n, m \in N}

are satisfied.

Theorem 5. A pair

(χ, π)

of binary relations is

(

faithful

)

projection representable for a representable Menger

(2, n)

-semigroup

G

if and only if

χ

is an

l

-regular and

v

-negative quasi-order such that

π = χ \cap χ^{- 1}

Proof. The necessity of these conditions follows from the proof of Theorem 1 .

To prove their sufficiency, for every element

g \in G

we define an

n

-place function

P_{a} (g) : A^{*} \to G

, where

a \in G

, putting

\begin{matrix} P_{a} (g) (x_{1}^{n}) = {\begin{matrix} g [x_{1}^{n}] & if a ⊏ g [x_{1}^{n}] and x_{1}^{n} \in G^{n}, \\ g & if a ⊏ g and x_{1}^{n} = e_{1}^{n}, \\ g \oplus i_{s} i_{1} y_{1}^{s} & if a ⊏ g \oplus i_{s} i_{1} y_{1}^{s} and x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s}), \\ i = 1, \dots, n, for some y_{1}^{s} \in G^{s}, \\ i_{1}, \dots, i_{s} \in {1, \dots, n} . \end{matrix} \end{matrix}

(37)

Since, for

h_{1} = h_{2} = a \in G,

the function

P_{(h_{1}, h_{2})} (g)

defined by (16 ) coincides with the function

P_{a} (g)

, from Propositions 1 – 3 it follows that the mapping

P_{a} : g \mapsto P_{a} (g)

is a representation of

G

n

-place functions. Further, analogously as in the proof of Theorem 1 , we can prove that

P_{0} = \sum_{a \in G} P_{a}

is a representation of

G

for which

χ = χ_{P_{0}}

and

π = π_{P_{0}}

. So, the pair

(χ, π)

is projection representable for

G

Let us show that

(χ, π)

is faithful projection representable. In [8] it is proved that each representable Menger

(2, n)

-semigroup has a faithful representation by

n

-place functions. Let

Λ

be such representation. Then obviously

χ_{Λ} = G \times G

and

π_{Λ} = G \times G

. Consider the representation

P = Λ + P_{0}

. Since

Λ

is a faithful representation,

P

is also faithful. Moreover

χ_{P} = χ_{Λ} \cap χ_{P_{0}} = G \times G \cap χ = χ

and

π_{P} = π_{Λ} \cap π_{P_{0}} = G \times G \cap π = π

. So,

(χ, π)

is faithful projection representable for

G

In the same manner, using the construction (37 ), we can prove the following theorem.

Theorem 6. A binary relation

χ

(

faithful

)

projection representable for a representable Menger

(2, n)

-semigroup if and only if it is an

l

-regular,

v

-negative quasi-order.

Theorem 7. A binary relation

π

(

faithful

)

projection representable for a representable Menger

(2, n)

-semigroup if and only if it is an

l

-regular equivalence such that

χ (π) \cap (χ (π))^{- 1} \subset π

Proof. Consider the pair $(χ (π), π)$ of binary relations, where $χ (π)$ is defined by (32 ). In a similar way, as in the proof of Theorem 3 , we can prove that this pair satisfies all the conditions of Theorem 5 , whence we conclude the validity of Theorem 7 .

Since, as it was showed above, the inclusion

χ (π) \cap (χ (π))^{- 1} \subset π

is equivalent to the system of conditions

(A_{n})_{n \in N}

, the last theorem can be rewritten in the form:

Theorem 8. A binary relation

π

(

faithful

)

projection representable for a representable Menger

(2, n)

-semigroup if and only if it is an

l

-regular equivalence and the system of conditions

(A_{n})_{n \in N}

is satisfied.

Consider on a Menger

(2, n)

-semigroup

G

the binary relation

χ_{0}

defined in the following way:

\begin{matrix} χ_{0} = f_{t} (f_{R} (δ_{2}) \circ δ_{1}) = ⋃_{n = 1}^{\infty} {((δ_{2} \cup △_{G}) \circ δ_{1})}^{n}, \end{matrix}

(38)

where

f_{t}

and

f_{R}

are reflexive and transitive closure operations.

Proposition 6.

χ_{0}

is the least

l

-regular and

v

-negative quasi-order on

G

The proof of this proposition is analogous to the proof of Proposition 3 .

Theorem 9. A binary relation

γ

is projection representable for a representable Menger

(2, n)

-semigroup if and only if it is an

l

-cancellative

0

-quasi-equivalence and the following implication

\begin{matrix} h_{1} ⊤ h_{2} \land h_{1} ⊏_{0} g_{1} \land h_{2} ⊏_{0} g_{2} ⟶ g_{1} ⊤ g_{2} \end{matrix}

(39)

is satisfied for all

h_{1}, h_{2}, g_{1}, g_{2} \in G

, where

h ⊏_{0} g

means

(h, g) \in χ_{0}

Proof. The necessity of (39 ) can be proved analogous as the necessity of (33 ) in the proof of Theorem 3 . To prove the sufficiency we consider the pair $(χ_{0}, γ)$ . By Proposition 6 , this pair satisfies all demands of Theorem 2 , whence we conclude the validity of Theorem 9 .

Problem 4. Find the necessary and sufficient conditions under which

γ

will be faithful projection representable.

Basing on the formula (38 ) we can prove the following proposition:

Proposition 7. From

(g_{1}, g_{2}) \in χ_{0}

, where

g_{1}, g_{2} \in G

, it follows that the system of conditions

g_{1} = x_{0} \land g_{2} = x_{n} \land ⋀_{i = 0}^{n - 1} ((\begin{matrix} x_{i} = t_{i} ((y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}]), \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}] \end{matrix}) \lor x_{i} = t_{i} (x_{i + 1}))

is valid for

n \in N

x_{i}, y_{i}, z_{i} \in G,

{\bar{w}}_{i} \in G^{n},

t_{i} \in T_{n}

k_{i} \in {1, \dots, n}

Denoting by

N (m, n)

the formula

⋀_{i = m}^{n} ((\begin{matrix} x_{i} = t_{i} ((y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}]), \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) [{\bar{w}}_{i}] \end{matrix}) \lor x_{i} = t_{i} (x_{i + 1})),

and using the same argumentation as in the proof of Theorem 4 , we can prove that the implication (39 ) is equivalent to the system of conditions

(C_{n, m})_{n, m \in N}

, where

C_{n, m} : x_{0} ⊤ x_{n + 1} \land N (0, n - 1) \land N (n + 1, n + m) ⟶ x_{0} ⊤ x_{n + m + 1} .

So, the following theorem is true:

Theorem 10. A binary relation

γ

is projection representable for a representable Menger

(2, n)

-semigroup if and only if it is an

l

-cancellative

0

-quasi-equivalence and the system of conditions

(C_{n, m})_{n, m \in N}

is satisfied.

^$1$ $χ_{(h_{1}, h_{2})}$ denotes this quasi-order which corresponds to the representation $P_{(h_{1}, h_{2})}$ . Analogously are defined $γ_{(h_{1}, h_{2})}$ and $π_{(h_{1}, h_{2})}$ .

^$2$ Remind that $σ \circ ρ = {(a, c) | (\exists b) (a, b) \in ρ \land (b, c) \in σ}$ , $f_{R} (ρ) = ρ \cup △_{A}$ , $f_{t} (ρ) = \cup_{n = 1}^{\infty} ρ^{n}$ , where $ρ^{n} = {\underset{︸}{ρ \circ ρ \circ \dots \circ ρ}}_{n}$ , $ρ, σ$ — binary relations on $A$ and $△_{A} = {(a, a) | a \in A}$ .

4 Pro jection representable relations on $(2, n)$ -semigroups

Let

χ

γ

and

π

be three binary relations on a

(2, n)

-semigroup

(G; \oplus 1, \dots, \oplus n)

. Similarly as in the case of Menger

(2, n)

-semigroups we say that the triplet

(χ, γ, π)

is (faithful) projection representable for a

(2, n)

-semigroup

(G; \oplus 1, \dots, \oplus n)

, if there exists such (faithful) representation

P

(G; \oplus 1, \dots, \oplus n)

n

-place functions for which

χ = χ_{P}

γ = γ_{P}

and

π = π_{P}

. Analogously we define the projection representable pairs and separate relations.

It is not difficult to verify that our Theorem 1 formulated for representable Menger

(2, n)

-semigroup is also valid for representable

(2, n)

-semigroups. The proof of this version of Theorem 1 is analogous to the proof of the previous version, but in the proof of the sufficiency instead the representation

P

we must consider the representation

P^{∙}

, which is the sum of the family of representations

(P_{(h_{1}, h_{2})}^{∙})_{(h_{1}, h_{2}) \in γ}

, where for every

g \in G

P_{(h_{1}, h_{2})}^{∙} (g) : A_{0}^{*} \to G

(

A_{0}^{*} = A_{0} \cup {(e_{1}, \dots, e_{n})}

see page ) is a partial

n

-place function such that

x_{1}^{n} \in pr 1 P_{(h_{1}, h_{2})}^{∙} (g) ⟷ {\begin{matrix} h_{1} ⊏ g \lor h_{2} ⊏ g & if x_{1}^{n} = e_{1}^{n}, \\ h_{1} ⊏ g \oplus i_{s} i_{1} y_{1}^{s} \lor h_{2} ⊏ g \oplus i_{s} i_{1} y_{1}^{s} & if x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s}), \\ i = 1, \dots, n, for \\ some y_{1}^{s} \in G^{s} and \\ i_{1} \dots, i_{s} \in {1, \dots, n} \end{matrix}

and

P_{(h_{1}, h_{2})}^{∙} (g) (x_{1}^{n}) = {\begin{matrix} g & if x_{1}^{n} = e_{1}^{n}, \\ g \oplus i_{s} i_{1} y_{1}^{s} & if x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s}), \\ i = 1, \dots, n, for some y_{1}^{s} \in G^{s} \\ and i_{1} \dots, i_{s} \in {1, \dots, n} . \end{matrix}

Also Theorem 2 is valid for

(2, n)

-semigroups. Moreover, problems analogous to Problem 1 and Problem 2 can be posed for

(2, n)

-semigroups, too.

Theorem 3 will be valid for

(2, n)

-semigroups if we replace the relation

χ (π)

by the relation

\begin{matrix} χ^{∙} (π) = f_{t} (f_{R} (δ_{2}) \circ π) = ⋃_{n = 1}^{\infty} {((δ_{2} \cup △_{G}) \circ π)}^{n}, \end{matrix}

(40)

i.e. if we delete

δ_{1}

from the formula (32 ). Proposition 5 for

(2, n)

-semigroups has the following form:

Proposition 8. The condition

(g_{1}, g_{2}) \in χ^{∙} (π)

, where

g_{1}, g_{2} \in G,

means that the system of conditions

g_{1} = x_{0} \land g_{2} = x_{n} \land ⋀_{i = 0}^{n - 1} ((\begin{matrix} x_{i} \equiv y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}, \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) \end{matrix}) \lor x_{i} \equiv x_{i + 1})

is valid for some

n \in N

x_{i}, y_{i}, z_{i} \in G,

k_{i} \in {1, \dots, n}

Denoting by

X (m, n)

the formula

⋀_{i = m}^{n} ((\begin{matrix} x_{i} \equiv y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}, \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) \end{matrix}) \lor x_{i} \equiv x_{i + 1})

and using the same argumentation as in the proof of Theorem 4 , we can prove

Theorem 11. A pair

(γ, π)

of binary relations on a representable

(2, n)

-semigroup is projection representable if and only if

γ

is an

l

-cancellative

0

-quasi-equivalence,

π

is an

l

-regular equivalence, and the systems of conditions

A_{n}^{∙}

and

B_{n, m}^{∙}

, where

\begin{matrix} A_{n}^{∙} : X (0, n - 1) \land x_{0} = x_{n} ⟶ x_{0} \equiv x_{1}, \end{matrix}

\begin{matrix} B_{n, m}^{∙} : x_{0} ⊤ x_{n + 1} \land X (0, n - 1) \land X (n + 1, n + m) ⟶ x_{n} ⊤ x_{n + m + 1} \end{matrix}

are satisfied.

Theorem 5 is valid for

(2, n)

-semigroups too, but in the proof, the representation

P_{a}

defined by (37 ), must be replaced by the representation

P_{a}^{∙}

, where

P_{a}^{∙} (g) (x_{1}^{n}) = {\begin{matrix} g & if a ⊏ g and x_{1} = e_{1}^{n}, \\ g \oplus i_{s} i_{1} y_{1}^{s} & if a ⊏ g \oplus i_{s} i_{1} y_{1}^{s} and x_{i} = μ_{i}^{*} (\oplus i_{s} i_{1} y_{1}^{s}), \\ i = 1, \dots, n, for some y_{1}^{s} \in G^{s}, \\ and i_{1}, \dots, i_{s} \in {1, \dots, n} . \end{matrix}

For

(2, n)

-semigroups Theorem 6 has the same form as for Menger

(2, n)

-semigroup, in Theorem 7 the relation

χ (π)

must be replaced by

χ^{∙} (π)

, and in Theorem 8 instead of

A_{n}

we must use

A_{n}^{∙}

Further, using the same argumentation as in the proof of Proposition 4 we can prove that the relation

χ_{0}^{∙} = f_{t} (f_{R} (δ_{2})) = ⋃_{n = 1}^{\infty} {(δ_{2} \cup △_{G})}^{n},

where

f_{t}

and

f_{R}

are reflexive and transitive closure operations, is the least

l

-regular and

v

-negative quasi-order on a given

(2, n)

-semigroup. Using this relation, we can prove the analog of Theorem 10 for

(2, n)

-semigroups. The analog of Problem 4 can be posed too.

Proposition 7 for

(2, n)

-semigroups has the following form:

Proposition 9. The condition

(g_{1}, g_{2}) \in χ_{0}^{∙}

, where

g_{1}, g_{2} \in G

, means that the system of conditions

g_{1} = x_{0} \land g_{2} = x_{n} \land ⋀_{i = 0}^{n - 1} ((\begin{matrix} x_{i} = y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}, \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) \end{matrix}) \lor x_{i} = x_{i + 1})

is valid for

n \in N

x_{i}, y_{i}, z_{i} \in G

Further, denoting by

B (m, n)

the formula

⋀_{i = m}^{n} ((\begin{matrix} x_{i} = y_{i} \oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}, \\ x_{i + 1} = μ_{k_{i}} (\oplus k_{s_{i}} k_{1_{i}} z_{1_{i}}^{s_{i}}) \end{matrix}) \lor x_{i} = x_{i + 1})

and using the same argumentation as in the proof of Theorem 10 , we can prove

Theorem 12. A binary relation

γ

is projection representable for a representable

(2, n)

-semigroup if and only if it is an

l

-cancellative

0

-quasi-equivalence and the system of conditions

(C_{n, m}^{∙})_{n, m \in N}

, where

C_{n, m}^{∙} : x_{0} ⊤ x_{n + 1} \land B (0, n - 1) \land B (n + 1, n + m) ⟶ x_{0} ⊤ x_{n + m + 1}

is satisfied.

References

Dudek W.A., Trokhimenko V.S. Functional Menger $P$ -algebras, Commun. Algebra 30 (2002), $5921 - 5931 .$
Mann H. On orthogonal Latin squares, Bull. Amer. Math. Soc. 50 (1944), 249-257.
Riguet J. Relations binaires, fermetures, correspondances de Galois, Bull. Soc. Math. France 76 (1948), $114 - 155$ .
Schein B.M. A relation of co-definability on semigroups of functions, (Russian), Ordered sets and lattices 1 (1971), $86 - 89,$ (Izdat. Saratov. Gos. Univ.)
Schein B.M. Projection partitions of function semigroups, C. R. Math. Rep. Acad. Sci. Canada 1 (1978/79), no. 2, $67 - 70 .$
Schein B. M. Lectures on semigroups of transformations, Amer. Math. Soc. Translat. (2), 113 (1979), $123 - 181 .$
Schein B. M., Trohimenko V. S. Algebras of multiplace functions, Semigroup Forum 17 (1979), $1 - 64 .$
Sokhatsky F. N. An abstract characterization of $(2, n)$ -semigroups of $n$ -ary operations, (Russian), Mat. Issled. 65 (1982), $132 - 139 .$
Trokhimenko V.S. Ordered algebras of multiplace functions, (Russian), Izv. Vyssh. Uchebn. Zaved. Matematika 1 (1971), $90 - 98 .$
Trokhimenko V.S. Abstract characterizations of certain algebras of multiplace functions, (Russian), Izv. Yyssh. Uchebn. Zaved. Matematika 4 (1971), $87 - 95 .$
Trokhimenko V.S. Characterization of the co-definability relation on ordered algebras of multiplace functions, (Russian), Izv. Vyssh. Uchebn. Zaved. Matematika 9 (1977), $80 - 88 .$
Yakubov T. On $(2, n)$ -semigroups of $n$ -ary operations, (Russian), Bull. Akad. Ş tiinţ a SSR Moldov. 1 (1974), $29 - 46 .$

Wiesław A. Dudek Institute of Mathematics, Technical University, 50-370 Wrocław, Poland E-mail: dudek@im.pwr.wroc.pl Valentin S. Trokhimenko Department of Mathematics, Pedagogical University, 21100 Vinnitsa, Ukraine E-mail: vtrokhim@sovamua.com

Pro jection representable relations on Menger $(2, n)$ -semigroups 2000 Mathematics Sub ject Classification: 20N15, 08N05. Keywords: $n$ -place function, algebra of functions, Menger algebra, $(2, n)$ -semigroup.

Wiesław A. Dudek and Valentin S. Trokhimenko

November 27, 2006