Krata (matematyka)

rodzaj struktury algebraicznej i porządkowej

Kraty (ang. lattice) – struktury matematyczne, które można opisywać albo algebraicznie, albo w sensie częściowych porządków[1].

Dzielniki 60 tworzą kratę.
Diagram Hassego kraty Tamriego. Warto zauważyć, iż punkty kraty tworzą wielościan, zwany angielskim terminem associahedron, co można przetłumaczyć jako „wielościan asocjacji”.

Struktura algebraiczna edytuj

Krata w sensie algebraicznym to struktura algebraiczna   gdzie   jest (niepustym) zbiorem, a   i   są odwzorowaniami z   w   spełniającymi dla dowolnych   następujące warunki:

1.    
2.    
3.    
4.    

Przykładem kraty jest dowolna algebra Boole’a.

W każdej kracie spełniona jest równoważność:   Relacja   zdefiniowana za pomocą równoważności

 

jest częściowym porządkiem, w którym każda para   ma kres górny i kres dolny:

 
 
Krata permutacji zbioru czteroelementowego.

Niekonieczność aksjomatu 1 edytuj

Aksjomat 1 podaje się tradycyjnie w definicji kraty, ale wynika on z aksjomatu 4:

Niech   Wtedy na mocy lewej części aksjomatu 4 otrzymujemy

 

a na mocy prawej:

 

co po podstawieniu do poprzedniego wzoru daje:

 

Podobnie dowodzi się, że  

Struktura porządkowa edytuj

Krata w sensie częściowych porządków to (niepusty) częściowy porządek   w którym każda para   ma kres dolny   i kres górny  

Jeśli zdefiniujemy

 
 

to dostaniemy kratę w sensie algebraicznym, w której oczywiście

 

Półkraty edytuj

Półkraty w sensie algebraicznym to dokładnie pasy przemienne, czyli półgrupy   przemienne, w których równość   zachodzi dla dowolnego  [2]. Para   gdzie relacja   jest zdefiniowana przez

 

nazywana jest półkratą górną (lub ∨-półkratą). Innymi słowy, jest to częściowy porządek, w którym każda para   ma kres górny:  

Jeśli zdefiniujemy   to otrzymamy półkratę dolną (lub ∧-półkratę), tzn. częściowy porządek, w którym każda para (x, y) ma kres dolny.

Podkraty edytuj

Podkratą kraty   nazywamy podzbiór   będący podalgebrą, tzn. dla każdego   musimy mieć  

Zupełność edytuj

Za pomocą indukcji matematycznej można udowodnić, że w kracie każdy skończony i niepusty podzbiór ma kres górny i kres dolny. Własność ta prowadzi do pojęcia kraty zupełnej – nazywamy tak częściowy porządek   w którym każdy podzbiór zbioru   ma kres górny i kres dolny[potrzebny przypis]; w szczególności, każda krata zupełna ma najmniejszy i największy element.

Rozdzielność edytuj

Krata jest rozdzielna (dystrybutywna), gdy dla każdego  

 
 

Można udowodnić, że w każdej kracie spełnione są nierówności

  oraz  

jeśli pierwsze prawo rozdzielności

 

jest spełnione dla dowolnych   to musi też zachodzić również drugie prawo rozdzielności.

Reprezentacja krat rozdzielnych edytuj

Dla każdego zbioru   zbiór potęgowy   (uporządkowany przez inkluzję  ) jest kratą rozdzielną. Podkrata kraty rozdzielnej jest zawsze sama rozdzielna, więc każda podkrata zbioru potęgowego jest też kratą rozdzielną.

Twierdzenie Birkhoffa-Stone'a o reprezentacji krat rozdzielnych mówi, że każda krata rozdzielna ma tę postać:

Każda krata rozdzielna jest izomorficzna z pewną podkratą kraty   (dla pewnego zbioru  ).

Przykłady edytuj

  • Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji na każdym zbiorze potęgowym.
  •   „Pięciokąt” lub krata   to krata pięciu elementów   spełniających relacje
  dla każdego  
 
 
  • „Diament” lub krata   to krata pięciu elementów   spełniających relacje
  dla każdego  
  dla każdych   w zbiorze  
  dla każdych   w zbiorze  

Pięciokąt i diament są kratami nierozdzielnymi, więc każda krata zawierająca pięciokąt albo diament jako podkratę musi być też nierozdzielna. Odwrotnie: w każdą kratę nierozdzielną można zanurzyć albo diament albo pięciokąt (lub obydwa) jako podkratę.

  • Rozważmy zbiór liczb całkowitych dodatnich wraz z operacjami NWD i NWW. Jeżeli zinterpretować NWD jako   a NWW jako   z własności obu operacji wynika, że spełnione są aksjomaty kraty. Z własności NWW i NWD wynika również, że jest to krata rozdzielna. Relacją   w tej kracie jest podzielność:   wtedy i tylko wtedy, gdy liczba   jest dzielnikiem liczby   Przykładem jej podkraty jest podkrata liczb parzystych.
  • Rozważmy zbiór wszystkich uporządkowanych par liczb całkowitych   wraz z relacją   określoną następująco:
     
    Relacja ta jest częściowym porządkiem i jeśli zdefiniujemy
     
    oraz
     
    to otrzymamy kratę. Na przykład
     
    oraz
     
    Krata ta ma wiele podkrat, jedną z nich jest choćby podkrata złożona z wszystkich par o drugiej współrzędnej parzystej.

Reprezentacja edytuj

Dla każdego zbioru   definiujemy   jest relacją równoważności   Wówczas   uporządkowany przez relację   jest kratą zupełną.

Można udowodnić, że każda krata jest izomorficzna z podkratą kraty   (dla pewnego zbioru  ).

Zobacz też edytuj

Przypisy edytuj

  1. krata, [w:] Encyklopedia PWN [dostęp 2021-10-02].
  2. półkrata, [w:] Encyklopedia PWN [dostęp 2022-10-12].

Linki zewnętrzne edytuj

  • Eric W. Weisstein, Lattice, [w:] MathWorld, Wolfram Research (ang.). [dostęp 2024-03-25].
  •   Lattice (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].
  •   Semi-lattice (ang.), Encyclopedia of Mathematics, encyclopediaofmath.org [dostęp 2024-03-25].