Zbiory uporządkowane, łańcuchy-zadanie

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Zbiory uporządkowane, łańcuchy-zadanie

Post autor: Jakub Gurak »

Jest takie zadanie (z ważniaka):

Czy w zbiorze uporządkowanym \(\displaystyle{ (X, \le )}\) jeśli każdy łańcuch jest skończony, czy zbiór \(\displaystyle{ X}\) musi być skończony? Czy taki zbiór może zawierać łańcuchy dowolnie dużej skończonej mocy?

Oczywiście, że nie musi. W zbiorze liczb naturalnych uporządkowanych relacją identyczności, każdy niepusty łańcuch jest jednoelelemntowy, a więc skończony, podczas gdy zbiór \(\displaystyle{ \NN}\) jest nieskończony.

Teraz wersja trudniejsza, z uwzględnieniem drugiego pytania:

Aby to rozwiązać, najlepiej na \(\displaystyle{ \NN\times \NN}\) (zbiorze nieskończonym) narysować na każdej prostej pionowej kolejno łańcuchy dowolnej skończonej mocy, czyli kolejno łańcuch jednoelementowy, dwuelementowy, trzyelementowy, itd., a w innych punktach uzupełniamy porządkiem identycznościowym.

Formalnie, definiujemy (najpierw jedynie silny) porządek \(\displaystyle{ \prec}\) na \(\displaystyle{ \NN\times\NN}\):

\(\displaystyle{ \left( x _{1},y _{1} \right)\prec \left( x _{2},y _{2} \right)\Longleftrightarrow x_1= x_2 \wedge y _{1}, y_2 \le x_1 \wedge y_1<y_2.}\)

Czyli jedna para liczb naturalnych jest istotnie mniejsza od drugiej pary liczb naturalnych, gdy leżą na tej samej prostej pionowej (\(\displaystyle{ x_1=x_2}\))- wtedy mamy łańcuch długości \(\displaystyle{ x_1+1=x+1}\), a więc łańcuch ten sięga od \(\displaystyle{ (x,0),(x,1),}\) do \(\displaystyle{ (x,x)}\), stąd warunek , że współrzędne \(\displaystyle{ y}\) są mniejsze od tej wartości \(\displaystyle{ x}\), no i, dalej już naturalnie, ta para na tej dowolnej ustalonej prostej pionowej jest mniejsza, której współrzędna \(\displaystyle{ y}\) jest mniejsza.

Dobrze :?: Bo coś zwątpiłem :? Chodzi o to by zapisać formalnie ten porządek narysowany, gdzie na kolejnych prostych pionowych mamy łańcuchy kolejno: jednoelementowy, dwuelementowy, trójelementowy,....

Dobrze :?:
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Zbiory uporządkowane, łańcuchy-zadanie

Post autor: Jakub Gurak »

Wczoraj udało się dokładnie rozwiązać to zadanie z ważniaka( w inny sposób, tak jak na ważniaku, tylko o wiele dokładniej). Dzisiaj też uogólniłem na dowolny zbiór nieskończony (pomysł nie jest trudny, przecież mamy prosty ogólny fakt, że na każdym niepustym zbiorze relacja identyczności jest relacją porządku, w szczególności na zbiorach nieskończonych). Przedstawię teraz rozwiązania.

Rozważmy zbiór \(\displaystyle{ \NN \times \NN}\) z porządkiem \(\displaystyle{ \sqsubseteq}\):

\(\displaystyle{ \left( x_1,y_1\right)\sqsubseteq \left( x_2,y_2\right) \Longleftrightarrow x_1+y_1=x_2+y_2 \hbox{ i } x_1 \le x_2 }\).

Czyli jedna para liczb naturalnych jest w relacji z drugą parą liczb naturalnych, gdy te pary mają taką samą sumę współrzędnych i pierwsza współrzędna mniejszej pary jest mniejsza lub równa od pierwszej współrzędnej drugiej pary. Skoro sumy współrzędnych par mają być jednakowe, to zmniejszając drugą współrzędną o jednostkę musimy zwiększyć pierwszą współrzędną o jednostkę, itd. \(\displaystyle{ n}\) kroków, a drugi warunek oznacza, że wraz ze wzrostem po osi \(\displaystyle{ x}\), nasz porządek na parach też będzie rosnący, czyli ten porządek wyglądać będzie tak:

