Krata (porządek)

Z Wikipedii

Masz nowe wiadomości (różnica z poprzednią wersją).

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

Spis treści

1 Struktura algebraiczna
2 Struktura porządkowa
3 Półkraty
4 Podkraty
5 Zupełność
6 Rozdzielność
- 6.1 Reprezentacja krat rozdzielnych
7 Przykłady
8 Reprezentacja
9 Zobacz też

[edytuj] Struktura algebraiczna

Krata w sensie algebraicznym to algebra (A, ∧, ∨), gdzie A jest (niepustym) zbiorem, a ∧ i ∨ są odwzorowaniami z A × A w A spełniającymi dla dowolnych x, y, z ∈ A nastepują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$

W każdej kracie spełniona jest równoważność: $x \lor y = y \Leftrightarrow x \land y = x.$ Relacja ≤, 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 dolny i kres górny:

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

[edytuj] Struktura porządkowa

Krata w sensie częściowych porządków to (niepusty) częściowy porządek (A, ≤), 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 algebraiczym, w której oczywiście

$x \le y \Leftrightarrow x \lor y = y.\$

[edytuj] Półkraty

Półkrata w sensie algebraicznym jest półgrupą (X, +) przemienną, w której równość x+x = x zachodzie dla dowolnego x∈X. Para (X,≤), gdzie relacja ≤ 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\le y\Leftrightarrow x + y = x$ , to otrzymamy półkratę dolnę (lub ∧-półkrata), tzn. częściowy porządek, w którym każda para (x, y) ma kres dolny.

[edytuj] Podkraty

Podkratą kraty $\langle K,\vee, \wedge\rangle$ nazywamy podzbiór P ⊆ K będący podalgebrą, tzn: dla każdego x, y ∈ P musimy mieć x ∧ y, x∨y ∈ P.

[edytuj] Zupełność

Za pomocą indukcji matematycznej można udowodnić, że w kracie każdy skończony i niepusty podzbior ma kres górny i kres dolny. Własność ta prowadzi do pojęcia kraty zupełnej – nazywamy tak częściowy porządek (P, ≤), w którym każdy podzbiór zbioru P ma kres górny i kres dolny; w szczególnosci, każda krata zupełna ma najmniejszy i największy element.

[edytuj] 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 \le (x \lor z) \land (y \lor z)$ oraz $(x \lor y) \land z \ge (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.

[edytuj] Reprezentacja krat rozdzielnych

Dla każdego zbioru X, zbiór potęgowy P(X) (uporządkowany przez inkluzję ⊆) 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).

[edytuj] Przykłady

Kratami są wszystkie zbiory uporządkowane liniowo oraz relacją inkluzji

na każdym zbiorze potęgowym.

"Pentagram" lub krata N₅ to krata pięciu elementów a, b, c, d, e, spełniaca relacji

c ≤ x ≤ a dla każdego x

d ∧ b = e ∧ b = c

d ∨ b = e ∨ b = a

"Diament" lub krata M₃ to krata pięciu elementów a, b, c, d, e, spełniających relacje

c ≤ x ≤ a dla każdego x

x ∧ y = c dla każdych x ≠ y w zbiorze {b,d, e}

x ∨ y = a dla każdych x ≠ y w zbiorze {b,d, e}

Pentagram i diament są kratami nierozdzielnymi, więc każda krata zawierająca pentagram albo diament jako podkratę musi być też nierozdzielna. Odwrotnie: w każdą kratę nierozdzielną można zanurzyć albo diament albo pentagon (lub oba) jako podkratę.

Rozważmy zbiór liczb całkowitych dodatnich wraz z operacjami NWD i NWW. Jeżeli zinterpretować NWD jako ∧, a NWW jako ∨, 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 rozdzielcza. Relacją ≤ w tej kracie jest podzielność: x ≤ 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 Z² wraz z relacją ≤ określoną następująco $(x_1, y_1)\le(x_2,y_2)\Leftrightarrow x_1\le x_2\mbox{ i } y_1\le y_2$ . Relacja ta jest częściowym porządkiem i jeśli zdefiniujmy $\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.