Własności kraty

[max123321]

Jeśli \(\displaystyle{ (A,r)}\) jest kratą to: (zaznacz zdania prawdziwe)

a) \(\displaystyle{ r}\) jest relacją porządku liniowego.

Nie wiem, czy dobrze rozumiem te kraty, ale z tego co myślę, to nie musi być to relacja porządku liniowego, bo na przykład jeśli \(\displaystyle{ A=\left\{ 1,2,3\right\} }\) i \(\displaystyle{ r=\left\{ (1,2)\right\} }\), to \(\displaystyle{ (A,r)}\) jest kratą, bo dla \(\displaystyle{ (1,2)}\), kres dolny to \(\displaystyle{ 1}\), a kres górny to \(\displaystyle{ 2}\), ale na przykład elementy \(\displaystyle{ 1}\) i \(\displaystyle{ 3}\) nie są porównywalne, zatem nie jest to porządek liniowy.

Dobrze to rozumiem?

[Jan Kraszewski]

Nie bardzo.

Po pierwsze, krata jest częściowym porządkiem, a relacja \(\displaystyle{ r=\{(1,2)\}}\) nie jest porządkiem. Zapewne chodziło Ci o relację \(\displaystyle{ r=\{(1,2),(1,1), (2,2),(3,3)\}.}\)

Po drugie, (po tej poprawce) nie jest to krata - w kracie każdy dwuelementowy podzbiór ma kres górny i kres dolny, a tutaj tylko zbiór \(\displaystyle{ \{1,2\}}\) ma kresy, zaś zbiory \(\displaystyle{ \{1,3\}}\) i \(\displaystyle{ \{2,3\}}\) nie mają kresów.

Pomyśl raczej o kracie \(\displaystyle{ \left\langle P(\{0,1\}), \subseteq \right\rangle .}\)

JK

[Jakub Gurak]

Podany przez Ciebie przykład relacji nie jest kratą, bo nie jest częściowym porządkiem, bo taka relacja nie jest zwrotna.
Proponuje rozważyć zbiór uporządkowany \(\displaystyle{ X}\) o poniższym diagramie Hassego:

Krata.jpg (7.83 KiB) Przejrzano 337 razy

Wtedy dla dowolnych dwóch różnych punktów \(\displaystyle{ x,y \in X}\) istnieje supremum \(\displaystyle{ \bigvee \left\{ x,y\right\}}\), i istnieje infimum \(\displaystyle{ \bigwedge \left\{ x,y\right\}}\), (a oczywiście \(\displaystyle{ \bigvee \left\{ x\right\} =x= \bigwedge\left\{ x\right\}}\)), wobec czego jest to krata, ale nie jest to oczywiście liniowy porządek.\(\displaystyle{ \square}\)

[max123321]

Kuźwa, no nie rozumiem tych krat. Co to są te kresy? Niby widzę tę definicję kresów z wikipedii, ale nie bardzo rozumiem. Możesz mi to wytłumaczyć na przykładzie? Moje pytanie jest, czy jak jest krata i w dowolnym podzbiorze \(\displaystyle{ A}\) jak mają być kres górny i dolny, to to oznacza, że dowolne dwa elementy mają być porównywalne? Chyba nie o to chodzi. Bo w tym przykładzie, który podałeś \(\displaystyle{ r=\{(1,2),(1,1), (2,2),(3,3)\}}\) mówisz, że podzbiór \(\displaystyle{ \left\{ 1,2\right\} }\), ma kresy i to jak rozumiem, z tego powodu, że jest element \(\displaystyle{ (1,2)}\) i w tym zbiorze mamy infimum \(\displaystyle{ 1}\) i supremum \(\displaystyle{ 2}\), a gdybyśmy zamiast \(\displaystyle{ (1,2)}\) mieli w tym zbiorze element \(\displaystyle{ (2,1)}\), to również istnieją kresy, tylko \(\displaystyle{ 2}\) to infimum, a \(\displaystyle{ 1}\) maksimum w tym przypadku? O to chodzi? A zbiór \(\displaystyle{ \left\{ 1,3\right\} }\) i \(\displaystyle{ \left\{ 2,3\right\} }\) nie mają kresów bo w tej relacji nie występuje, żaden element z \(\displaystyle{ (1,3),(3,1),(2,3),(3,2)}\), tak? Czy dla dowolnych dwóch elementów kresy mają zawsze być te same?

