Krata (porządek)

Kraty (ang. lattice) są strukturami matematycznymi, które można opisywać albo algebraicznie albo w sensie częściowych porządków:

Struktura algebraiczna

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

1.	$x \land x = x\;$	$x \lor x = x\;$
2.	$(x\land y) \land z = x\and (y \and z)\;$	$(x\lor y)\or z = x \or (y \or z)\;$
3.	$x \and y = y \and x\;$	$x \or y = y \or x\;$
4.	$(x \land y) \or y = y\;$	$(x \lor y) \and y = y\;$

Przykładem kraty jest dowolna algebra Boole'a.

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

$x \le y \Leftrightarrow x \or y = y\;$

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

$\sup(x,y) = x\vee y$, $\inf(x,y) = x\wedge y$.

Niekonieczność aksjomatu 1

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

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

$(X \land y) \lor y = y$

a na mocy prawej:

$X \land y = y$

co po podstawieniu do poprzedniego wzoru daje:

$y \lor y = y$.

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

Struktura porządkowa

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

Jeśli zdefiniujemy

• $x\lor y := \sup(x, y)\;$
• $x\land y := \inf(x, y)\;$

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

$x \leqslant y \Leftrightarrow x \lor y = y.\;$

Półkraty

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

$x\le 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 $x, y\;$ ma kres górny: $\sup(x, y)=x + y.$

Jeśli zdefiniujemy $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 $\langle K,\vee, \wedge\rangle$ nazywamy podzbiór $P \subseteq K\;$ będący podalgebrą, tzn. dla każdego $x, y \in P\;$ musimy mieć $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 $(P, \le),\;$ w którym każdy podzbiór zbioru $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 $x,y,z:\;$

• $(x \land y) \lor z = (x \lor z) \land (y \lor z)\,$
• $(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

$(x \land y) \lor z \leqslant (x \lor z) \land (y \lor z)$ oraz $(x \lor y) \land z \geqslant (x \land z) \lor (y \land z)$

• jeśli pierwsze prawo rozdzielności

$(x \land y) \lor z = (x \lor z) \land (y \lor z)\,$

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

Reprezentacja krat rozdzielnych

Dla każdego zbioru $X,\;$ zbiór potęgowy $P(X)\;$ (uporządkowany przez inkluzję $\subseteq\;$) jest kratą rozdzielną. Podkrata kraty rozdzielnej jest zawsze sama rozdzielna, więc każda podkrata zbioru potęgowego jest też kratą rozdzielną.

Twierdzenia 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 $P(X)\;$ (dla pewnego zbioru $X\;$).

Przykłady

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

$c \leqslant x \leqslant a\;$ dla każdego $x\;$

$d \land b = e \land b =c\;$

$d \lor b = e \lor b = a$

• "Diament" lub krata $M_3\;$ to krata pięciu elementów $a,b,c,d,e,\;$ spełniających relacje

$c \leqslant x \leqslant a\;$ dla każdego $x\;$

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

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

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

Zobacz też

• Twierdzenie Stone'a o reprezentacji algebr Boole'a