zbMATH — the first resource for mathematics

Preorders and equivalences generated by commuting relations. (English) Zbl 1012.08003
Two binary relations $$R$$, $$S$$ on a set $$X$$ are called commuting, if $$R\circ S=S\circ R$$, where the symbol $$\circ$$ denotes the composition of relations. The paper starts by the study of compositions of powers of commuting relations $$R$$, $$S$$. The main result states that $$(R\cup S)^n=\bigcup^n_{k=0}S^{n-k}\circ R^k$$ holds for them. For every binary relation $$R$$ on $$X$$ the relation $$R^*=\bigcup^\infty_{n=1}R^n$$ is defined; this is the smallest (with respect to set inclusion) preorder on $$X$$ containing $$R$$. Further, the smallest equivalence $$(R\cup R^{-1})^*$$ on $$X$$ containing $$R$$ is defined. It is also denoted by $$R$$ with asterisk, but that asterisk is bigger. The properties of these concepts are studied.

MSC:
 08A02 Relational systems, laws of composition
Full Text: