|
Ten artykuł wymaga uzupełnienia informacji.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. |
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 (ang. lattice) – struktury matematyczne, które można opisywać albo algebraicznie, albo w sensie częściowych porządków[1].
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.
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
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 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.
Podkratą kraty
nazywamy podzbiór
będący podalgebrą, tzn. dla każdego
musimy mieć
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.
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 | edytuj kod]
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
).
- 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.
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
).