Własności kraty

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Własności kraty

Post autor: 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
Administrator
Administrator
Posty: 34540
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Własności kraty

Post autor: 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
Użytkownik
Użytkownik
Posty: 1431
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 70 razy
Pomógł: 84 razy

Re: Własności kraty

Post autor: 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
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}\) :lol:
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Re: Własności kraty

Post autor: 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
Użytkownik
Użytkownik
Posty: 1431
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 70 razy
Pomógł: 84 razy

Re: Własności kraty

Post autor: Jakub Gurak »

max123321 pisze: 21 maja 2024, o 21:50Moje 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\}}\) 8-) ).
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Re: Własności kraty

Post autor: 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
Administrator
Administrator
Posty: 34540
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Własności kraty

Post autor: Jan Kraszewski »

max123321 pisze: 21 maja 2024, o 21:50Dobra 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.
max123321 pisze: 21 maja 2024, o 21:50 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.
max123321 pisze: 21 maja 2024, o 23:04b) 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
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Re: Własności kraty

Post autor: max123321 »

Jan Kraszewski pisze: 22 maja 2024, o 00:14
max123321 pisze: 21 maja 2024, o 21:50 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
Administrator
Administrator
Posty: 34540
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Własności kraty

Post autor: Jan Kraszewski »

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

JK
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Re: Własności kraty

Post autor: 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
Administrator
Administrator
Posty: 34540
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Własności kraty

Post autor: Jan Kraszewski »

max123321 pisze: 22 maja 2024, o 13:35 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.
max123321 pisze: 22 maja 2024, o 13:35 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
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Re: Własności kraty

Post autor: 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
Administrator
Administrator
Posty: 34540
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Własności kraty

Post autor: Jan Kraszewski »

Dobrze.

JK
max123321
Użytkownik
Użytkownik
Posty: 3446
Rejestracja: 26 maja 2016, o 01:25
Płeć: Mężczyzna
Lokalizacja: Kraków
Podziękował: 1007 razy
Pomógł: 3 razy

Re: Własności kraty

Post autor: 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
Administrator
Administrator
Posty: 34540
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 4 razy
Pomógł: 5226 razy

Re: Własności kraty

Post autor: Jan Kraszewski »

max123321 pisze: 22 maja 2024, o 15:08 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).
max123321 pisze: 22 maja 2024, o 15:08 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
ODPOWIEDZ