Reszty zbioru liniowo uporządkowanego

[Jakub Gurak]

Udowodniłem wczoraj parę rzeczy związane z resztą w zbiorze liniowo uporządkowanym. Udowodniłem na przykład, że w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) para zbiorów tworzy przekrój Dedekinda, dokładnie wtedy, gdy drugi zbiór z tego przekroju jest niepustą i różną od całego zbioru \(\displaystyle{ X}\) resztą, a pierwszy zbiór z pary jest jego dopełnieniem. Udowodniłem też, że w zbiorze dobrze uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) każda niepusta reszta jest postaci \(\displaystyle{ \left[ x, \rightarrow \right)}\), dla pewnego \(\displaystyle{ x\in X.}\) Wskazałem też kontrprzykład mówiący, że w zbiorze dobrze uporządkowanym może istnieć niepusta i różna od całego zbioru \(\displaystyle{ X}\) reszta, która nie jest postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), dla żadnego \(\displaystyle{ x\in X}\). Udowodniłem też, że w zbiorze liniowo uporządkowanym, jak mamy dwie reszty, to jedna się zawiera w drugiej, i jeszcze\(\displaystyle{ }\) parę innych podstawowych faktów związanych z resztą. Przedstawię teraz dowody tych ciekawych faktów.

Przypomnę może najpierw definicję:

W zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) zbiór \(\displaystyle{ A\subset X}\) nazywamy resztą zbioru \(\displaystyle{ X}\), gdy dla dowolnego \(\displaystyle{ a\in A}\), dla dowolnego \(\displaystyle{ x\in X}\), takiego, że \(\displaystyle{ x>a}\), zachodzi \(\displaystyle{ x\in A}\).

(Czyli zbiór \(\displaystyle{ A}\) jest resztą, gdy z każdym swoim elementem zawiera także wszystkie elementy zbioru \(\displaystyle{ X}\), które są od niego większe).

Przypominam, w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) zbiory postaci \(\displaystyle{ \left( x, \rightarrow \right) =\left\{ y\in X: y>x\right\} }\), gdzie \(\displaystyle{ x\in X}\), są zawsze resztą. Podobnie zbiory postaci \(\displaystyle{ \left[ x, \rightarrow \right)=\left\{ y\in X: y \ge x \right\}}\) , gdzie \(\displaystyle{ x\in X}\), takie zbiory są zawsze resztą, również cały zbiór \(\displaystyle{ X}\), formalnie rzecz biorąc, jest resztą.

Jednak w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) nie każda istotna (różna od \(\displaystyle{ X}\)) i niepusta reszta jest postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), gdzie \(\displaystyle{ x\in X;}\) podobnie nie każda reszta jest postaci \(\displaystyle{ \left[ x, \rightarrow \right]}\)) , dla pewnego \(\displaystyle{ x\in X}\). Co więcej, w zbiorze liniowo uporządkowanym może istnieć niepusta i różna od całego zbioru \(\displaystyle{ X}\) reszta, która ani nie jest postaci \(\displaystyle{ \left( x, \rightarrow \right) }\),gdzie \(\displaystyle{ x\in X}\), ani nie jest postaci \(\displaystyle{ \left[ x, \rightarrow \right)}\), gdzie \(\displaystyle{ x\in X,}\) udowodniłem to ostatnio TUTAJ . Można tam też przeczytać, że w zbiorze liniowo uporządkowanym ciągłym \(\displaystyle{ \left( X, \le \right)}\) już tak nie jest- każda reszta jest postaci \(\displaystyle{ \left[ x, \rightarrow \right] }\), gdzie \(\displaystyle{ x\in X}\), albo postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), gdzie \(\displaystyle{ x\in X}\).

Przypominam przekrój Dedekinda w zbiorze liniowo uporządkowanym \(\displaystyle{ (X, \le) }\), to para jego podzbiorów, która 'tworzy' jego 'rozcięcie', dowolne rozcięcie zbioru \(\displaystyle{ X}\). Wtedy pierwszy zbiór pary nazywamy klasą dolną przekroju, drugi zbiór nazywamy klasą górną przekroju. Ścisła definicja chyba nie będzie nam potrzebna, za to przypominam charakteryzację przekrojów Dedekinda:

W zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) para podzbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda, dokładnie wtedy, gdy pierwszy zbiór \(\displaystyle{ A}\) jest niepustym i różnym od całego zbioru \(\displaystyle{ X}\) przedziałem początkowym, a drugi zbiór \(\displaystyle{ B}\) jest jego dopełnieniem do zbioru \(\displaystyle{ X}\), będziemy z tego korzystać.

Przypominam w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le \right) }\) zbiór \(\displaystyle{ A\subset X}\) jest przedziałem początkowym (wyrażę się teraz językiem potocznym, uproszczę sobie- gdyż definicja przedziału początkowego jest symetryczna względem definicji reszty), czyli gdy z każdym swoim elementem zawiera także wszystkie od niego mniejsze elementy zbioru \(\displaystyle{ X}\). (Czyli jest to zbiór od początku do pewnego momentu ).

Przypominam zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\) nazywamy zbiorem dobrze uporządkowanym, gdy każdy niepusty podzbiór zbioru \(\displaystyle{ X}\) ma element najmniejszy.

Przejdźmy zatem do naszych dowodów:

Udowodnijmy najpierw, że w zbiorze liniowo uporządkowanym dopełnienie przedziału początkowego jest resztą, i dopełnienie reszty jest przedziałem początkowym.

Dowód:

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem liniowo uporządkowanym, a \(\displaystyle{ A\subset X}\) przedziałem początkowym. Wykażemy, że \(\displaystyle{ A'=X \setminus A }\) jest resztą. W tym celu weźmy \(\displaystyle{ x\in A' , y\in X}\), takie, że \(\displaystyle{ y>x}\), i pokażmy, że \(\displaystyle{ y\in A'=X \setminus A.}\) Przypuśćmy nie wprost, że \(\displaystyle{ y\not\in X \setminus A}\), ponieważ \(\displaystyle{ y\in X}\), więc \(\displaystyle{ y\in A}\). Ponieważ \(\displaystyle{ x<y\in A}\), a \(\displaystyle{ A}\) jest przedziałem początkowym, więc również \(\displaystyle{ x\in A}\), a \(\displaystyle{ x\in A'=X \setminus A}\)-sprzeczność.

Przypuśćmy teraz, że zbiór \(\displaystyle{ A\subset X}\) jest resztą. Wykażemy, że \(\displaystyle{ A'=X \setminus A}\) jest przedziałem początkowym. W tym celu weźmy \(\displaystyle{ x\in A'}\), i weźmy \(\displaystyle{ y\in X}\), takie, ze \(\displaystyle{ y<x}\), i pokażmy, ze \(\displaystyle{ y\in A'}\). Przypuśćmy, że tak nie jest. wtedy \(\displaystyle{ y\not\in X \setminus A}\), ale \(\displaystyle{ y\in X}\), wiec musi \(\displaystyle{ y\in A}\). Ponieważ \(\displaystyle{ y\in A}\), \(\displaystyle{ y<x}\), a zbiór \(\displaystyle{ A}\) jest resztą, więc wnioskujemy, że \(\displaystyle{ x\in A}\), a \(\displaystyle{ x\in A'=X \setminus A}\)-sprzeczność. \(\displaystyle{ \square}\)