Dobra teraz myślę o tym Twoim \(\displaystyle{ \left\langle P(\{0,1\}), \subseteq \right\rangle}\). To jak rozumiem elementami tej kraty są na przykład \(\displaystyle{ (\emptyset,\emptyset)}\) lub \(\displaystyle{ (\left\{ 0\right\},\left\{ 0,1\right\}) }\) i inne. Sprawdziłem, że jest to relacja zwrotna, bo każdy zbiór zawiera się sam w sobie i jest antysymetryczna, bo dowolne dwa różne elementy jeśli są ze sobą w relacji to tylko w jedną stronę i jest też przechodnia co myślę, że jest widoczne. Czyli faktycznie jest to porządek, ale elementy \(\displaystyle{ \left\{ 0\right\} }\) i \(\displaystyle{ \left\{ 1\right\} }\) nie są porównywalne, zatem nie może to być porządek liniowy. A no i te kresy w tej kracie to jak rozumiem dla dowolnego dwuelementowego podzbioru kres dolny to jest zawsze \(\displaystyle{ \emptyset}\), a kres górny to \(\displaystyle{ \left\{ 0,1\right\} }\), zgadza się?

[Jakub Gurak]

Moje pytanie jest, czy jak jest krata i w dowolnym podzbiorze \(\displaystyle{ A}\) jak mają być kres górny i dolny, to to oznacza, że dowolne dwa elementy mają być porównywalne? Chyba nie o to chodzi.

Kres górny zbioru \(\displaystyle{ A \subset X}\), to jest to jego najmniejsze ograniczenie górne (czyli jego element największy lub taki element rozgraniczający, że wśród ograniczeń górnych tego zbioru jest element najmniejszy). Na podanym diagramie Hassego poszukujesz więc takich ograniczeń górnych; i istota wyboru takich dwóch różnych punktów jest w tym, że jak na moim diagramie weźmiesz punkty leżące wzdłuż prostej poziomej jaką można poprowadzić łącząc dwa odpowiednie punkty, to ten daszek nad nimi i jego wierzchołek, to jest to ograniczenie górne tych dwóch punktów (formalnie zbioru dwuelementowego złożonego z tych dwóch punktów); ponadto takie ograniczenie jest jedyne, a zatem jest najmniejsze z nich, i jest to kres górny takiego zbioru. Podobnie infimum zbioru \(\displaystyle{ A \subset X}\) jest to jego ograniczenie dolne- największe z możliwych. Poszukujesz zatem dla tych dwóch punktów (tych samych co powyżej) ograniczeń dolnych; a ponieważ mamy ten 'daszek' dolny, to jego wierzchołek jest ograniczeniem dolnym tych dwóch punktów, i to w dodatku jedynym, a zatem jest wśród nich największym takim ograniczeniem, a więc jest to infimum dla tych dwóch punktów.
(To dla mnie jest to już trudniejszy temat, bo nie ma tu prostej drogi z supremum infimum zbiorów na prostej do takich diagramów Hassego... Ja jestem specjalistą od zastosowań zbiorów jednoelementowych, np. od zastosowań \(\displaystyle{ \left\{ 0\right\}}\) ).

[max123321]

Ok, rozumiem. Tu jest jeszcze podpunkt

b) Czy prawdą jest, że jeśli \(\displaystyle{ (A,r)}\) jest kratą, to w zbiorze uporządkowanym \(\displaystyle{ (A,r)}\) jest element największy?

Jak to zrobić?

[Jan Kraszewski]

