Krata (porządek)

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

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

Struktura algebraiczna[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

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ść[edytuj | edytuj kod]

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[edytuj | edytuj kod]

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[edytuj | edytuj kod]

  • Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji na każdym zbiorze potęgowym.
  • Przykłady krat nierozdzielnych
    "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[edytuj | edytuj kod]

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ż[edytuj | edytuj kod]