Wykażemy, teraz, że w zbiorze liniowo uporządkowanym, dla dwóch reszt, jedna się zawiera w drugiej.

W tym celu przypomnijmy, że jak mamy zbiór liniowo uporządkowany, to rodzina jego wszystkich przedziałów początkowych jest uporządkowana liniowo przez inkluzję, co oznacza, ze dla dwóch przedziałów początkowych jeden się zawiera w drugim, będziemy z tego korzystać.

Dowód:

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem liniowo uporządkowanym, a \(\displaystyle{ A_1,A_2\subset X}\) resztami. Wykażemy, ze \(\displaystyle{ A_1\subset A_2}\) lub \(\displaystyle{ A_2\subset A_1}\).

Rozważmy dopełnienia \(\displaystyle{ B_1=A'_1, B_2=A'_2.}\) Ponieważ dopełnienie reszty jest przedziałem początkowym, więc zbiory \(\displaystyle{ B_1,B_2}\) są przedziałami początkowymi. A zatem jeden z nich się zawiera w drugim, tzn. \(\displaystyle{ B_1\subset B_2}\) lub \(\displaystyle{ B_2\subset B_1.}\)
Jeśli \(\displaystyle{ B_1\subset B_2}\), to dla dopełnień: \(\displaystyle{ B'_1\supset B'_2}\), ponieważ \(\displaystyle{ B_1=A'_1, B_2=A'_2}\), więc \(\displaystyle{ A_1=\left( A'_1\right)'\supset \left( A'_2\right)'=A_2}\), więc \(\displaystyle{ A_1\supset A_2.}\) Drugi przypadek (\(\displaystyle{ B_2\subset B_1}\)) symetrycznie prowadzi do inkluzji: \(\displaystyle{ A_2\supset A_1.\square}\)

Wynika stąd, że suma dwóch reszt jest resztą- jest to po prostu dłuższa z tych dwóch reszt, podobnie przekrój dwóch reszt jest resztą- jest to po prostu krótsza z tych dwóch reszt.

Wykażemy teraz drugą charakteryzację przekrojów Dedekinda, tzn.

W zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) , para zbiorów \(\displaystyle{ (A,B)}\), gdzie \(\displaystyle{ A,B\subset X}\) są dowolnymi podzbiorami zbioru \(\displaystyle{ X}\), taka para zbiorów jest przekrojem Dedekinda, dokładnie wtedy, gdy drugi zbiór \(\displaystyle{ B}\) jest niepustą i różną od całego zbioru \(\displaystyle{ X}\) resztą, a \(\displaystyle{ A=B'}\) - pierwszy zbiór \(\displaystyle{ A}\) jest jego dopełnieniem.

Dowód:

Jeśli para zbiorów \(\displaystyle{ (A,B)}\) tworzy przekrój Dedekinda w \(\displaystyle{ X}\), to (zgodnie z charakteryzacją przekrojów Dedekinda) zbiór \(\displaystyle{ A}\) jest przedziałem pocżatkowym, niepustym, i różnym od calego zbioru \(\displaystyle{ X}\), a \(\displaystyle{ B=A'}\)- drugi zbiór \(\displaystyle{ B}\) jest jego dopełnieniem. Ponieważ \(\displaystyle{ A}\) jest przedziałem początkowym , to \(\displaystyle{ B=A' }\) jest resztą. Ponieważ \(\displaystyle{ A \neq X}\), to \(\displaystyle{ X\not\subset A}\) (i \(\displaystyle{ X \neq \emptyset}\) ), więc zaprzeczając definicji inkluzji otrzymujemy, że istnieje \(\displaystyle{ x\in X}\), takie, ze \(\displaystyle{ x\not\in A}\), wtedy \(\displaystyle{ x\in A'=X \setminus A}\), a więc \(\displaystyle{ B=A' \neq \left\{ \right\}. }\)Ponieważ \(\displaystyle{ A \neq \left\{ \right\}}\), to \(\displaystyle{ B=A' \neq X}\), i \(\displaystyle{ B'=\left( A' \right)'=A}\). Wszystkie warunki są więc spełnione, co kończy dowód jednej implikacji.

Załóżmy teraz, że dla pary zbiorów \(\displaystyle{ (A,B) }\) mamy: \(\displaystyle{ B}\) jest resztą niepustą i różną od \(\displaystyle{ X}\), i \(\displaystyle{ A=B'.}\) Ponieważ \(\displaystyle{ B}\) jest resztą, to \(\displaystyle{ A=B'}\) jest przedziałem początkowym. Ponieważ \(\displaystyle{ B \neq X}\), to \(\displaystyle{ A=B' \neq \left\{ \right\} }\)(uzasadniamy podobnie jak wcześniej, \(\displaystyle{ B \neq X}\), zatem \(\displaystyle{ X\not\subset B}\), (i \(\displaystyle{ X \neq \left\{ \right\} }\)), więc zaprzeczając definicji inkluzji otrzymujemy, że istnieje \(\displaystyle{ x\in X}\), taki, że \(\displaystyle{ x\not\in B}\), a wtedy \(\displaystyle{ x\in B'=X \setminus B}\)), a zatem \(\displaystyle{ A=B' \neq \left\{ \right\}}\). Ponieważ \(\displaystyle{ B \neq \left\{ \right\} ,}\) to \(\displaystyle{ A=B' \neq X.}\) I \(\displaystyle{ B=\left( B'\right)'=A'. }\)
Podsumowując: \(\displaystyle{ A}\) jest niepustym i różnym od całego zbioru \(\displaystyle{ X}\) przedziałem pocżątkowym, a \(\displaystyle{ B}\) jest jego dopełnieniem, a zatem, w myśl charakteryzacji przekrojów Dedekinda, para zbiorów \(\displaystyle{ (A,B)}\) tworzy przekrój Dedekinda. \(\displaystyle{ \square}\)

Wykażemy, jeszcze, że w zbiorze dobrze uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) każda niepusta reszta \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) jest postaci \(\displaystyle{ A=\left[ x, \rightarrow \right)=\left\{ y\in X: \ y \ge x\right\}}\) , dla pewnego \(\displaystyle{ x\in X.}\)

Dowód:

Ponieważ \(\displaystyle{ \left\{ \right\} \neq A\subset X}\)- \(\displaystyle{ A}\) jest niepustym podzbiorem \(\displaystyle{ X}\), a \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem dobrze uporządkowanym, więc zbiór \(\displaystyle{ A}\) ma element najmniejszy \(\displaystyle{ a\in A}\). Wtedy \(\displaystyle{ a\in X}\), i ja teraz stwierdzam, że \(\displaystyle{ A=\left[ a, \rightarrow \right).}\) Jednak musimy tą równość zbiorów udowodnić. Niech \(\displaystyle{ b\in A}\), wtedy \(\displaystyle{ b\in X}\), a \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ A}\), więc \(\displaystyle{ a \le b}\), a stad \(\displaystyle{ b\in \left[ a, \rightarrow \right).}\)
Niech teraz \(\displaystyle{ b\in \left[ a, \rightarrow \right)}\), wtedy \(\displaystyle{ b\in X, b \ge a}\). Ponieważ zbiór \(\displaystyle{ A}\) jest resztą, a \(\displaystyle{ a\in A}\), \(\displaystyle{ b\in X, b \ge a}\), więc wnioskujemy, że \(\displaystyle{ b\in A}\). Tak więc \(\displaystyle{ A=\left[ a, \rightarrow \right] , a\in X.\square}\)

Na koniec pokażemy, że w zbiorze dobrze uporządkowanym może istnieć niepusta i rózna od calego zbioru \(\displaystyle{ X}\) reszta, która nie jest postaci \(\displaystyle{ \left(x, \rightarrow \right),}\) dla żadnego \(\displaystyle{ x\in X}\).

Dowód:

Rozwzażmy zbiór liczb naturalnych ze zwykłym porządkiem (dobrym), oraz jeden element \(\displaystyle{ T}\) spoza \(\displaystyle{ \NN}\)- \(\displaystyle{ T\not\in\NN}\). Rozważmy zbiór \(\displaystyle{ \NN \cup \left\{ T\right\} }\), z porządkiem \(\displaystyle{ \le _{X}:= \le \cup \left( X\times \left\{ T\right\} \right)}\), czyli rozszerzamy zbiór liczb naturalnych dodając jeden element \(\displaystyle{ T}\) jako największy. Ponieważ \(\displaystyle{ \left( \NN, \le\right) }\) jest zbiorem dobrze uporządkowanym, to po takiej operacji otrzymamy dalej zbiór dobrze uporządkowany, a więc \(\displaystyle{ \left( X, \le _X\right) }\) jest zbiorem dobrze uporządkowanym. Rozważmy \(\displaystyle{ \left\{ T\right\}}\). Taki zbiór jest resztą. W tym celu nalezy pokazać, że jeśli \(\displaystyle{ x\in \left\{ T\right\}, y\in X,}\) jest takie, że \(\displaystyle{ x \le _X y}\), to \(\displaystyle{ y\in\left\{ T\right\}}\). Ale wtedy \(\displaystyle{ x=T}\), \(\displaystyle{ y \ge_X T}\), a \(\displaystyle{ T}\) jest największy tutaj, więc \(\displaystyle{ y=T\in \left\{ T\right\}.}\) A wiec zbiór \(\displaystyle{ \left\{ T\right\}}\) jest resztą. Teraz nalezy pokazać, ze nie jest on postaci \(\displaystyle{ \left( x, \rightarrow \right)}\), dla żadnego \(\displaystyle{ x\in X.}\) Niewątpliwie \(\displaystyle{ \left\{ T\right\} \neq \left( T, \rightarrow \right) =\left\{ \right\}.}\) Czyli reszta nie jest tej postaci. Jeśli \(\displaystyle{ x\in X=\NN \cup\left\{ T\right\} }\), i \(\displaystyle{ x \neq T}\) , to \(\displaystyle{ x\in \NN}\), wtedy \(\displaystyle{ (x+1)\in X}\), i \(\displaystyle{ x+1>x}\), a ponieważ porządek \(\displaystyle{ \le _X}\) jest rozszerzeniem zwyklego \(\displaystyle{ \le}\) na \(\displaystyle{ \NN}\), to \(\displaystyle{ x+1>_X x}\), a stad \(\displaystyle{ (x+1)\in \left( x, \rightarrow \right)}\), a \(\displaystyle{ (x+1)\not\in \left\{ T\right\} }\) (bo \(\displaystyle{ x+1\in\NN}\), a \(\displaystyle{ T\not\in \NN}\)) , tak więc \(\displaystyle{ \left( x, \rightarrow \right) \neq \left\{ T\right\}}\) , a więc reszta \(\displaystyle{ \left\{ T\right\}}\) nie jest tej postaci. \(\displaystyle{ \square }\)

[Jakub Gurak]

Udowodniłem wczoraj, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) mamy niepustą rodzinę reszt w \(\displaystyle{ X}\), to jej suma jest resztą. Wynika stąd, że jeśli \(\displaystyle{ \mathbb{A}}\) jest rodziną wszystkich reszt w \(\displaystyle{ X}\) uporządkowaną inkluzją, to jeśli \(\displaystyle{ \left\{ \right\} \neq \mathbb{B} \subset \mathbb{A}}\) jest niepustym podzbiorem \(\displaystyle{ \mathbb{A}}\), to ma on supremum, suma rodziny reszt \(\displaystyle{ \mathbb{B} }\) jest resztą, i jest to supremum rodziny reszt. Udowodniłem też wczoraj podobnie, że w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X , \le\right) }\), jeśli \(\displaystyle{ \mathbb{B} }\) jest niepustą rodziną reszt w \(\displaystyle{ X}\), to jej przekrój jest resztą. Wynika stąd, że jeśli \(\displaystyle{ \mathbb{A}}\) jest rodziną wszystkich reszt w \(\displaystyle{ X}\) uporządkowaną inkluzją, to jeśli \(\displaystyle{ \left\{ \right\} \neq \mathbb{B} \subset \mathbb{A} }\) jest niepustym podzbiorem, to ma on infimum- przekrój niepustej rodziny reszt \(\displaystyle{ \mathbb{B} }\) jest resztą, i jest to infimum rodziny reszt. Przedstawię teraz dowody tych ciekawych faktów.