Dobra teraz myślę o tym Twoim \(\displaystyle{ \left\langle P(\{0,1\}), \subseteq \right\rangle}\).

Nie wiem, czy zauważyłeś, ale diagram Hassego tego porządku chwilę później narysował Jakub Gurak.

A no i te kresy w tej kracie to jak rozumiem dla dowolnego dwuelementowego podzbioru kres dolny to jest zawsze \(\displaystyle{ \emptyset}\), a kres górny to \(\displaystyle{ \left\{ 0,1\right\} }\), zgadza się?

Nie.

b) Czy prawdą jest, że jeśli \(\displaystyle{ (A,r)}\) jest kratą, to w zbiorze uporządkowanym \(\displaystyle{ (A,r)}\) jest element największy?

Jak to zrobić?

Pomyśl o rodzinie wszystkich skończonych podzbiorów zbioru \(\displaystyle{ \NN}\). Czy to jest krata? Czy ma element największy?

JK

[max123321]

A no i te kresy w tej kracie to jak rozumiem dla dowolnego dwuelementowego podzbioru kres dolny to jest zawsze \(\displaystyle{ \emptyset}\), a kres górny to \(\displaystyle{ \left\{ 0,1\right\} }\), zgadza się?

Nie.

Dlaczego? A jakie tu są kresy?

[Jan Kraszewski]

To zależy jakiej pary. Np. \(\displaystyle{ \sup\{\emptyset,\{0\}\}=\{0\}.}\)

JK

[max123321]

Czyli \(\displaystyle{ \inf\left\{ \emptyset,\emptyset\right\}=\sup\left\{ \emptyset,\emptyset\right\}=\emptyset }\),
\(\displaystyle{ \inf\left\{ \emptyset,\left\{ 1\right\} \right\} =\emptyset}\),\(\displaystyle{ \sup\left\{ \emptyset,\left\{ 1\right\} \right\} =\left\{ 1\right\} }\),\(\displaystyle{ \inf\left\{ \left\{ 1\right\} ,\left\{ 0,1\right\} \right\} =\left\{ 1\right\}}\),\(\displaystyle{ \sup\left\{ \left\{ 1\right\} ,\left\{ 0,1\right\} \right\} =\left\{ 0,1\right\} }\) itd. Dobrze?

Czyli kres dolny to jest mniejszy z elementów pary, a kres górny to jest większy z elementów pary?

[Jan Kraszewski]

Czyli \(\displaystyle{ \inf\left\{ \emptyset,\emptyset\right\}=\sup\left\{ \emptyset,\emptyset\right\}=\emptyset }\),
\(\displaystyle{ \inf\left\{ \emptyset,\left\{ 1\right\} \right\} =\emptyset}\),\(\displaystyle{ \sup\left\{ \emptyset,\left\{ 1\right\} \right\} =\left\{ 1\right\} }\),\(\displaystyle{ \inf\left\{ \left\{ 1\right\} ,\left\{ 0,1\right\} \right\} =\left\{ 1\right\}}\),\(\displaystyle{ \sup\left\{ \left\{ 1\right\} ,\left\{ 0,1\right\} \right\} =\left\{ 0,1\right\} }\) itd. Dobrze?

Dobrze.

Czyli kres dolny to jest mniejszy z elementów pary, a kres górny to jest większy z elementów pary?

Tylko wtedy, gdy elementy w tej parze są porównywalne.

JK

[max123321]

