Porządek produktowy

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

Porządek produktowy

Post autor: Jakub Gurak »

Udowodnilem wczoraj, że jeśli mamy dwa zbiory uporządkowane \(\displaystyle{ \left( X, \le _X\right)}\) oraz \(\displaystyle{ \left( Y, \le _Y\right)}\) (uporządkowane, tym razem, niekoniecznie liniowo), oraz gdy mamy antyłańcuch \(\displaystyle{ A\subset X}\) w \(\displaystyle{ X}\), i mamy antyałańcuch \(\displaystyle{ B\subset Y}\) w \(\displaystyle{ Y}\), to zbiór \(\displaystyle{ A \times B}\) jest antyłańcuchem w \(\displaystyle{ X \times Y}\) z porządkiem prduktowym, tzn. z porządkiem \(\displaystyle{ \le _P}\), zdefiniowanym w poniższy sposób:

\(\displaystyle{ \left( x_1,y_1\right) \le _P \left( x_2, y_2\right) \Leftrightarrow \left( x_1 \le _X x_2 \hbox{ i } y_1\le y_2 \right).
}\)


Udowodniłem też wczoraj, że jeśli mamy prócz tego zbiory \(\displaystyle{ A\subset X }\) oraz \(\displaystyle{ B\subset Y}\), to zbiór \(\displaystyle{ A \times B}\) ma element największy względem porządku produktowego, dokładnie wtedy, gdy zbiór \(\displaystyle{ A}\) ma element największy i zbiór \(\displaystyle{ B}\) ma element największy. Udowodniłem też dzisiaj analogiczny fakt dla elementów najmniejszych, jak i udowodniłem, że porządek odwrotny do porządku produktowego dwóch porządków jest porządkiem produktowym porządków odwrotnych tych dwóch porządków. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ \left( X, \le _X\right); \left( Y, \le _Y\right) }\) będą zbiorami uporządkowanymi. Rozważmy antyłańcuch \(\displaystyle{ A\subset X}\) w zbiorze uporządkowanym \(\displaystyle{ X, }\) oraz rozważmy antyłańcuch \(\displaystyle{ B\subset Y}\) w zbiorze \(\displaystyle{ Y}\). Wykażemy, że zbiór \(\displaystyle{ A \times B}\) jest antyłańcuchem w \(\displaystyle{ X \times Y}\) z porządkiem produktowym \(\displaystyle{ \le _P}\).

DOWÓD TEGO FAKTU:

Zauważmy najpierw, że \(\displaystyle{ A \times B\subset X \times Y}\), jak trzeba.

Aby wykazać, że ten zbiór jest antyłańcuchem, to weźmy dwie różne pary \(\displaystyle{ \left( a_1, b_1\right) ; \left( a_2,b_2\right) \in A \times B}\). Wtedy \(\displaystyle{ a_1 \neq a_2}\) lub \(\displaystyle{ b_1 \neq b_2.}\)

Przypuśćmy, że \(\displaystyle{ a_1 \neq a_2. }\)
Przypuśćmy nie wprost, że \(\displaystyle{ \left( a_1,b_1\right) \le _P \left( a_2,b_2\right) }\). Wtedy, z definicji porządku produktowego wnioskujemy, że \(\displaystyle{ a_1 \le _X a_2}\), i \(\displaystyle{ a_1 \neq a_2}\) i \(\displaystyle{ a_1,a_2\in A}\), a zbiór \(\displaystyle{ A}\) jest antyłańcuchem w \(\displaystyle{ X}\), więc wnioskujemy, że elementy \(\displaystyle{ a_1}\) i \(\displaystyle{ a_2}\) są nieporównywalne, a \(\displaystyle{ a_1 \le_X a_ 2}\). Sprzeczność. Wobec czego \(\displaystyle{ \left( a_1,b_1\right) \not \le_P \left( a_2,b_2\right).}\)
Przypuśćmy teraz, że \(\displaystyle{ \left( a_2,b_2\right) \le _P \left( a_1,b_1\right) }\). Wtedy \(\displaystyle{ a_2 \le _X a_1}\) i \(\displaystyle{ a_1 \neq a_2}\). Ponieważ zbiór \(\displaystyle{ A}\) jest antyłańcuchem, a \(\displaystyle{ a_1}\) i \(\displaystyle{ a_2}\) jego dwoma różnymi elementami, więc wnioskujemy, że elementy \(\displaystyle{ a_1, a_2}\) są nieporównywalne, lecz \(\displaystyle{ a_2 \le _X a_1}\)- sprzeczność. Wobec czego \(\displaystyle{ \left( a_2,b_2\right) \not \le _P \left( a_1,b_1\right). }\)
Wobec czego pary \(\displaystyle{ \left( a_1,b_1\right) }\) i \(\displaystyle{ \left( a_2,b_2\right)}\) są nieporównywalne.

