Krata (matematyka)

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].

Struktura algebraiczna

Krata w sensie algebraicznym to struktura algebraiczna ${\displaystyle (A,\land ,\lor ),}$ gdzie ${\displaystyle A}$ jest (niepustym) zbiorem, a ${\displaystyle \land }$ i ${\displaystyle \lor }$ są odwzorowaniami z ${\displaystyle A\times A}$ w ${\displaystyle A}$ spełniającymi dla dowolnych ${\displaystyle x,y,z\in A}$ następujące warunki:

Przykładem kraty jest dowolna algebra Boole’a.

W każdej kracie spełniona jest równoważność: ${\displaystyle x\lor y=y\Leftrightarrow x\land y=x.}$ Relacja ${\displaystyle \leqslant ,}$ zdefiniowana za pomocą równoważności

${\displaystyle x\leqslant y\Leftrightarrow x\lor y=y}$

jest częściowym porządkiem, w którym każda para ${\displaystyle x,y}$ ma kres górny i kres dolny:

${\displaystyle \sup(x,y)=x\vee y,\quad \inf(x,y)=x\wedge y.}$

Krata permutacji zbioru czteroelementowego.

Niekonieczność aksjomatu 1

Aksjomat 1 podaje się tradycyjnie w definicji kraty, ale wynika on z aksjomatu 4:

Niech ${\displaystyle X:=x\lor y.}$ Wtedy na mocy lewej części aksjomatu 4 otrzymujemy

${\displaystyle (X\land y)\lor y=y}$

a na mocy prawej:

${\displaystyle X\land y=y}$

co po podstawieniu do poprzedniego wzoru daje:

${\displaystyle y\lor y=y.}$

Podobnie dowodzi się, że ${\displaystyle y\land y=y.}$

Struktura porządkowa

Krata w sensie częściowych porządków to (niepusty) częściowy porządek ${\displaystyle (A,\leqslant ),}$ w którym każda para ${\displaystyle x,y}$ ma kres dolny ${\displaystyle \inf(x,y)}$ i kres górny ${\displaystyle \sup(x,y).}$

Jeśli zdefiniujemy

${\displaystyle x\lor y:=\sup(x,y),}$

${\displaystyle x\land y:=\inf(x,y),}$

to dostaniemy kratę w sensie algebraicznym, w której oczywiście

${\displaystyle x\leqslant y\Leftrightarrow x\lor y=y.}$

Półkraty

Półkraty w sensie algebraicznym to dokładnie pasy przemienne, czyli półgrupy ${\displaystyle (X,+)}$ przemienne, w których równość ${\displaystyle x+x=x}$ zachodzi dla dowolnego ${\displaystyle x\in X}$^[2]. Para ${\displaystyle (X,\leqslant ),}$ gdzie relacja ${\displaystyle \leqslant }$ jest zdefiniowana przez

${\displaystyle x\leqslant y\Leftrightarrow x+y=y,}$

nazywana jest półkratą górną (lub ∨-półkratą). Innymi słowy, jest to częściowy porządek, w którym każda para ${\displaystyle x,y}$ ma kres górny: ${\displaystyle \sup(x,y)=x+y.}$

Jeśli zdefiniujemy ${\displaystyle x\leqslant y\Leftrightarrow x+y=x,}$ 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 ${\displaystyle (K,\vee ,\wedge )}$ nazywamy podzbiór ${\displaystyle P\subseteq K}$ będący podalgebrą, tzn. dla każdego ${\displaystyle x,y\in P}$ musimy mieć ${\displaystyle x\land y,x\lor y\in P.}$

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 ${\displaystyle (P,\leqslant ),}$ w którym każdy podzbiór zbioru ${\displaystyle P}$ 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 ${\displaystyle x,y,z{:}}$

${\displaystyle (x\land y)\lor z=(x\lor z)\land (y\lor z),}$

${\displaystyle (x\lor y)\land z=(x\land z)\lor (y\land z).}$

Można udowodnić, że w każdej kracie spełnione są nierówności

