mały|Dzielniki liczby 60, uporządkowane przez podzielność, tworzą kratę. Kresem dolnym dwóch liczb jest ich największy wspólny dzielnik, a kresem górnym – najmniejsza wspólna wielokrotność. mały|Diagram Hassego kraty Tamriego

Krata – struktura matematyczna opisująca sytuację, w której dla każdej pary elementów istnieją dwa wyróżnione elementy: ich największe wspólne ograniczenie dolne oraz najmniejsze wspólne ograniczenie górne. Kraty można definiować równoważnie na dwa sposoby: jako szczególne zbiory częściowo uporządkowane albo jako struktury algebraiczne z dwiema działaniami wewnętrznymi, zwykle oznaczanymi przez i .

Intuicyjnie krata jest więc porządkiem, w którym dowolne dwa elementy można w jednoznaczny sposób „połączyć od góry” i „przeciąć od dołu”. W języku porządkowym działania te są kresem górnym i kresem dolnym, natomiast w języku algebraicznym są podstawowymi działaniami struktury. Typowymi przykładami są zbiór potęgowy z działaniami sumy i przecięcia, dodatnie liczby całkowite z działaniami NWD i NWW, rodziny podprzestrzeni liniowych oraz kraty podgrup, ideałów lub relacji równoważności.

Kraty są badane w teorii porządku, algebrze uniwersalnej, logice matematycznej, teorii mnogości, topologii, analizie funkcjonalnej i informatyce teoretycznej. Szczególnymi klasami krat są między innymi algebry Boole’a, algebry Heytinga, kraty rozdzielne, kraty modularne, kraty ortomodularne, kraty zupełne oraz kraty Banacha.

Ujęcie porządkowe Niech będzie zbiorem częściowo uporządkowanym. Mówi się, że jest kratą, jeżeli dla każdych dwóch elementów istnieją: kres dolny albo infimum elementów i , oznaczany przez ; kres górny albo supremum elementów i , oznaczany przez .

Innymi słowy,

Element jest największym elementem spośród wszystkich elementów mniejszych lub równych zarówno , jak i . Element jest najmniejszym elementem spośród wszystkich elementów większych lub równych zarówno , jak i .

Jeżeli każdy skończony niepusty podzbiór zbioru częściowo uporządkowanego ma kres dolny i kres górny, to w szczególności każda para ma takie kresy. Odwrotnie, jeśli każda para ma kres dolny i górny, to przez indukcję wynika istnienie kresów dla każdego skończonego niepustego podzbioru.

Ujęcie algebraiczne Kratę można także zdefiniować czysto algebraicznie. Krata to algebra

gdzie jest niepustym zbiorem, a i są działaniami dwuargumentowymi na , spełniającymi dla wszystkich następujące prawa: Nazwa prawa Dla Dla idempotentność przemienność łączność prawa absorpcji

Działanie nazywa się często spotkaniem albo iloczynem kratowym (ang. meet), natomiast – złączeniem albo sumą kratową (ang. join).

Z definicji algebraicznej można odzyskać porządek, kładąc

Równoważnie,

Relacja ta jest częściowym porządkiem, a działania i są odpowiednio kresami dolnymi i górnymi w tym porządku.

Odwrotnie, jeżeli jest kratą w sensie porządkowym, to działania

spełniają powyższe aksjomaty algebraiczne. Oba ujęcia są zatem równoważne.

Dualność Teoria krat ma naturalną zasadę dualności. Jeżeli w prawdziwym twierdzeniu o kratach zamieni się: na , na , kresy dolne na kresy górne, element najmniejszy na element największy,

to otrzymuje się twierdzenie dualne, również prawdziwe. Na przykład dualnym prawem do

jest

Elementy wyróżnione Krata może, ale nie musi, mieć element najmniejszy i największy. Element nazywa się zerem albo elementem najmniejszym, jeżeli

dla każdego . Element nazywa się jedynką albo elementem największym, jeżeli

dla każdego .

Krata mająca oba te elementy nazywa się kratą ograniczoną. W kracie ograniczonej element jest dopełnieniem elementu , jeżeli

Kratę ograniczoną, w której każdy element ma co najmniej jedno dopełnienie, nazywa się kratą dopełnioną. Dopełnienie nie musi być jednoznaczne, chyba że rozważa się dodatkowe założenia, na przykład strukturę algebry Boole’a.

Półkraty Półkrata górna albo -półkrata to częściowy porządek, w którym każda para elementów ma kres górny. Algebraicznie jest to przemienna, łączna i idempotentna półgrupa . Porządek można wtedy zdefiniować przez