Ponieważ naturalny porządek na \(\displaystyle{ \NN}\) jest relacją porządku, ponieważ równość jest relacją zwrotna i przechodnią, to \(\displaystyle{ \sqsubseteq}\) jest relacją porządku. Wykażemy np. antysymetrię:
Ukryta treść:    
Łatwo można sprawdzić zwrotność i przechodniość, wobec czego jest to relacja porządku, i \(\displaystyle{ (\NN \times \NN,\sqsubseteq)}\) jest zbiorem uporządkowanym.

Aby wykazać, że w tym zbiorze uporządkowanym każdy łańcuch jest skończony, podajmy teraz lemat( który z resztą wykorzystamy co najmniej dwa razy).

Lemat. Jeśli \(\displaystyle{ n\in\NN}\) jest liczbą naturalną, to zbiór
\(\displaystyle{ A_n=\left\{ (x,y) \in \NN \times \NN\Bigl| \ \ n=x+y\right\} \sim (n+1)}\),

taki zbiór jest równoliczny z liczbą naturalną von Neumanna \(\displaystyle{ (n+1)}\), czyli po prostu ma (\(\displaystyle{ n+1}\)) elementów, (gdyż liczbę naturalną \(\displaystyle{ n}\) można rozłożyć na sumę dwóch liczb naturalnych na \(\displaystyle{ \left( n+1\right) }\) sposobów). Przedstawimy teraz indukcyjny dowód tego faktu.

Jeśli \(\displaystyle{ n=0}\), to \(\displaystyle{ \left\{ \left( x,y\right): 0=x+y \right\} =\left\{ \left( 0,0\right) \right\} \sim 1.}\)

Przypuśćmy, że twierdzenie zachodzi dla \(\displaystyle{ n}\). Pokażemy, że zachodzi dla \(\displaystyle{ n+1}\). Rozważmy zbiór \(\displaystyle{ B=\left\{ \left( x,y\right)\in\NN \times \NN: \ \ n+1=x+y \right\},}\) oraz zbiór \(\displaystyle{ C=\left\{ \left( x,y\right): \ \ n=x+y\right\}.}\) Pokażemy, że zbiór C jest równoliczny z \(\displaystyle{ B \setminus \left\{ \left( 0,n+1\right) \right\}.}\)

Rozważmy funkcję \(\displaystyle{ f:C \rightarrow B \setminus \left\{ \left( 0,n+1\right) \right\} }\), określoną następująco:

\(\displaystyle{ f(\left( x,y\right) ) =\left( x+1,y\right).}\)

Funkcja \(\displaystyle{ f}\) jest dobrze określona, gdyż jeśli \(\displaystyle{ (x,y)\in C}\), to z definicji zbioru \(\displaystyle{ C}\): \(\displaystyle{ x+y=n}\), a więc \(\displaystyle{ (x+1)+y=n+1}\), a więc \(\displaystyle{ f(x,y)=(x+1,y)\in B}\), i oczywiście \(\displaystyle{ f(x,y) \neq \left( 0,n+1\right)}\), tak więc \(\displaystyle{ f(x,y)\in B \setminus \left\{ \left( 0,n+1\right) \right\}}\), i funkcja \(\displaystyle{ f}\) jest dobrze określona.

Łatwo sprawdzić, że jest różnowartościowa. Pokażemy teraz, że jest 'na'.
Ukryta treść:    
Zatem funkcja \(\displaystyle{ f}\) jest 'na', zatem jest bijekcją. A zatem \(\displaystyle{ C\sim B \setminus \left\{ \left( 0,n+1\right) \right\}}\), z założenia indukcyjnego \(\displaystyle{ C\sim (n+1)}\), zatem \(\displaystyle{ B \setminus \left\{ \left( 0,n+1\right) \right\} \sim n+1}\), a zatem \(\displaystyle{ B\sim (n+2)}\) (\(\displaystyle{ \left( 0,n+1\right)\in B}\)). Zatem twierdzenie zachodzi dla (\(\displaystyle{ n+1}\)), i krok indukcyjny został dowiedziony. Z zasady indukcji matematycznej otrzymujemy, że lemat jest udowodniony.\(\displaystyle{ \square}\) 8-)

