Abstract:
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.
Fulltext:
PDF file (1505 kB)