Artykuł należy uzupełnić o istotne informacje: coś o homomorfizmach; rozbudować wstęp, w miarę możliwości wypracować definicje intuicyjną. Dokładniejsze informacje o tym, co należy poprawić, być może znajdują się w dyskusji tego artykułu. Po wyeliminowaniu niedoskonałości należy usunąć szablon {{Dopracować}} z tego artykułu.
Ten artykuł dotyczy matematyki. Zobacz też: inne znaczenia słowa „krata”.
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”.
Kraty – struktury matematyczne, które można opisywać albo algebraicznie, albo w sensie częściowych porządków[1].
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:
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 [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
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[potrzebny przypis]; 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 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
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 ).