Niech \(\displaystyle{ (a,b) \in \NN \times \NN}\), i rozważmy zbiór \(\displaystyle{ A=\left\{ \left( c,d\right)\in\NN \times \NN: \ \ (c,d)\sqsubseteq (a,b \vee (a,b)\sqsubseteq (c,d) \right\} .}\)

Jest to zbiór par \(\displaystyle{ (c,d)}\) porównywalnych z naszą parą \(\displaystyle{ (a,b).}\)

Zauważmy, że jeśli \(\displaystyle{ (c,d) \in \NN \times \NN}\), to, mamy:

\(\displaystyle{ (c,d) \in A \Leftrightarrow (c,d)\sqsubseteq (a,b) \vee (a,b)\sqsubseteq (c,d) \Leftrightarrow \left( c+d=a+b \wedge c \le a\right) \vee \left( a+b=c+d \wedge a \le c\right) \Leftrightarrow \\ \Leftrightarrow \left( c+d=a+b \wedge c \le a\right) \vee \left( c+d=a+b \wedge a \le c\right) \Leftrightarrow \left( c+d=a+b\right) \wedge \left( c \le a \vee a \le c\right) \Leftrightarrow \left( c+d=a+b \right) \wedge\left( \textbf{1}\right) \Leftrightarrow c +d=a+b,}\), gdzie \(\displaystyle{ \left( \textbf{1}\right) }\) oznacza zdanie zawsze prawdziwe.

Otrzymujemy zatem, że \(\displaystyle{ A=\left\{ \left( c,d\right): \ \ c+d=a+b \right\}}\), który to zbiór ponieważ \(\displaystyle{ (a+b) \in \NN}\), więc na mocy lematu jest równoliczny z \(\displaystyle{ (a+b+1)}\). A zatem zbiór \(\displaystyle{ A}\) jest skończony.

Wykażemy teraz, że w \(\displaystyle{ \NN \times \NN}\) każdy łańcuch jest skończony.
W tym celu ustalmy dowolny łańcuch \(\displaystyle{ X\subset \NN \times \NN}\). Jeśli \(\displaystyle{ X=\emptyset}\), to \(\displaystyle{ X}\) jest skończony.
Jeśli \(\displaystyle{ X \neq \emptyset}\), to niech \(\displaystyle{ (a,b)\in X\subset \NN \times \NN}\). Pokażemy, że \(\displaystyle{ X\subset A}\). Niech \(\displaystyle{ (c,d)\in X.}\) Wtedy \(\displaystyle{ (c,d)\in\NN \times \NN}\). Mamy \(\displaystyle{ (c,d);(a,b)\in X}\), a \(\displaystyle{ X}\) jest łańcuchem więc pary są porównywalne, a stąd z definicji zbioru \(\displaystyle{ A}\) wnioskujemy, że \(\displaystyle{ (c,d)\in A}\). A zatem, z dowolności wyboru takiej pary, otrzymujemy \(\displaystyle{ X\subset A}\). Ponieważ zbiór \(\displaystyle{ A}\) jest skończony, więc zbiór \(\displaystyle{ X}\) jako podzbiór zbioru skończonego jest zbiorem skończonym. Otrzymujemy, że w \(\displaystyle{ \NN\times \NN}\) każdy łańcuch jest skończony( A cały zbiór \(\displaystyle{ \NN \times \NN}\) jest nieskończony).

Pozostaje wykazać, że są tu łańcuchy dowolniej dużej skończonej mocy, tzn. że dla dowolnego \(\displaystyle{ n\in\NN}\) istniej łańcuch mocy \(\displaystyle{ n}\).
W tym celu, niech \(\displaystyle{ n\in\NN}\), i rozważmy zbiór \(\displaystyle{ A_n=\left\{ \left( a,b\right)\in\NN \times \NN\Bigl| \ \ a+b=n \right\}.}\)

Pokażemy, że zbiór \(\displaystyle{ A_n}\) jest łańcuchem. Niewątpliwie \(\displaystyle{ A_n\subset \NN \times \NN.}\) Niech \(\displaystyle{ (a_1,b_1);(a_2,b_2)\in A_n.}\) Wtedy, z definicji zbioru \(\displaystyle{ A_n}\) wnioskujemy, że \(\displaystyle{ a_1+b_1=n}\), i \(\displaystyle{ a_2+b_2=n}\), a zatem \(\displaystyle{ a_1+b_1=a_2+b_2.}\) Mamy \(\displaystyle{ a_1,a_2\in\NN}\), więc jeśli \(\displaystyle{ a_1 \le a_2}\), to z definicji \(\displaystyle{ \sqsubseteq}\) otrzymujemy \(\displaystyle{ (a_1,b_1)\sqsubseteq (a_2,b_2).}\) W przeciwnym razie \(\displaystyle{ a_2<a_1}\), wtedy \(\displaystyle{ a_2+b_2=a_1+b_1}\) ( i \(\displaystyle{ a_2 \le a_1}\)), więc \(\displaystyle{ (a_2, b_2)\sqsubseteq (a_1,b_1)}\). A więc zbiór \(\displaystyle{ A_n}\) jest łańcuchem. Z lematu \(\displaystyle{ A_n}\) jest równoliczny z (\(\displaystyle{ n+1}\)), czyli wzorcowym zbiorem \(\displaystyle{ (n+1)}\)-elementowym, czyli \(\displaystyle{ A_n}\) jest łańcuchem, który ma \(\displaystyle{ (n+1)}\) elementów. Z dowolności n, otrzymujemy, że dla każdego \(\displaystyle{ n\in\NN}\) istnieje łańcuch mocy \(\displaystyle{ (n+1)}\), czyli istnieją łańcuchy dowolnie dużej skończonej mocy. Zauważmy jeszcze, że istnieje łańcuch \(\displaystyle{ 0}\)-elementowy- łańcuch pusty; czyli rzeczywiście dla każdej mocy skończonej istnieje łańcuch tej mocy. \(\displaystyle{ \square}\) :lol: :D

Na koniec, może krócej, bo już się zmęczyłem tym pisaniem, uzasadniłem takie zadanie,że:

jeśli \(\displaystyle{ X}\) jest dowolnym zbiorem nieskończonym, to można znależć porządek na zbiorze \(\displaystyle{ Y\sim X}\) równolicznym z \(\displaystyle{ X}\), taki, że każdy łańcuch jest skończony( a zbiór jest nieskończony- dowolnie nieskończony), i dla dowolnego \(\displaystyle{ n\in\NN}\) istnieje łańcuch mocy \(\displaystyle{ n}\), czyli istnieją łańcuchy dowolnie dużej skończonej mocy.

Aby to uzasadnić znajdźmy najpierw zbiór \(\displaystyle{ Y\supset \NN \times \NN}\), równoliczny z \(\displaystyle{ X}\). W tym celu odnajdźmy w zbiorze nieskończonym \(\displaystyle{ X}\) nieskończony zbiór przeliczalny, tzn. zbiór \(\displaystyle{ X_0\sim \NN}\), taki, że \(\displaystyle{ X_0\subset X}\). Możemy założyć, że \(\displaystyle{ X}\) jest nieprzeliczalny (bo dla zbiorów przeliczalnych wynik z poprzedniego zadania łatwo spełnia to zadanie). Ponieważ zbiory nieprzeliczalne są odporne na dodawanie i ujmowanie zbiorów co najwyżej przeliczalnych,co udowodniłem TUTAJ to \(\displaystyle{ X \setminus X_0\sim X}\), i dalej \(\displaystyle{ Y:=\left( X \setminus X_0\right) \cup \left( \NN \times \NN\right)\sim X}\). A zatem \(\displaystyle{ Y\sim X}\), i \(\displaystyle{ Y\supset \NN \times \NN.}\) Mamy \(\displaystyle{ Y \setminus \left( \NN \times \NN\right) \neq \left\{ \right\}}\), i identyczność na tym zbiorze jest relacją porządku- gdyż na każdym niepustym zbiorze identyczność jest relacją porządku. Oznaczmy ten zbiór jako \(\displaystyle{ Z}\), wtedy \(\displaystyle{ (Z,I_Z)}\) jest zbiorem uporządkowanym, wiemy z rozwiązanego zadania, że \(\displaystyle{ \left( \NN \times \NN, \sqsubseteq\right) }\) jest zbiorem uporządkowanym. Mamy, że \(\displaystyle{ Z=Y \setminus (\NN \times \NN)}\) i \(\displaystyle{ \NN \times \NN }\) są zbiorami rozłącznymi, a zatem ich suma czyli \(\displaystyle{ \le :=\left( I_Z\right) \cup \left( \sqsubseteq\right)}\) jest relacją porządku w \(\displaystyle{ \left[ Y \setminus \left( \NN \times \NN\right)\right] \cup \left( \NN \times \NN\right) =Y \cup \left( \NN \times \NN\right) \stackrel {\NN \times \NN\subset Y}{=} Y.}\) A więc \(\displaystyle{ \left( Y, \le\right) }\) jest zbiorem uporządkowanym. Wtedy, w \(\displaystyle{ Y}\) każdy łańcuch jest skończony, gdyż wiemy, że w \(\displaystyle{ \NN \times \NN}\) każdy łańcuch jest skończony, a na pozostałym zbiorze identyczność, czyli tu mogą być łańcuchy co najwyżej jednoelementowe. Dla \(\displaystyle{ n\in \NN}\), łańcuchy z rozwiązania \(\displaystyle{ A_n\subset \NN\times \NN\subset Y}\) są łańcuchami w \(\displaystyle{ \le}\) , gdyż \(\displaystyle{ \left( \le\right) \supset \left( \sqsubseteq\right)}\), a zatem \(\displaystyle{ \le}\) rozszerza \(\displaystyle{ \sqsubseteq}\), a stąd chyba łatwo sprawdzić, że to będą łańcuchy względem \(\displaystyle{ \le }\), i \(\displaystyle{ A_n\sim (n+1).}\) Z dowolności \(\displaystyle{ n\in\NN}\), otrzymujemy, że dla każdego \(\displaystyle{ n}\) istnieje w \(\displaystyle{ \left( Y, \le\right) }\) łańcuch mocy \(\displaystyle{ n.\square}\) :lol: 8-)
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Re: Zbiory uporządkowane, łańcuchy-zadanie