Półkrata dolna albo -półkrata to częściowy porządek, w którym każda para elementów ma kres dolny. Algebraicznie jest to przemienna, łączna i idempotentna półgrupa , a porządek można zdefiniować przez

Każda krata jest jednocześnie półkratą dolną i półkratą górną, przy czym oba porządki są zgodne.

Podkraty Niech będzie kratą. Podzbiór nazywa się podkratą, jeżeli jest zamknięty na oba działania kratowe, to znaczy dla każdych zachodzi

Podkrata z porządkiem odziedziczonym z jest kratą, ale trzeba zachować ostrożność: kresy w podkracie muszą być liczone wewnątrz tej podkraty. Jeżeli podzbiór jest zamknięty na działania i pochodzące z , to kresy w podkracie pokrywają się z tymi działaniami.

Homomorfizmy i izomorfizmy Jeżeli i są kratami, to odwzorowanie

nazywa się homomorfizmem krat, jeżeli dla wszystkich zachodzi

Każdy homomorfizm krat jest odwzorowaniem monotonicznym, to znaczy

Wynika to z faktu, że jest równoważne , a więc

Odwzorowanie monotoniczne nie musi jednak być homomorfizmem krat, ponieważ może nie zachowywać kresów.

Bijektywny homomorfizm krat, którego odwrotność również jest homomorfizmem krat, nazywa się izomorfizmem krat. Równoważnie jest to bijekcja zachowująca oba działania kratowe. Dwie kraty izomorficzne uważa się za takie same z punktu widzenia teorii krat.

Jeżeli kraty są ograniczone, często wymaga się dodatkowo, aby homomorfizm zachowywał i . W literaturze konwencje mogą się różnić: czasami zachowywanie kresów pustych, a więc elementów i , jest włączone do definicji homomorfizmu krat ograniczonych.

Ideały i filtry W kracie ideałem nazywa się zwykle niepusty podzbiór , który jest: skierowany w górę względem , to znaczy pociąga ; dziedziczny w dół, to znaczy jeśli oraz , to .

Dualnie, filtrem jest niepusty podzbiór , który jest zamknięty na i dziedziczny w górę. Ideały i filtry odgrywają istotną rolę w reprezentacji krat rozdzielnych, algebrach Boole’a, algebrach Heytinga i logice.

Kraty zupełne Krata jest zupełna, jeżeli każdy podzbiór ma kres dolny i kres górny:

W szczególności krata zupełna ma element najmniejszy i największy, ponieważ

przy jednej z powszechnych konwencji porządkowych. Równoważnie można pisać

Przykładami krat zupełnych są: zbiór potęgowy uporządkowany przez inkluzję; krata wszystkich podprzestrzeni liniowych danej przestrzeni liniowej; krata wszystkich domkniętych podprzestrzeni przestrzeni Hilberta; krata relacji równoważności na ustalonym zbiorze; krata wszystkich podgrup danej grupy; krata wszystkich ideałów danego pierścienia.

W każdej kracie zupełnej kresy dowolnych rodzin można traktować jako nieskończone odpowiedniki działań i . Kraty zupełne są podstawowe w teorii punktów stałych, teorii dziedzin, semantyce języków programowania i topologii. Klasycznym wynikiem jest twierdzenie Knastera-Tarskiego, według którego monotoniczne odwzorowanie kraty zupełnej w siebie ma kratę punktów stałych.

Rozdzielność Krata jest rozdzielna albo dystrybutywna, jeżeli dla wszystkich zachodzą równoważne prawa rozdzielności:

W każdej kracie zachodzą nierówności

Równości są dodatkowym warunkiem charakterystycznym dla krat rozdzielnych.

Każda algebra Boole’a jest kratą rozdzielną. Z drugiej strony krata rozdzielna nie musi być algebrą Boole’a, ponieważ może nie mieć dopełnień.

Klasyczne twierdzenie Birkhoffa mówi, że krata jest rozdzielna wtedy i tylko wtedy, gdy nie zawiera podkraty izomorficznej z jedną z dwóch pięcioelementowych krat nierozdzielnych: albo .

mały|300px|Pięcioelementowe kraty nierozdzielne i

Kraty modularne Krata jest modularna, jeżeli dla wszystkich takich, że , zachodzi

Każda krata rozdzielna jest modularna, ale nie każda krata modularna jest rozdzielna. Klasycznym przykładem kraty modularnej nierozdzielnej jest krata wszystkich podprzestrzeni liniowych przestrzeni wektorowej wymiaru co najmniej dwa.

