|
'''Półgrupa relacji binarnych''' to– [[półgrupa]] wszystkich [[relacja (matematyka)|relacji binarnych]] binarnychpewnego na pewnym zbiorze[[zbiór|zbioru]] z działaniem ich [[złożenie relacji|składania relacji]]. Dla [[zbiór skończony|zbioru skończonego]] o[[moc zbioru|mocy]] <math>\scriptstyle n</math> jest ona [[izomorfizm|izomorficzna]] z półgrupą [[macierz logiczna|macierzy logicznych]] rozmiarutypu <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>, oraz żea każdy idempotent półgrupy relacji binarnych musi być [[relacja przechodnia|relacją przechodnią]]. Istnieją jednak relacje idempotentne , które nie sąniebędące praporządkami , oraz relacje przechodnie, które nie są idempotentami. Warunkiem[[Równoważność|Warunkami koniecznym i dostatecznym ]] na to, abyby relacja <math> \scriptstyle R</math> na zbiorze <math> \scriptstyle X</math> była idempotentna, jest byjej byłajednoczesna jednocześnie[[relacja przechodnia |przechodniość]] i '' interpolatywnainterpolatywność'' .<ref>''Continuous ideal completions and compactifications'', Gerhard Gierz and Klaus Keimel, Lecture Notes in Mathematics, 1981, Volume 871/1981, 97-124</ref> Relacja interpolatywna to taka, że (dla każdychdowolnych <math> \scriptstyle a, b \in X</math> , jeżelirelacja <math> a\ ,scriptstyle R \(a, b )</math> , topociąga istnienie istniejetakiego <math> \scriptstyle x \in X ,</math> , takidla żektórego <math> a\ ,scriptstyle R \(a, x )</math> ioraz <math> x\ ,scriptstyle R \(x, b .)</math> ) Powyższe dwie własności można scharakteryzować w Zachodząnastępujący równoważnościsposób:▼
=== Oznaczenia ===
*: <math> \scriptstyle R \circ R \subseteq R </math> wtedy i tylko wtedy, gdy <math>\ Longleftrightarrowscriptstyle R</math> jest przechodnia ,▼Dla oznaczenia zbioru wszystkich relacji binarnych na zbiorze <math>X</math> stosuje się symbol <math>\mathcal{B}_X</math> lub symbol <math>\mathcal{B}(X).</math>
oraz
*: <math> \scriptstyle R \circ R \supseteq R </math> wtedy i tylko wtedy, gdy <math>\ Longleftrightarrowscriptstyle R</math> jest interpolatywna. ▼
=== Własności ===
Półgrupy relacji binarnych nie mają dobrych własności. W szczególności, dla <math>|X|>2</math> nie są one 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> Idempotenty półgrupy relacji binarnych nie stanowią żadnej z ogólnie znanych klas relacji. Można łatwo sprawdzić, że każdy [[praporządek]] jest idempotentem<ref>
▲''Algebraic models for social networks'', Philippa Pattison, Cambridge University Press, 1993, str. 128</ref>, oraz że każdy idempotent półgrupy relacji binarnych musi być [[relacja przechodnia|relacją przechodnią]]. Istnieją jednak relacje idempotentne, które nie są praporządkami, oraz relacje przechodnie, które nie są idempotentami. Warunkiem koniecznym i dostatecznym, aby relacja <math>R</math> na <math>X</math> była idempotentna, jest by była jednocześnie przechodnia i ''interpolatywna''.<ref>''Continuous ideal completions and compactifications'', Gerhard Gierz and Klaus Keimel, Lecture Notes in Mathematics, 1981, Volume 871/1981, 97-124</ref> Relacja interpolatywna to taka, że dla każdych <math>a,b\in X</math>, jeżeli <math>a\,R\,b</math>, to istnieje <math>x\in X</math>, taki że <math>a\,R\,x</math> i <math>x\,R\,b.</math> Zachodzą równoważności
▲* <math>R\circ R\subseteq R \Longleftrightarrow R</math> jest przechodnia,
▲* <math>R\circ R\supseteq R \Longleftrightarrow R</math> jest interpolatywna.
[[Kategoria:Teoria półgrup]]
[[Kategoria:Relacje]]
|