Zacznijmy od prostszego spostrzeżenia, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) mamy \(\displaystyle{ n}\) reszt \(\displaystyle{ A_1,A_2,\ldots,A_n\subset X, n=1,2,\ldots}\), to suma \(\displaystyle{ A_1 \cup A_2 \cup \ldots \cup A_n}\) jest resztą, i przekrój \(\displaystyle{ A_1 \cap A_2 \cap \ldots \cap A_n}\) jest resztą.

Dowód:

Wykażmy najpierw, że rodzina \(\displaystyle{ \left\{ A_1,A_2,\ldots,A_n\right\}}\) jest łańcuchem względem inkluzji. Niech \(\displaystyle{ i,j \in \left\{ 1,2\ldots, n \right\}}\),i \(\displaystyle{ i \neq j}\), i popatrzmy na zbiory \(\displaystyle{ A_i, A_j}\)- są to reszty. Ponieważ dla dwóch reszt jedna się zawiera w drugiej, to \(\displaystyle{ A_i \subset A_j}\) lub \(\displaystyle{ A_j\subset A_i}\). A więc rodzina \(\displaystyle{ \left\{ A_1,A_2,\ldots, A_n\right\}}\) jest łańcuchem względem inkluzji. Ponieważ jest to skończony niepusty (\(\displaystyle{ n \ge 1}\)) łańcuch zbiorów, to suma \(\displaystyle{ A_1 \cup A_2 \cup \ldots \cup A_n}\) jest zbiorem największym, względem inkluzj, spośród z nich. Jako element największy, \(\displaystyle{ \left( A_1\cup A_2 \cup \ldots \cup A_n\right) }\) jest elementem \(\displaystyle{ \left\{ A_1,A_2,\ldots,A_n\right\}}\), a więc jest resztą.\(\displaystyle{ \square}\) (Jest to po prostu najdłuższa z tych reszt).

