On varieties of semigruops of relations with unary primitive-positive operations
by
D. A. Bredikhin
Saratov, Lermontova 7-22, Russia, 410002

In the investigation of algebras of relations, one of the most important problem is to study their identities [1, 2]. For any set \Omega of operations on binary relations, let R{\Omega} be the class of algebras whose elements are binary relations and whose operations are members of \Omega, and let Var{\Omega} be a variety generated by R{\Omega}.

We shall consider the operations of relation product o and unary primitive positive operations [3] which can be defined by logical formulas with two free variables that contain one atomic formula and existential quantifiers only. There exist six such operations: Ñ₁(\rho)={(x, y):(y, x) in \rho}, Ñ₂(\rho)={(x, y): ( existsz) (x, z) in \rho}, Ñ₃(\rho)={(x, y) : ( existsz) (z, y) in \rho}, Ñ₄(\rho)={(x, y): ( existsw, z) (w, z) in \rho}, Ñ₅(\rho)={(x, y): ( existsz) (z, x) in \rho}, Ñ₆(\rho)={(x, y): ( existsz) (y, z) in \rho}.

The operation Ñ₁ is the relation inverse and the operations Ñ₁, Ñ₁ are the operations of cylindrification [4].

There are nine different clones Cl(\Omega) where { o } subset \Omega subset or equal { o , Ñ₁, ..., Ñ₆}. These are Cl( o , Ñ₁), Cl( o , Ñ₂), Cl( o , Ñ₃), Cl( o , Ñ₂, Ñ₃), Cl( o , Ñ₄), Cl( o , Ñ₅), Cl( o , Ñ₆), Cl( o , Ñ₅, Ñ₆), Cl( o , Ñ₁, Ñ₄).

The variety Var{ o , Ñ₁} was described in [5]. The finite basis of identities in others eight cases was obtained. Let's illustrate character of the received results on the following theorem.

Theorem. An algebra (A, ·, ^* ) of the type (2, 1) belongs to the variety Var{ o , Ñ₄ } if and only if it satisfies the identities: (x ^* ) ^* =x ^* , (x ^* )²=x ^* , x ^* y ^* =y ^* x ^* (x ^* y) ^* =x ^* y ^* =(xy ^* ) ^* , (xy) ^* y ^* = x ^* y ^* =x ^* (xy) ^* , xyx ^* =xyy ^* , x ^* yx=y ^* yx, x ^* yz ^* =x ^* y ^* z ^* .

REFERENCES:

[1] Tarski A. On the calculus of relations. J. Symbolic Logic. 6(1941), P.73 - 89.

[2] Tarski A. Some methodological results concerning the calculus of relations. J. Symbolic Logic 18(1953), P.188 -189.

[3] Böner F., Pöschel R. Clones of operations on binary relations. Contributions to general algebras. - Wien, 7(1991), P.50-70.

[4] Henkin L., Monk J.D. and Tarski A. Cylindric algeras I, II. North-Holland, Amsterdam, 1971, 1985.

[5] Schein B.M. Representation of involuted semigroups by binary relations. Fundamenta Math. 82(1974), P.121-141.

Date received: April 30, 2004