Iloczyn kartezjański z porządkiem leksykograficznym

[Jakub Gurak]

Udowodniłem, w ostatnich dniach, parę podstawowych faktów związanych z mnożeniem typów porządkowych zbiorów liniowo uporządkowanych. Udowodniłem na przykład, że jeśli ustawimy na osi zbiory skończone \(\displaystyle{ n}\)-elementowe, (weźmy, dla ilustracji, powiedzmy \(\displaystyle{ n=3}\)), gdy ustawimy zbiory trzyelementowe, tak jak ustawiamy liczby całkowite na osi, gdy zamiast nich ustawimy zbiory trzyelementowe, jeden za drugim, to otrzymamy zbiór typu zbioru liczb całkowitych. Podobnie, gdy ustawimy zbiory trzyelementowe, tak jak układamy na osi liczby naturalne, gdy ustawimy zamiast nich zbiory trzyelementowe, jeden za drugim, to otrzymamy zbiór typu zbioru liczb naturalnych. I podobną konstrukcję można rozważyć dla zbioru liczb całkowitych ujemnych wraz z zerem. Również, jeśli rozważymy przedziały domknięto-otwarte \(\displaystyle{ \left| a,b\right)}\), i jeśli je ustawimy, tak jak ustawiamy liczby całkowite na osi, gdy ustawimy zamiast nich takie przedziały domknięto-otwarte, jeden za drugim, to otrzymamy zbiór typu zbioru liczb rzeczywistych. A jak będziemy ustawiać przedziały domknięto-otwarte, jeden za drugim, tak jak ustawiamy liczby naturalne na osi, to otrzymamy zbiór typu zbioru liczb rzeczywistych nieujemnych, czyli półprostą wraz z początkiem. Niestety, nie można zastąpić przedziałów domknięto-otwartych przez przedziały obustronnie domknięte (bo pomiędzy jednym przedziałem a następnym drugim będą puste przedziały, a więc nie otrzymamy prostej ani półprostej), ani nie można przedziałów domknięto-otwartych zastąpić przez przedziały obustronnie otwarte (bo pomiędzy jednym przedziałem a następnym będzie przynajmniej luka). Jedynie jest szansa zastąpić takie przedziały przez przedziały otwarto-domknięte, ale nie wiem, tego nie badałem. Oczywiście zdaje sobie sprawę, że wyrażam się w sposób nieścisły (bo co to znaczy ustawić zbiór jeden za drugim), ale chciałem tu oddać intuicję. Jednak mam to wszystko dokładnie uściślone przy pomocy porządku leksykograficznego na iloczynie kartezjańskim. Dokładnie zbadałem te wspomniane powyżej fakty. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ n\in\NN}\), \(\displaystyle{ n \ge 1.}\) Niech \(\displaystyle{ Y=\left\{ m\in\NN: \ m<n\right\} }\).

Wykażemy, że zbiór \(\displaystyle{ \NN \times Y}\), z porządkiem leksykograficznym jest podobny do \(\displaystyle{ \NN}\) (co oznacza, że gdy weźmiemy \(\displaystyle{ n=3}\), to jak ustawimy zbiory trzyelementowe jeden za drugim , tak jak układamy liczby naturalne na osi, to otrzymamy zbiór typu zbioru liczb naturalnych, bo o porządku leksykograficznym na iloczynie kartezjańskim można myśleć jak o ustawieniu jedna za jedną prostą pionową tego iloczynu kartezjańskiego).

Rozważmy funkcję \(\displaystyle{ f:\NN \times Y \rightarrow \NN}\), daną jako:

\(\displaystyle{ f(a,b)= a \cdot n+b.}\)

Wykażemy, że ta funkcja jest podobieństwem.

Niech \(\displaystyle{ (a_1,b_1); (a_2,b_2) \in \NN \times Y}\) będą różnymi parami.

Jeśli \(\displaystyle{ a_1 \neq a_2}\), ponieważ \(\displaystyle{ a_1,a_2 \in \NN}\), więc \(\displaystyle{ a_1<a_2}\) lub \(\displaystyle{ a_2<a_1.}\)

Jeśli \(\displaystyle{ a_1<a_2}\), to \(\displaystyle{ f(a_2, b_2)=a_2 \cdot n+ b_2 \ge a_2 \cdot n}\),

i ponieważ \(\displaystyle{ a_1<a_2,}\) i \(\displaystyle{ a_1, a_2 \in\NN}\), więc to jest większe lub równe niż

\(\displaystyle{ \left( a_1+1\right) \cdot n= a_1 \cdot n+n}\),

i ponieważ \(\displaystyle{ b_1\in Y=\left\{ m\in\NN: \ m<n \right\}}\), więc \(\displaystyle{ b_1<n}\), więc to jest istotnie większe niż:

\(\displaystyle{ a_1 \cdot n+b_1= f(a_1, b_1)}\),

czyli \(\displaystyle{ f(a_2, b_2)> f(a_1,b_1)}\), a więc \(\displaystyle{ f(a_2, b_2) \neq f(a_1, b_1).}\)

Jeśli \(\displaystyle{ a_2<a_1}\), to analogicznie pokazujemy, że \(\displaystyle{ f(a_1, b_1)> f(a_2,b_2)}\), a więc \(\displaystyle{ f(a_2, b_2) \neq f(a_1, b_1).}\)

Jeśli \(\displaystyle{ a_1=a_2}\), to oznaczmy tą wartość jako \(\displaystyle{ a.}\) Wtedy musi być \(\displaystyle{ b_1 \neq b_2}\). Wtedy:

\(\displaystyle{ f(a_1,b_1)= a \cdot n+b_1}\), i podobnie

\(\displaystyle{ f(a_2,b_2)=a \cdot n+b_2.}\)

Przypuśćmy na moment, że \(\displaystyle{ a \cdot n+b_1=a \cdot n+b_2}\).

Wtedy z prawa skracania dla dodawania w liczbach naturalnych: \(\displaystyle{ b_1=b_2}\)- sprzeczność.

Wobec czego \(\displaystyle{ f(a_1,b_1)=a \cdot n+b_1 \neq a \cdot n+b_2 =f(a_2, b_2)}\), czyli \(\displaystyle{ f(a_1, b_1) \neq f(a_2, b_2).}\)

A zatem funkcja \(\displaystyle{ f}\) jest różnowartościowa.


Wykażemy teraz, że funkcja \(\displaystyle{ f}\) jest 'na'.

Zauważmy, że \(\displaystyle{ \NN= \bigcup_{m\in\NN} \left\{ m\right\} .}\)