Post autor: Jakub Gurak »

Można podać zadanie analogiczne do tego zadania z ważniaka:

Czy zbiór uporządkowany, w którym każdy antyłańcuch jest skończony, musi być skończony? Czy w takim zbiorze uporządkowanym mogą istnieć antyłańcuchy dowolnej skończonej mocy, czyli zero-elementowe, jaki i jednoelementowe, jak i dwuelementowe, itd.??

Wczoraj dokładnie rozwiązałem to zadanie. Udowodniłem też, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest niepustym zbiorem uporządkowanym, to jeśli rozważymy podzbiór kwadratu \(\displaystyle{ X \times X}\), złożony z punktów leżących powyżej przekątnej wraz z tą przekątna, to można w tym zbiorze wprowadzić relację porządku (trochę taką sieć), ale tak aby przecięcia prostych poziomych z tym zbiorem były antyłańcuchami. Przedstawię teraz dowody tych ciekawych faktów.

Dowód:

Rozważmy zbiór \(\displaystyle{ X}\), zdefiniowany jako:

\(\displaystyle{ X=\left\{ \left( n,m\right)\in\NN \times \NN: \ n \le m \right\}}\),

jest to górna połowa kwadratu \(\displaystyle{ \NN \times \NN,}\) wraz z przekątną.

