Półgrupa relacji binarnych

Półgrupa relacji binarnychpół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.

PrzypisyEdytuj

  1. Generalized Inverses of Boolean Relation Matrices, R. J. Plemmons, SIAM Journal on Applied Mathematics, Vol. 20, No. 3 (May, 1971), s. 426–433.
  2. Algebraic models for social networks, Philippa Pattison, Cambridge University Press, 1993, s. 128.
  3. Continuous ideal completions and compactifications, Gerhard Gierz and Klaus Keimel, Lecture Notes in Mathematics, 1981, Volume 871/1981, 97-124.