Przypominam mamy prawo, jeśli \(\displaystyle{ \mathbb{B}}\) jest niepustą rodziną zbiorów, a \(\displaystyle{ A}\) jest niepustym zbiorem, to mamy prawo:

\(\displaystyle{ (\bigcup\mathbb{B} ) \times A= \bigcup_{B\in\mathbb{B}} \left( B \times A\right).}\)

W związku z czym, u nas mamy:

\(\displaystyle{ \NN \times Y = \left( \bigcup_{m\in\NN} \left\{ m\right\} \right) \times Y= \bigcup_{m\in\NN} \left( \left\{ m\right\} \times Y\right) .}\)

A zatem \(\displaystyle{ f_P=\stackrel { \rightarrow }{f}\left( \NN \times Y\right) =\stackrel { \rightarrow }{f} \left( \bigcup_{m\in\NN} \left( m\right\} \times Y \right)= \bigcup_{m\in\NN} \stackrel { \rightarrow }{f} \left( \left\{ m\right\} \times Y\right) .}\)

Teraz zauważmy, ze dla dowolnego ustalonego \(\displaystyle{ m\in\NN}\), mamy:

\(\displaystyle{ \left\{ m\right\} \times Y =\left\{ \left( m,y\right)\Bigl| \ y\in Y \right\}}\) , i \(\displaystyle{ Y=n=\left\{ x\in\NN: \ x<n\right\}.}\) A zatem

\(\displaystyle{ \left\{ m\right\} \times Y=\left\{ \left( m,x\right)\Bigl| \ x\in Y=n\right\} .}\) Wobec czego:

\(\displaystyle{ f_P= \bigcup_{m\in\NN} \stackrel { \rightarrow }{f} \left( \left\{ m\right\} \times Y\right) = \bigcup_{m\in\NN} \stackrel { \rightarrow }{f} \left( \left\{ \left( m,x\right) \Bigl| \ x\in n\right\} \right) = \bigcup_{m\in\NN} \left\{ f(m,0); f(m,1); \ldots; f(m,n-1) \right\} = \\ =\bigcup_{m\in\NN} \left\{ m \cdot n+0, m \cdot n+1,\ldots , m \cdot n+\left( n-1\right)\right\} = \\ =\left\{ 0,1, \ldots, n-1\right\} \cup \left\{ n, n+1,\ldots, 2n-1 \right\} \cup \left\{ 2n, 2n+1, \ldots, 2n+(n-1)=3n-1\right\} \cup \ldots= \NN.}\)

Wykazaliśmy zatem, że \(\displaystyle{ f_P=\NN}\). A zatem funkcja \(\displaystyle{ f}\) jest 'na', i \(\displaystyle{ f}\) jest bijekcją.

Wykażemy teraz, że funkcja \(\displaystyle{ f}\) jest monotoniczna.

Weźmy pary \(\displaystyle{ (a_1, b_1); (a_2, b_2)\in\NN \times Y}\), takie, że \(\displaystyle{ (a_1,b_1)<_l \left( a_2, b_2\right)}\) (gdzie \(\displaystyle{ \le _l}\) oznacza porządek leksykograficzny).

Jeśli \(\displaystyle{ a_1 \neq a_2}\), to z definicji porządku leksykograficznego musi być : \(\displaystyle{ a_1<a_2}\). Ponieważ \(\displaystyle{ a_1, a_2}\) są liczbami naturalnymi, to \(\displaystyle{ a_2 \ge a_1+1}\), a zatem

\(\displaystyle{ f(a_2, b_2)= a_2 \cdot n+b_2 \ge (a_1+1) \cdot n+b_2 \ge a_1 \cdot n+n}\),

i ponieważ \(\displaystyle{ b_1\in Y}\), więc \(\displaystyle{ b_1<n}\), więc to jest istotnie większe od:

\(\displaystyle{ a_1 \cdot n+b_1= f(a_1, b_1)}\),

czyli \(\displaystyle{ f(a_1, b_1)< f(a_2, b_2).}\)

Jeśli \(\displaystyle{ a_1=a_2}\), to oznaczmy tą wartość jako \(\displaystyle{ a}\). Wtedy musi być \(\displaystyle{ b_1<b_2}\). I wtedy:

\(\displaystyle{ f(a_1, b_1)=f(a, b_1)= a \cdot n+b_1< a \cdot n+b_2= f(a, b_2)=f(a_2, b_2)}\),

czyli \(\displaystyle{ f(a_1, b_1)< f(a_2, b_2).}\)

Wobec czego funkcja \(\displaystyle{ f}\) jest monotoniczna.

Ponieważ funkcja \(\displaystyle{ f}\) jest bijekcją monotoniczną pomiędzy \(\displaystyle{ \NN \times Y}\) , a \(\displaystyle{ \NN}\), czyli pomiędzy dwoma zbiorami liniowo uporządkowanymi, to funkcja \(\displaystyle{ f}\) jest podobieństwem, i zbiory \(\displaystyle{ \NN \times Y}\) i \(\displaystyle{ \NN}\) są podobne. Wobec czego mamy równość typów porządkowych: \(\displaystyle{ \omega \cdot n=\omega.\square}\)


Wykażemy teraz, że zbiór \(\displaystyle{ \left( \ZZ _{-} \cup \left\{ 0\right\} \right) \times \left\{ 1,2,\ldots, n \right\}}\) (z porządkiem leksykograficznym) jest podobny do zbioru \(\displaystyle{ \ZZ _{-} \cup \left\{ 0\right\} .}\)

Dowód:

Ponieważ porządek odwrotny do leksykograficznego na iloczynie kartezjańskim dwóch zbiorów jest porządkiem leksykograficznym porządków odwrotnych (dość elementarny jest to fakt), więc:

\(\displaystyle{ \left( \NN\otimes \left\{ 1,2,\ldots, n\right\} \right) ^{-1}= \NN ^{-1}\otimes \left\{ 1,2,\ldots, n\right\} ^{-1}}\),

a to jest zbiór podobny do \(\displaystyle{ \left( \ZZ_- \cup\left\{ 0\right\} \right) \otimes \left\{ 1,2,\ldots, n\right\}}\), gdyż porządek odwrotny do danego na zbiorze skończonym, wtedy porządek odwrotny do danego jest podobny do danego (ten fakt udowodniłem tu).

Wykazaliśmy zatem, że zbiór \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\}\right) \otimes \left\{ 1,2,\ldots, n\right\}}\) jest podobny do porządku odwrotnego \(\displaystyle{ \left( \NN\otimes \left\{ 1,2,\ldots,n\right\}\right) ^{-1} }\).

