Półgrupa relacji binarnych

Półgrupa relacji binarnych – półgrupa wszystkich relacji binarnych pewnego zbioru z działaniem ich składania. Dla zbioru skończonego mocy $n$ jest ona izomorficzna z półgrupą macierzy logicznych typu $n\times n$ z działaniem ich mnożenia. Zbiór wszystkich relacji binarnych określonych na zbiorze $X$ oznacza się symbolami ${\mathcal {B}}_{X}$ lub ${\mathcal {B}}(X).$

Półgrupy relacji binarnych nie mają dobrych własności: dla $|X|>2$ nie są one regularne; idempotenty półgrupy relacji binarnych nie tworzą żadnej z ogólnie znanych klas relacji. Każdy praporządek jest idempotentem, a każdy idempotent półgrupy relacji binarnych musi być relacją przechodnią. Istnieją jednak relacje idempotentne niebędące praporządkami oraz relacje przechodnie, które nie są idempotentami. Warunkiem koniecznym i dostatecznym na to, by relacja $R$ na zbiorze $X$ była idempotentna, jest jej jednoczesna przechodniość i interpolatywność (dla dowolnych $a,b\in X$ relacja $R(a,b)$ pociąga istnienie takiego $x\in X,$ dla którego $R(a,x)$ oraz $R(x,b)$). Powyższe dwie własności można scharakteryzować w następujący sposób:

$R\circ R\subseteq R$ wtedy i tylko wtedy, gdy $R$ jest przechodnia

oraz

$R\circ R\supseteq R$ wtedy i tylko wtedy, gdy $R$ jest interpolatywna.