B. M. SHAIN

INVOLUTED SEMIGROUPS OF COMPLETE BINARY RELATIONS

(Presented by Academician A. I. Mal’tsev on 27 I 1964)

An involuted semigroup is an algebraic system of the form \(\langle G,\cdot,^{-1}\rangle\), where \(\cdot\) is a binary operation and \(^{-1}\) is a unary operation on a nonempty set \(G\), with \(\langle G,\cdot\rangle\) a semigroup, \(\langle G,^{-1}\rangle\) a set with an involution (i.e., for every \(g\in G\), \((g^{-1})^{-1}=g\)), and multiplication \(\cdot\) and the involution \(^{-1}\) are related as follows: for any \(g_1\) and \(g_2\),
\[ (g_1\cdot g_2)^{-1}=g_2^{-1}\cdot g_1^{-1}. \]

It is obvious that groups and generalized groups, regarded as algebraic systems with two operations, will be involuted semigroups. The set \(\mathfrak P(A\times A)\) of all binary relations between elements of a certain set \(A\), on which the operations \(\circ\) of multiplication of binary relations and \(^{-1}\) of inversion of binary relations are introduced, will also be an involuted semigroup. Involuted subsemigroups of this involuted semigroup are called involuted semigroups of binary relations. Thus, a subset \(\Phi\) of the set \(\mathfrak P(A\times A)\) is a set of elements of an involuted semigroup of binary relations if and only if, for any \(\varphi_1,\varphi_2\) in \(\Phi\), \(\varphi_2\circ\varphi_1\) and \(\varphi_1^{-1}\) belong to \(\Phi\).

A binary relation \(\varphi\) between elements of the set \(A\) is called complete if its first projection coincides with \(A\). Let \(\langle\Phi,\circ,^{-1}\rangle\) be an involuted semigroup of complete binary relations between elements of the set \(A\). If \(\varphi\in\Phi\), then also \(\varphi^{-1}\in\Phi\). Since the first projection of \(\varphi^{-1}\) coincides with the second projection of \(\varphi\), we obtain that both projections of \(\varphi\) coincide with the set \(A\), i.e., for every \(\varphi\in\Phi\) and every \(a\in A\) there exist such \(a_1,a_2\in A\) that \((a_1,a)\in\varphi\land(a,a_2)\in\varphi\).

