Krata (matematyka)

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

Struktura algebraiczna 
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:

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:

Niekonieczność aksjomatu 1 
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 
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 
Półkraty w sensie algebraicznym to dokładnie pasy przemienne, czyli półgrupy  przemienne, w których równość  zachodzi dla dowolnego . 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 
Podkratą kraty  nazywamy podzbiór  będący podalgebrą, tzn. dla każdego  musimy mieć

Zupełność 
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; w szczególności, każda krata zupełna ma najmniejszy i największy element.

Rozdzielność 
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 
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 
 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 zdefiniujemyorazto otrzymamy kratę. Na przykładorazKrata ta ma wiele podkrat, jedną z nich jest choćby podkrata złożona z wszystkich par o drugiej współrzędnej parzystej.

Reprezentacja 
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ż 
 algebra Heytinga
 twierdzenie Stone’a o reprezentacji algebr Boole’a

Przypisy 

 
Struktury dwóch działań wewnętrznych