Jeśli \(\displaystyle{ a_1=a_2}\), to \(\displaystyle{ b_1 \neq b_2}\), i w sposób analogiczny jak powyżej uzasadniamy, że pary \(\displaystyle{ \left( a_1, b_1\right)}\) i \(\displaystyle{ \left( a_2, b_2\right) }\) są nieporównywalne.

A zatem zbiór \(\displaystyle{ A \times B}\) jest antyłańcuchem. \(\displaystyle{ \square}\) :D


Rozważmy prostokąt \(\displaystyle{ X \times Y}\) z porządkiem produktowym \(\displaystyle{ \le _P}\) porządków \(\displaystyle{ \le _X}\) i \(\displaystyle{ \le _Y.}\) Rozważmy dwa zbiory \(\displaystyle{ A\subset X}\), oraz \(\displaystyle{ B\subset Y}\). Wykazemy, że zbiór \(\displaystyle{ A \times B}\) ma element największy względem porządku produktowego, dokładnie wtedy, gdy \(\displaystyle{ A}\) ma element największy, względem \(\displaystyle{ \le _X,}\) i zbiór \(\displaystyle{ B}\) ma element największy, względem \(\displaystyle{ \le _Y.}\)

DOWÓD TEGO FAKTU:

Załóżmy, że zbiór \(\displaystyle{ A \times B}\) ma element największy \(\displaystyle{ \left( a,b\right) \in A \times B}\). Wtedy oczywiście \(\displaystyle{ a\in A}\) i \(\displaystyle{ b\in B}\). Wykażemy, że element \(\displaystyle{ a}\) jest największy w zbiorze \(\displaystyle{ A.}\)
Niech \(\displaystyle{ x\in A}\). Ponieważ \(\displaystyle{ \left( x,b\right) \in A \times B}\), a para \(\displaystyle{ \left( a,b\right)}\) jest elementem największym zbioru \(\displaystyle{ A \times B}\), więc: \(\displaystyle{ \left( x,b\right) \le _P \left( a,b\right) }\), a stąd mozemy wnioskować (z definicji porządku produktowego), że: \(\displaystyle{ x \le _X a}\), i element \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A.}\)

W sposób symetryczny udowadniamy, że element \(\displaystyle{ b}\) jest największy w zbiorze \(\displaystyle{ B}\), co dowodzi implikacji w prawo.

Aby pokazać implikację w lewo, załóżmy, że zbiór \(\displaystyle{ A}\) ma element największy \(\displaystyle{ a\in A}\) oraz, że zbiór \(\displaystyle{ B}\) ma element największy \(\displaystyle{ b\in B}\). Pokażemy, że para \(\displaystyle{ \left( a,b\right)}\) jest elementem największym zbioru \(\displaystyle{ A \times B}\). Ponieważ \(\displaystyle{ a\in A}\) i \(\displaystyle{ b\in B}\), to \(\displaystyle{ \left( a,b\right) \in A \times B.}\) Niech \(\displaystyle{ \left( x,y\right) \in A \times B.}\) Pokażemy, że \(\displaystyle{ \left( x,y\right) \le_P \left( a,b\right).}\) Mamy \(\displaystyle{ x\in A, y\in B.}\) Ponieważ element \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A}\), to \(\displaystyle{ x \le _X a}\), a ponieważ element \(\displaystyle{ b}\) jest największy w \(\displaystyle{ B}\), więc \(\displaystyle{ y \le _Y b}\), a zatem, na podstawie definicji porządku produktowego otrzymujemy, że: \(\displaystyle{ \left( x,y\right) \le _P \left( a,b\right)}\), i para \(\displaystyle{ \left( a,b\right)}\) jest elementem największym zbioru \(\displaystyle{ A \times B.\square}\)