Dobra to b). Mówisz o rodzinie wszystkich skończonych podzbiorów zbioru \(\displaystyle{ \NN}\), a relację bierzemy \(\displaystyle{ \subseteq }\), jak rozumiem? Ja bym powiedział, że to jest krata bo dla dowolnych dwóch podzbiorów skończonych zbioru \(\displaystyle{ \NN}\) istnieje zawsze najmniejszy w sensie zawierania zbiór, który zawiera te dwa podzbiory. Jak mamy przykładowo zbiory \(\displaystyle{ \left\{ 1,2,3\right\} }\) i \(\displaystyle{ \left\{ 2,3,4\right\} }\) to najmniejszy zbiór, który zawiera te zbiory istnieje i jest równy \(\displaystyle{ \left\{ 1,2,3,4\right\} }\) i tak jest dla dowolnych dwóch podzbiorów skończonych \(\displaystyle{ \NN}\). Analogicznie istnieje zawsze największy zbiór, który zawierają te dwa zbiory, w tym przykładzie będzie to \(\displaystyle{ \left\{ 2,3\right\} }\). Bo to w sumie będzie suma i przecięcie zbiorów. Dobrze mówię? No i ta krata ma element najmniejszy czyli zbiór pusty, a największego elementu nie ma, bo największy musiałby zawierać wszystkie liczby naturalne i byłby to zbiór nieskończony, a takich nie rozpatrujemy. Dobrze?

[Jan Kraszewski]

Dobrze.

JK

[max123321]

Dobra to tu jeszcze jest podpunkt

c) Jeśli \(\displaystyle{ (A,r)}\) jest kratą to czy dla dowolnego skończonego zbioru \(\displaystyle{ \left\{ a_1,...,a_n\right\} }\) zawartego w \(\displaystyle{ A}\) istnieje \(\displaystyle{ \inf\left\{ a_1,...,a_n\right\} }\)?

Ja bym powiedział, że to jest prawda, gdyż jak jest to krata to dowolne jej dwa elementy mają kresy czyli w szczególności istnieje \(\displaystyle{ \inf\left\{ a,b\right\} }\) dla dowolnych \(\displaystyle{ a,b \in A}\), a zatem istnieje też \(\displaystyle{ \inf\left\{ a_1,...,a_n\right\} }\) dla dowolnych \(\displaystyle{ a_1,...,a_n \in A}\). Dobrze?

Dodano po 19 minutach 11 sekundach:
I tu jest jeszcze podpunkt

d) Jeśli \(\displaystyle{ (A,r)}\) jest kratą to czy dla dowolnego podzbioru \(\displaystyle{ A_0}\) zbioru \(\displaystyle{ A}\) istnieje \(\displaystyle{ \inf A_0}\)?

Myślę, że to jest fałsz, gdyż jeśli weźmiemy na przykład zbiór liczb całkowitych i relację \(\displaystyle{ \le }\), to to jest krata, a nie ma elementu najmniejszego bo zbiór liczb całkowitych jest nieograniczony z dołu. Dobrze?

[Jan Kraszewski]

c) Jeśli \(\displaystyle{ (A,r)}\) jest kratą to czy dla dowolnego skończonego zbioru \(\displaystyle{ \left\{ a_1,...,a_n\right\} }\) zawartego w \(\displaystyle{ A}\) istnieje \(\displaystyle{ \inf\left\{ a_1,...,a_n\right\} }\)?

Ja bym powiedział, że to jest prawda, gdyż jak jest to krata to dowolne jej dwa elementy mają kresy czyli w szczególności istnieje \(\displaystyle{ \inf\left\{ a,b\right\} }\) dla dowolnych \(\displaystyle{ a,b \in A}\), a zatem istnieje też \(\displaystyle{ \inf\left\{ a_1,...,a_n\right\} }\) dla dowolnych \(\displaystyle{ a_1,...,a_n \in A}\). Dobrze?

To prawda, ale wymaga dowodu (indukcyjnego).

d) Jeśli \(\displaystyle{ (A,r)}\) jest kratą to czy dla dowolnego podzbioru \(\displaystyle{ A_0}\) zbioru \(\displaystyle{ A}\) istnieje \(\displaystyle{ \inf A_0}\)?

Myślę, że to jest fałsz, gdyż jeśli weźmiemy na przykład zbiór liczb całkowitych i relację \(\displaystyle{ \le }\), to to jest krata, a nie ma elementu najmniejszego bo zbiór liczb całkowitych jest nieograniczony z dołu. Dobrze?

Dobrze.

JK