Zadania z krat

[squared]

Przepraszam, że tak wiele na raz pytam, ale wolę tak od razu, niż zakładać na każdy osobny temat, chyba, że tak powinienem robić? Mam parę pytań dotyczących krat:

\(\displaystyle{ 1)}\) Narysować diagram Hasse'go dowolnej relacji porządku, która
\(\displaystyle{ a)}\) ma element największy, ale nie ma maksymalnego
\(\displaystyle{ b)}\) ma jeden element minimalny, ale nie ma najmniejszego.

No moim zdaniem a) nie istnieje, bo przecież element największy jest jednocześnie maksymalny, podobnie jeśli ma jeden element minimalny tylko, to jest to zarazem najmniejszy, więc zdanie b też jest fałszywe. Czy dobrze myślę?

\(\displaystyle{ 2)}\) \(\displaystyle{ A}\) - krata. Pokazać, że \(\displaystyle{ \forall x,y,z,t\in A}\) mamy:
\(\displaystyle{ a) \ x \le z, y \le t \Longrightarrow x \vee y \le z \vee t}\)

Próbowałem sobie to jakoś rozpisać, ilustrując to sobie jest to fakt oczywisty. Nie wiem jak to poprzekształcać, jak się za to załapać.
Na pewno:
\(\displaystyle{ x \le \sup\left\{ x;y\right\}=x \vee y \\
y \le \sup\left\{ x;y\right\}=x \vee y\\
z \le \sup\left\{ z;t\right\}=z \vee t\\
t \le \sup\left\{ z;t\right\}=z \vee t \\
\\
\text{z założenia:} \ \ x \le z \le z \vee t \\
y \le t \le z \vee t}\)

I nie wiem co dalej...
\(\displaystyle{ b) \ x \le z, y \le t \Longrightarrow x \wedge y \le z \wedge t}\)
\(\displaystyle{ c) \ x \vee y = x \Longleftrightarrow x \wedge y=y}\)

\(\displaystyle{ 3)}\) Pokazać, że jeśli: \(\displaystyle{ (A_1; \le _{1}),(A_2; \le _{2})}\) są kratami, to \(\displaystyle{ A_1 x A_2}\) z porządkiem produktowym jest kratą.

Najpierw zapisałem sobie definicję porządku produktowego:
\(\displaystyle{ \forall a_1,a_{1}' \in A_{1} \ \ \ \forall a_{2}, a_{2}\ \in A_{2} \ \ (a_{1},a_{2}) \le _{3} \left( a_{1},a_{2}'\right) \Leftrightarrow a_{1} \le _{1}a_{1}\ \ \text{oraz} \ \ \ b_{1} \le _{2} b_{2}}\)

Potem mam
\(\displaystyle{ a_{1} \vee a_{1}' = a_{1}' \\
a_{2} \vee a_{2}'\ = a_{2}'}\)

Stąd: \(\displaystyle{ (a_{1}';b_{1}')= \left( a_{1} \vee a_{1}'; a_{2} \vee a_{2}' \right)}\)

i to na nic się nie przyda, ponieważ chodziło mi by uzyskać:
\(\displaystyle{ \left( a_1;a_2 \right) = \left( \left( a_1;a_2 \right) ; \left( a_{1}';a_{2}'\right) \right)}\)
Chociaż już sam się w tym gubię, nawet w oznaczeniach...

\(\displaystyle{ 4)}\) Pokazać, że jeśli \(\displaystyle{ f}\) jest izomofrizmem kart \(\displaystyle{ \left( A_{1}, \le_{1}),\left( A_{2}.\le_{2}\right) \right)}\), to dal dowolnych \(\displaystyle{ a,b\in A_{1}}\) mamy \(\displaystyle{ f(a \wedge b)=f(a) \wedge f(b)}\) oraz \(\displaystyle{ f(a \vee b)=f(a) \vee f(b)}\).

\(\displaystyle{ 5)}\) Ile jest nieizomorficznych krat co najwyżej 5 - elementowych?

Jednoelementowe: 1
Dwuelementowa: 1 (łańcuch 2 - elementowy)
Trzyelementowa: 1 (łańcuch 3 - elementowy)
Czteroelementowa: 2 (łańcuch + "romb")
Pięcioelementowe: 2 (łańcuch + jedno inne)

Czy jakieś jeszcze są, czy po prostu nie umiem wymyślić innych?

[norwimaj]

No moim zdaniem a) nie istnieje, bo przecież element największy jest jednocześnie maksymalny,

Masz rację, dlatego w tym zadaniu Ci nie pomogę.

podobnie jeśli ma jeden element minimalny tylko, to jest to zarazem najmniejszy, więc zdanie b też jest fałszywe.