An ordered involuted semigroup is an algebraic system of the form \(\langle G,\cdot,^{-1},\prec\rangle\), where \(\langle G,\cdot,^{-1}\rangle\) is an involuted semigroup, and \(\langle G,\prec\rangle\) is an ordered set, the order relation \(\prec\) being stable with respect to the operations \(\cdot\) and \(^{-1}\) (i.e., stable with respect to \(\cdot\):
\[ g_1\prec g_2\land g_3\prec g_4\to g_1\cdot g_3\prec g_2\cdot g_4 \]
and stable with respect to \(^{-1}\), or involutively invariant:
\[ g_1\prec g_2\to g_1^{-1}\prec g_2^{-1}. \]
If \(\langle\Phi,\circ,^{-1}\rangle\) is an involuted semigroup of binary relations, and \(\subset\) is the set-theoretic inclusion relation between binary relations from \(\Phi\), then \(\langle\Phi,\circ,^{-1},\subset\rangle\) will be an ordered involuted semigroup. Such algebraic systems will be called ordered involuted semigroups of binary relations. The isomorphism of two (ordered) involuted semigroups is understood in the sense of the theory of algebraic systems (i.e., under an isomorphism the multiplication and involution operations, and the order relation, are preserved).

Let \(\mathfrak G=\langle G,\cdot,^{-1},\prec\rangle\) be an ordered involuted semigroup. The product of elements \(g_1\) and \(g_2\) will be denoted, as usual, by \(g_1,g_2\). If the semigroup \(\langle G,\cdot\rangle\) does not contain an identity, then adjoin to the set \(G\) an element \(e\), not belonging to \(G\), and denote the resulting set by \(G^e\). Extend the operations and relations from \(\mathfrak G\) to the set \(G^e\), defining \(eg=ge=g\) for all \(g\in G^e\), \(e^{-1}=e\); set \(e\prec g\) if and only if there is such a \(g_1\in G\) that \(g_1g_1^{-1}\prec g\), or if \(g=e\). The extended operations and relations will be denoted by the same symbols as the old operations and relations. It is obvious that \(\langle G^e,\cdot,^{-1}\rangle\) will be an invo-

involuted semigroup. It is not hard to verify that \(\langle G^e,\cdot,^{-1},\prec\rangle\) will be an ordered involuted semigroup, and that the order relation from \(G^e\) induces on the set \(G\) the order relation from \(G\).

Theorem 1. In order that an ordered involuted semigroup \(\langle G,\cdot,^{-1},\prec\rangle\) be isomorphic to some ordered involuted semigroup of full binary relations, it is necessary and sufficient that, for any \(g,g_1\in G\), the condition
\[ g_1 \prec gg^{-1}g_1 \]
be satisfied.

If the semigroup \(\langle G,\cdot\rangle\) contains an identity \(e\), this condition is equivalent to the simpler condition: for every \(g\in G\),
\[ e \prec gg^{-1}. \]

Indeed, let us first note that for ordered involuted semigroups with an identity both conditions are equivalent: putting \(g_1=e\) in the first condition, we obtain the second; multiplying the second condition on the right by \(g_1\), we obtain the first condition.

Let \(\langle \Phi,\circ,^{-1},\subset\rangle\) be an ordered involuted semigroup of full binary relations. If \(\varphi\in\Phi\) and \(a\in A\), then \((a,a_2)\in\varphi\) for some \(a_2\), and \((a,a)\in\varphi\circ\varphi^{-1}\), whence it follows that \(\varphi\circ\varphi^{-1}\) is reflexive, i.e.
\[ \Delta_A\subset \varphi\circ\varphi^{-1}, \]
where \(\Delta_A\) denotes the identity binary relation. Therefore, for any \(\varphi_1\in\Phi\) we obtain that
\[ \varphi_1=\varphi_1\circ\Delta_A\subset \varphi_1\circ\varphi\circ\varphi^{-1}. \]

To prove sufficiency, we construct an isomorphism \(P\) of the ordered involuted semigroup \(\langle G,\cdot,^{-1},\prec\rangle\), satisfying the conditions of the theorem, onto an ordered involuted semigroup of binary relations. We may assume that \(\langle G,\cdot\rangle\) contains an identity \(e\), since otherwise an identity can always be adjoined, as was shown above. A subset \(H\) of the set \(G\) is called majorantly saturated if, for any \(g\) and \(g_1\) such that \(g\in H\) and \(g\prec g_1\), it follows that \(g_1\in H\). Denote by \(\mathfrak M\) the set of all majorantly saturated subsets of the set \(G\). To each \(g\in G\) assign the binary relation \(P(g)\) between the elements of the set \(\mathfrak M\), defined by the formula:
\[ (H_1,H_2)\in P(g)\leftrightarrow H_1\{g\}\subset H_2\land H_2\{g^{-1}\}\subset H_1. \]
From the definition it is clear that
\[ \overline{P(g)}=P(g^{-1}). \]
It is not hard to verify that
\[ P(g_2)\circ P(g_1)\subset P(g_1g_2). \]
Let \((H_1,H_2)\in P(g_1g_2)\). Denote by \(H\) the majorantly saturated closure of the set \(H_1\{g_1\}\cup H_2\{g_2^{-1}\}\). Using the majorant saturation of the subsets \(H,H_1,H_2\), the stability of the order relation \(\prec\), and the condition of the theorem, we easily obtain that \((H_1,H)\in P(g_1)\land (H,H_2)\in P(g_2)\), whence \((H_1,H_2)\in P(g_2)\circ P(g_1)\). Therefore
\[ P(g_2)\circ P(g_1)=P(g_1g_2). \]
If \(g_1\prec g_2\), then, using the condition of the theorem and the stability of the relation \(\prec\), we obtain that
\[ P(g_1)\subset P(g_2). \]
Let \(P(g_1)\subset P(g_2)\). Denote by \((e)\) the set of all majorants of the identity. It is not hard to verify that \(((e),(e)\{g_1\})\in P(g_1)\), whence \(((e),(e)\{g_1\})\in P(g_2)\), i.e.
\[ (e)\{g_2\}\subset (e)\{g_1\}. \]
From this \(g_2\in(e)\{g_1\}\) and \(g_1\prec g_2\). Therefore
\[ g_1\prec g_2 \leftrightarrow P(g_1)\subset P(g_2). \]
Noting that from \(P(g_1)=P(g_2)\) it follows that
\[ g_1\prec g_2\land g_2\prec g_1 \]
and \(g_1=g_2\), we obtain that \(P\) is an isomorphism of \(\langle G,\cdot,^{-1},\prec\rangle\) onto an ordered involuted semigroup of binary relations. It remains to note that all the relations \(P(g)\) are full, since
\[ (H,H\{g\})\in P(g) \]
for any \(H\in\mathfrak M\).

Denote by \(I_n\) the formula
\[ \left( \begin{array}{c} x_1y_1y_1^{-1}z_1=x_2z_2\land\\ x_2y_2y_2^{-1}z_2=x_3z_3\land\\ \cdots\\ x_{n-1}y_{n-1}y_{n-1}^{-1}z_{n-1}=x_nz_n\land\\ x_ny_ny_n^{-1}z_n=x_1z_1 \end{array} \right)\to x_1z_1=x_2z_2 . \]

Here the variables \(x_i, y_i, z_i\) may be empty symbols. If \(y_i\) is an empty symbol, then \(y_i^{-1}\) is also an empty symbol. \(u_1u_2\ldots u_i\) is an empty symbol if and only if \(u_1,u_2,\ldots,u_i\) are empty symbols.

Theorem 2. An involuted semigroup \(\langle G,\cdot,^{-1}\rangle\) is isomorphic to some involuted semigroup of complete binary relations if and only if our semigroup satisfies the conditions \(I_n\) for all \(n\).

Proof. Let \(\langle \Phi,\circ,^{-1}\rangle\) be an involuted semigroup of binary relations and suppose the premise of the formula \(I_n\) holds. Then, by what was proved earlier,

\[ x_1z_1 \subset x_1y_1y_1^{-1}z_1 = x_2z_2 \subset x_2y_2y_2^{-1}z_2 = x_3z_3 \subset \cdots \subset x_ny_ny_n^{-1}z_n = x_1z_1, \]

whence \(x_1z_1=x_2z_2\), i.e. \(I_n\) holds for all \(n\). Now let \(\langle G,\cdot,^{-1}\rangle\) be some involuted semigroup. We construct a binary relation \(\omega\) between elements of the set \(G\) by putting \((g_1,g_2)\in\omega\) if and only if, for some \(x_i,y_i,z_i\) that are elements of \(G\) or empty symbols,

\[ g_1=x_1z_1 \wedge x_1y_1y_1^{-1}z_1 = x_2z_2 \wedge x_2y_2y_2^{-1}z_2 = x_3z_3 \wedge \cdots \wedge x_ny_ny_n^{-1}z_n = x_{n+1}z_{n+1}=g_2. \]

It is not hard to show that \(\omega\) will be a stable relation of the quasiorder of the involuted semigroup and that \((g_1,gg^{-1}g_1)\in\omega\) for any \(g,g_1\). The conditions \(I_n\) express nothing other than the antisymmetry of \(\omega\); therefore, from the fulfillment of these conditions it follows, by Theorem 1, that the ordered involuted semigroup \(\langle G,\cdot,^{-1},\omega\rangle\) is isomorphic to an ordered involuted semigroup of complete binary relations. This completes the proof of Theorem 2.

Thus, \(I_1,I_2,\ldots\) is a system of elementary axioms for the class of involuted semigroups isomorphic to involuted semigroups of complete binary relations. Strictly speaking, each of the formulas \(I_n\) is not an axiom, but a scheme of a finite number of axioms (since empty symbols may occur in \(I_n\)). It can be shown that for any \(n\), from \(I_n\) all formulas \(I_m\), where \(m<n\), follow. Moreover:

Theorem 3. If \(m<n\), then the formula \(I_m\) follows from the formula \(I_n\), but the formula \(I_n\) does not follow from the formula \(I_m\). Therefore the system of axioms \(I_1,I_2,\ldots\) is not equivalent to any of its finite subsystems, and the class of involuted semigroups isomorphic to involuted semigroups of complete binary relations cannot be characterized by any finite system of elementary axioms.

The proof of this theorem, because of its length, cannot be given here. We note only that it is based on the fact that, for each \(n\), an example of an involuted semigroup is constructed by a uniform method in which the axiom \(I_n\) holds and the axiom \(I_{n+1}\) does not hold. The second part of the theorem follows from known results in the theory of algebraic systems.

It can be shown that every semigroup can be isomorphically embedded (with respect to the operation of multiplication) in an involuted semigroup of complete binary relations.

Theorem 4. For a commutative involuted semigroup \(\langle G,\cdot,^{-1}\rangle\), the following three properties are equivalent:

1) \(\langle G,\cdot,^{-1}\rangle\) is isomorphic to an involuted semigroup of complete binary relations.

