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 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.
Przypisy
[edytuj | edytuj kod]- ↑ Generalized Inverses of Boolean Relation Matrices, R. J. Plemmons, SIAM Journal on Applied Mathematics, Vol. 20, No. 3 (May, 1971), s. 426–433.
- ↑ Algebraic models for social networks, Philippa Pattison, Cambridge University Press, 1993, s. 128.
- ↑ Continuous ideal completions and compactifications, Gerhard Gierz and Klaus Keimel, Lecture Notes in Mathematics, 1981, Volume 871/1981, 97-124.