Ale na podstawie faktu dowiedzionego powyżej zbiór \(\displaystyle{ \NN \times \left\{ 1,2,\ldots, n\right\}}\) jest podobny do \(\displaystyle{ \NN}\). A zatem porządek do niego odwrotny jest podobny do porządku odwrotnego \(\displaystyle{ \left( \NN, \le ^{-1} \right)}\) , a ten zbiór jest podobny do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\} }\).

A zatem (z przechodniości podobieństwa) otrzymujemy, że \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\}\right) \otimes \left\{ 1,2,\ldots, n\right\}}\) jest podobny do \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\} . \square}\)


Udowodnimy teraz, że zbiór \(\displaystyle{ \ZZ \times \left\{ 1,2,\ldots, n\right\}}\) jest podobny do \(\displaystyle{ \ZZ.}\)

Mamy \(\displaystyle{ \ZZ=\ZZ_-\oplus \NN}\)- zbiór liczb całkowitych jest sumą porządkową zbioru liczb całkowitych ujemnych i zbioru liczb naturalnych, a więc zbiór \(\displaystyle{ \ZZ \otimes \left\{ 1,2,\ldots, n\right\}}\) będzie, korzystając z rozdzielności sumy porządkowej względem porządku leksykograficznego, co udowodniłem TUTAJ, pod koniec, otrzymujemy, że jest to identyczny zbiór co \(\displaystyle{ (\ZZ_-\otimes \left\{ 1,2,\ldots, n\right\} )\oplus( \NN\otimes \left\{ \left\{ 1,2,\ldots, n\right\} \right\} )}\), ponieważ zbiór \(\displaystyle{ \ZZ_-}\)jest oczywiście podobny do zbioru \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\}}\), i ponieważ udowodniliśmy, że zbiór \(\displaystyle{ \NN\otimes \left\{ 1,2,\ldots, n\right\}}\) jest podobny do \(\displaystyle{ \NN}\), więc cały otrzymany powyżej zbiór- jest to zbiór podobny do \(\displaystyle{ \left[ \left( \ZZ_- \cup \left\{ 0\right\} \right) \otimes \left\{ 1,2,\ldots, n\right\}\right] \oplus \NN}\). Ale przed chwilą wykazałem, że zbiór \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\}\right) \otimes \left\{ 1,2,\ldots, n\right\} }\) jest podobny do \(\displaystyle{ (\ZZ_- \cup \left\{0 \right\}}\), więc całość będzie zbiorem podobnym do \(\displaystyle{ \left( \ZZ_- \cup \left\{ 0\right\} \right) \oplus \NN}\), i ponieważ \(\displaystyle{ \ZZ_- \approx \ZZ_- \cup \left\{ 0 \right\}}\), więc jest to zbiór podobny do \(\displaystyle{ \ZZ_-\oplus \NN =\ZZ. \square}\)


Rozważmy teraz przedział domknięto-otwarty \(\displaystyle{ \left[ a,b\right) \subset \RR}\), gdzie \(\displaystyle{ a<b}\). Rozważmy iloczyn kartezjański \(\displaystyle{ \ZZ \times \left[ a,b\right)}\) (z porządkiem leksykograficznym). Wykażemy, że jest to zbiór podobny do zbioru liczb rzeczywistych \(\displaystyle{ \RR}\).

Dowód:

Na początek przeskalujmy przedział \(\displaystyle{ \left[ a,b\right)}\) na przedział \(\displaystyle{ \left[ 0,1\right)}\), tzn. wykażmy, że te dwa przedziały są podobne. W tym celu rozważmy funkcję \(\displaystyle{ f:\left[ a,b\right) \rightarrow \left[ 0,1\right)}\), daną jako:

\(\displaystyle{ f(x)= \frac{x-a}{b-a}.}\)

Ponieważ \(\displaystyle{ a<b}\), więc \(\displaystyle{ b-a \neq 0.}\)

Zauważmy, że jeśli \(\displaystyle{ x\in\left[ a,b\right)}\), to \(\displaystyle{ a \le x<b}\), a zatem \(\displaystyle{ 0 \le x-a <b-a}\), i ponieważ \(\displaystyle{ b-a>0}\), więc

\(\displaystyle{ 0= \frac{0}{b-a} \le \frac{x-a}{b-a}< \frac{b-a}{b-a}=1}\) ,

czyli \(\displaystyle{ 0 \le f(x)= \frac{x-a}{b-a} <1}\), i \(\displaystyle{ f(x)\in \left[ 0,1\right),}\) i funkcja \(\displaystyle{ f}\) jest dobrze określona.

Wykażemy, że funkcja \(\displaystyle{ f}\) jest podobieństwem.

Łatwo jest pokazać, że funkcja \(\displaystyle{ f}\) jest różnowartościowa. Wykażemy teraz, że funkcja \(\displaystyle{ f}\) jest 'na'.

DOWÓD TEGO FAKTU:    

Niech \(\displaystyle{ y \in \left[ 0,1\right)}\). Rozważmy \(\displaystyle{ x:=y \cdot \left( b-a\right)+a}\). Wtedy \(\displaystyle{ 0 \cdot \left( b-a\right) =0 \le y \cdot \left( b-a\right) <b-a}\), i po dodaniu liczby \(\displaystyle{ a}\) stronami, otrzymujemy

\(\displaystyle{ a \le x=y \cdot (b-a)+a<b-a+a=b}\), a więc \(\displaystyle{ x\in \left[ a,b\right)}\), i mamy:

\(\displaystyle{ f(x)= \frac{y \cdot \left( b-a\right) +a-a}{b-a}= \frac{y \cdot \left( b-a\right) }{b-a} =y,}\)

a więc element \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ f.}\) Z dowolności wyboru takiego elementu otrzymujemy, że funkcja \(\displaystyle{ f}\) jest 'na\(\displaystyle{ .\square }\)

Zatem funkcja \(\displaystyle{ f}\) jest bijekcją. Pokażemy, że jest monotoniczna.

Jeśli \(\displaystyle{ x_1, x_2\in \left[ a,b\right)}\), i \(\displaystyle{ x_1<x_2}\), to \(\displaystyle{ x_1-a<x_2-a}\), i ponieważ \(\displaystyle{ (b-a)>0}\), więc również \(\displaystyle{ \frac{x_1-a}{b-a} < \frac{x_2-a}{b-a}}\), czyli \(\displaystyle{ f(x_1) <f(x_2)}\), i funkcja \(\displaystyle{ f}\) jest monotoniczna.

Ponieważ funkcja \(\displaystyle{ f}\) jest bijekcją monotoniczną pomiędzy dwoma przedziałami, więc funkcja \(\displaystyle{ f}\) jest podobieństwem, i przedziały \(\displaystyle{ \left[ a,b\right) }\) oraz \(\displaystyle{ \left[ 0,1\right)}\) są podobne.