${\displaystyle (x\land y)\lor z\leqslant (x\lor z)\land (y\lor z)}$ oraz ${\displaystyle (x\lor y)\land z\geqslant (x\land z)\lor (y\land z),}$

jeśli pierwsze prawo rozdzielności

${\displaystyle (x\land y)\lor z=(x\lor z)\land (y\lor z)}$

jest spełnione dla dowolnych ${\displaystyle x,y,z,}$ to musi też zachodzić również drugie prawo rozdzielności.

Reprezentacja krat rozdzielnych

Dla każdego zbioru ${\displaystyle X,}$ zbiór potęgowy ${\displaystyle P(X)}$ (uporządkowany przez inkluzję ${\displaystyle \subseteq }$) 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 ${\displaystyle P(X)}$ (dla pewnego zbioru ${\displaystyle X}$).

Przykłady

• Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji na każdym zbiorze potęgowym.
• „Pięciokąt” lub krata ${\displaystyle N_{5}}$ to krata pięciu elementów ${\displaystyle a,b,c,d,e,}$ spełniających relacje

${\displaystyle c\leqslant x\leqslant a}$ dla każdego ${\displaystyle x}$

${\displaystyle d\land b=e\land b=c}$

${\displaystyle d\lor b=e\lor b=a}$

• „Diament” lub krata ${\displaystyle M_{3}}$ to krata pięciu elementów ${\displaystyle a,b,c,d,e,}$ spełniających relacje

${\displaystyle c\leqslant x\leqslant a}$ dla każdego ${\displaystyle x}$

${\displaystyle x\land y=c}$ dla każdych ${\displaystyle x\neq y}$ w zbiorze ${\displaystyle \{b,d,e\}}$

${\displaystyle x\lor y=a}$ dla każdych ${\displaystyle x\neq y}$ w zbiorze ${\displaystyle \{b,d,e\}}$

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 ${\displaystyle \land ,}$ a NWW jako ${\displaystyle \lor ,}$ 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ą ${\displaystyle \leqslant }$ w tej kracie jest podzielność: ${\displaystyle x\leqslant y}$ wtedy i tylko wtedy, gdy liczba ${\displaystyle x}$ jest dzielnikiem liczby ${\displaystyle y.}$ Przykładem jej podkraty jest podkrata liczb parzystych.
• Rozważmy zbiór wszystkich uporządkowanych par liczb całkowitych ${\displaystyle \mathbb {Z} ^{2}}$ wraz z relacją ${\displaystyle \leqslant }$ określoną następująco:
  ${\displaystyle (x_{1},y_{1})\leqslant (x_{2},y_{2})\Leftrightarrow x_{1}\leqslant x_{2}{\text{ i }}y_{1}\leqslant y_{2}.}$
  Relacja ta jest częściowym porządkiem i jeśli zdefiniujemy
  ${\displaystyle \inf((x_{1},y_{1}),(x_{2},y_{2})):=(\min(x_{1},x_{2}),\min(y_{1},y_{2}))}$
  oraz
  ${\displaystyle \sup((x_{1},y_{1}),(x_{2},y_{2})):=(\max(x_{1},x_{2}),\max(y_{1},y_{2})),}$
  to otrzymamy kratę. Na przykład
  ${\displaystyle \inf((-2,3),(1,2)):=(-2,2)}$
  oraz
  ${\displaystyle \sup((-2,3),(1,2)):=(1,3).}$
  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 ${\displaystyle A}$ definiujemy ${\displaystyle \operatorname {Eq} (A)=\{\rho \subseteq A\times A:\rho }$ jest relacją równoważności ${\displaystyle \}.}$ Wówczas ${\displaystyle \operatorname {Eq} (A),}$ uporządkowany przez relację ${\displaystyle \subseteq ,}$ jest kratą zupełną.

Można udowodnić, że każda krata jest izomorficzna z podkratą kraty ${\displaystyle \operatorname {Eq} (A)}$ (dla pewnego zbioru ${\displaystyle A}$).

Zobacz też

• algebra Heytinga
• twierdzenie Stone’a o reprezentacji algebr Boole’a

Przypisy