Semiring identities of semigroups of reflexive relations and upper triangular boolean matrices

Abstract

We show that the following semirings satisfy the same identities: the semiring ${\mathcal{R}}_n$ of all reflexive binary relations on a set with $n$ elements, the semiring ${\mathcal{U}}_n$ of all $n\times n$ upper triangular matrices over the boolean semiring, the semiring ${\mathcal{C}}_n$ of all order preserving and extensive transformations of a chain with $n$ elements. In view of the result of Klíma and Polák, which states that ${\mathcal{C}}_n$ has a finite basis of identities for all $n$, this implies that the identities of ${\mathcal{R}}_n$ and ${\mathcal{U}}_n$ admit a finite basis as well.