A tu nie masz racji. To jest prawdą dla porządków na zbiorach skończonych, ale w ogólności nie.

-- 21 mar 2014, o 21:18 --

\(\displaystyle{ 2)}\) \(\displaystyle{ A}\) - krata. Pokazać, że \(\displaystyle{ \forall x,y,z,t\in A}\) mamy:
\(\displaystyle{ a) \ x \le z, y \le t \Longrightarrow x \vee y \le z \vee t}\)

Spróbuj pomału: \(\displaystyle{ x \vee y \le x \vee t \le z \vee t}\).

-- 21 mar 2014, o 21:21 --

\(\displaystyle{ b) \ x \le z, y \le t \Longrightarrow x \wedge y \le z \wedge t}\)

Dualne do poprzedniego, więc pomijam.

\(\displaystyle{ c) \ x \vee y = x \Longleftrightarrow x \wedge y=y}\)

Spróbuj w ten sposób: \(\displaystyle{ \ x \vee y = x \Longleftrightarrow y\le x \Longleftrightarrow x \wedge y=y}\).

[squared]

Co do \(\displaystyle{ 1b}\)

np. taki diagram Hasse'go dla zbioru liczb całkowitych ujemnych (relacja porządku: \(\displaystyle{ \le}\)) i dać gdziekolwiek "odnogę" skończoną np. z 1 punktem? Mam nadzieję, że pojęcie "odnoga" jest zrozumiałe. Odnoga - dodatkowa gałąź/połączenie wraz z punktem.

[norwimaj]

Ad 3. Napisz od nowa, bo sporo jest namieszane.

Ad 4. Nie powinno być z tym problemu. Podjąłeś już próbę?

Jednoelementowe: 1
Dwuelementowa: 1 (łańcuch 2 - elementowy)
Trzyelementowa: 1 (łańcuch 3 - elementowy)
Czteroelementowa: 2 (łańcuch + "romb")

To wygląda wiarygodnie.

Pięcioelementowe: 2 (łańcuch + jedno inne)

Za mało.

Co do \(\displaystyle{ 1b}\)

np. taki diagram Hasse'go dla zbioru liczb całkowitych ujemnych (relacja porządku: \(\displaystyle{ \le}\)) i dać gdziekolwiek "odnogę" skończoną np. z 1 punktem? Mam nadzieję, że pojęcie "odnoga" jest zrozumiałe. Odnoga - dodatkowa gałąź/połączenie wraz z punktem.

Tak, to dobry przykład.

[squared]

Ad. 4. Znalazłem jeszcze dwie, więc 5 - elementowych mam 4. Jeszcze więcej?

Pozostałe przejrzę na nowo jutro, bo już pora męcząca na myślenie dla mnie intensywne.

[norwimaj]

Zapomniałem jeszcze, że trzeba uwzględnić porządek na zbiorze pustym. (chyba że z jakichś względów jest on wykluczony z rozważań)

Ja mam pięć pięcioelementowych. Żeby mieć pewność, że nic nie przeoczyłeś, musisz w jakiś systematyczny sposób rozważyć wszystkie możliwości. Na przykład tak:

Przypadek 1: łańcuch (tylko jedna możliwość)

Przypadek 2: niełańcuch

Skoro nie jest to łańcuch, to istnieją w nim dwa nieporównywalne elementy: \(\displaystyle{ a}\) i \(\displaystyle{ b}\). Niech \(\displaystyle{ c=a\wedge b}\), \(\displaystyle{ d=a\vee b}\). Mamy już cztery różne elementy, tworzące romb, więc trzeba dodać jeszcze jeden element \(\displaystyle{ e}\). Zauważmy, że element \(\displaystyle{ e}\) nie może być nieporównywalny z \(\displaystyle{ c}\), gdyż wtedy \(\displaystyle{ e\wedge c}\) byłby szóstym elementem. Analogicznie z \(\displaystyle{ d}\). Zatem mamy tylko trzy podprzypadki:

Przypadek 2.1: \(\displaystyle{ e\ge d}\) (jedna możliwość)

Przypadek 2.2: \(\displaystyle{ e\le c}\) (jedna możliwość)

Przypadek 2.3: \(\displaystyle{ c\le e \le d}\) (po rozbiciu na kolejne podprzypadki otrzymujemy dwie istotnie różne możliwości)

[squared]

Ad.5
Hmm na pewno w 2.3 są dwie możliwości, ja zauważyłem tylko jedną...
Że mamy romb, którego wierzchołkami są c,a,b,d oraz e jest w środku rombu, między c i d. Między c,e i d jest połączenie. Jaki inny ma być?