I zdefiniujmy relację silnego porządku \(\displaystyle{ \prec}\) na tym zbiorze \(\displaystyle{ X}\), jako:

\(\displaystyle{ \left( n_1,m_1\right)\prec \left( n_2,m_2\right) \Longleftrightarrow m_1<m_2}\),

tzn. pomiędzy dwoma wierszami poziomymi każda para z wiersza niższego jest mniejsza od każdej pary z wiersza wyższego, a w danym tym samym wierszu punkty są nieporównywalne, dzięki temu, takie kolejne wiersze, to będą antyłańcuchy, kolejno od dołu : jednoelementowy, dwuelementowy, trzyelementowy, itd., ale musimy to udowodnić w sposób ścisły.

Wykażemy, że relacja \(\displaystyle{ \prec}\) jest przeciwzwrotna i przechodnia.
DOWÓD TEGO FAKTU:    
Przypomnę może, że jeśli \(\displaystyle{ Y}\) jest zbiorem, a \(\displaystyle{ \sqsubset }\) relacją w zbiorze \(\displaystyle{ Y}\), relacją przeciwzwrotną i przechodnią, to relacją \(\displaystyle{ \sqsubseteq}\) na \(\displaystyle{ Y}\), dana jako:

\(\displaystyle{ x \sqsubseteq y \Leftrightarrow x \sqsubset y \vee x=y}\),

jest relacją porządku na zbiorze \(\displaystyle{ Y}\).

Jest to elementarny fakt.

W związku z czym, ponieważ u nas relacja \(\displaystyle{ \prec}\) na \(\displaystyle{ X}\) jest przeciwzwrotna i przechodnia, więc relacja \(\displaystyle{ \preccurlyeq}\) na zbiorze \(\displaystyle{ X}\), dana jako:

\(\displaystyle{ \left( n_1,m_1\right)\preccurlyeq (n_2,m_2) \Leftrightarrow \left[ \left( n_1,m_1\right)\prec (n_2,m_2) \vee \left( n_1,m_1\right) =\left( n_2,m_2\right)\right] }\),

jest relacją porządku na zbiorze \(\displaystyle{ X}\), i \(\displaystyle{ \left( X,\preccurlyeq\right) }\) jest zbiorem uporządkowanym.


Zauważmy, że zbiór \(\displaystyle{ X}\) jest nieskończony, gdyż:

\(\displaystyle{ X\supset \left\{ \left( 0,m\right)\Bigl| \ \ m\in\NN \right\}}\), (gdyż \(\displaystyle{ 0 \le m}\), dla każdego \(\displaystyle{ m\in\NN}\)). A zatem \(\displaystyle{ X\supset \left\{ 0\right\} \times \NN \sim \NN}\), ponieważ zbiór równoliczny ze zbiorem nieskończonym jest nieskończony, ponieważ nadzbiór zbioru nieskończonego jest nieskończony, więc zbiór \(\displaystyle{ X}\) jest nieskończony.


Wiemy, że istnieje antyłańcuch zero-elementowy- antyłańcuch pusty. Rozważmy ciąg antyłańcuchów \(\displaystyle{ (A_n)}\), gdzie \(\displaystyle{ n\in\NN}\). Tzn. zdefiniujmy:

\(\displaystyle{ A_n=\left( \NN \times \left\{ n\right\} \right) \cap X\subset X.}\)

Wykażemy, że zbiory \(\displaystyle{ A_n}\) są zawsze antyłańcuchami.

Niech \(\displaystyle{ (n_1,m_1);(n_2,m_2)\in A_n}\) będą różnymi parami.

Przypuśćmy, że \(\displaystyle{ (n_1,m_1)\prec (n_2,m_2).}\) Mamy, z definicji zbiorów \(\displaystyle{ A_n}\), mamy: \(\displaystyle{ (n_1,m_1)\in X, (n_1,m_1)\in\NN \times \left\{ n\right\}}\), skąd \(\displaystyle{ m_1=n.}\) Mamy \(\displaystyle{ (n_2,m_2)\in A_n}\), więc \(\displaystyle{ (n_2,m_2)\in X}\) i \(\displaystyle{ (n_2,m_2)\in\NN \times \left\{ n\right\},}\) skąd \(\displaystyle{ m_2=n}\). Ponieważ \(\displaystyle{ (n_1,m_1)\prec (n_2,m_2)}\), więc \(\displaystyle{ m_1<m_2}\), a ponieważ \(\displaystyle{ m_1=n=m_2}\), więc \(\displaystyle{ n<n}\) -sprzeczność.

Jeśli \(\displaystyle{ (n_2,m_2)\prec (n_1,m_1)}\), to analogicznie otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ (n_2,m_2)\not\prec (n_1,m_1)}\) oraz \(\displaystyle{ (n_1,m_1)\not\prec (n_2,m_2)}\), i zbiór \(\displaystyle{ A_n}\) jest antyłańcuchem.

Zatem zbiory \(\displaystyle{ A_n}\), gdzie \(\displaystyle{ n\in\NN,}\) są zawsze antyłańcuchami. Zauważmy, że dla dowolnego \(\displaystyle{ n\in\NN,}\) antyłańcuch \(\displaystyle{ A_n}\) ma \(\displaystyle{ (n+1)}\) elementów, czyli mamy antyłańcuch jednoelementowy, dwuelementowy, itd. Mamy również antyłańcuch pusty. Wobec czego, dla każdego \(\displaystyle{ n\in \NN,}\) istnieje antyłańcuch mocy \(\displaystyle{ n}\).


Pozostaje wykazać, że w tym zbiorze uporządkowanym nie ma nieskończonych antyłańcuchów.

Ustalmy dowolną parę \(\displaystyle{ (a,b)\in X}\); i rozważmy zbiór \(\displaystyle{ X_\left( a,b\right),}\) dany jako:

\(\displaystyle{ X_{a,b}=\left\{ \left( n,m\right)\in X: \ \ \hbox{ para } (n,m) \hbox{ jest nieporównywalna z parą } (a,b) \right\} .}\)

