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
- ↑ 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.
pojęcia podstawowe |
|
---|
własności i typy | według liczby argumentów |
|
---|
konkretne przykłady |
|
---|
własności relacji binarnych |
|
---|
praporządki |
|
---|
inne zestawy własności |
|
---|
|
---|
działania na relacjach | |
---|
powiązane struktury | |
---|
pozostałe pojęcia |
|
---|