Kraty modularne pojawiają się naturalnie w algebrze liniowej, geometrii rzutowej, teorii grup i teorii modułów. Krata podprzestrzeni przestrzeni liniowej jest modularna, ponieważ dla zachodzi tożsamość

Kraty ortomodularne Krata ortomodularna jest kratą ograniczoną z działaniem ortodopełnienia , spełniającą prawo ortomodularne:

Najważniejszym przykładem jest krata domkniętych podprzestrzeni przestrzeni Hilberta, gdzie oznacza dopełnienie ortogonalne. Kraty ortomodularne są podstawowym obiektem logiki kwantowej.

Reprezentacje krat Kraty można reprezentować na różne sposoby jako kraty podzbiorów, relacji lub struktur algebraicznych.

Dla każdego zbioru zbiór

uporządkowany przez inkluzję jest kratą zupełną. Kres dolny rodziny relacji równoważności jest ich przecięciem, natomiast kres górny jest najmniejszą relacją równoważności zawierającą ich sumę. Twierdzenie Whitmana mówi, że każda krata jest izomorficzna z podkratą kraty relacji równoważności pewnego zbioru.

Dla krat rozdzielnych istnieją reprezentacje przez zbiory. W szczególności każda krata rozdzielna może być zanurzona w kracie zbiorów z działaniami przecięcia i sumy. Dla skończonych krat rozdzielnych klasyczne twierdzenie Birkhoffa przedstawia kratę jako kratę ideałów porządku częściowego elementów nierozkładalnych względem złączenia.

Dla algebr Boole’a szczególną postacią takiej reprezentacji jest twierdzenie Stone’a o reprezentacji algebr Boole’a.

Kraty Banacha W analizie funkcjonalnej ważną rolę odgrywają kraty Banacha. Są to przestrzenie Banacha wyposażone w porządek kratowy zgodny ze strukturą liniową i normą. Dokładniej, rzeczywista przestrzeń Banacha jest kratą Banacha, jeżeli jest jednocześnie kratą wektorową oraz jej norma spełnia warunek monotoniczności:

gdzie

Przykładami krat Banacha są: przestrzenie funkcji ciągłych na zwartej przestrzeni Hausdorffa , z porządkiem punktowym; przestrzenie dla , z porządkiem prawie wszędzie; przestrzeń ciągów ; przestrzeń ciągów zbieżnych do zera.

Kraty Banacha łączą teorię porządku, analizę funkcjonalną i teorię operatorów dodatnich. Bada się w nich między innymi ideały kratowe, pasma, operatory dodatnie, własności porządkowe normy oraz związki z teorią miary.

Przykłady Zbiory potęgowe Dla dowolnego zbioru jego zbiór potęgowy , uporządkowany przez inkluzję, jest kratą zupełną. Dla zachodzi

Jest to algebra Boole’a z elementem najmniejszym i największym .

Łańcuchy Każdy zbiór liniowo uporządkowany, w którym każda para ma minimum i maksimum, jest kratą:

W szczególności każdy niepusty porządek liniowy jest kratą w sensie par, ponieważ każda para ma minimum i maksimum.

Liczby naturalne z podzielnością Zbiór dodatnich liczb całkowitych uporządkowany przez relację podzielności jest kratą. Dla :

Krata ta jest rozdzielna. Jeżeli ograniczy się ją do dzielników ustalonej liczby , otrzymuje się kratę skończoną.

Produkt krat Jeżeli i są kratami, to ich iloczyn kartezjański z porządkiem współrzędnościowym jest kratą. Dla par liczb całkowitych:

Wtedy

Podprzestrzenie liniowe Zbiór wszystkich podprzestrzeni liniowych przestrzeni wektorowej jest kratą zupełną. Kresem dolnym jest przecięcie, a kresem górnym suma podprzestrzeni:

Krata ta jest modularna. Zwykle nie jest rozdzielna, gdy wymiar przestrzeni jest co najmniej dwa.

Podgrupy i ideały Zbiór wszystkich podgrup danej grupy, uporządkowany przez inkluzję, jest kratą zupełną. Kres dolny jest przecięciem, a kres górny jest podgrupą generowaną przez sumę mnogościową podgrup. Podobnie zbiór ideałów pierścienia tworzy kratę, gdzie kres dolny jest przecięciem, a kres górny sumą ideałów.

Relacje równoważności Dla ustalonego zbioru zbiór wszystkich relacji równoważności na , uporządkowany przez inkluzję, jest kratą zupełną. Jest to ważny przykład w algebrze uniwersalnej, gdzie relacje równoważności zgodne z działaniami algebry nazywa się kongruencjami.

Krata partycji