Ad. 2a
\(\displaystyle{ a) \ x \le z, y \le t \Longrightarrow x \vee y \le z \vee t \\
\begin{cases} x \le x \vee y \\ y \le x \vee y \end{cases} \\
\begin{cases} x \le x \vee t \\ t \le x \vee t \end{cases} \\
\\
\text{z założenia} \ \ y \le t \Rightarrow y \le t \le x \vee t\\
\blue \begin{cases} y \le x \vee t \\ x \le x \vee t \end{cases}}\)
Czy z tego zaznaczonego na niebiesko wynika już bezpośrednio, że:
\(\displaystyle{ x \vee y \le x \vee y}\) ?

Czy to błędy wniosek?

Ad. 2c
Z założenia
\(\displaystyle{ x \vee y = x \\
\text{Ogólnie:} \ \ x \le x \vee y \\
y \le x \vee y \\
\text{Z uwzględnieniem założenia:} \ \ x \vee y = x \\
\blue y \le x \\
\black \text{Ogólnie:} \ \ x \wedge y \le x \\
x \wedge y \le y}\)

Czy biorąc pod uwagę to co mam na niebiesko można już napisać, że \(\displaystyle{ x \wedge y = y}\)? Czy trzeba tu jeszcze coś dokończyć, jeśli tak to co? Czy muszę dowód robić w drugą stronę, czy może wszystkie przejścia były równoważne?

Ad. 3
Spróbuję to ładniej zapisać:

Z def. porządku produktowego:
\(\displaystyle{ \forall a,b \in A_{1} \ \ \ \forall c,d \in A_{2} \ \ (a,c) \le _{3} \left( b,d\right) \Leftrightarrow a \le _{1}b \ \ \text{oraz} \ \ \ c \le _{2} d}\)

Ponieważ są to karty, więc:
\(\displaystyle{ \blue a \le _{1} b \Leftrightarrow a \vee b = b \\
c \le _{2} d \Leftrightarrow c \vee d = d}\)
Zatem: \(\displaystyle{ (b;d)=(a \vee b;c \vee d)}\)

Mieliśmy pokazać, że \(\displaystyle{ (a;b) \vee (c;d) = (c;d)}\)?

A z zaznaczonego na niebisko mamy:
\(\displaystyle{ (a; a \vee b) \vee (c;c \vee d) =^{?} (c;d)}\)
Czy to coś ostatniego Nam dało, wydaje mi się, że nie i zadanie dalej nie rozwiązane...

Ad.4
Z izomorfizmu
\(\displaystyle{ \forall a,b \in A_{1} \ \ a \le _{1} b \Rightarrow f(a) \le_{2} f(b)}\)

Z własności krat:
\(\displaystyle{ a \le _{1} b \Leftrightarrow a \vee b = b \\
f(a) \le _{2} f(b) \Leftrightarrow f(a) \vee f(b) = f(b)\\ \\

f( a \vee b) = f(b) = f(a) \vee f(b)}\)

Z własności krat:
\(\displaystyle{ a \le _{1} b \Leftrightarrow a \wedge b = a\\
f(a) \le _{2} f(b) \Leftrightarrow f(a) \wedge f(b) = f(a)\\ \\

f( a \wedge b) = f(a) = f(a) \wedge f(b)}\)

Dobrze?

[norwimaj]

Ad.5
Hmm na pewno w 2.3 są dwie możliwości, ja zauważyłem tylko jedną...

Ja to rozbiłem na podprzypadki:
Przypadek 2.3.1: \(\displaystyle{ e}\) jest nieporównywalny z \(\displaystyle{ a}\) i \(\displaystyle{ b}\),
Przypadek 2.3.2: \(\displaystyle{ e}\) jest porównywalny z \(\displaystyle{ a}\) i \(\displaystyle{ b}\),
Przypadek 2.3.3: \(\displaystyle{ e}\) jest porównywalny z dokładnie jednym: \(\displaystyle{ a}\) albo \(\displaystyle{ b}\).

Łącznie uzyskałem dwie możliwości.

Ad. 2a
\(\displaystyle{ \blue \begin{cases} y \le x \vee t \\ x \le x \vee t \end{cases}}\)
Czy z tego zaznaczonego na niebiesko wynika już bezpośrednio, że:
\(\displaystyle{ x \vee y \le x \vee y}\) ?

Wynika, że \(\displaystyle{ x \vee t}\) jest ograniczeniem górnym zbioru \(\displaystyle{ \{x,y\}}\), a skoro \(\displaystyle{ x \vee y}\) jest najmniejszym takim ograniczeniem, to \(\displaystyle{ x \vee y\le x\vee t}\).