Dla przekroju, dowód przebiega podobnie, należy wykorzystać fakt, że jak mamy skończony niepusty łańcuch zbiorów, to jego przekrój jest zbiorem najmniejszym, jest to prosty fakt.

Ten przekrój, będący resztą, jest to po prostu najkrótsza z tych reszt.


Znacznie ciekawsze są nieskończone rodziny reszt, więc, zgodnie z zapowiedzią, wykażemy teraz fakt ogólny, że:

jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}}\) rodziną reszt w \(\displaystyle{ X}\), to suma \(\displaystyle{ \bigcup\mathbb{B}}\) jest resztą.\(\displaystyle{
}\)

Wykorzystamy dwa proste fakty, że dopełnienie przedziału początkowego jest resztą, i dopełnienie reszty jest przedziałem początkowym, oraz fakt, że przekrój dowolnej niepustej rodziny przedziałów początkowych jest przedziałem początkowym, co udowodniłem TUTAJ, i fakt, że suma niepustej rodziny przedziałów początkowych jest przedziałem początkowym, co jest prostym faktem. Przejdźmy zatem do naszych dowodów:

DOWÓD:

Niewątpliwie \(\displaystyle{ \bigcup\mathbb{B}\subset X}\) (suma podzbiorów \(\displaystyle{ X}\)). Mamy (przez \(\displaystyle{ '}\) oznaczam dopełnienie do zbioru \(\displaystyle{ X}\)):

\(\displaystyle{ \bigcup\mathbb{B}=\left( \left( \bigcup\mathbb{B}\right) '\right)'= \left( \bigcap_{A\in\mathbb{B} } A' \right)'}\),

teraz zauważmy, że jeśli \(\displaystyle{ A\in\mathbb{B}}\), to \(\displaystyle{ A}\) jest resztą, zatem jej dopełnienie jest przedziałem początkowym. A zatem \(\displaystyle{ \bigcap_{A\in\mathbb{B}} A' }\) jako przekrój (niepustej) rodziny przedziałów początkowych jest przedziałem początkowym, więc jego dopełnienie \(\displaystyle{ \left( \bigcap_{A\in\mathbb{B} } A' \right) '}\) jest resztą, co wobec uzasadnionej równości oznacza, że również \(\displaystyle{ \bigcup\mathbb{B} }\), jako ten sam zbiór, jest resztą.\(\displaystyle{ \square}\)

Wynika stąd, że jeśli \(\displaystyle{ \mathbb{A} }\) jest rodziną wszystkich reszt w \(\displaystyle{ X}\), wtedy \(\displaystyle{ (\mathbb{A}, \subset )}\) jest zbiorem uporządkowanym, i jeśli \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}\subset \mathbb{A}}\) jest niepustym podzbiorem, to ma on supremum, gdyż:

\(\displaystyle{ \left\{ \right\} \neq \mathbb{B}\subset \mathbb{A}}\), a więc \(\displaystyle{ \mathbb{B}}\) jest niepustą rodziną reszt, zatem, na mocy tego, co wykazaliśmy, \(\displaystyle{ \bigcup\mathbb{B}}\) jest resztą, a zatem \(\displaystyle{ \bigcup\mathbb{B}\in\mathbb{A}}\), czyli \(\displaystyle{ \bigcup\mathbb{B}}\) jest elementem zbioru uporządkowanego \(\displaystyle{ \mathbb{A}}\), a zatem \(\displaystyle{ \bigcup\mathbb{B}= \bigvee \mathbb{B}}\)- suma rodziny \(\displaystyle{ \mathbb{B}}\) jest jej supremum.


Wykażemy teraz podobnie, że przekrój niepustej rodziny reszt jest resztą, tzn.:

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}}\) niepustą rodziną reszt w \(\displaystyle{ X}\), to przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest resztą.

Dowód:

Niewątpliwie \(\displaystyle{ \bigcap\mathbb{B}\subset X.}\)

Mamy \(\displaystyle{ \bigcap\mathbb{B}= \left( \left( \bigcap\mathbb{B} \right) '\right)'= \left( \bigcup_{A\in\mathbb{B}} A' \right) '}\),

teraz zauważmy, że jeśli \(\displaystyle{ A\in\mathbb{B}}\), to \(\displaystyle{ A}\) jest resztą, zatem jej dopełnienie \(\displaystyle{ A'}\) jest przedziałem początkowym, a zatem \(\displaystyle{ \bigcup_{A\in\mathbb{B}} A'}\) jako suma przedziałów początkowych jest przedziałem początkowym, a więc jej dopełnienie jest resztą, co oznacza, że również \(\displaystyle{ \bigcap\mathbb{B}}\), jako ten sam zbiór, jest resztą. \(\displaystyle{ \square}\)

Wynika stąd, że jeśli \(\displaystyle{ \mathbb{A}}\) jest rodziną wszystkich reszt w \(\displaystyle{ X}\), to \(\displaystyle{ \left( \mathbb{A}, \subset\right) }\) jest zbiorem uporządkowanym, i jeśli \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}\subset \mathbb{A}}\) jest niepustym podzbiorem, to ma on infimum, gdyż:

\(\displaystyle{ \mathbb{B}}\) jest niepustą rodziną reszt, więc jej przekrój jest resztą, zgodnie z tym, co wykazałem przed chwilą, a zatem \(\displaystyle{ \bigcap\mathbb{B}\in\mathbb{A}}\), czyli ten przekrój jest elementem zbioru uporządkowanego \(\displaystyle{ \mathbb{A}}\), i rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, a zatem \(\displaystyle{ \bigcap\mathbb{B}= \bigwedge \mathbb{B}}\)- przekrój rodziny \(\displaystyle{ \mathbb{B}}\) jest jej infimum. \(\displaystyle{ \square}\)

[Jakub Gurak]

Przedwczoraj udowodniłem, że jeśli mamy zbiór dobrze uporządkowany, i rodzinę wszystkich niepustych reszt w \(\displaystyle{ X}\), uporządkowaną przez odwrotną inkluzję na takich podzbiorach zbioru \(\displaystyle{ X}\) , czyli przez \(\displaystyle{ \supset _{X} = \subset _{X} ^{-1}}\) , to jest to zbiór liniowo uporządkowany podobny do tego danego zbioru dobrze uporządkowanego (a więc jest to również zbiór dobrze uporządkowany). Wykazałem też, że porządek odwrotny do dobrego jest podobny do rodziny wszystkich niepustych przedziałów początkowych w tym porządku odwrotnym \(\displaystyle{ \left( X, \le ^{-1} \right)}\), uporządkowanych inkluzją. Jednak, zbiór dobrze uporządkowany nie musi być podobny do rodziny wszystkich niepustych przedziałów początkowych (ale włącznie z całym zbiorem \(\displaystyle{ X}\)), uporządkowanych inkluzją. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem dobrze uporządkowanym. Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich niepustych reszt w \(\displaystyle{ \left( X, \le\right) }\) , tzn.:

\(\displaystyle{ \mathbb{B}= \left\{ A\subset X\Bigl| \ \ \left\{ \right\} \neq A \hbox{ jest resztą niepustą} \right\},}\)

uporządkowaną przez \(\displaystyle{ \supset= \subset ^{-1}.}\)

Wtedy \(\displaystyle{ \left( \mathbb{B},\supset\right) }\) jest zbiorem uporządkowanym; a ponieważ mamy taki prosty fakt, że dla dwóch reszt, w danym zbiorze liniowo uporządkowanym, jedna zawiera się w drugiej, to łatwo jest pokazać, że \(\displaystyle{ \left( \mathbb{B}, \supset\right)}\) jest zbiorem liniowo uporządkowanym.

Wykażemy, że ten zbiór liniowo uporządkowany jest podobny do zbioru \(\displaystyle{ \left( X, \le \right) .}\)

DOWÓD TEGO FAKTU:

Definniujemy podobieństwo \(\displaystyle{ f:X \rightarrow \mathbb{B}}\), jako:

\(\displaystyle{ f(x)= \left[ x, \rightarrow \right) = \left\{ y\in X: \ y \ge x\right\}.}\)

Niewątpliwie, taki przypisany zbiór przez tą funkcję jest resztą (bo zbiory, będące w takiej postaci, są zawsze resztą) niepustą ( \(\displaystyle{ x\in \left[ x, \rightarrow \right)}\) ) , a zatem \(\displaystyle{ \left[ x, \rightarrow \right) \in \mathbb{B}}\), i funkcja \(\displaystyle{ f}\) jest dobrze określona.

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

Wykażemy najpierw, że jest to funkcja 'na'.

Niech \(\displaystyle{ A\in\mathbb{B}}\). Wtedy \(\displaystyle{ A \subset X}\) i zbiór \(\displaystyle{ A}\) jest niepustą resztą. Ponieważ zbiór \(\displaystyle{ \left( X, \le \right)}\) jest zbiorem dobrze uporządkowanym, a zbiór \(\displaystyle{ A }\) jest niepustą resztą w nim, to na mocy faktu udowodnionego w pierwszym poście tego wątku, reszta \(\displaystyle{ A}\) jest w postaci: \(\displaystyle{ A= \left[ x, \rightarrow \right)}\), gdzie \(\displaystyle{ x\in X}\). Wtedy \(\displaystyle{ f(x)= \left[ x, \rightarrow \right) =A}\), a więc zbiór \(\displaystyle{ A}\) jest wartością funkcji \(\displaystyle{ f}\). Z dowolności wyboru takiego zbioru otrzymujemy, że funkcja \(\displaystyle{ f}\) jest funkcją 'na'.

Wykażemy, że funkcja \(\displaystyle{ f}\) jest różnowartościowa.

Jeśli \(\displaystyle{ f\left( x_1\right)= f\left( x_2\right)}\), to to oznacza, z definicji tej funkcji, że \(\displaystyle{ \left[ x_1, \rightarrow \right)= \left[ x_2, \rightarrow \right)}\), oznaczmy ten zbiór jako \(\displaystyle{ A}\). Wtedy element \(\displaystyle{ x_1}\) jest najmniejszy w \(\displaystyle{ A}\) i element \(\displaystyle{ x_2}\) jest najmniejszy w \(\displaystyle{ A}\); ponieważ w danym zbiorze może istnieć tylko jeden element najmniejszy, a więc \(\displaystyle{ x_1= x_2}\), i funkcja \(\displaystyle{ f}\) jest różnowartościowa.

A więc funkcja \(\displaystyle{ f}\) jest bijekcją.

Pokażemy, że jest monotoniczna.

Niech \(\displaystyle{ x_1,x_2\in X}\), będą takimi elementami, że \(\displaystyle{ x_1 <x_2}\). Pokażemy, że \(\displaystyle{ f\left( x_1\right)\supset f\left( x_2\right).}\)

Wtedy \(\displaystyle{ f(x_1)= \left[ x _{1}, \rightarrow \right)}\) i \(\displaystyle{ f\left( x _{2} \right) = \left[ x_2, \rightarrow \right)}\).

Niech \(\displaystyle{ z \in f(x_2)= \left[ x_2, \rightarrow \right)}\). Wtedy \(\displaystyle{ z \in X}\) i \(\displaystyle{ z \ge x_2}\). Ponieważ \(\displaystyle{ x_2>x_1}\), to \(\displaystyle{ z> x_1}\), a zatem \(\displaystyle{ z \ge x_1}\), a więc \(\displaystyle{ z \in \left[ x_1, \rightarrow \right) = f\left( x_1\right)}\),

i \(\displaystyle{ f\left( x_2\right) \subset f\left( x_1\right)}\), i funkcja \(\displaystyle{ f}\) jest monotoniczna.

A więc funkcja \(\displaystyle{ f}\) jest podobieństwem i \(\displaystyle{ \left( \mathbb{B}, \supset \right) \approx \left( X, \le\right) }\).

Ponieważ \(\displaystyle{ \left( X, \le \right) }\) jest zbiorem dobrze uporządkowanym, więc również zbiór liniowo uporządkowany \(\displaystyle{ \left( \mathbb{B}, \supset\right) }\), jako zbiór do niego podobny, jest zbiorem dobrze uporządkowanym. \(\displaystyle{ \square}\)


Przejdźmy do następnego naszego problemu.

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem dobrze uporządkowanym. Rozważmy porządek odwrotny do niego \(\displaystyle{ \left( X, \le ^{-1} \right) }\)- zbiór liniowo uporządkowany (niekoniecznie dobrze ). Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich niepustych przedziałów początkowych w tym porządku odwrotnym, tzn.:

\(\displaystyle{ \mathbb{B} =\left\{ A \subset X\Bigl| \ \ A \neq \left\{ \right\} \hbox{ jest niepustym przedziałem początkowym w } \left( X, \le ^{-1} \right) \right\}}\),

uporządkowaną inkluzją.

Wykażemy, że \(\displaystyle{ \left( X, \le ^{-1} \right) \approx \left( \mathbb{B}, \subset \right),}\)

czyli wykażemy, że ten nasz zbiór \(\displaystyle{ X}\) z porządkiem odwrotnym jest podobny do rodziny \(\displaystyle{ \mathbb{B}}\) przedziałów początkowych, uporządkowanych inkluzją.

DOWÓD TEGO FAKTU:

Niech:

\(\displaystyle{ \mathbb{A}= \left\{ A\subset X\Bigl| \ \ A \hbox{ jest resztą niepustą w } \left( X, \le \right) \right\}.}\)

Wtedy, na mocy faktu udowodnionego przed chwilą: \(\displaystyle{ \left( X, \le \right) \approx \left( \mathbb{A}, \supset\right)}\) , a więc również \(\displaystyle{ \left( X, \le ^{-1} \right) \approx \left( \mathbb{A}, \subset \right)}\). Wykażemy, że \(\displaystyle{ \mathbb{A}= \mathbb{B}}\).