Przejdźmy do naszego problemu.

Aby wykazać, że zbiory \(\displaystyle{ \ZZ \times \left[ a,b\right)}\) oraz \(\displaystyle{ \RR}\) są podobne, rozważmy funkcję \(\displaystyle{ g:\ZZ \times \left[ a,b\right) \rightarrow \RR}\), zdefiniowaną jako:

\(\displaystyle{ g(n,x)=n+f(x) ,}\)

gdzie przypominam zawsze \(\displaystyle{ f(x) \in \left[ 0,1\right).}\)

Wykażemy, że funkcja \(\displaystyle{ g}\) jest podobieństwem.

Aby wykazać, że funkcja \(\displaystyle{ g}\) jest różnowartościowa, to weźmy dwie dowolne różne pary \(\displaystyle{ (n_1, x_1); (n_2, x_2)\in\ZZ \times \left[ a,b\right).}\)

Jeśli \(\displaystyle{ n_1 \neq n_2}\), więc ponieważ naturalny porządek na zbiorze liczb całkowitych jest porządkiem liniowym, więc \(\displaystyle{ n_1<n_2 }\) lub \(\displaystyle{ n_2<n_1}\).

Jeśli \(\displaystyle{ n_1<n_2}\), ponieważ tutaj elementy \(\displaystyle{ n_1, n_2}\) są liczbami całkowitymi, więc \(\displaystyle{ n_1+1 \le n_2}\), więc

\(\displaystyle{ g(n_1, x_1)=n_1+\underbrace{f(x_1)}_{\in\left[0,1 \right) }< n_1+1 \le n_2 \le n_2+f(x _{2} )= g(n_2, x_2),}\)

czyli \(\displaystyle{ g(n_1,x_1)< g(n_2, x_2)}\), a więc \(\displaystyle{ g(n_1, x_1) \neq g(n_2, x_2).}\)

Jeśli \(\displaystyle{ n_1>n_2}\), to analogicznie pokazujemy, że \(\displaystyle{ g(n_1, x_1)> g(n_2, x_2)}\), a więc \(\displaystyle{ g(n_1, x_1) \neq g(n_2, x_2).}\)

Jeśli \(\displaystyle{ n_1=n_2}\), to oznaczmy tą wartość jako \(\displaystyle{ n}\).
Wtedy musi być, gdyż wybrane dwie pary są różne, więc musi być: \(\displaystyle{ x_1 \neq x_2.}\) Wtedy:

\(\displaystyle{ g(n_1, x_1)= n+f(x_1)}\), oraz \(\displaystyle{ g(n_2, x_2)= n+f(x_2).}\) Ponieważ \(\displaystyle{ x_1 \neq x_2}\), a funkcja \(\displaystyle{ f}\) jest podobieństwem, więc funkcja \(\displaystyle{ f}\) jest różnowartościowa, więc również \(\displaystyle{ f(x_1) \neq f(x_2)}\) , więc wtedy:

\(\displaystyle{ g(n_2, x_2) = n+f(x_2) \neq n+ f(x_1)= g(n_1, x_1)}\),

(łatwo to nie wprost udowodnić), czyli

\(\displaystyle{ g(n_1, x_1) \neq g(n_2, x_2)}\) , i funkcja \(\displaystyle{ g}\) jest różnowartościowa.


Nim udowodnimy, że funkcja \(\displaystyle{ g}\) jest 'na', przypomnijmy dwa proste fakty:

Jeśli mamy liczbę rzeczywistą \(\displaystyle{ y \ge 0}\), to można ją jednoznacznie przedstawić w postaci \(\displaystyle{ y=n+a}\), gdzie \(\displaystyle{ n}\) jest liczbą naturalną, a \(\displaystyle{ a}\) jest liczbą z przedziału \(\displaystyle{ \left[ 0,1\right)}\)- jest to prosty fakt.

A jeśli \(\displaystyle{ y<0}\) jest liczbą rzeczywistą ujemną, to liczbę \(\displaystyle{ y}\)- można ją przedstawić w postaci \(\displaystyle{ y=n-a}\), gdzie \(\displaystyle{ n}\) jest liczbą całkowitą ujemna bądź zerem, a \(\displaystyle{ a}\) jest liczbą z przedziału \(\displaystyle{ \left[ 0,1\right)}\)- jest to podobnie prosty fakt.

Wykażemy teraz, że funkcja \(\displaystyle{ g}\) jest 'na'. Niech \(\displaystyle{ y\in\RR.}\)

Rozważmy najpierw przypadek gdy: \(\displaystyle{ y \ge 0}\).
Wtedy, na mocy pierwszego ze wspomnianych faktów, otrzymujemy, że istnieje (jedyna) para \(\displaystyle{ (n,a) \in \NN \times\left[ 0,1\right)}\), taka, że \(\displaystyle{ y=n+a}\). Wtedy \(\displaystyle{ n\in \ZZ}\), \(\displaystyle{ a \in\left[ 0,1\right)}\). Ponieważ funkcja \(\displaystyle{ f}\) jest podobieństwem, więc jest 'na' zbiór \(\displaystyle{ \left[ 0,1\right)}\) , więc otrzymujemy, że \(\displaystyle{ a= f(x)}\), gdzie \(\displaystyle{ x\in\left[ a,b\right) }\). Wtedy

\(\displaystyle{ g(n,x)=n+f(x)=n+a=y}\),

a więc \(\displaystyle{ y=g(n,x)}\), czyli element \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ g.}\)

Jeśli \(\displaystyle{ y<0}\), to na mocy drugiego ze wspomnianych faktów, otrzymujemy, że istnieje para \(\displaystyle{ (n,a) \in \left( \ZZ_- \cup \left\{ 0\right\}\right) \times \left[ 0,1\right)}\), taka, że \(\displaystyle{ y=n-a.}\)

Jeśli \(\displaystyle{ a=0}\), to \(\displaystyle{ y=n}\), wtedy \(\displaystyle{ n\in\ZZ, a\in \left[ a,b\right)}\), i wtedy:

\(\displaystyle{ g(n,a)= n+f(a)= n+ \frac{a-a}{b-a}=n=y}\), a więc element \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ g.}\)

Jeśli \(\displaystyle{ a \neq 0,}\) to \(\displaystyle{ a\in\left( 0,1\right)}\), wtedy \(\displaystyle{ (1-a)\in \left( 0,1\right), n\in\ZZ}\), więc również \(\displaystyle{ (n-1)\in\ZZ}\). Mamy \(\displaystyle{ (1-a)\in \left[ 0,1\right)}\), a funkcja \(\displaystyle{ f}\) jest podobieństwem, więc funkcja \(\displaystyle{ f}\) jest 'na', więc otrzymujemy, że \(\displaystyle{ 1-a=f(x)}\), gdzie \(\displaystyle{ x\in \left[ a,b\right)}\), mamy \(\displaystyle{ (n-1)\in\ZZ}\), i wtedy:

\(\displaystyle{ g(n-1,x)=n-1+f(x) =n-1+1-a=n-a=y}\), a więc również element \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ g}\).

A więc funkcja \(\displaystyle{ g}\) jest 'na', i \(\displaystyle{ g}\) jest bijekcją.

Wykażemy teraz, że funkcja \(\displaystyle{ g}\) jest monotoniczna

Weźmy pary \(\displaystyle{ (n_1, x_1); (n_2,x_2)\in\ZZ \times \left[ a,b\right)}\), takie, że \(\displaystyle{ (n_1, x_1)<_l (n_2, x_2)}\). Rozważmy dwa przypadki:

Jeśli \(\displaystyle{ n_1 \neq n_2}\).
Wtedy, z definicji porządku leksykograficznego, musi być: \(\displaystyle{ n_1<n_2.}\) Ponieważ elementy \(\displaystyle{ n_1, n_2}\) są liczbami całkowitymi, więc \(\displaystyle{ n_1+1 \le n_2}\), i wtedy:

\(\displaystyle{ g(n_1, x_1)=n_1+\underbrace {f(x_1)}_{ \in \left[ 0,1\right) }<n_1+1 \le n_2+f(x_2)= g(n_2, x_2)}\), czyli \(\displaystyle{ g(n_1, x_1) < g(n_2, x_2).}\)

Jeśli \(\displaystyle{ n_1=n_2}\), to oznaczmy tą liczbę całkowitą jako \(\displaystyle{ n}\).
Wtedy, na podstawie definicji porządku leksykograficznego: \(\displaystyle{ x_1<x_2}\). Ponieważ funkcja \(\displaystyle{ f}\) jest podobieństwem, więc jest monotoniczna, więc otrzymujemy nierówność \(\displaystyle{ f(x_1) \le f(x_2)}\), i w efekcie otrzymujemy :

\(\displaystyle{ g(n_1, x_1)=n+f(x_1) \le n+f(x_2)= g(n_2, x_2)}\),

co należało pokazać. Wobec czego funkcja \(\displaystyle{ g}\) jest monotoniczna.

Ponieważ funkcja \(\displaystyle{ g}\) jest bijekcją monotoniczną pomiędzy \(\displaystyle{ \ZZ \times \left[ a,b\right)}\), zbiorem liniowo uporządkowanym, a \(\displaystyle{ \RR}\)- zbiorem liniowo uporządkowanym, więc \(\displaystyle{ g}\) jest podobieństwem, i zbiór \(\displaystyle{ \ZZ \times\left[ a,b\right)}\) jest podobny do zbioru \(\displaystyle{ \RR.\square }\)


I ostatni problem.

Rozważmy przedział \(\displaystyle{ \left[ a,b\right)\subset \RR}\), gdzie \(\displaystyle{ a<b.}\)

Rozważmy zbiór \(\displaystyle{ \NN \times \left[ a,b\right)}\) z porządkiem leksykograficznym. Wykażemy, że taki zbiór jest podobny do \(\displaystyle{ \RR_+ \cup \left\{ 0\right\} .}\)

Nim to udowodnimy, podajmy pewien lemat.

LEMAT: Jeśli mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right) ; \left( Y, \le _Y\right)}\)- zbiory liniowo uporządkowane podobne (\(\displaystyle{ X \approx Y}\)), oraz gdy mamy zbiór \(\displaystyle{ A\subset X}\), to dla każdego podobieństwa \(\displaystyle{ f:X \rightarrow Y}\): zbiór \(\displaystyle{ A}\) jest podobny do jego obrazu przez to podobieństwo, tzn. \(\displaystyle{ A \approx \stackrel { \rightarrow }{f} \left( A\right).}\)

DOWÓD TEGO FAKTU:    

Niech \(\displaystyle{ f:X \rightarrow Y}\) będzie dowolnym podobieństwem. Wykażemy, że zbiór \(\displaystyle{ A}\) jest podobny do jego obrazu \(\displaystyle{ \stackrel { \rightarrow }{f} (A)}\).

Funkcja \(\displaystyle{ f}\), jako podobieństwo, jest bijekcją. Wtedy ta funkcja, obcięta do zbioru \(\displaystyle{ A,}\) jest również bijekcją z \(\displaystyle{ A}\) w \(\displaystyle{ \stackrel { \rightarrow }{f} (A)}\), łatwo to można sprawdzić. Pozostaje pokazać monotoniczność.

Jeśli \(\displaystyle{ x,y\in A}\), i \(\displaystyle{ x \ \left( \le _X \right) _{|A} \ y}\) (przez \(\displaystyle{ \left( \le _X\right) _{|A}}\) oznaczam porządek \(\displaystyle{ \le _X}\) zawężony do zbioru \(\displaystyle{ A}\), i w podobny sposób będę oznaczał porządek na obrazie tego zbioru).

Wtedy \(\displaystyle{ x \le _X y.}\) Ponieważ funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest podobieństwem, więc funkcja \(\displaystyle{ f}\) jest monotoniczna, więc \(\displaystyle{ f(x) \le _{Y} f(y)}\). Ponieważ \(\displaystyle{ x,y\in A}\), więc \(\displaystyle{ f(x), f(y)\in \stackrel { \rightarrow }{f} (A)}\), i dalej:

\(\displaystyle{ \left( f _{|A} \right)(x)=f(x) \ \left( \le _Y\right) _{|\stackrel { \rightarrow }{f} \left( A\right) } \ f(y)=\left( f _{|A} \right) (y)}\),

i funkcja \(\displaystyle{ f _{|A}}\) jest monotoniczna.

Ponieważ funkcja \(\displaystyle{ f_{|A}}\) jest bijekcją monotoniczną pomiędzy zbiorem \(\displaystyle{ ( \ A, (\le _X ) _{|A} \ )}\), jako podzbiorem zbioru liniowo uporządkowanego \(\displaystyle{ X}\)) zbiorem liniowo uporządkowanym, a zbiorem \(\displaystyle{ \left( \ \stackrel {\rightarrow }{f} \left( A\right) \subset Y, \left( \le _Y\right) _{| \stackrel { \rightarrow } {f} (A) } \ \right), }\) zbiorem liniowo uporządkowanym, więc funkcja \(\displaystyle{ f_{|A}}\) jest podobieństwem, i \(\displaystyle{ A \approx \stackrel { \rightarrow }{f}(A) .\square }\)

