Kraty

Krata to zbiór uporządkowany, który ma dodatkowo tę własność, że dla każdych dwóch elementów danej kraty musi istnieć supremum i infimum, które także należą do tej kraty.

Stożek górny i dolny

Na początku mamy zbiór M, w którym jest zdefiniowany jakiś porządek ≤. Ten porządek może być dowolny, ale musi spełniać warunki relacji porządku.

Dalej weźmiemy jakiś element a ze zbioru M. Stożek górny elementu a w zbiorze M definiujemy jako wszystkie x ∈ M, które są większe lub równe a, czyli zachodzi dla nich a ≤ x. Innymi słowy jest to zbiór wszystkich ograniczeń górnych tego elementu.

Jeśli jako zbiór weźmiemy liczby naturalne, a jako element a = 7, to stożkiem górnym jest zbiór liczb {7, 8, 9, …}. W liczbach rzeczywistych dostalibyśmy przedział <7, ∞).

Weźmy teraz zbiór M = 2^ℕ — jest to zbiór potęgowy, czyli zbiór wszystkich podzbiorów liczb naturalnych. Są to więc wszystkie zbiory, które możemy zbudować z liczb naturalnych. Porządek będzie wyznaczony przez relację zawierania (bycia podzbiorem). Zachodzi więc {3, 5} ≤ {3, 4, 5} itp.

Stożkiem górnym zbioru {1, 2, 3, 4} będą wszystkie zbiory, które zawierają elementy 1, 2, 3, 4. Na przykład zbiór {1, 2, 3, 4, 5, 6, 9} albo {1, 2, 3, 4, 2323, 454645}. W stożku górnym będzie też sam zbiór {1, 2, 3, 4}.

Stożek dolny definiujemy analogicznie — zawiera elementy, które są mniejsze lub równe elementowi a. Dla a = 7 i M równego zbiorowi liczb naturalnych (liczymy je tu od jedynki) dostaniemy zbiór {1, 2, 3, 4, 5, 6, 7}. Są to te liczby naturalne, które są mniejsze lub równe siedmiu.

Dla zbioru {1, 2, 3, 4} dostaniemy wszystkie podzbiory tego zbioru.

Stożek górny i dolny kilku elementów

W poprzedniej części zdefiniowaliśmy stożki dla jednego elementu. Możemy jednak zdefiniować stożek także dla kilku elementów. Jeśli mamy zbiór M i elementy a, b, to ich wspólny stożek górny będzie zawierał elementy, które są większe lub równe jednocześnie obu elementom a i b. Innymi słowy obliczymy stożki górne obu elementów i wyznaczymy ich część wspólną. Dostaniemy w ten sposób elementy, które są na pewno większe niż a i jednocześnie większe niż b.

Zostańmy przy liczbach naturalnych: a = 3, b = 5. Wszystkie elementy większe lub równe a tworzą zbiór {3, 4, 5, 6, …}, a większe lub równe b: {5, 6, 7, 8, …}. Teraz wyznaczymy część wspólną, dzięki czemu dostaniemy znowu zbiór {5, 6, 7, 8, …}. Jeśli mamy zbiór liniowo uporządkowany, to wystarczy znaleźć większy z tych dwóch elementów i wyznaczyć jego stożek górny.

W przypadku zbiorów nie będzie to już takie proste. Możemy spróbować wyznaczyć stożek dolny zbiorów: a = {1, 2, 3} i b = {2, 3, 4}. Są to wszystkie zbiory, które są jednocześnie podzbiorami a i b. Czy na przykład zbiór {1, 2, 3} jest podzbiorem a? Tak. Czy jest też podzbiorem b? Nie. Ten zbiór nie będzie w stożku dolnym.

