Wiemy że dla dwóch zbiorów dobrze uporządkowanych porządek leksykograficzny na iloczynie kartezjańskim jest również dobry.
Ciekawy szkic konstrukcji:
Niech \(\displaystyle{ \left( X, \le _{X} \right) ,\left( Y, \le _{Y} \right)}\)będą zbiorami dobrze uporządkowanymi. Niech \(\displaystyle{ \left\{ \right\} \neq A \subset X\times Y}\) będzie niepustym podzbiorem. Jak wymierzyć element najmniejszy. Zauważmy, że zbiór \(\displaystyle{ A}\) jest relacją między \(\displaystyle{ X}\) a \(\displaystyle{ Y}\). Rozważmy \(\displaystyle{ A _{L}}\)- jest to lewa dziedzina tej relacji. Ponieważ \(\displaystyle{ A}\) jest niepustą relacją, to ma w sobie parę \(\displaystyle{ (x,y)}\), a wtedy \(\displaystyle{ x\in A_L}\), czyli zbiór \(\displaystyle{ A_L}\) jest niepusty. Jest podzbiorem \(\displaystyle{ X}\). Zatem z definicji zbioru dobrze uporządkowanego ma element najmniejszy \(\displaystyle{ x_0}\). Rozważmy teraz zbiór \(\displaystyle{ Y_0=\left\{ y\in Y \Bigl| \ \ \left( x _{0},y \right)\in A \right\}}\). Ponieważ element najmniejszy \(\displaystyle{ x_0\in A_L}\), więc przy pewnym \(\displaystyle{ y\in Y}\) mamy \(\displaystyle{ (x_0,y)\in A}\). Oznacza to, że \(\displaystyle{ y\in Y_0.}\)Zatem jest to zbiór niepusty. Jest podzbiorem \(\displaystyle{ Y}\). Zatem z definicji zbioru dobrze uporządkowanego \(\displaystyle{ Y}\) ma element najmniejszy \(\displaystyle{ y_0}\). I pokazujemy, że para \(\displaystyle{ (x_0,y_0)}\) jest elementem najmniejszym w \(\displaystyle{ A}\) względem porządku leksykograficznego. Oto ilustracja:
Zachodzi pytanie czy w drugą stronę, dla dwóch niepustych zbiorów \(\displaystyle{ X,Y}\) jeśli przynajmniej jeden nie jest dobrze uporządkowany , to porządek leksykograficzny na iloczynie kartezjańskim nie jest dobry Czyli aby porządek leksykograficzny na iloczynie kartezjańskim dwóch zbiorów był dobry, to obydwa muszą być dobrze uporządkowane? (Dla zbioru pustego \(\displaystyle{ \rightarrow}\) iloczyn kartezjański jest pusty \(\displaystyle{ \rightarrow}\) otrzymujemy porządek pusty, a więc dobry porządek, dobrze myślę , choć drugi zbiór może być jakikolwiek, czyli nie być dobrze uporządkowany).
Spróbuję to wcześniejsze uzasadnić. Przypuśćmy, że zbiór \(\displaystyle{ X}\) nie jest dobrze uporządkowany. Ma zatem niepusty podzbiór \(\displaystyle{ A}\), który nie ma elementu najmniejszego. Ponieważ \(\displaystyle{ Y}\) jest niepusty, więc istnieje \(\displaystyle{ y\in Y}\). Ustalmy taki element. Popatrzmy na \(\displaystyle{ A \times \left\{ y\right\},}\) taki zbiór jest niepustym podzbiorem \(\displaystyle{ X\times Y}\). Przypuśćmy dla dowodu niewprost, że porządek leksykograficzny jest dobry. Wtedy zbiór \(\displaystyle{ A \times \left\{ y\right\},}\) ma element najmniejszy \(\displaystyle{ (x,y)}\). Wtedy \(\displaystyle{ x}\) jest elementem najmniejszym \(\displaystyle{ A}\)- sprzeczność.(Dobrze )
Pozostał oddzielny drugi przypadek, gdy zbiór \(\displaystyle{ Y}\) nie jest dobrze uporządkowany. Ma zatem niepusty podzbiór \(\displaystyle{ B,}\) który nie ma elementu najmniejszego. Ponieważ \(\displaystyle{ X}\) jest niepusty, więc istnieje \(\displaystyle{ x\in X}\). Ustalmy taki element. Popatrzmy na \(\displaystyle{ \left\{ x\right\} \times B}\)- taki zbiór jest niepustym podzbiorem \(\displaystyle{ X\times Y}\). Przypuśćmy dla dowodu nie wprost, że porządek leksykograficzny jest dobry. Wtedy zbiór \(\displaystyle{ \left\{ x\right\} \times B}\) ma element najmniejszy \(\displaystyle{ (x,y_0)}\). Wtedy para \(\displaystyle{ (x,y_0)}\) jest mniejsza od każdej pary ze zbioru \(\displaystyle{ \left\{ x\right\} \times B}\) oznaczmy ją \(\displaystyle{ (x,y)}\), a to oznacza z definicji porządku leksykograficznego, że \(\displaystyle{ y_0}\) jest mniejsze od każdego \(\displaystyle{ y\in B}\), oraz \(\displaystyle{ y_0\in B}\), zatem \(\displaystyle{ y_0}\) jest najmniejszym elementem \(\displaystyle{ B}\) - sprzeczność z tym, że w \(\displaystyle{ B}\) nie ma elementu najmniejszego. \(\displaystyle{ \square}\) (Dobrze ?)