Przejdźmy do naszego zadania.

Dowód:

Zbiór \(\displaystyle{ \ZZ \times \left[ a,b \right)}\) jest zbiorem liniowo uporządkowanym, zbiór \(\displaystyle{ \RR}\) jest zbiorem liniowo uporządkowanym. Funkcja \(\displaystyle{ g:\ZZ \times \left[ a,b\right) \rightarrow \RR}\), z poprzedniego zadania, jest podobieństwem, i te dwa zbiory są podobne. Ponieważ \(\displaystyle{ \NN\subset \ZZ}\), więc \(\displaystyle{ \NN \times \left[ a,b\right) \subset \ZZ \times \left[ a,b\right)}\), i funkcja \(\displaystyle{ g}\) jest podobieństwem. Stosując zatem powyższy lemat, otrzymujemy, że zbiór \(\displaystyle{ \NN \times \left[ a,b\right) }\) jest podobny do obrazu tego zbioru przez to podobieństwo \(\displaystyle{ g.}\)

Wykażemy teraz, że ten obraz jest równy zbiorowi liczb rzeczywistych nieujemnych.

Jeśli \(\displaystyle{ (n,x)\in \NN \times \left[ a,b\right) }\), to \(\displaystyle{ g(n,x)=\underbrace{n}_{ \in \NN} + \underbrace{f(x)}_{ \in \left[ 0,1\right) } \ge 0}\),

a więc \(\displaystyle{ g(n,x) \ge 0}\), i \(\displaystyle{ \stackrel{ \rightarrow }{g} (\NN \times \left[ a,b\right) )\subset \RR_+ \cup \left\{ 0\right\} .}\)

Aby pokazać inkluzję w drugą stronę, to niech \(\displaystyle{ y \ge 0}\).
Wtedy, na mocy jednego z faktów powyżej o przedstawieniu liczby rzeczywistej nieujemnej w postaci sumy liczby naturalnej i liczby z przedziału \(\displaystyle{ \left[ 0,1\right],}\) otrzymujemy, że istnieje jedyna para \(\displaystyle{ (n,a)\in\NN \times \left[ 0,1\right)}\), taka, że \(\displaystyle{ y=n+a}\). Wtedy \(\displaystyle{ a\in\left[ 0,1\right) }\), a funkcja \(\displaystyle{ f}\) jest podobieństwem, więc \(\displaystyle{ f}\) jest funkcją 'na', więc \(\displaystyle{ a=f(x)}\), gdzie \(\displaystyle{ x\in\left[ a,b\right) }\), Mamy \(\displaystyle{ n\in\NN}\). I wtedy: \(\displaystyle{ g(n,x)=n+f(x)=n+a =y}\), czyli \(\displaystyle{ y=g(n,x)}\), gdzie \(\displaystyle{ n\in\NN, x\in \left[ a,b\right)}\), a zatem \(\displaystyle{ y=g(n,x)\in \stackrel { \rightarrow }{g} \left( \NN \times \left[ a,b\right) \ \right)}\), a zatem \(\displaystyle{ \stackrel { \rightarrow }{g} (\NN \times \left[ a,b\right) \ ) =\RR_+ \cup \left\{ 0\right\} . }\)

Ponieważ zbiór \(\displaystyle{ \NN \times \left[ a,b\right)}\) jest podobny do jego obrazu przez funkcję \(\displaystyle{ g}\), więc zbiór \(\displaystyle{ \NN \times \left[ a,b\right)}\) jest podobny do zbioru liczb rzeczywistych nieujemnych- \(\displaystyle{ \NN \times \left[ a,b\right) \approx \RR_+ \cup \left\{ 0\right\}. \square }\)

Dodano po 1 roku 1 miesiącu 14 dniach 23 godzinach 49 minutach 20 sekundach:
Udowodniłem wczoraj, że jak mamy trzy niepuste zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right)}\); \(\displaystyle{ \left( Y, \le _Y\right)}\) i \(\displaystyle{ \left( Z, \le _Z\right),}\) przy czym zbiór \(\displaystyle{ X}\) jest podobny do zbioru \(\displaystyle{ \left( \NN, \le \right)}\) , a zbiory \(\displaystyle{ Y}\) i \(\displaystyle{ Z}\) są niepuste i są skończone, to zbiór\(\displaystyle{ X \times \left( Y \times Z\right)}\) z porządkiem leksykograficznym jest podobny do zbioru \(\displaystyle{ \left( \NN, \le\right), }\) i jest to zbiór dobrze uporządkowany. Przedstawię też tutaj dowód (niedawno przeprowadzony przeze mnie) faktu mówiącego, że jeżeli mamy dowolną rodzinę \(\displaystyle{ \mathbb{B}}\) zbiorów jednoelementowych, to uogólniony iloczyn kartezjański \(\displaystyle{ \prod\mathbb{B}}\) jest również jednoelementowy. Przedstawię teraz dowody tych ciekawych faktów.


Rozważmy zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le _X\right) }\) podobny do zbioru \(\displaystyle{ \left( \NN, \le\right) }\), oraz rozważmy dwa niepuste skończone zbiory liniowo uporządkowane \(\displaystyle{ \left( Y, \le _Y\right)}\) i \(\displaystyle{ \left( Z, \le _Z\right)}\). Wykażemy, że zbiór \(\displaystyle{ X \times \left( Y \times Z\right)}\), z porządkiem leksykograficznym, jest podobny do zbioru \(\displaystyle{ \left( \NN, \le\right) }\), i jest to zbiór dobrze uporządkowany.

PROSTY DOWÓD TEGO FAKTU:

Ponieważ zbiory \(\displaystyle{ Y}\) i \(\displaystyle{ Z}\) są skończone i niepuste, to przyjmijmy, że:
\(\displaystyle{ \left| Y\right| =n}\), gdzie \(\displaystyle{ n \in \NN}\), \(\displaystyle{ n \ge 1}\); oraz \(\displaystyle{ \left| Z\right| =m}\), gdzie \(\displaystyle{ m \in \NN, m \ge 1}\).

