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 ${\displaystyle n}$ jest ona izomorficzna z półgrupą macierzy logicznych typu ${\displaystyle n\times n}$ z działaniem ich mnożenia. Zbiór wszystkich relacji binarnych określonych na zbiorze ${\displaystyle X}$ oznacza się symbolami ${\displaystyle {\mathcal {B}}_{X}}$ lub ${\displaystyle {\mathcal {B}}(X).}$

Półgrupy relacji binarnych nie mają dobrych własności: dla ${\displaystyle |X|>2}$ nie są one regularne^[1]; idempotenty półgrupy relacji binarnych nie tworzą żadnej z ogólnie znanych klas relacji. Każdy praporządek jest idempotentem^[2], 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 ${\displaystyle R}$ na zbiorze ${\displaystyle X}$ była idempotentna, jest jej jednoczesna przechodniość i interpolatywność^[3] (dla dowolnych ${\displaystyle a,b\in X}$ relacja ${\displaystyle R(a,b)}$ pociąga istnienie takiego ${\displaystyle x\in X,}$ dla którego ${\displaystyle R(a,x)}$ oraz ${\displaystyle R(x,b)}$). Powyższe dwie własności można scharakteryzować w następujący sposób:

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

oraz

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

Przypisy