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.

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