Wtedy \(\displaystyle{ \left| Y \times Z\right| = n \cdot m \in \NN}\), i \(\displaystyle{ n \cdot m \ge 1 \cdot m=m \ge 1}\).
Zbiór \(\displaystyle{ Y \times Z}\) z porządkiem leksykograficznym jest zbiorem liniowo uporządkowanym, (bo zbiory \(\displaystyle{ Y}\) i \(\displaystyle{ Z}\) są liniowo uporządkowane). Mamy \(\displaystyle{ \left\{ 1,2,\ldots, n \cdot m\right\} \sim \left( n \cdot m\right) \sim Y \times Z}\), i zbiór \(\displaystyle{ \left\{ 1,2,\ldots, n \cdot m\right\}}\) jest oczywiście liniowo uporządkowany przez naturalny porządek na nim, a zatem (dwa zbiory liniowo uporządkowane skończone i równoliczne są podobne), w związku z czym zbiór \(\displaystyle{ Y \times Z}\) jest podobny do zbioru \(\displaystyle{ \left\{ 1,2,\ldots, n \cdot m\right\}}\) .

Ponieważ zbiór \(\displaystyle{ \left( X, \le _X\right) }\) jest podobny do zbioru \(\displaystyle{ \left( \NN, \le\right) }\) więc:

\(\displaystyle{ X \times \left( Y \times Z\right) \approx \NN \times \left\{ 1,2, \ldots, n \cdot m\right\}. }\)

Niech:

\(\displaystyle{ Y=\left\{ k \in \NN: \ k< n \cdot m\right\}.}\)

Wtedy oczywiście \(\displaystyle{ Y\sim \left\{ 1,2,\ldots, n \cdot m\right\}}\) , a zatem \(\displaystyle{ \left\{ 1,2, \ldots, n \cdot m\right\} \approx Y.}\)

A zatem \(\displaystyle{ X \times \left( Y \times Z\right) \approx \NN \times \left\{ 1,2,\ldots, n \cdot m\right\} \approx \NN \times Y}\),

gdzie \(\displaystyle{ Y}\) jest zbiorem wszystkich liczb naturalnych mniejszych niż liczba naturalna \(\displaystyle{ n \cdot m}\), i \(\displaystyle{ n \cdot m \ge 1}\), a zatem, na mocy faktu udowodnionego w poście powyżej, jest to zbiór podobny do zbioru \(\displaystyle{ \left( \NN, \le\right) }\), a zatem (z przechodniości podobieństwa): \(\displaystyle{ X \times \left( Y \times Z\right) \approx \NN.}\)

Ponieważ zbiór liczb naturalnych ze zwykłym porządkiem jest dobrze uporządkowany, więc również zbiór \(\displaystyle{ X \times \left( Y \times Z\right)}\), jako zbiór do niego podobny, jest również dobrze uporządkowany.\(\displaystyle{ \square}\)

Udowodnijmy jeszcze jeden fakt:

Niech \(\displaystyle{ \mathbb{B}}\) będzie dowolną rodziną zbiorów jednoelementowych, tzn. jeśli \(\displaystyle{ A \in \mathbb{B}}\), to zbiór \(\displaystyle{ A}\) jest jednoelementowy.
Wykażemy, że wtedy również produkt uogólniony \(\displaystyle{ \prod\mathbb{B}}\) jest jednoelementowy.

DOWÓD TEGO FAKTU::    

Zauważmy, że jeśli rodzina \(\displaystyle{ \mathbb{B}}\) jest pusta, to \(\displaystyle{ \prod\mathbb{B}= \left\{ \hbox{ FUNKCJA PUSTA}\right\}\sim 1}\).

Załóżmy więc dalej, że rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta.

Jeśli \(\displaystyle{ A \in \mathbb{B}}\), to zbiór \(\displaystyle{ A}\) jest jednoelementowy, tzn. \(\displaystyle{ A= \left\{ a_A\right\}}\), dla pewnego elementu \(\displaystyle{ a _{A}}\) (i oczywiście taki element jest jedyny, oznaczmy więc go jako \(\displaystyle{ a_A}\) ) . Niech:

\(\displaystyle{ f= \left\{ \left( A, a _{A} \right)\Bigl| \ \ A \in \mathbb{B} \right\}.}\)

Wtedy \(\displaystyle{ f: \mathbb{B} \rightarrow \bigcup\mathbb{B}}\), i mamy \(\displaystyle{ f\left( A\right) = a_A \in A}\), dla każdego zbioru \(\displaystyle{ A \in \mathbb{B}}\), a zatem \(\displaystyle{ f \in \prod\mathbb{B}.}\)

Niech \(\displaystyle{ g \in \prod\mathbb{B}.}\) Wtedy \(\displaystyle{ g: \mathbb{B} \rightarrow \bigcup\mathbb{B}}\); pokażemy, że \(\displaystyle{ g=f}\).
Ponieważ funkcje te mają tą samą dziedzinę i maja tą samą przeciwdziedzinę, więc wystarczy pokazać, że funkcje te na każdym zbiorze \(\displaystyle{ A \in \mathbb{B}}\) przyjmują te same wartości. Niech więc \(\displaystyle{ A \in \mathbb{B}}\). Ponieważ, z definicji produktu uogólnionego: \(\displaystyle{ g\left( A \right) \in A}\), a \(\displaystyle{ A=\left\{ a_A\right\}}\), więc \(\displaystyle{ g(A) =a_A= f(A)}\), a zatem \(\displaystyle{ g=f}\),

i produkt \(\displaystyle{ \prod\mathbb{B} \sim 1}\) jest jednoelementowy\(\displaystyle{ .\square}\)

[Jakub Gurak]

