Transitivity-preserving operators on relations

L. A. Sholomov

Diskretnaya Matematika, Tome 10 (1998) no. 1, pp. 28-45

Résumé

Let $\mathcal T=\mathcal T(A)$ be the class of all transitive relations on a finite set $A$. We say that an operator $r=F(r_1,\ldots, r_n)$ on the set of relations preserves transitivity if $$ r_1,\ldots,r_n\in\mathcal T\quad \Rightarrow\quad r\in\mathcal T. $$ Let us introduce operators $\tau_n^{(u)}(r_1,\ldots,r_n)$, $u=0,1$, $n\geq 0$, by setting $\tau_0^{(0)}=\emptyset$, $\tau_0^{(1)}=A^2$, $$ \tau_n^{(u)}=r_1\cap(\overline{(r_1^{-1})}\cup \tau_{n-1}^{(u)}(r_2,\ldots,r_n)), \qquad n\geq 1. $$ Any operator derived from $\tau_n^{(u)}$ by replacing some of $r_i$, $1\leq i\leq n,$ with $r_i^{-1}$ is called a $\tau$-operator. It is shown that an operator $F$ representable by means of set-theoretic operations and inversion of relations preserves transitivity if and only if it is representable as an intersection of $\tau$-operators.