Półgrupa relacji binarnych
struktura algebraiczna z działaniem składania relacji binarnych / Z Wikipedii, wolnej encyclopedia
Półgrupa relacji binarnych – półgrupa wszystkich relacji binarnych pewnego zbioru z działaniem ich składania. Dla zbioru skończonego mocy jest ona izomorficzna z półgrupą macierzy logicznych typu z działaniem ich mnożenia. Zbiór wszystkich relacji binarnych określonych na zbiorze oznacza się symbolami lub
Półgrupy relacji binarnych nie mają dobrych własności: dla 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 na zbiorze była idempotentna, jest jej jednoczesna przechodniość i interpolatywność[3] (dla dowolnych relacja pociąga istnienie takiego dla którego oraz ). Powyższe dwie własności można scharakteryzować w następujący sposób:
- wtedy i tylko wtedy, gdy jest przechodnia
oraz
- wtedy i tylko wtedy, gdy jest interpolatywna.