Półgrupa relacji binarnych: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
Nie podano opisu zmian |
Nie podano opisu zmian |
||
Linia 1:
'''Półgrupa relacji binarnych''' – [[półgrupa]] wszystkich [[relacja (matematyka)|relacji binarnych]] pewnego [[zbiór|zbioru]] z działaniem ich [[złożenie relacji|składania]]. Dla [[zbiór skończony|zbioru skończonego]] [[moc zbioru|mocy]] <math>\scriptstyle n</math> jest ona [[izomorfizm|izomorficzna]] z półgrupą [[macierz logiczna|macierzy logicznych]] typu <math>\scriptstyle n \times n</math> z działaniem ich [[mnożenie macierzy|mnożenia]]. Zbiór wszystkich relacji binarnych określonych na zbiorze <math>\scriptstyle X</math> oznacza się symbolami <math>\scriptstyle \mathcal B_X</math> lub <math>\scriptstyle \mathcal B(X).</math>
Półgrupy relacji binarnych nie mają dobrych własności: dla <math>\scriptstyle |X|>2</math> nie są one [[regularność|regularne]]<ref>''Generalized Inverses of Boolean Relation Matrices'', R. J. Plemmons, SIAM Journal on Applied Mathematics, Vol. 20, No. 3 (May, 1971), str. 426-433</ref>; [[idempotentność|idempotenty]] półgrupy relacji binarnych nie tworzą żadnej z ogólnie znanych klas relacji. Każdy [[praporządek]] jest idempotentem<ref>''Algebraic models for social networks'', Philippa Pattison, Cambridge University Press, 1993, str. 128</ref>, a każdy idempotent półgrupy relacji binarnych musi być [[relacja przechodnia|relacją przechodnią]]. Istnieją jednak relacje idempotentne niebędące praporządkami oraz relacje przechodnie, które nie są idempotentami. [[Równoważność|Warunkami koniecznym i dostatecznym]] na to, by relacja <math>\scriptstyle R</math> na zbiorze <math>\scriptstyle X</math> była idempotentna, jest jej jednoczesna [[relacja przechodnia|przechodniość]] i ''interpolatywność''<ref>''Continuous ideal completions and compactifications'', Gerhard Gierz and Klaus Keimel, Lecture Notes in Mathematics, 1981, Volume 871/1981, 97-124</ref> (dla dowolnych <math>\scriptstyle a, b \in X</math> relacja <math>\scriptstyle R(a, b)</math> pociąga istnienie takiego <math>\scriptstyle x \in X,</math> dla którego <math>\scriptstyle R(a, x)</math> oraz <math>\scriptstyle R(x, b)</math>). Powyższe dwie własności można scharakteryzować w następujący sposób:
: <math>\scriptstyle R \circ R \subseteq R</math> wtedy i tylko wtedy, gdy <math>\scriptstyle R</math> jest przechodnia
oraz
| |||