Udowodniłem przedwczoraj, że jeśli mamy trzy zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right) }\); \(\displaystyle{ \left( Y, \le _Y\right) }\) i \(\displaystyle{ \left( Z, \le _Z\right) }\), i gdy na kostce \(\displaystyle{ X \times \left( Y \times Z\right)}\) rozważymy porządek leksykograficzny, i jeśli mamy jeszcze trzy mniejsze zbiory \(\displaystyle{ X' \subset X, Y' \subset Y}\) i \(\displaystyle{ Z' \subset Z}\) mające elementy największe równe odpowiednio \(\displaystyle{ x, y}\) i \(\displaystyle{ z}\), to trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem największym w zbiorze \(\displaystyle{ X' \times \left( Y' \times Z'\right). }\)
Udowodniłem też wczoraj analogiczny fakt dla elementów najmniejszych.
Przestawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ \left( X, \le _X\right) }\);\(\displaystyle{ \left( Y, \le _Y\right) }\); \(\displaystyle{ \left( Z, \le _Z\right) }\) będą zbiorami liniowo uporządkowanymi.
Rozważmy kostkę \(\displaystyle{ X \times \left( Y \times Z\right)}\) z porządkiem leksykograficznym \(\displaystyle{ \le _{X\otimes \left( Y \otimes Z\right) } .}\)
Rozważmy trzy zbiory \(\displaystyle{ X' \subset X, Y' \subset Y}\) i \(\displaystyle{ Z' \subset Z}\) mające elementy największe \(\displaystyle{ x \in X'}\), \(\displaystyle{ y \in Y'}\) i \(\displaystyle{ z \in Z'.}\)
Wykażemy, że trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem największym kostki \(\displaystyle{ X' \times \left( Y' \times Z'\right) .}\)

DOWÓD TEGO FAKTU:

Mamy \(\displaystyle{ x \in X', y \in Y'}\) i \(\displaystyle{ z \in Z'}\) , a zatem \(\displaystyle{ \left( x,y,z\right) \in X' \times Y' \times Z'. }\)

Niech \(\displaystyle{ \left( x',y',z'\right) \in X' \times Y' \times Z'}\).

Wtedy \(\displaystyle{ x' \in X' , y' \in Y'}\) i \(\displaystyle{ z' \in Z'.}\)

Ponieważ element \(\displaystyle{ x}\) jest największy w \(\displaystyle{ X'}\), więc \(\displaystyle{ x \ge_X x'.}\)

W podobny sposób otrzymujemy (na mocy naszych założeń), że: \(\displaystyle{ y \ge _Y y'}\) i \(\displaystyle{ z \ge_Z z'.}\)

Jeśli \(\displaystyle{ x \neq x'}\), to \(\displaystyle{ x> x'}\), a zatem, z definicji porządku leksykograficznego \(\displaystyle{ \le _{X \otimes \left( Y\otimes Z\right) },}\) otrzymujemy:

\(\displaystyle{ \left( x,y,z\right) > \left( x', y', z'\right).}\)

Jeśli \(\displaystyle{ x=x'}\), to:

jeśli \(\displaystyle{ y \neq y',}\) to \(\displaystyle{ y> y'.}\) Wtedy, z definicji porządku leksykograficznego: \(\displaystyle{ \left( y,z\right) > \left( y', z'\right)}\) , i dalej:

\(\displaystyle{ \left( x,y,z\right) = \left( x, \left( y,z\right) \right) > \left( x, \left( y',z'\right) \right) =\left( x', \left( y',z'\right) \right) = \left( x', y',z'\right) .}\)

Jeśli \(\displaystyle{ y=y'}\), to:

jeśli \(\displaystyle{ z \neq z'}\), to \(\displaystyle{ z>_Z z'.}\) A wtedy:

\(\displaystyle{ \left( x,y,z\right) = \left( x',y', z \right)> \left( x', y', z'\right).}\)

Jeśli \(\displaystyle{ z=z'}\), to niewątpliwie (ze zwrotności porządku) :\(\displaystyle{ }\)

\(\displaystyle{ \left( x,y,z\right) = \left( x', y' ,z'\right) \ge \left( x', y', z'\right).}\)

A zatem trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem największym zbioru \(\displaystyle{ X' \times \left( Y' \times Z'\right) .\square}\)


Wykażemy analogiczny fakt dla elementów najmniejszych.

Nim to zrobimy, przypomnijmy, że jak mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ \left( A, \le _A\right) }\) i \(\displaystyle{ \left( B, \le _B\right) }\), i gdy rozważymy produkt \(\displaystyle{ A \times B}\) z porządkiem leksykograficznym, i gdy rozważymy porządek do niego odwrotny, to mamy prawo:

\(\displaystyle{ \left( A\otimes B\right) ^{-1} = A ^{-1} \otimes B ^{-1},}\)

porządek odwrotny do leksykograficznego jest porządkiem leksykograficznym porządków odwrotnych- jest to dość podstawowy fakt.

Przejdźmy do naszego zadania:

Rozważmy trzy zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right) ; \left( Y, \le _Y\right)}\) i \(\displaystyle{ \left( Z, \le_Z\right) .}\)
Rozważmy kostkę \(\displaystyle{ X \times \left( Y \times Z\right)}\) z porządkiem leksykograficznym \(\displaystyle{ \le _{X\otimes \left( Y\otimes Z\right) } .}\)
Rozważmy trzy zbiory: zbiór \(\displaystyle{ X' \subset X}\) mający element najmniejszy \(\displaystyle{ x \in X'}\), zbiór \(\displaystyle{ Y' \subset Y}\) mający element najmniejszy \(\displaystyle{ y \in Y'}\) oraz zbiór \(\displaystyle{ Z' \subset Z}\) mający element najmniejszy \(\displaystyle{ z \in Z'.}\)
Wykażemy, że trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem najmniejszym zbioru \(\displaystyle{ X' \times Y' \times Z'.}\)

DOWÓD TEGO FAKTU:

Rozważmy porządki odwrotne: \(\displaystyle{ \left( X, \le _{X} ^{-1} \right) ; \left( Y, \le _{Y} ^{-1}\right)}\) i \(\displaystyle{ \left( Z, \le _{Z} ^{-1}\right) }\) -zbiory liniowo uporządkowane.

Wtedy element \(\displaystyle{ x}\) jest największy w \(\displaystyle{ X',}\) względem \(\displaystyle{ \le _X ^{-1}}\), i \(\displaystyle{ X' \subset X}\);
również element \(\displaystyle{ y}\) jest największy w \(\displaystyle{ Y',}\) względem \(\displaystyle{ \le _Y ^{-1},}\) i \(\displaystyle{ Y' \subset Y}\);
oraz element \(\displaystyle{ z}\) jest największy w \(\displaystyle{ Z',}\) względem \(\displaystyle{ \le _Z ^{-1},}\) i \(\displaystyle{ Z' \subset Z.}\)

Możemy zatem zastosować powyżej udowodniony fakt, i dostać, że trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem największym zbioru \(\displaystyle{ X' \times \left( Y' \times Z' \right)}\) względem \(\displaystyle{ \le _{X ^{-1} \otimes \left( Y ^{-1} \otimes Z ^{-1} \right) }}\) .

A zatem ta trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem najmniejszym tego zbioru względem porządku do niego odwrotnego, czyli względem porządku :

\(\displaystyle{ \left( X ^{-1} \otimes \left( Y ^{-1} \otimes Z ^{-1} \right) \right) ^{-1} = \left( X ^{-1} \right) ^{-1} \otimes \left( Y ^{-1} \otimes Z ^{-1} \right) ^{-1} = X \otimes \left[ \left( Y ^{-1} \right) ^{-1} \otimes \left( Z ^{-1} \right) ^{-1} \right] = X\otimes \left( Y\otimes Z\right)}\);

czyli trójka \(\displaystyle{ \left( x,y,z\right)}\) jest elementem najmniejszym zbioru \(\displaystyle{ X' \times \left( Y' \times Z' \right)}\) względem porządku \(\displaystyle{ \le _{X\otimes \left( Y \otimes Z\right) }.\square}\)