2) \(\langle G,\cdot,^{-1}\rangle\) is isomorphic to an involuted semigroup of binary relations.

3) \(\langle G,\cdot,^{-1}\rangle\) satisfies the axiom:

\[ g=gg_1^{-1}g_1g_2^{-1}g_2 \to g=gg_1^{-1}g_1. \]

From 1) follows 2) in an obvious way. Let \(\langle \Phi,\circ,^{-1}\rangle\) be a commutative involuted semigroup of binary relations and

\[ \varphi=\varphi_2\circ\varphi_2^{-1}\circ\varphi_1\circ\varphi_1^{-1}\circ\varphi. \]

Then

\[ \operatorname{pr}_2\varphi \subset \operatorname{pr}_2\varphi_2. \]

Using the commutativity of multiplication, we obtain that

\[ \operatorname{pr}_2\varphi \subset \operatorname{pr}_2\varphi_1. \]

Hence

\[ \Delta_{\operatorname{pr}_2\varphi}\subset \varphi_2\circ\varphi_2^{-1}\cap\varphi_1\circ\varphi_1^{-1} \]

and

\[ \varphi\subset \varphi_1\circ\varphi_1^{-1}\circ\varphi \subset \varphi_2\circ\varphi_2^{-1}\circ\varphi_1\circ\varphi_1^{-1}\circ\varphi=\varphi, \]

