Tarski clones of operations on binary relations and their characterization
by
Reinhard Pöschel
TU Dresden, Institute of Algebra (GERMANY)
Coauthors: Dragan Masulovic (University Novi Sad)

We give a characterization of the following three clones of operations on binary relations: the clone of primitive-positive Tarski operations, the clone of positive Tarski operations and the clone of all Tarski operations (or the classical clone). Operations from each of the three clones can be represented by special first-order formulas; to each such formula we assign a labelled multigraph and show that an operation belongs to the respective clone if and only if the suitably transformed graph of its formula does not contain a subgraph homeomorphic to K₄. We also address a problem of A. Tarski to characterize closed first-order formulas that can be in a suitable way represented by an identity in the language of relation algebras.

Date received: January 10, 2003