Możemy spróbować sprawdzić, jaki będzie największy zbiór, który będzie podzbiorem a i b. Będzie to oczywiście zbiór {2, 3}, czyli zbiór, który powstanie jako część wspólna zbiorów a ∩ b. W stożku dolnym będzie. I wszystkie podzbiory tego zbioru także. Bo jeśli na przykład ∅ ⊆ {2, 3} i jednocześnie {2, 3} ⊆ a ∧ {2, 3} ⊆ b, to na pewno także ∅ ⊆ a ∧ ∅ ⊆ b. Wynika to z przechodniości.

Na koniec zdefiniujemy stożek górny i dolny dla całego zbioru, a nie tylko dla pary elementów. Mamy zbiór M i jakiś zbiór A ⊆ M, dla którego chcemy wyznaczyć stożek górny i dolny. Wtedy zachodzi:

$$\begin{eqnarray} H(A)&=&\left\{x,|,\forall a\in A: x \ge a\right\}\\ D(A)&=&\left\{x,|,\forall a\in A: x \le a\right\} \end{eqnarray}$$

Supremum i infimum

Za pomocą stożków możemy łatwo zdefiniować infimum i supremum. Jeśli mamy zbiór M i element a ∈ M, to supremum i infimum elementu a jest znowu ten sam element a.

Jeśli jednak chcemy znaleźć supremum dwóch elementów z M, elementów a, b, to musimy się do tego zabrać inaczej. Supremum elementów a, b, oznaczane a ∨ b albo sup(a, b), jest równe najmniejszemu elementowi stożka górnego elementów a, b. Czyli wyznaczamy wszystkie elementy, które są większe lub równe elementom a, b, i z tych elementów bierzemy element najmniejszy. Nie minimalny, najmniejszy. Element najmniejszy w ogólności nie musi istnieć, więc i supremum w ogólności nie musi istnieć.

Jeśli liczymy infimum, to najpierw znajdujemy stożek dolny obu elementów, a potem jego element największy.

Przykład: wiemy już, że stożkiem górnym liczb 3 i 5 jest zbiór {5, 6, 7, …}. Elementem najmniejszym jest pięć. Zachodzi więc sup(3, 5) = 5.

Dalej wiemy, że stożek dolny zbiorów a = {1, 2, 3} i b = {2, 3, 4} jest równy zbiorowi wszystkich podzbiorów zbioru {2, 3}. Odpowiada to zbiorom: {2, 3}, {2}, {3}, ∅. Przy tym największym zbiorem jest właśnie zbiór {2, 3}. Ten zbiór jest więc infimum zbiorów a, b. Zapisujemy a ∧ b = {2, 3} albo inf(a, b) = {2, 3}.

Definicja kraty

Krata S to zbiór uporządkowany, w którym dla każdych dwóch elementów a, b ∈ S istnieje supremum i infimum, przy czym to infimum i supremum należy do zbioru S. Możemy więc napisać, że zbiór uporządkowany S jest kratą, jeśli

$$\forall a,b \in S:\quad \sup(a, b) \in S\quad\mbox{i}\quad \inf(a, b) \in S$$

Prostym przykładem kraty są liczby rzeczywiste ze zwykłym porządkiem. Zachodzi sup(a, b) = max(a, b) i inf(a, b) = min(a, b), a to są zawsze liczby rzeczywiste.

Rodzina zbiorów uporządkowana relacją zawierania, taka jak ta, którą wprowadziliśmy wcześniej, też jest kratą. Zachodzi sup(a, b) = a ∪ b i inf(a, b) = a ∩ b. To są znowu zbiory z tej rodziny zbiorów.

Jeśli jako rodzinę zbiorów S weźmiemy wszystkie dwuelementowe podzbiory liczb naturalnych (np. {1, 2}, {7, 19}, ...), to ten zbiór nie jest kratą, bo na przykład sup({1, 2}, {3, 4}) = {1, 2, 3, 4}, a zbiór {1, 2, 3, 4} nie jest elementem zbioru wszystkich dwuelementowych podzbiorów liczb naturalnych.