i.e. 3) holds. Finally, directly

... by computations we verify that in the commutative case all the formulas \(I_1, I_2, \ldots\) follow from 3).

Let us note that the problem of finding a system of axioms for the class of involuted semigroups isomorphic to involuted semigroups of binary relations has not yet been solved. It can be shown that this class is quasiprimitive in the sense of \((^1)\), i.e., it can be characterized by a system of conditional identities. The class of involuted semigroups isomorphic to involuted semigroups of all binary relations is an example of a class that is, of course, axiomatizable with the aid of an additional predicate (the order relation).

Recalling that the order relation inverse to the canonical order relation of a generalized group satisfies the condition of Theorem 1 \((^2)\), and using the results of \((^2)\), we obtain that for quasi-one-valued binary relations (i.e., such relations \(\varphi\) for which \(\varphi=\varphi\circ\varphi^{-1}\circ\varphi\)) the following holds.

Theorem 5. An involuted semigroup is isomorphic to an involuted semigroup of all quasi-one-valued binary relations if and only if this involuted semigroup is a generalized group.

An ordered involuted semigroup \(\langle G,\cdot,^{-1},\prec\rangle\) is called positively ordered if \(g_1\prec g_1g_2 \wedge g_2\prec g_1g_2\) for any \(g_1,g_2\in G\). Combining Theorem 1 with the results of \((^3)\), we obtain:

Theorem 6. In order that an ordered involuted semigroup be isomorphic to an ordered involuted semigroup of reflexive binary relations, it is necessary and sufficient that it be positively ordered.

A binary relation \(\varphi\) is called symmetric if \(\varphi=\varphi^{-1}\), and partially reflexive if \(\Delta_{\mathrm{pr}_1\varphi\cup\mathrm{pr}_2\varphi}\subset \varphi\), i.e., from \((a_1,a_2)\in\varphi\) it follows that \((a_1,a_1)\in\varphi \wedge (a_2,a_2)\in\varphi\). Using Theorems 4 and 6, we easily obtain:

Theorem 7. For a semigroup \(\langle G,\cdot\rangle\) the following properties are equivalent:

1) \(\langle G,\cdot\rangle\) is isomorphic to a semigroup of all symmetric binary relations.

2) \(\langle G,\cdot\rangle\) is isomorphic to a semigroup of symmetric binary relations.

3) \(\langle G,\cdot\rangle\) is commutative and satisfies the condition
\(g=gg_1^2g_2^2 \to g=gg_1^2\).

Theorem 8. For a semigroup \(\langle G,\cdot\rangle\) the following properties are equivalent:

1) \(\langle G,\cdot\rangle\) is isomorphic to a semigroup of symmetric and reflexive binary relations.

2) \(\langle G,\cdot\rangle\) is isomorphic to a semigroup of symmetric and partially reflexive binary relations.

3) \(\langle G,\cdot\rangle\) is isomorphic to a commutative semigroup of reflexive binary relations.

4) \(\langle G,\cdot\rangle\) is commutative and satisfies the condition
\(g=gg_1g_2 \to g=gg_1\).

From this and from Theorem 5 it follows that

Theorem 9. For a subgroup \(\langle G,\cdot\rangle\) the following properties are equivalent:

1) \(\langle G,\cdot\rangle\) is isomorphic to a semigroup of equivalence relations.

2) \(\langle G,\cdot\rangle\) is isomorphic to a semigroup of symmetric and transitive binary relations.

3) \(\langle G,\cdot\rangle\) is commutative and idempotent.

Saratov State University
named after N. G. Chernyshevsky

Received
24 I 1964

REFERENCES

\(^1\) A. I. Maltsev, DAN, 108, No. 2, 187 (1956).
\(^2\) B. M. Schein, DAN, 153, No. 2, 296 (1963).
\(^3\) K. A. Zaretskii, Izv. vyssh. uchebn. zaved., Matem., No. 6 (13), 48 (1959).