Ad. 2c
Z założenia
\(\displaystyle{ x \vee y = x \\
\text{Ogólnie:}{\red \ \ x \le x \vee y }\\
y \le x \vee y \\
\text{Z uwzględnieniem założenia:} \ \ x \vee y = x \\
\blue y \le x}\)

Czy czerwony wzór jest używany w rozumowaniu? Jeśli nie, to po co go pisać?

Czy biorąc pod uwagę to co mam na niebiesko można już napisać, że \(\displaystyle{ x \wedge y = y}\)?

Ja bym to uzasadnił korzystając z definicji kresu dolnego.

Czy muszę dowód robić w drugą stronę, czy może wszystkie przejścia były równoważne?

Przejścia zdecydowanie nie były równoważne, ale implikacja w drugą stronę jest dualna do tej.

Ad. 3
Mieliśmy pokazać, że \(\displaystyle{ (a;b) \vee (c;d) = (c;d)}\)?

Ja nic o tym nie wiem. Zajrzyj do definicji kraty, bo wydaje mi się, że nie wiesz, co masz do udowodnienia.

Ad.4
Z własności krat:
\(\displaystyle{ a \le _{1} b \Leftrightarrow a \vee b = b \\
f(a) \le _{2} f(b) \Leftrightarrow f(a) \vee f(b) = f(b)\\ \\

f( a \vee b) = f(b) = f(a) \vee f(b)}\)

Tak jak w poprzednim, masz tendencję do rozpatrywania tylko elementów porównywalnych.

[Winged]

3. Istotą jest pokazanie, że \(\displaystyle{ (a,c) \vee_3 (b,d) = (a \vee_1 b, c \vee_2 d)}\). Na początek zapytajmy, czy \(\displaystyle{ (a \vee_1 b, c \vee_2 d)}\) jest ograniczeniem górnym \(\displaystyle{ \{(a,c),(b,d)\}}\)? \(\displaystyle{ a \vee_1 b}\) jest większe zarówno od \(\displaystyle{ a}\), jak i od \(\displaystyle{ b}\). Podobnie \(\displaystyle{ c \vee_2 d}\) jest większe od \(\displaystyle{ c}\) i \(\displaystyle{ d}\). Pytanie, czy \(\displaystyle{ (a \vee_1 b, c \vee_2 d)}\) jest najmniejszym spośród elementów posiadających tą własność? Ciekawe, co gdyby tak nie było.

[norwimaj]

Ciekawe, co gdyby tak nie było.

Dlaczego nie wprost?

[Winged]

Hmm, w zasadzie to można po prostu rozważyć dowolny element ograniczający ten zbiór z góry i oszacowanie samo wyjdzie w dobrą stroną. Tak, czy siak wychodzi.

[squared]

Ad.5
Do rysunku krat - przepraszam, za bylejakość narysowania, jak takie znalazłem:

AU

e12fbdd8b0ac0f87med.jpg (7.97 KiB) Przejrzano 113 razy

Ad.2a
Czyli pierwszą nierówność mam, teraz już analogicznie
\(\displaystyle{ x \vee t \le z \vee t}\) ?

Ad.2b
\(\displaystyle{ \text{Ogólnie:}{\red \ \ x \le x \vee y }}\) - nie było potrzebne, tak przy spisywaniu myśli mi się napisało, nie używałem tego.

Hmmm, 2c w drugą stronę
\(\displaystyle{ c) \ x \vee y = x \Longleftrightarrow x \wedge y=y \\
\\
\blue \Longleftarrow \\ \\
\black \\ x \wedge y \le x \ \ (1) \\
\text{Z założenia i (1):} \ \ y \le x \\}\)
Wystarczy słownie napisać, że jeśli dwa elementy są porównywalne to większy z nich jest kresem górnym zbioru dwuelementowego złożonego z danych dwóch elementów?

Ad.3
Co do trzeciego to tak się już zamotałem, że chyba nie wiem jak to zrobić...

Ad.4
To dobre pytanie, co jeśli są nieporównywalne. No na pewno dla obu porządków mają one \(\displaystyle{ \sup \ i \ \inf}\). No i co dalej? Z tego mam wysnuć podobne wnioski, jak dla elementów porównywanych?

[Jan Kraszewski]

Ad.5
Do rysunku krat - przepraszam, za bylejakość narysowania, jak takie znalazłem:

Brakuje Ci jednego:

Najmniejszy, największy i dwa łańcuchy łączące te elementy: trzy i czteroelementowy (czyli pomiędzy najmniejszym i największym dopisujesz z jednej strony jeden, a z drugiej dwa elementy).

JK