DOWÓD TEGO FAKTU::    

Jeśli \(\displaystyle{ A \in \mathbb{A}}\), wtedy \(\displaystyle{ A \subset X}\), \(\displaystyle{ A \neq \left\{ \right\}}\) i zbiór \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ \left( X, \le \right).}\) Ponieważ zbiór \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ \left( X, \le\right) }\), to w porządku do niego odwrotnym zbiór \(\displaystyle{ A}\) jest przedziałem początkowym, i mamy \(\displaystyle{ A \neq \left\{ \right\}}\), a zatem \(\displaystyle{ A \in \mathbb{B}.}\)

A jeśli \(\displaystyle{ A \in \mathbb{B},}\) wtedy zbiór \(\displaystyle{ A}\) jest przedziałem początkowym w \(\displaystyle{ \left( X, \le ^{-1} \right)}\), i jest to zbiór niepusty. Wtedy zbiór \(\displaystyle{ A}\) jest resztą w porządku do niego odwrotnym, czyli zbiór \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ \left( X, \left( \le ^{-1} \right) ^{-1} = \le \right)}\), a stąd \(\displaystyle{ A \in \mathbb{A}.\square }\)

A zatem \(\displaystyle{ \mathbb{B} =\mathbb{A}}\), a zatem \(\displaystyle{ \left( X, \le ^{-1} \right) \approx \left( \mathbb{B}, \subset \right).\square}\)


Na koniec wykażemy, zgodnie z zapowiedzią, że zbiór dobrze uporządkowany nie musi być podobny do rodziny wszystkich niepustych przedziałów początkowych (ale wliczając do tej rodziny również cały zbiór \(\displaystyle{ X}\) ), uporządkowanych inkluzją.

DOWÓD TEGO FAKTU:

W tym celu rozważmy jeden element \(\displaystyle{ T}\) spoza zbioru liczb naturalnych- \(\displaystyle{ T\not\in \NN}\);
i rozważmy zbiór \(\displaystyle{ \NN \cup \left\{ T\right\}}\) , z takim porządkiem, że do zbioru liczb naturalnych ze zwykłym porządkiem dodajemy jeden element \(\displaystyle{ T}\) jako największy.

Jest to zbiór dobrze uporządkowany.

Wtedy kolejnymi, względem relacji inkluzji, niepustymi przedziałami początkowymi są:

\(\displaystyle{ \left\{ 0\right\}; \left\{ 0,1\right\}; \left\{ 0,1,2\right\} ;\ldots,}\)

ale również przedziałami początkowymi są:

\(\displaystyle{ \NN= O(T)= \left\{ x \in \NN \cup \left\{ T\right\} : \ x<T\right\};}\)

oraz cały zbiór \(\displaystyle{ \NN \cup \left\{ T\right\} .}\)

A zatem ta rodzina przedziałów początkowych jest typu \(\displaystyle{ \omega+2}\), a nasz zbiór jest typu \(\displaystyle{ \omega +1}\). A zatem takie zbiory dobrze uporządkowane mają różne typy porządkowe, nie są więc podobne.\(\displaystyle{ \square}\)



Dodano po 1 miesiącu 1 dniu 1 godzinie 58 minutach 7 sekundach:
Można spotkać takie poniższe zadanie:

Niech \(\displaystyle{ \left( X, \le \right)}\) będzie zbiorem liniowo uporządkowanym. Dla dowolnego \(\displaystyle{ x \in X}\), niech:

\(\displaystyle{ P(x)= \left\{ y \in X\Bigl| \ \ y<x\right\},}\)

(silna nierówność).

Wykazać, że zbiór uporządkowany \(\displaystyle{ \left( \left( P(x)\right) _{x \in X}, \subset \right)}\) jest podobny do zbioru \(\displaystyle{ \left( X, \le \right).}\)

Ja przedwczoraj dumałem jeszcze z jakąś godzinę nad tą konstrukcją (bo to zadanie rozwiązałem już wcześniej i nawet je zilustrowałem, ale miałem wtedy niedosyt), i przedwczoraj jeszcze dumałem z jakąś godzinę nad tą konstrukcją (i już mniej więcej to rozumiem); i zrobiłem zadanie analogiczne do tego dla reszt w zbiorze liniowo uporządkowanym. Wykazałem również, że porządek odwrotny do dobrego jest podobny do rodziny wszystkich istotnych reszt w tym porządku odwrotnym, uporządkowanych przez odwrotną inkluzję. A przedwczoraj, na dobranoc, wykazałem, że istnieje dokładnie continuum funkcji różnowartościowych ze zbioru liczb całkowitych w zbiór liczb naturalnych. Przedstawię teraz dowody tych ciekawych faktów.

Co do przytoczonego zadania:

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a dla \(\displaystyle{ x \in X}\):

\(\displaystyle{ P(x)= \left\{ y \in X\Bigl| \ \ y<x\right\},}\)

to aby pokazać, że zbiór uporządkowany \(\displaystyle{ \left(\left( P\left( x\right) \right) _{x \in X}, \subset \right)}\) jest podobny do \(\displaystyle{ \left( X, \le\right) }\), to rozważamy funkcję \(\displaystyle{ f}\) działającą w poniższy sposób:

\(\displaystyle{ x \in X\stackrel{ f}{ \rightarrow } P(x),}\)

i łatwo pokazujemy, że jest to monotoniczna bijekcja (oraz, ze zbiór \(\displaystyle{ \left( \left( P(x)\right) _{x \in X} \right) , \subset )}\) jest zbiorem liniowo uporządkowanym, a zatem zbiór \(\displaystyle{ \left( \left( P_x\right) _{x \in X}, \subset \right)}\) jest podobny do zbioru \(\displaystyle{ \left( X, \le \right).\square}\)

Jeszcze słowo wyjaśnienia, bo przedwczoraj udało mi się to lepiej zrozumieć, (a wczoraj robiąc rysunek jeszcze lepiej to zrozumiałem), wcześniej dziwiło mnie, że działa to dla dowolnego zbioru liniowo uporządkowanego, gdzie jest wiele różnych rozmaitości takich zbiorów liniowo uporządkowanych. Ale jeśli \(\displaystyle{ x,y \in X}\) i \(\displaystyle{ x<y}\), to element \(\displaystyle{ y}\) leży dalej niż element \(\displaystyle{ x}\), a wtedy zbiór \(\displaystyle{ P(x)}\) jako zbiór elementów silnie mniejszych od elementu \(\displaystyle{ x}\) jest istotnym podzbiorem zbioru \(\displaystyle{ P(y)}\) (z przechodniości porządku); i ponieważ \(\displaystyle{ x<y}\), to mamy przynajmniej jeden element na prawo od elementu \(\displaystyle{ x,}\) i mamy również zbiór dłuższy od zbioru \(\displaystyle{ P(x)}\)- jest nim zbiór \(\displaystyle{ P(y)}\)- jest to zbiór istotnie dłuższy, bo \(\displaystyle{ x<y}\), a więc \(\displaystyle{ x \in P(y)}\), a \(\displaystyle{ x\not <x}\), a zatem \(\displaystyle{ x \not\in P(x)}\); a więc jest to zbiór dłuższy o elementy zbioru \(\displaystyle{ \left[ x,y\right) \neq \left\{ \right\} }\), bo \(\displaystyle{ x \in \left[ x,y\right)}\); i ... tak dalej, dla elementów coraz bardziej na prawo mamy odpowiadające im coraz to dłuższe zbiory, oto:

ILUSTRACJA TEGO NIEZWYKŁEGO FAKTU:\(\displaystyle{ \\}\)

\(\displaystyle{ \\}\)

Przejdźmy do naszych zadań:

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem liniowo uporządkowanym. Dla dowolnego \(\displaystyle{ x\in X}\) rozważmy resztę:

\(\displaystyle{ R_x=\left( x, \rightarrow \right)= \left\{ y \in X: \ \ y>x\right\}.}\)

Wykażemy, że zbiór uporządkowany \(\displaystyle{ \left( \left\{ R_x\right\} _{x \in X}, \subset \right)}\) jest podobny do porządku odwrotnego \(\displaystyle{ \left( X, \le ^{-1} \right)}\). Oto ilustracja tego faktu:\(\displaystyle{ \\}\)

\(\displaystyle{ \\}\)
Przejdźmy do dowodu tego faktu:

Dla dowolnego \(\displaystyle{ x \in X,}\) zbiór \(\displaystyle{ R_x}\) jest resztą w zbiorze \(\displaystyle{ \left( X, \le \right)}\) , (bo zbiory będące w takiej postaci są zawsze resztą), a więc zbiór \(\displaystyle{ R_x}\) w porządku odwrotnym \(\displaystyle{ \left( X, \le ^{-1}\right)}\) jest przedziałem początkowym. Zauważmy, że ten porządek odwrotny jest porządkiem liniowym na zbiorze \(\displaystyle{ X}\), a zatem para \(\displaystyle{ \left( X, \le ^{-1} \right)}\) jest zbiorem liniowo uporządkowanym. Stosując zatem fakt z przytoczonego zadania, otrzymujemy, że: zbiór
uporządkowany \(\displaystyle{ \left( P(x) _{x \in X} , \subset \right)}\) jest podobny do zbioru \(\displaystyle{ \left( X, \le ^{-1} \right) .}\) Ale, dla dowolnego \(\displaystyle{ x \in X}\), mamy:

\(\displaystyle{ P_x= \left\{ y \in X: \ y < ^{-1} x \right\} \stackrel {y \neq x} {=} \left\{ y \in X: \ y>x\right\} = R_x,}\)

a zatem (z dowolności wyboru \(\displaystyle{ x \in X}\)) otrzymujemy, że \(\displaystyle{ P_x= R_x}\), dla każdego \(\displaystyle{ x \in X}\), a zatem \(\displaystyle{ \left\{ P_x: \ x \in X\right\} = \left\{ R_x: \ x \in X\right\}}\), a zatem ponieważ \(\displaystyle{ \left( \left\{ P_x\right\} _{x \in X} , \subset \right) \approx \left( X, \le ^{-1} \right)}\) , więc również \(\displaystyle{ \left( \left\{ R_x\right\} _{x \in X}, \subset \right) \approx \left( X, \le ^{-1} \right) .\square }\)


Przejdźmy do naszego drugiego zadania:

Niech \(\displaystyle{ \left( X, \le\right) }\) będzie zbiorem dobrze uporządkowanym. Rozważmy porządek odwrotny \(\displaystyle{ \left( X, \le ^{-1} \right) }\)(będzie to porządek liniowy- niekoniecznie dobry).

Niech \(\displaystyle{ \mathbb{B}}\) będzie rodziną wszystkich istotnych reszt w tym porządku odwrotnym, tzn. :

\(\displaystyle{ \mathbb{B} = \left\{ A \subset X: \ \ A \neq X \hbox{ i } A \hbox{ jest resztą w} \left( X, \le ^{-1} \right) \right\}. }\)

Wykażemy, że ten porządek odwrotny jest podobny do tej rodziny reszt \(\displaystyle{ \mathbb{B}}\) uporządkowanej przez \(\displaystyle{ \supset_X:= \subset _{X} ^{-1}.}\)

Nim to zrobimy, przypomnijmy, że dowolny zbiór dobrze uporządkowany \(\displaystyle{ \left( X, \le\right) }\) jest podobny do rodziny wszystkich istotnych przedziałów początkowych w tym zbiorze dobrze uporządkowanym, uporządkowanych inkluzją.

Ten fakt, dowodzi się, definiując funkcję \(\displaystyle{ f:X \rightarrow \mathbb{A}}\), gdzie \(\displaystyle{ \mathbb{A}}\) jest tą rodziną przedziałów początkowych, definiujemy tą funkcję jako:

\(\displaystyle{ f(x)= O(x)= \left\{ y\in X: \ y<x\right\}.}\)

I łatwo jest pokazać, że taka funkcja jest podobieństwem.

Przejdźmy do dowodu naszego faktu:

Niech

\(\displaystyle{ \mathbb{A}= \left\{ A \subset X\Bigl| \ \ A \hbox{ jest przedziałem początkowym w} \left( X, \le \right) \hbox{ i } A \neq X \right\}}\).

będzie rodziną wszystkich istotnych przedziałów początkowych w \(\displaystyle{ \left( X, \le \right)}\), uporządkowanych inkluzją.

Ponieważ zbiór \(\displaystyle{ \left( X, \le\right) }\) jest dobrze uporządkowany, więc na mocy faktu przytoczonego powyżej, otrzymujemy:
\(\displaystyle{ \left( \mathbb{A}, \subset \right) \approx \left( X, \le\right)}\), a zatem również \(\displaystyle{ \left( \mathbb{A}, \supset \right) \approx \left( X, \le ^{-1} \right) }\). Ale:

\(\displaystyle{ \mathbb{A}= \left\{ A \subset X\Bigl| \ \ A \neq X \hbox{ i } A \hbox{ jest przedziałem początkowym w } \left( X, \le \right) \right\} = \left\{ A \subset X\Bigl| \ A \neq X \hbox{ i } A \hbox{ jest resztą w} \left( X, \le ^{-1} \right) \right\} = \mathbb{B}}\).

Czyli:

\(\displaystyle{ \mathbb{B}= \mathbb{A}}\). Ponieważ rodzina \(\displaystyle{ \mathbb{A},}\) uporządkowana przez \(\displaystyle{ \supset}\), jest podobna do porządku odwrotnego \(\displaystyle{ \left( X, \le ^{-1}\right) }\), więc również rodzina \(\displaystyle{ \mathbb{B}}\), jako ta sama rodzina podzbiorów zbioru \(\displaystyle{ X}\), uporządkowana przez \(\displaystyle{ \supset}\), jest również podobna do tego porządku odwrotnego, czyli \(\displaystyle{ \left( \mathbb{B}, \supset \right) \approx \left( X, \le ^{-1} \right). \square}\)


I jeszcze jedno nasze zadanie:

Niech \(\displaystyle{ \mathbb{B}}\), będzie rodziną wszystkich funkcji różnowartościowych ze zbioru liczb całkowitych w zbiór liczb naturalnych, tzn.:

\(\displaystyle{ \mathbb{B}=\left\{ f: \ZZ \rightarrow \NN\Bigl| \ \ f \hbox{ jest różnowartościowa}\right\}.}\)

I pytamy o moc rodziny \(\displaystyle{ \mathbb{B}.}\)

Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest mocy continuum.

Nim to udowodnimy, przypomnijmy, że jak mamy trzy zbiory równoliczne \(\displaystyle{ X_0, X_1}\) i \(\displaystyle{ X_2}\), to jest tyle samo bijekcji ze zbioru \(\displaystyle{ X_0}\) w \(\displaystyle{ X_0}\), ile jest bijekcji z \(\displaystyle{ X_1}\) w \(\displaystyle{ X_2}\) (dowód tego faktu jest analogiczny do dowodu faktu o równoliczności zbiorów funkcji, czyli faktu mówiącego, że: \(\displaystyle{ A ^{B}\sim C ^{D}}\), jeśli tylko \(\displaystyle{ A\sim C}\) i \(\displaystyle{ B\sim D}\), i ten nasz dowód faktu z bijekcjami- dowód tego faktu jest chyba analogiczny do tego).

Przypomnijmy, wszystkich bijekcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum.

Przejdźmy do dowodu naszego faktu:

Niech:

\(\displaystyle{ \mathbb{A}= \left\{ f: \ZZ \rightarrow \NN\Bigl| \ \ f \hbox{ jest bijekcją}\right\}.}\)

I niech:

\(\displaystyle{ \mathbb{D}= \left\{ f: \NN \rightarrow \NN\Bigl| \ f \hbox{ jest bijekcją } \right\}\sim \RR.}\)

Ponieważ \(\displaystyle{ \ZZ\sim \NN}\) i \(\displaystyle{ \NN\sim \NN}\), więc na mocy przytoczonego faktu: \(\displaystyle{ \mathbb{A} \sim \mathbb{D} \sim \RR}\), czyli \(\displaystyle{ \mathbb{A}\sim \RR.}\)

Niewątpliwie \(\displaystyle{ \mathbb{B} \supset \mathbb{A}}\) (każda bijekcja jest funkcją różnowartościowa ), a zatem \(\displaystyle{ \left|
\mathbb{B}\right| \ge \left| \mathbb{A}\right| = \left| \RR\right|}\), czyli \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \RR\right|.}\)

Ale \(\displaystyle{ \mathbb{B} \subset \NN ^{\ZZ} \stackrel{\ZZ\sim \NN} {\sim } \NN ^{\NN}\sim \RR,}\)

a zatem \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right| , }\)

i na mocy twierdzenia Cantora- Bernsteina: \(\displaystyle{ \mathbb{B}\sim \RR.\square }\)


Na koniec, przypomnę treść aksjomatu wyboru i dodam do tego pewną uwagę.
Aksjomat wyboru mówi, ze jeśli \(\displaystyle{ \mathbb{B}}\) jest niepustą rodziną zbiorów niepustych i rozłącznych, to istnieje zbiór, który wybiera z każdego zbioru tej rodziny po jednym elemencie. Dokładniej, chodzi tu o taki zbiór, którego przekrój z każdym zbiorem tej rodziny \(\displaystyle{ \mathbb{B}}\) jest jednoelementowy. Autorzy ważniaka piszą, że aby "możliwe było wybranie dokładnie jednego elementu z każdego zbioru niezbędne było założenie o rozłączności tych zbiorów". I właśnie uważam, że nie do końca jest to niezbędne.

UZASDNIENIE TEJ OBSERWACJI:    

Tzn. sama niepustość jest nie wystarczająca- wystarczy rozważyć zbiór dwuelementowy, oraz jego dwa jednoelementowe podzbiory. Są to trzy niepuste zbiory. I spróbujmy wybrać z każdego z tych trzech zbiorów po jednym elemencie. Ale wybierając ze zbiorów jednoelementowych po jednym elemencie, to z tego zbioru dwuelementowego wybierzemy obydwa jego elementy, a więc wybierzemy więcej niż jeden element. Rzeczywiście, sama niepustość zbiorów to za mało.

Ale uważam, że rozłączność nie jest tu niezbędnym warunkiem. Aby to pokazać rozważmy \(\displaystyle{ 2n}\) zbiorów, gdzie \(\displaystyle{ n}\) jest liczbą naturalną i \(\displaystyle{ n \ge 1}\), tzn, rozważmy zbiory niepuste: \(\displaystyle{ X_1, X_2, \ldots, X_n, Y_1, Y_2,\ldots Y_n}\), gdzie zbiory \(\displaystyle{ X_1, X_2,\ldots, X_n}\) są rozłączne, i wprawdzie tak, aby zbiory \(\displaystyle{ Y_1,Y_2, \ldots, Y_n}\) również były rozłączne, ale tak aby nie wszystkie zbiory z tej podwójnej listy zbiorów były tu rozłączne, tzn. tak aby \(\displaystyle{ X_1 \subsetneq Y_1, X_2 \subsetneq Y_2 , \ldots, X_n \subsetneq Y_n}\). Można łatwo znaleźć takie zbiory na płaszczyźnie. Takie zbiory, z tej podwójnej listy zbiorów nie są rozłączne, gdyż np. \(\displaystyle{ X_1 \cap Y_1= X_1 \neq \left\{ \right\} }\). I wtedy wybierając po jednym elemencie ze zbiorów \(\displaystyle{ X_1, X_2,\ldots, X_n}\), wtedy po prostu ze zbiorów \(\displaystyle{ Y_1, Y_2,\ldots, Y_n}\) nie musimy już specjalnie wybierać elementów, gdyż zostały już wybrane. I wtedy, z każdego zbioru \(\displaystyle{ X_1,X_2,\ldots, X_n,Y_1, Y_2,\ldots, Y_n}\) zostanie wybrany po dokładnie jednym elemencie. Moim zdaniem, da się tu tak to w ten sposób zrobić , mimo, że zbiory nie są rozłączne.

Musi zachodzić tu trochę inny warunek, muszą to być niewątpliwie zbiory niepuste, aby można było z nich wybrać po jednym elemencie (zbiór pusty nie ma elementów), i żaden zbiór tej rodziny nie może zawierać sumy dwóch rozłącznych zbiorów tej rodziny; zbiór rodziny nie może zawierać sumy dwóch rozłącznych zbiorów tej rodziny, bo gdyby tak było, ponieważ z każdego zbioru wybieramy po jednym elemencie, to wybierając z rozłącznych zbiorów leżących wewnątrz tego zbioru, wybierając z nich po jednym elemencie, ponieważ ten zbiór jest to nadzbiór takich dwóch zbiorów rozłącznych, więc czy wybierzemy z niego trzeci element czy nie, to dwa elementy już są z niego wybrane, a więc jest wybrany więcej niż jeden element- sprzeczność. Wobec czego żaden zbiór tej rodziny nie może zawierać sumy dwóch rozłącznych zbiorów tej rodziny.