Wykażemy analogiczny fakt dla elementów najmniejszych . Podajmy najpierw pewien lemat.

LEMAT. Rozważmy prostokąt kartezjański \(\displaystyle{ X \times Y}\) z porządkiem produktowym \(\displaystyle{ \le _P}\) dwóch porzadków \(\displaystyle{ \le _X}\) i \(\displaystyle{ \le _Y}\). Wykażemy, że porządek odwrotny do porządku produktowego tych dwóch porzadków jest porządkiem produktowym porządków odwrotnych, tzn. jeśli porządek produktowy dwóch porządków \(\displaystyle{ \le _A}\) i \(\displaystyle{ \le _B}\) na zbiorach \(\displaystyle{ A,B}\), gdy porządek produktowy oznaczymy jako: \(\displaystyle{ \le _A \otimes_P \le _B }\), to wykażemy, że \(\displaystyle{ \left( \le _X \otimes_P \le _Y\right) ^{-1}= \left( \le _{X} ^{-1} \right) \otimes_P \left( \le _{Y} ^{-1}\right) }\).
DOWÓD TEGO FAKTU::    
Rozważmy teraz prostokąt \(\displaystyle{ X \times Y}\) z porządkiem produktowym porządków \(\displaystyle{ \le _X }\) i \(\displaystyle{ \le _Y}\). Rozważmy dwa zbiory: \(\displaystyle{ A\subset X}\) i \(\displaystyle{ B\subset Y.}\) Wykażemy, że zbiór \(\displaystyle{ A \times B}\) ma element najmniejszy, dokładnie wtedy, gdy zbiór \(\displaystyle{ A}\) ma element najmniejszy, względem \(\displaystyle{ \le _X,}\) i zbiór \(\displaystyle{ B}\) ma element najmniejszy, względem \(\displaystyle{ \le _Y.}\)

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ A\subset X}\) , niech \(\displaystyle{ B\subset Y.}\)

Mamy, na mocy lematu powyżej, i na mocy faktu udowodnionego tuz przed nim:

Zbiór \(\displaystyle{ A \times B}\) ma element najmniejszy względem \(\displaystyle{ \left( \le _X \otimes_P \le _Y\right) }\) , dokładnie wtedy, gdy zbiór \(\displaystyle{ A \times B}\) ma element największy względem \(\displaystyle{ \left( \le _X \otimes_P \le _Y\right) ^{-1}= \left( \le _{X} ^{-1} \right) \otimes_P \left( \le _{Y} ^{-1}\right) }\), a to zachodzi (na mocy już udowodnionego analogicznego faktu), dokładnie wtedy, gdy: \(\displaystyle{ A}\) ma element największy względem \(\displaystyle{ \le _X ^{-1}}\) i zbiór \(\displaystyle{ B}\) ma element największy względem \(\displaystyle{ \le_Y ^{-1}}\), a to zachodzi wtedy, gdy zbiór \(\displaystyle{ A}\) ma element najmniejszy wzgledem \(\displaystyle{ \le _X}\) i zbiór \(\displaystyle{ B}\) ma element najmniejszy względem \(\displaystyle{ \le _Y. \square}\) :lol:

Dodano po 9 miesiącach 14 dniach 21 godzinach 33 minutach 9 sekundach:
Można też rozważać porządek produktowy trzech zbiorów uporządkowanych. tzn.:

Jeśli mamy trzy zbiory uporządkowane ( tym razem niekoniecznie liniowo): \(\displaystyle{ \left( X, \le _{X}\right) }\); \(\displaystyle{ \left( Y, \le _{Y}\right) }\) i \(\displaystyle{ \left( Z, \le _{Z}\right), }\) to na zbiorze \(\displaystyle{ (X \times Y) \times Z}\) możemy rozważać porządek produktowy \(\displaystyle{ \le _P:= \left( \le _X\otimes _{P} \le _{Y} \right) \otimes _{P} \le _{Z}}\), który, na mocy łączności koniunkcji i na mocy definicji porządku produktowego dwóch zbiorów, możemy określić w równoważny sposób:

\(\displaystyle{ \left( x_1, y_1, z_1\right) \le_P \left( x_2, y_2, z_2\right) \Longleftrightarrow x_1 \le _{X} x_2 \hbox{ i } y_1 \le _{Y} y_2 \hbox{ i } z_1 \le _{Z} z_2.}\)

Łatwo jest wykazać, że dla trzech zbiorów \(\displaystyle{ X_1 \subset X}\), \(\displaystyle{ Y_1 \subset Y}\) i \(\displaystyle{ Z_1 \subset Z}\) kostka \(\displaystyle{ \left( X_1 \times Y_1\right) \times Z_1}\) ma element najmniejszy, wtedy i tylko wtedy, gdy zbiór \(\displaystyle{ X_1}\) ma element najmniejszy, względem \(\displaystyle{ \le _Y}\), i zbiór \(\displaystyle{ Y_1}\) ma element najmniejszy i zbiór \(\displaystyle{ Z_1}\) ma element najmniejszy, gdyż (na mocy faktu z postu powyżej):

zbiór \(\displaystyle{ \left( X_1 \times Y_1\right) \times Z_1}\) ma element najmniejszy, względem \(\displaystyle{ \le _P}\), dokładnie wtedy, gdy zbiór \(\displaystyle{ \left( X_1 \times Y_1\right)}\) ma element najmniejszy względem \(\displaystyle{ \left( \le _{X} \right) \otimes _P\left( \le _Y\right)}\)
i zbiór \(\displaystyle{ Z_1}\) ma element najmniejszy, a to zachodzi dokładnie wtedy, gdy: \(\displaystyle{ X_1}\) ma element najmniejszy względem \(\displaystyle{ \le _X}\) i \(\displaystyle{ Y_1}\) ma element najmniejszy względem \(\displaystyle{ \le _Y}\) i \(\displaystyle{ Z_1}\) ma element najmniejszy względem \(\displaystyle{ \le _Z.\square}\) 8-)

Podobny fakt można sformułować i udowodnić dla elementów największych.

Wczoraj wykazałem, że jeśli mamy trzy zbiory uporządkowane \(\displaystyle{ \left( X, \le _X\right) }\); \(\displaystyle{ \left( Y, \le _Y\right) }\) i \(\displaystyle{ \left( Z, \le _Z \right) }\) oraz mamy trzy antyłańcuchy \(\displaystyle{ X_1 \subset X}\), \(\displaystyle{ Y_1 \subset Y}\) i \(\displaystyle{ Z_1 \subset Z}\), to kostka \(\displaystyle{ \left( X_1 \times Y_1\right) \times Z_1}\) jest antyłańcuchem, względem porżądku produktowego \(\displaystyle{ \le _P.}\)

Oto:

DOWÓD TEGO FAKTU:

Niech \(\displaystyle{ \left( x_1, y_1, z_1\right)}\) ;\(\displaystyle{ \left( x_2, y_2, z_2\right) \in \left( X_1 \times Y_1\right) \times Z}\)_będą różnymi trójkami.

Wtedy: \(\displaystyle{ x_1 \neq x_2}\) lub \(\displaystyle{ y_1 \neq y_2}\) lub \(\displaystyle{ z_1 \neq z_2.}\)

Przypuśćmy, że:

\(\displaystyle{ \left( x_1, y_1, z_1\right) <_P \left( x_2, y_2, z_2 \right).}\)

Wtedy, z definicji porządku produktowego: \(\displaystyle{ x_1 \le x_2}\) i \(\displaystyle{ y_1 \le y_2}\) i \(\displaystyle{ z_1 \le z_2}\).