Wykażemy, że \(\displaystyle{ X_{a,b}\subset A_b}\), czyli ten zbiór \(\displaystyle{ X_{a,b}}\) zawiera się w tym naszym skonstruowanym antyłańcuchu o numerze, którym jest liczba naturalna \(\displaystyle{ b.}\)

Niech \(\displaystyle{ (n,m)\in X_{a,b}}\). Wtedy \(\displaystyle{ (n,m) \in X}\) i para \(\displaystyle{ (n,m)}\) jest nieporównywalna z parą \(\displaystyle{ (a,b).}\) Pokażemy, że \(\displaystyle{ m=b}\). Przypuśćmy nie wprost, że \(\displaystyle{ m \neq b}\). Wtedy \(\displaystyle{ m<b}\) lub \(\displaystyle{ b<m}\) (to jest przecież zwykły porządek na liczbach naturalnych).

Jeśli \(\displaystyle{ m<b}\), to z definicji relacji \(\displaystyle{ \prec}\) możemy wnioskować, że \(\displaystyle{ (n,m)\prec (a,b)}\), a para \(\displaystyle{ (n,m)}\) jest nieporównywalna z parą \(\displaystyle{ (a,b)}\), i otrzymaliśmy sprzeczność.

Jeśli \(\displaystyle{ b<m}\), to podobnie możemy wnioskować, że \(\displaystyle{ (a,b)\prec (n,m)}\), a para \(\displaystyle{ (n,m)}\) jest nieporównywalna z parą \(\displaystyle{ (a,b)}\) - i otrzymaliśmy sprzeczność.

Wobec czego \(\displaystyle{ m=b}\), mamy \(\displaystyle{ (n,m)\in X}\), a zatem \(\displaystyle{ (n,m)\in \left( \NN \times \left\{ b\right\} \right) \cap X=A_b.}\)

A zatem \(\displaystyle{ X_{a,b} \subset A_b.}\)

Wiemy, że zbiór \(\displaystyle{ A_b}\) ma dokładnie \(\displaystyle{ (b+1)}\) elementów, a więc jest zbiorem skończonym, więc również zbiór \(\displaystyle{ X_{a,b},}\) jako podzbiór zbioru skończonego, jest zbiorem skończonym.


Przypuśćmy nie wprost, że pewien zbiór \(\displaystyle{ B\subset X}\) jest nieskończonym antyłańcuchem. Niech \(\displaystyle{ (a,b)\in B \neq \left\{ \right\}}\). Rozważmy zbiór \(\displaystyle{ C}\), określony jako:

\(\displaystyle{ C=\left\{ \left( n,m\right)\in B: (n,m) \neq \left( a,b\right) \hbox{ i para } (n,m) \hbox{ jest nieporównywalna z parą } (a,b)\right\}.}\)

Wtedy oczywiście \(\displaystyle{ C\subset X_{a,b}}\), który to zbiór \(\displaystyle{ X_{a,b}}\) jest zbiorem skończonym, więc również zbiór \(\displaystyle{ C}\) jest zbiorem skończonym.


Pokażemy teraz, że \(\displaystyle{ B=C \cup \left\{ \left( a,b\right) \right\} .}\)

Mamy \(\displaystyle{ C\subset B}\), \(\displaystyle{ (a,b)\in B}\), wiec wystarczy pokazać, że \(\displaystyle{ B\subset C \cup \left\{ \left( a,b\right) \right\}.}\)

Niech \(\displaystyle{ (n,m)\in B}\), i załóżmy, że \(\displaystyle{ (n,m) \neq \left( a,b\right)}\) i pokażmy, że \(\displaystyle{ (n,m)\in C}\). Mamy \(\displaystyle{ (n,m)\in B}\), \(\displaystyle{ (a,b)\in B}\) i \(\displaystyle{ B}\) jest antyłańcuchem, więc ponieważ \(\displaystyle{ (n,m) \neq \left( a,b\right)}\), wiec pary \(\displaystyle{ (n,m)}\) i \(\displaystyle{ (a,b)}\) jako dwa różne elementy antyłańcucha \(\displaystyle{ B}\) są nieporównywalne, więc możemy wnioskować (i mamy \(\displaystyle{ (n,m) \neq \left( a,b\right)}\) ), więc wnioskujemy, że \(\displaystyle{ (n,m)\in C.}\)

