Krata (matematyka)

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ść.

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 $\wedge$ i $\vee$.

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 $(L,\leqslant )$ będzie zbiorem częściowo uporządkowanym. Mówi się, że $L$ jest kratą, jeżeli dla każdych dwóch elementów $x,y\in L$ istnieją:

• kres dolny albo infimum elementów $x$ i $y$, oznaczany przez $x\wedge y$;
• kres górny albo supremum elementów $x$ i $y$, oznaczany przez $x\vee y$.

Innymi słowy,

$x\wedge y=\inf\{x,y\},$

$x\vee y=\sup\{x,y\}.$

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

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

$(L,\wedge ,\vee ),$

gdzie $L$ jest niepustym zbiorem, a $\wedge$ i $\vee$ są działaniami dwuargumentowymi na $L$, spełniającymi dla wszystkich $x,y,z\in L$ następujące prawa:

Nazwa prawa	Dla $\wedge$	Dla $\vee$
idempotentność	$x\wedge x=x$	$x\vee x=x$
przemienność	$x\wedge y=y\wedge x$	$x\vee y=y\vee x$
łączność	$(x\wedge y)\wedge z=x\wedge (y\wedge z)$	$(x\vee y)\vee z=x\vee (y\vee z)$
prawa absorpcji	$x\wedge (x\vee y)=x$	$x\vee (x\wedge y)=x$

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

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

$x\leqslant y\quad \Longleftrightarrow \quad x\vee y=y.$

Równoważnie,

$x\leqslant y\quad \Longleftrightarrow \quad x\wedge y=x.$

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

Odwrotnie, jeżeli $(L,\leqslant )$ jest kratą w sensie porządkowym, to działania

$x\wedge y=\inf\{x,y\},\qquad x\vee y=\sup\{x,y\}$

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ę:

• $\leqslant$ na $\geqslant$,
• $\wedge$ na $\vee$,
• 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

$x\wedge (x\vee y)=x$

jest

$x\vee (x\wedge y)=x.$

Elementy wyróżnione

Krata może, ale nie musi, mieć element najmniejszy i największy. Element $0\in L$ nazywa się zerem albo elementem najmniejszym, jeżeli

$0\leqslant x$

dla każdego $x\in L$. Element $1\in L$ nazywa się jedynką albo elementem największym, jeżeli

$x\leqslant 1$

dla każdego $x\in L$.

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

$x\wedge y=0,\qquad x\vee y=1.$

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 $\vee$-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 $(S,\vee )$. Porządek można wtedy zdefiniować przez

$x\leqslant y\quad \Longleftrightarrow \quad x\vee y=y.$

Półkrata dolna albo $\wedge$-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 $(S,\wedge )$, a porządek można zdefiniować przez

$x\leqslant y\quad \Longleftrightarrow \quad x\wedge y=x.$

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

Podkraty

Niech $(L,\wedge ,\vee )$ będzie kratą. Podzbiór $S\subseteq L$ nazywa się podkratą, jeżeli jest zamknięty na oba działania kratowe, to znaczy dla każdych $x,y\in S$ zachodzi

$x\wedge y\in S,\qquad x\vee y\in S.$

Podkrata z porządkiem odziedziczonym z $L$ 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 $\wedge$ i $\vee$ pochodzące z $L$, to kresy w podkracie pokrywają się z tymi działaniami.

Homomorfizmy i izomorfizmy

Jeżeli $L$ i $M$ są kratami, to odwzorowanie

$f\colon L\to M$

nazywa się homomorfizmem krat, jeżeli dla wszystkich $x,y\in L$ zachodzi

$f(x\wedge y)=f(x)\wedge f(y),$

$f(x\vee y)=f(x)\vee f(y).$

Każdy homomorfizm krat jest odwzorowaniem monotonicznym, to znaczy

$x\leqslant y\quad \Longrightarrow \quad f(x)\leqslant f(y).$

Wynika to z faktu, że $x\leqslant y$ jest równoważne $x\wedge y=x$, a więc