Jeśli \(\displaystyle{ x_1 \neq x_2}\), to ponieważ \(\displaystyle{ x_1, x_2 \in X_1}\), a zbiór \(\displaystyle{ X_1}\) jest antyłańcuchem, więc ponieważ \(\displaystyle{ x_1 \le x_2}\), więc otrzymujemy sprzeczność z definicją antyłańcucha.

Jeśli \(\displaystyle{ y_1 \neq y_2}\), to ponieważ zbiór \(\displaystyle{ Y_1}\) jest antyłańcuchem, a \(\displaystyle{ y_1,y_2 \in Y_1}\) jego dwoma różnymi elementami i \(\displaystyle{ y_1 \le y_2}\), więc również otrzymujemy sprzeczność.

Jeśli \(\displaystyle{ z_1 \neq z_2}\), to podobnie otrzymujemy sprzeczność.\(\displaystyle{ }\)

Wobec czego \(\displaystyle{ \left( x_1, y_1, z_1\right)\not \le_P \left( x_2, y_2, z_2\right).}\)

Przypuśćmy teraz, że: \(\displaystyle{ \left( x_1, y_1, z_1\right) >_P \left( x_2, y_2, z_2\right).}\)

Wtedy \(\displaystyle{ x_1 \ge x_2}\); \(\displaystyle{ y_1 \ge y_2}\) i \(\displaystyle{ z_1 \ge z_2}\).

Jeśli \(\displaystyle{ x_1 \neq x_2}\), to ponieważ \(\displaystyle{ x_1, x_2 \in X_1}\), a zbiór \(\displaystyle{ X_1}\) jest antyłańcuchem i \(\displaystyle{ x_1 \ge x_2}\), więc otrzymujemy sprzeczność.

Jeśli \(\displaystyle{ y_1 \neq y_2}\), to podobnie otrzymujemy sprzeczność; i tak samo w przypadku \(\displaystyle{ z_1 \neq z_2}\) otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ \left( x_1, y_1, z_1\right) \not>_P \left( x_2, y_2, z_2\right).}\) Mamy też \(\displaystyle{ \left( x_1, y_1, z_1\right) \not \le _P \left( x_2, y_2, z_2\right)}\) , a więc trójki \(\displaystyle{ \left( x_1, y_1, z_1\right)}\) i \(\displaystyle{ \left( x_2, y_2, z_2\right)}\) są nieporównywalne.

Z dowolności wyboru takich trójek otrzymujemy, że kostka \(\displaystyle{ \left( X_1 \times Y_1\right) \times Z_1}\) jest antyłańcuchem.\(\displaystyle{ \square}\)


Na koniec dodam, że wczoraj odkryłem sytuację, kiedy dopełnienie sumy rodziny zbiorów jest równe sumie dopełnień (trochę w innym sensie):

Rozważmy ciąg przedziałów ograniczonych na prostej: \(\displaystyle{ \left( A_n\right) _{n \in \NN}}\); gdzie \(\displaystyle{ A_n \subset \RR}\).
Rozważmy jeszcze drugi ciąg przedziałów \(\displaystyle{ \left( B_n\right) _{n \in \NN}}\), gdzie \(\displaystyle{ B_n \subset \RR,}\) i gdzie \(\displaystyle{ B_n \subset A_n}\), dla każdego \(\displaystyle{ n}\) naturalnego.

Dla dowolnego \(\displaystyle{ n \in \NN}\), niech:

\(\displaystyle{ B''_n= A_n \setminus B_n}\),

i niech:

\(\displaystyle{ \left( \bigcup_{n \in \NN} B_n\right)''= \left( \bigcup_{n \in \NN} A_n\right) \setminus \left( \bigcup_{n \in \NN} B_n\right) }\).

Wtedy zapewne:

\(\displaystyle{ \left( \bigcup_{n \in \NN} B_n \right) ''= \bigcup_{n \in \NN} B''_n. }\)

Muszę to udowdnić. 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: Porządek produktowy

Post autor: Jakub Gurak »

Ups :? ,
zapomniałem założenia, że ciąg przedziałów \(\displaystyle{ \left( A_n\right) _{n \in \NN} }\) ma być ciągiem zbiorów rozłącznych...
ODPOWIEDZ