A zatem \(\displaystyle{ B\subset C \cup \left\{ \left( a,b\right) \right\}}\) , i \(\displaystyle{ B=C \cup \left\{ \left( a,b\right) \right\}.}\)


Ponieważ \(\displaystyle{ C}\) jest zbiorem skończonym, więc po dodaniu jednej pary otrzymamy, że również \(\displaystyle{ B}\) jest zbiorem skończonym, a \(\displaystyle{ B}\) z założenia jest nieskończonym antyłańcuchem- więc otrzymujemy sprzeczność. Wobec czego, w tym zbiorze uporządkowanym nie ma nieskończonych antyłańcuchów.\(\displaystyle{ \square}\) :D :lol:



Niech \(\displaystyle{ (X, \le)}\) będzie niepustym zbiorem uporządkowanym. Rozważmy kwadrat \(\displaystyle{ X \times X}\), i rozważmy górną połowę tego kwadratu wraz z przekątną, tzn. rozważmy zbiór \(\displaystyle{ X_0}\):

\(\displaystyle{ X_0=\left\{ \left( a,b\right)\in X \times X\Bigl| \ \ a \le b\right\} }\),

i rozważmy relację \(\displaystyle{ \prec}\) na zbiorze \(\displaystyle{ X_0}\), daną jako:

\(\displaystyle{ (x_1,y_1)\prec (x_2, y_2) \longleftrightarrow y_1<y_2.}\)

Wykażemy, że to jest relacja przeciwzwrotna i przechodnia.
Dowód tego faktu::    
Ponieważ relacja \(\displaystyle{ \prec}\) jest przeciwzwrotna i przechodnia w \(\displaystyle{ X_0}\), to relacja \(\displaystyle{ \preccurlyeq}\) na \(\displaystyle{ X_0}\), dana jako:

\(\displaystyle{ (x\preccurlyeq y \Leftrightarrow x\prec y \vee x=y)}\),

jest relacją porządku na \(\displaystyle{ X_0}\), a więc \(\displaystyle{ \left( X_0,\preccurlyeq\right) }\) jest zbiorem uporządkowanym.


Wykażemy, że dla dowolnego punktu \(\displaystyle{ x\in X}\), zbiór \(\displaystyle{ A_x}\) zdefiniowany jako:

\(\displaystyle{ A_x=\left( X \times \left\{ x\right\} \right) \cap X_0,}\)

taki zbiór \(\displaystyle{ A_x}\) jest antyłańcuchem.

Mamy \(\displaystyle{ A_x\subset X_0}\), jak trzeba.

Aby wykazać, że ten zbiór \(\displaystyle{ A_x}\) jest antyłańcuchem, to weźmy dowolne różne pary \(\displaystyle{ (x_1,y_1); (x_2,y_2)\in A_x}\), czyli takie, że \(\displaystyle{ (x_1, y_1) \neq (x_2, y_2).}\)

Przypuśćmy, że \(\displaystyle{ (x_1,y_1)\prec (x_2, y_2)}\). Wtedy z definicji \(\displaystyle{ \prec}\), mamy: \(\displaystyle{ y_1<y_2.}\) Mamy \(\displaystyle{ (x_1,y_1)\in A_x}\), zatem \(\displaystyle{ (x_1,y_1)\in X \times \left\{ x \right\}}\), skąd \(\displaystyle{ y_1=x}\). Ponieważ \(\displaystyle{ (x_2,y_2)\in A_x}\), więc \(\displaystyle{ (x_2, y_2)\in X \times \left\{ x\right\}}\) , skąd \(\displaystyle{ y_2=x}\). Ponieważ \(\displaystyle{ y_1<y_2}\), to możemy wnioskować, że \(\displaystyle{ x<x}\)-sprzeczność.

Jeśli \(\displaystyle{ (x_2, y_2)\prec (x_1,y_1)}\), to analogicznie otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ (x_1, y_1)\not\prec (x_2,y_2)}\) oraz \(\displaystyle{ (x_2,y_2)\not\prec (x_1, y_1) }\), czyli pary \(\displaystyle{ (x_1,y_1)}\) i \(\displaystyle{ (x_2,y_2)}\) są nieporównywalne. Z dowolności wyboru takich par otrzymujemy, że zbór \(\displaystyle{ A_x}\) jest antyłańcuchem.\(\displaystyle{ \square}\) :D
ODPOWIEDZ