$f(x)=f(x\wedge y)=f(x)\wedge f(y).$

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ł $0$ i $1$. W literaturze konwencje mogą się różnić: czasami zachowywanie kresów pustych, a więc elementów $0$ i $1$, jest włączone do definicji homomorfizmu krat ograniczonych.

Ideały i filtry

W kracie $L$ ideałem nazywa się zwykle niepusty podzbiór $I\subseteq L$, który jest:

• skierowany w górę względem $\vee$, to znaczy $x,y\in I$ pociąga $x\vee y\in I$;
• dziedziczny w dół, to znaczy jeśli $x\in I$ oraz $y\leqslant x$, to $y\in I$.

Dualnie, filtrem jest niepusty podzbiór $F\subseteq L$, który jest zamknięty na $\wedge$ 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 $L$ jest zupełna, jeżeli każdy podzbiór $A\subseteq L$ ma kres dolny i kres górny:

$\bigwedge A,\qquad \bigvee A.$

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

$0=\bigvee \varnothing ,\qquad 1=\bigwedge \varnothing$

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

$0=\bigwedge L,\qquad 1=\bigvee L.$

Przykładami krat zupełnych są:

• zbiór potęgowy ${\mathcal {P}}(X)$ 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ń $\wedge$ i $\vee$. 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 $L$ jest rozdzielna albo dystrybutywna, jeżeli dla wszystkich $x,y,z\in L$ zachodzą równoważne prawa rozdzielności:

$x\wedge (y\vee z)=(x\wedge y)\vee (x\wedge z),$

$x\vee (y\wedge z)=(x\vee y)\wedge (x\vee z).$

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

$(x\wedge y)\vee (x\wedge z)\leqslant x\wedge (y\vee z),$

$x\vee (y\wedge z)\leqslant (x\vee y)\wedge (x\vee z).$

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: $M_{3}$ albo $N_{5}$.

Pięcioelementowe kraty nierozdzielne $M_{3}$ i $N_{5}$

Kraty modularne

Krata $L$ jest modularna, jeżeli dla wszystkich $x,y,z\in L$ takich, że $x\leqslant z$, zachodzi

$x\vee (y\wedge z)=(x\vee y)\wedge z.$

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 $U\subseteq W$ zachodzi tożsamość

$U+(V\cap W)=(U+V)\cap W.$

Kraty ortomodularne

Krata ortomodularna jest kratą ograniczoną z działaniem ortodopełnienia $x\mapsto x^{\perp }$, spełniającą prawo ortomodularne:

$x\leqslant y\quad \Longrightarrow \quad y=x\vee (y\wedge x^{\perp }).$

Najważniejszym przykładem jest krata domkniętych podprzestrzeni przestrzeni Hilberta, gdzie $x^{\perp }$ 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 $A$ zbiór

$\operatorname {Eq} (A)=\{\rho \subseteq A\times A:\rho {\text{ jest relacją równoważności}}\}$

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 $E$ jest kratą Banacha, jeżeli jest jednocześnie kratą wektorową oraz jej norma spełnia warunek monotoniczności:

$|x|\leqslant |y|\quad \Longrightarrow \quad \|x\|\leqslant \|y\|,$

gdzie

$|x|=x\vee (-x).$

Przykładami krat Banacha są:

• przestrzenie $C(K)$ funkcji ciągłych na zwartej przestrzeni Hausdorffa $K$, z porządkiem punktowym;
• przestrzenie $L^{p}(\mu )$ dla $1\leqslant p\leqslant \infty$, z porządkiem prawie wszędzie;
• przestrzeń ciągów $\ell ^{p}$;
• przestrzeń $c_{0}$ 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 $X$ jego zbiór potęgowy ${\mathcal {P}}(X)$, uporządkowany przez inkluzję, jest kratą zupełną. Dla $A,B\subseteq X$ zachodzi

$A\wedge B=A\cap B,\qquad A\vee B=A\cup B.$

Jest to algebra Boole’a z elementem najmniejszym $\varnothing$ i największym $X$.

Łańcuchy

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

$x\wedge y=\min\{x,y\},\qquad x\vee y=\max\{x,y\}.$

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 $m,n\in \mathbb {N}$:

$m\wedge n=\operatorname {NWD} (m,n),$

$m\vee n=\operatorname {NWW} (m,n).$

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

Produkt krat

Jeżeli $L_{1}$ i $L_{2}$ są kratami, to ich iloczyn kartezjański $L_{1}\times L_{2}$ z porządkiem współrzędnościowym jest kratą. Dla par liczb całkowitych:

$(a,b)\leqslant (c,d)\quad \Longleftrightarrow \quad a\leqslant c{\text{ oraz }}b\leqslant d.$

Wtedy

$(a,b)\wedge (c,d)=(\min(a,c),\min(b,d)),$

$(a,b)\vee (c,d)=(\max(a,c),\max(b,d)).$

Podprzestrzenie liniowe

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

$U\wedge V=U\cap V,\qquad U\vee V=U+V.$

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 $A$ zbiór wszystkich relacji równoważności na $A$, 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

Zbiór wszystkich partycji zbioru $n$-elementowego tworzy kratę, naturalnie izomorficzną z kratą relacji równoważności na tym zbiorze. Porządek oznacza uszczegółowienie albo pogrubienie partycji.

Krata partycji zbioru czteroelementowego

Kraty skończone i diagramy Hassego

Kraty skończone często przedstawia się za pomocą diagramów Hassego. Elementy rysuje się jako punkty, a relację pokrywania jako krawędzie skierowane ku górze. W takim diagramie kres górny dwóch elementów jest najniższym punktem leżącym nad oboma, a kres dolny – najwyższym punktem leżącym pod oboma.

Najprostsze przykłady krat skończonych to:

• krata dwuelementowa;
• łańcuchy skończone;
• krata $M_{3}$, zwana diamentem;
• krata $N_{5}$, zwana pięciokątem;
• kraty podzbiorów zbiorów skończonych;
• kraty partycji zbiorów skończonych;
• kraty dzielników ustalonej liczby naturalnej.

Znaczenie i zastosowania

Kraty dostarczają wspólnego języka dla wielu konstrukcji matematycznych opartych na pojęciach porządku, przecięcia i generowania. W logice algebry Boole’a opisują klasyczną logikę zdań, algebry Heytinga opisują logikę intuicjonistyczną, a kraty ortomodularne pojawiają się w logice kwantowej. W algebrze kraty podgrup, ideałów i kongruencji opisują strukturę obiektów algebraicznych. W analizie funkcjonalnej kraty Banacha łączą porządek z normą i operatorami dodatnimi. W informatyce kraty zupełne i półkraty występują w analizie statycznej programów, semantyce denotacyjnej, teorii dziedzin i analizie przepływu danych.

Zobacz też

• algebra Boole’a
• algebra Heytinga
• krata ortomodularna
• teoria porządku
• diagram Hassego
• półkrata
• twierdzenie Knastera-Tarskiego
• twierdzenie Stone’a o reprezentacji algebr Boole’a
• krata Banacha

Bibliografia

• Garrett Birkhoff, Lattice Theory, American Mathematical Society, 1967.
• B.A. Davey, H.A. Priestley, Introduction to Lattices and Order, Cambridge University Press, 2002.
• George Grätzer, General Lattice Theory, Birkhäuser, 2003.
• George Grätzer, Lattice Theory: Foundation, Birkhäuser, 2011.
• Peter Crawley, Robert P. Dilworth, Algebraic Theory of Lattices, Prentice-Hall, 1973.
• Charalambos D. Aliprantis, Owen Burkinshaw, Positive Operators, Springer, 2006.
• Peter Meyer-Nieberg, Banach Lattices, Springer, 1991.

Linki zewnętrzne

• Eric W.E.W. Weisstein Eric W.E.W., Lattice, [w:] MathWorld, Wolfram Research  (ang.). [dostęp 2026-05-08].
• Lattice (ang.), Encyclopedia of Mathematics [dostęp 2026-05-08].
• Semi-lattice (ang.), Encyclopedia of Mathematics [dostęp 2026-05-08].