Przedziały zbioru liniowo uporządkowanego

[Jakub Gurak]

Udowodniłem też ostatnio, że w zbiorze dobrze uporządkowanym \(\displaystyle{ \left( X, \le \right)}\) każdy niepusty przedział, nie będący przedziałem początkowym ani resztą, jest postaci \(\displaystyle{ A=\left[ x,y\right) =\left\{ z\in X: \ x \le z <y\right\}}\), gdzie \(\displaystyle{ x,y\in X}\). Podam teraz dowód tego ciekawego faktu. Podam też podstawowe fakty związane z przedziałami zbioru liniowo uporządkowanego.

Przypomnijmy, że 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.

Przypomnijmy, w zbiorze liniowo uporządkowanym \(\displaystyle{ (X, \le) }\) zbiór \(\displaystyle{ A\subset X}\) nazywamy przedziałem, gdy dla każdych \(\displaystyle{ x,y\in A}\), dla każdego \(\displaystyle{ z\in X}\), takiego, że \(\displaystyle{ x<z<y}\), zachodzi \(\displaystyle{ z\in A.}\)

(Czyli zbiór \(\displaystyle{ A}\) jest przedziałem, gdy z każdymi dwoma jego elementami każdy pośredni element zbioru \(\displaystyle{ X}\) do niego również należy).

Definicję reszty, przedziału początkowego można znaleźć TUTAJ. Zostało tam też udowodnione, że w zbiorze liniowo uporządkowanym każdy przedział początkowy jest przedziałem, i każda reszta jest przedziałem. Oczywiście nie na odwrót, to są skrajne przypadki przedziałów.

Natomiast, w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\), dla \(\displaystyle{ a,b \in X}\) zbiory postaci \(\displaystyle{ \left( a,b\right)=\left\{ x\in X: a<x<b\right\}}\) są zawsze przedziałami, podobnie zbiory postaci \(\displaystyle{ \left[ a,b\right] =\left\{ x\in X: a \le x \le b\right\}}\) są zawsze przedziałami, jak i zbiory postaci \(\displaystyle{ \left[ a,b\right)=\left\{ x\in X: a \le x<b\right\}}\) są zawsze przedziałami, i wreszcie zbiory postaci \(\displaystyle{ \left( a,b\right]= \left\{ x\in X: \ a<x \le b\right\}}\) są zawsze przedziałami.

Jednak w zbiorze liniowo uporządkowanym może istnieć niepusty przedział nie będący przedziałem początkowym ani resztą, który nie jest (tzn. nie może być) w żadnej z tych czterech postaci.

Aby to wykazać rozważmy zbiór liczb rzeczywistych bez \(\displaystyle{ 0}\) i bez \(\displaystyle{ 1}\)- \(\displaystyle{ \RR \setminus \left\{ 0,1\right\}}\) , z naturalnym porządkiem \(\displaystyle{ \le _{\RR \setminus \left\{ 0,1\right\} }}\), zbiór liniowo uporządkowany. Rozważmy zwykły odcinek \(\displaystyle{ \left( 0,1\right) \subset \RR \setminus \left\{ 0,1\right\} }\). Wykażemy, że on jest przedziałem w \(\displaystyle{ \RR \setminus \left\{ 0,1\right\}.}\) Niech \(\displaystyle{ x,y\in (0,1)}\), niech \(\displaystyle{ z\in\RR \setminus \left\{ 0,1\right\} }\), będzie taką liczbą rzeczywistą ,że \(\displaystyle{ x<z<y}\), i pokażmy, że \(\displaystyle{ z\in (0,1).}\) To jednak jest proste, mamy \(\displaystyle{ 0<x<z<y<1}\), a więc \(\displaystyle{ 0<z<1}\), a więc \(\displaystyle{ z\in(0,1)}\), i odcinek \(\displaystyle{ \left( 0,1\right)}\) jest przedziałem (niepustym), nie jest przedziałem początkowym w \(\displaystyle{ \RR \setminus \left\{ 0,1\right\} }\),i nie jest resztą w \(\displaystyle{ \RR \setminus \left\{ 0,1\right\} }\),i nie jest postaci \(\displaystyle{ (a,b),}\) dla żadnych \(\displaystyle{ \left( a,b\right) \in \RR \setminus \left\{ 0,1\right\}}\) (rozważamy \(\displaystyle{ \RR}\) bez zera i jedynki, więc końce muszą być rożne od zera i jedynki ); i nie jest postaci \(\displaystyle{ \left( a,b\right],}\) dla żadnych \(\displaystyle{ a,b\in\RR \setminus \left\{ 0,1\right\}}\); nie jest postaci \(\displaystyle{ \left[ a,b\right],}\) dla żadnych \(\displaystyle{ a,b\in\RR \setminus \left\{ 0,1\right\}}\); i nie jest postaci \(\displaystyle{ \left[ a,b\right),}\) dla żadnych \(\displaystyle{ a,b \in \RR \setminus \left\{ 0,1\right\} .\square
}\)


Przejdźmy zatem do zapowiedzianego dowodu, wykażemy, że

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem dobrze uporządkowanym, a \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) niepustym przedziałem, nie będącym przedziałem początkowym ani resztą, to \(\displaystyle{ A}\) jest postaci \(\displaystyle{ A=\left[ x,y\right) =\left\{ z\in X: \ x \le z<y \right\}}\) , dla pewnych \(\displaystyle{ x,y\in X}\) (takich, ze \(\displaystyle{ x<y}\)).

Dowód:

Ponieważ \(\displaystyle{ \left\{ \right\} \neq A\subset X}\), a \(\displaystyle{ (X, \le)}\) jest zbiorem dobrze uporządkowanym, zatem zbiór \(\displaystyle{ A}\) ma element najmniejszy \(\displaystyle{ a\in A.}\) Ponieważ \(\displaystyle{ A}\) nie jest resztą, i \(\displaystyle{ A \neq \left\{ \right\}}\), więc zaprzeczając definicji reszty otrzymujemy, że istnieje \(\displaystyle{ b\in A}\), i istnieje \(\displaystyle{ x\in X}\), taki, że \(\displaystyle{ x>b,}\) i taki, ze \(\displaystyle{ x\not\in A}\). Ustalmy takie \(\displaystyle{ b\in A}\). Ponieważ \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ A}\), więc \(\displaystyle{ a \le b}\). I rozważmy teraz zbiór \(\displaystyle{ B:}\)

\(\displaystyle{ B:=\left\{ x\in X: x>b \hbox{ i } x\not\in A\right\}\subset X.}\)

Na mocy wypowiedzi powyżej zbiór \(\displaystyle{ B}\) jest niepusty, i jest podzbiorem \(\displaystyle{ X}\), ponieważ \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem dobrze uporządkowanym, więc \(\displaystyle{ B}\) ma element najmniejszy \(\displaystyle{ b_0\in B}\). Wtedy \(\displaystyle{ b_0>b, b_0\not\in A.}\) Ponieważ \(\displaystyle{ b_0>b \ge a}\), to \(\displaystyle{ b_0>a}\). Ja teraz stwierdzam, że \(\displaystyle{ A=\left[ a,b_0\right), a,b_0\in X}\). Musimy jednak tą równość zbiorów udowodnić.
Niech \(\displaystyle{ x\in A}\). Ponieważ \(\displaystyle{ a}\) jest najmniejszy w \(\displaystyle{ A}\), to \(\displaystyle{ a \le x}\). Chcemy pokazać, że \(\displaystyle{ x<b_0}\). Przypuśćmy nie wprost, że tak nie jest. Wtedy \(\displaystyle{ b_0 \le x\in A}\) (porządek dobry jest liniowy), ponieważ \(\displaystyle{ A\ni a<b_0 \le x\in A}\), a zbiór \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ b_0\in A}\), a \(\displaystyle{ b_0\not\in A}\)-sprzeczność. Wobec czego \(\displaystyle{ x<b_0}\), i \(\displaystyle{ A\subset \left[ a,b_0\right). }\)
Niech teraz \(\displaystyle{ x\in\left[ a,b_0\right).}\) Przypuśćmy nie wprost, że \(\displaystyle{ x\not\in A}\), wtedy \(\displaystyle{ x>b}\) (Gdyby byłoby \(\displaystyle{ x \le b}\), to poniewaz \(\displaystyle{ A\ni a \le x \le b\in A}\), a \(\displaystyle{ A}\) jest przedziałem, więc moglibyśmy wnioskować, że \(\displaystyle{ x\in A}\)- sprzeczność). Zatem \(\displaystyle{ x>b}\). Mamy \(\displaystyle{ a \le x< b_0}\). Ponieważ \(\displaystyle{ b_0}\) jest najmniejszy w \(\displaystyle{ B}\), a \(\displaystyle{ x<b_0}\), to \(\displaystyle{ x\not\in B}\) (gdyby należał do \(\displaystyle{ B}\), to z definicji elementu najmniejszego otrzymalibyśmy \(\displaystyle{ b_0 \le x}\)), zatem \(\displaystyle{ x\not\in B}\), ponieważ \(\displaystyle{ x\in X}\), \(\displaystyle{ x>b}\), to z definicji zbioru \(\displaystyle{ B}\), pozostaje możliwość (tzn. musi być) \(\displaystyle{ x\in A}\)- sprzeczność.
A zatem \(\displaystyle{ \left[ a,b_0\right)\subset A}\), i \(\displaystyle{ \left[ a,b_0\right)=A}\), gdzie \(\displaystyle{ a,b_0\in X. \square}\)

Podejrzewam teraz, że założenie, ze \(\displaystyle{ A}\) nie jest przedziałem początkowym jest nieistotne, chyba z tego nie korzystałem, ale trzeba będzie to sprawdzić.

[Jakub Gurak]

Udowodniłem wczoraj, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) mamy dwa przedziały \(\displaystyle{ A,B,}\) takie, że \(\displaystyle{ A}\) nie zawiera się w \(\displaystyle{ B}\) (\(\displaystyle{ A\not\subset B}\)), i \(\displaystyle{ B}\) nie zawiera się w \(\displaystyle{ A}\), to ich różnica \(\displaystyle{ A \setminus B}\) jest przedziałem niepustym. Myślę, że to ciekawe. Oto ilustacja:
Udowodniłem też, że przekrój dwóch przedziałów jest przedziałem. Łatwo przez indukcję można uogólnić na dowolną skończoną ilość przedziałów. Przedstawię teraz dowody tych ciekawych faktów.

Niech \(\displaystyle{ (X, \le)}\) będzie zbiorem liniowo uporządkowanym, a zbiory \(\displaystyle{ A,B\subset X}\) będą przedziałami, takimi, że \(\displaystyle{ A\not\subset B}\) i \(\displaystyle{ B\not\subset A}\). Wykażemy, że różnica \(\displaystyle{ A \setminus B }\) jest przedziałem niepustym.

Dowód:

Niewątpliwie \(\displaystyle{ A \setminus B\subset X.}\)

Aby wykazać, że różnica \(\displaystyle{ A \setminus B}\) jest przedziałem, to weżmy \(\displaystyle{ x,y\in A \setminus B}\), oraz weźmy element \(\displaystyle{ z\in X}\), taki, że \(\displaystyle{ x<z<y}\), i pokażmy, że \(\displaystyle{ z\in A \setminus B.}\)

Mamy \(\displaystyle{ x,y\in A}\), więc ponieważ \(\displaystyle{ A\ni x<z<y\in A}\), a \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ z\in A.}\)

Pozostaje pokazać, że \(\displaystyle{ z\not\in B}\). Przypuśćmy nie wprost, że \(\displaystyle{ z\in B}\). Ponieważ \(\displaystyle{ B\not\subset A}\), to \(\displaystyle{ B \neq \emptyset }\)(zbiór pusty jest podzbiorem każdego zbioru), i, zgodnie z definicją inkluzji zbiorów, nie każdy element \(\displaystyle{ B}\) jest elementem \(\displaystyle{ A}\), więc istnieje element \(\displaystyle{ b\in B}\), taki, że \(\displaystyle{ b\not\in A}\). Ustalmy taki element. I rozważmy teraz trzy przypadki.

Jeśli \(\displaystyle{ b \ge y}\), to ponieważ \(\displaystyle{ B\ni z<y \le b\in B}\), a \(\displaystyle{ B}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ y\in B}\), a \(\displaystyle{ y\in A \setminus B}\), więc \(\displaystyle{ y\not\in B}\)-sprzeczność.

W przeciwnym przypadku (\(\displaystyle{ b<y}\)), to nie może być \(\displaystyle{ b \ge x}\). Gdyby bowiem byłoby \(\displaystyle{ b \ge x}\), to ponieważ \(\displaystyle{ A\ni y>b \ge x\in A}\), a \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ b\in A}\)- sprzeczność.

Pozostaje przypadek \(\displaystyle{ b<x}\). On również prowadzi do sprzeczności. Wtedy:
\(\displaystyle{ B\ni b<x<z\in B}\), a zbiór \(\displaystyle{ B}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ x\in B}\), a \(\displaystyle{ x\in A \setminus B}\)- sprzeczność.

A zatem \(\displaystyle{ z\not\in B}\), a zatem \(\displaystyle{ z\in A \setminus B}\), i \(\displaystyle{ A \setminus B}\) jest przedziałem. Pozostaje wykazać, że jest to zbiór niepusty.

Ponieważ \(\displaystyle{ A\not \subset B}\), to \(\displaystyle{ A \neq \emptyset}\) (zbiór pusty jest podzbiorem każdego zbioru ), więc zaprzeczając definicji inkluzji otrzymujemy, że istnieje element \(\displaystyle{ a\in A}\), taki, że \(\displaystyle{ a\not\in B}\), wtedy \(\displaystyle{ a\in A \setminus B}\), a więc \(\displaystyle{ A \setminus B \neq \left\{ \right\}}\)- jest to zbiór niepusty. \(\displaystyle{ \square}\)


Wykażemy jeszcze, że przekrój dwóch przedziałów jest przedziałem, tzn. wykażemy, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a zbiory \(\displaystyle{ A,B\subset X}\) są przedziałami , to przekrój \(\displaystyle{ A \cap B}\) jest przedziałem.

PROSTY DOWÓD:    

Niewątpliwie \(\displaystyle{ A \cap B\subset X}\).

Aby wykazać, że ten zbiór jest przedziałem, to weźmy \(\displaystyle{ x,y\in A \cap B}\), oraz element \(\displaystyle{ z \in X}\), taki, że \(\displaystyle{ x<z<y}\), i pokażmy, że \(\displaystyle{ z\in A \cap B.
}\)

Mamy \(\displaystyle{ x,y\in A}\). Ponieważ \(\displaystyle{ A\ni x<z<y \in A}\), a zbiór \(\displaystyle{ A}\) jest przedziałem, wiec wnioskujemy, że \(\displaystyle{ z\in A.}\)

Podobnie pokażemy teraz, że \(\displaystyle{ z\in B.}\) Mamy \(\displaystyle{ x,y\in B.}\) Ponieważ \(\displaystyle{ B\ni x<z<y\in B}\), a \(\displaystyle{ B}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ z\in B.}\)

A zatem \(\displaystyle{ z\in A \cap B}\), i \(\displaystyle{ A \cap B }\) jest przedziałem\(\displaystyle{ .\square }\)

Również jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, i mamy \(\displaystyle{ n}\) przedziałów \(\displaystyle{ A_1,A_2,\ldots,A_n\subset X}\), to ich przekrój \(\displaystyle{ A_1 \cap A_2 \cap \ldots \cap A_n}\) jest przedziałem, łatwo to przez indukcję można udowodnić.

Na koniec wykażemy, co udowodniłem też w ostatnich dniach, że jeśli mamy dwa przedziały, których przekrój jest niepusty, to ich suma jest przedziałem, tzn.:

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym,a zbiory \(\displaystyle{ A,B\subset X }\) są przedziałami, takimi, że \(\displaystyle{ A \cap B \neq \left\{ \right\}}\), to suma \(\displaystyle{ A \cup B}\) jest przedziałem.

Dowód:

Niewątpliwie \(\displaystyle{ A \cup B\subset X.}\)

Aby wykazać, że zbiór \(\displaystyle{ A \cup B}\) jest przedziałem, to weźmy \(\displaystyle{ x,y\in A \cup B}\), oraz elememt \(\displaystyle{ z\in X}\), taki, że \(\displaystyle{ x<z<y}\), i pokażmy, że \(\displaystyle{ z\in A \cup B}\). Rozważmy teraz przypadki:

Jeśli \(\displaystyle{ x,y\in A}\), a \(\displaystyle{ x<z<y}\), i \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ z\in A}\), a więc \(\displaystyle{ z\in A \cup B.}\)

Podobnie sprawdzamy przypadek gdy: \(\displaystyle{ x,y\in B}\).

Rozważmy teraz przypadek, gdy: \(\displaystyle{ x\in A, y\in B}\). Ponieważ \(\displaystyle{ A \cap B \neq \left\{ \right\}}\) , więc istnieje element \(\displaystyle{ w\in A \cap B}\), wtedy \(\displaystyle{ w\in A,B}\). Ponieważ \(\displaystyle{ z,w\in X}\), a \(\displaystyle{ (X, \le)}\) jest zbiorem liniowo uporządkowanym, więc \(\displaystyle{ z \le w}\) lub \(\displaystyle{ w \le z}\).
Jeśli \(\displaystyle{ z \le w}\), to \(\displaystyle{ A\ni x<z \le w\in A}\), a \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ z\in A}\), a więc \(\displaystyle{ z\in A \cup B.}\)
Jeśli \(\displaystyle{ w \le z}\), to ponieważ \(\displaystyle{ B\ni w \le z<y\in B}\), a \(\displaystyle{ B }\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ z\in B}\), i \(\displaystyle{ z\in A \cup B.}\)

Pozostaje do rozważenia przypadek gdy: \(\displaystyle{ x\in B, y\in A}\). Ponieważ \(\displaystyle{ A \cap B \neq \left\{ \right\}}\) , więc istnieje element \(\displaystyle{ w\in A \cap B}\), wtedy \(\displaystyle{ w,z\in X}\), a \(\displaystyle{ ( X, \le )}\) jest zbiorem liniowo uporządkowanym, więc \(\displaystyle{ w \le z}\) lub \(\displaystyle{ z \le w.}\)
Jeśli \(\displaystyle{ w \le z}\), to ponieważ \(\displaystyle{ A\ni w \le z<y\in A}\), a \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ z\in A}\), i \(\displaystyle{ z\in A \cup B.}\)
Jeśli \(\displaystyle{ z \le w}\), to sprawdzamy to podobnie.

A zatem, w każdym przypadku, \(\displaystyle{ z\in A \cup B}\), i \(\displaystyle{ A \cup B}\) jest przedziałem. \(\displaystyle{ \square}\)

[Jakub Gurak]

Udowodniłem ostatnio uogólnienie powyższego faktu na \(\displaystyle{ n}\) przedziałów, tzn. jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, i mamy \(\displaystyle{ n}\) przedziałów \(\displaystyle{ A_1,A_2,\ldots,A_n\subset X}\), których przekrój \(\displaystyle{ A_1\cap A_2\cap\ldots \cap A_n \neq \left\{ \right\} }\) jest niepusty , to ich suma \(\displaystyle{ A_1 \cup A_2\cup\ldots \cup A_n}\) jest przedziałem. Przedstawię teraz dowód tego ciekawego faktu.

Dowód:

Dowód jest indukcyjny.

Dla \(\displaystyle{ n=1}\), \(\displaystyle{ A_1= \bigcap\left\{ A_1\right\} \neq \left\{ \right\},}\) i zbiór \(\displaystyle{ A_1}\) jest przedziałem, więc \(\displaystyle{ \bigcup\left\{ A_1\right\} =A_1}\) jest oczywiście przedziałem.
Dla \(\displaystyle{ n=2}\), własność zachodzi na mocy dowodu powyżej.


Krok indukcyjny, weźmy \(\displaystyle{ n \ge 2}\), i przypuśćmy, że twierdzenie zachodzi dla \(\displaystyle{ n}\). Pokażemy, że zachodzi dla \(\displaystyle{ (n+1).}\) W tym celu weźmy \(\displaystyle{ (n+1)}\) przedziałów \(\displaystyle{ A_1,A_2,\ldots,A_n, A_{n+1}}\), takich, że ich przekrój \(\displaystyle{ \bigcap_{i=1}^{n+1} A_i \neq \left\{ \right\}}\) jest niepusty. Pokażemy, że \(\displaystyle{ \bigcup_{i=1}^{n+1} A_i}\) jest przedziałem.
Niewątplwie mamy: \(\displaystyle{ \bigcup_{i=1}^{n+1}=\left( \bigcup_{i=1}^{n} A_i\right) \cup A_{n+1}.}\) Zbiory \(\displaystyle{ A_1, A_2,\ldots, A_n}\)- są to przedziały. Mamy również, gdyż ponieważ przekrój większej rodziny zbiorów jest mniejszy, więc \(\displaystyle{ \bigcap_{i=1}^{n} A_i\supset \bigcap_{i=1}^{n+1}A_i \neq \left\{ \right\}}\) (z założenia naszego jest to zbiór niepusty), więc również zbiór \(\displaystyle{ \bigcap_{i=1}^{n} A_i}\) jest niepusty, więc z założenia indukcyjnego suma \(\displaystyle{ \bigcup_{i=1}^{n} A_i}\) jest przedziałem. Mamy również, że zbiór \(\displaystyle{ A_{n+1}}\) jest przedziałem. Wykażemy teraz, że przekrój \(\displaystyle{ \left( A_1 \cup A_2 \cup \dots \cup A_n \right) \cap A _{n+1}}\) jest niepusty. Niewątpliwie:

\(\displaystyle{ \left( A_1 \cup A_2 \cup \dots \cup A_n \right) \cap A _{n+1}=\left( A_1 \cap A_{n+1}\right) \cup \left( A_2 \cap A_{n+1}\right) \cup \ldots \cup \left( A_n \cap A_{n+1}\right)}\), i teraz zauważmy, że \(\displaystyle{ A_1 \cap A_{n+1}= \bigcap \left\{ A_1,A_{n+1}\right\} \supset \bigcap\left\{ A_1,A_2,\ldots, A_{n+1}\right\} \neq \left\{ \right\}}\), gdyż przekrój większej rodziny zbiorów jest mniejszy. A zatem również zbiór po lewej stronie inkluzji jest niepusty, czyli zbiór \(\displaystyle{ A_1 \cap A_{n+1}}\) jest niepusty, a więc cała rozważana powyżej suma tym bardziej jest zbiorem niepustym, więc to oznacza, że \(\displaystyle{ \left( A_1 \cup A_2 \cup\ldots \cup A_n\right) \cap A_{n+1}}\) jest zbiorem niepustym. Mamy, że zbiór \(\displaystyle{ A_1 \cup A_2 \cup \ldots \cup A_n}\) jest przedziałem, i zbiór \(\displaystyle{ A_{n+1}}\) jest przedziałem (i ich przekrój jest niepusty), więc suma \(\displaystyle{ \left( A_1 \cup A_2 \cup\ldots \cup A_n\right) \cup A_{n+1}}\) jest przedziałem, czyli \(\displaystyle{ \bigcup_{i=1}^{n+1} A_i}\) jest przedziałem.\(\displaystyle{ \square}\)

[Jakub Gurak]

Udowodniłem wczoraj, że jeśli mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right) ; \left( Y, \le _Y\right) }\) tak, że zbiory \(\displaystyle{ X, Y}\) są rozłączne (wtedy na \(\displaystyle{ X \cup Y}\) możemy rozważać sumę porządkową tych dwóch porządków), jeśli zbiór \(\displaystyle{ A\subset X}\) jest resztą w \(\displaystyle{ X}\), a zbiór \(\displaystyle{ B\subset Y}\) jest przedziałem początkowym w \(\displaystyle{ Y}\), to \(\displaystyle{ A \cup B}\) jest przedziałem w \(\displaystyle{ X \cup Y}\) ze sumą porządkową. Udowodniłem też, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ A\subset X}\) dowolnym przedziałem, a \(\displaystyle{ Y}\) podzbiorem liniowo uporządkowanym, to przekrój \(\displaystyle{ A \cap Y}\) jest przedziałem w \(\displaystyle{ Y}\). Przedstawię teraz dowody tych ciekawych faktów.


Aby udowodnić pierwszy fakt:

Zauważmy najpierw, że \(\displaystyle{ A\subset X\subset X \cup Y}\), i \(\displaystyle{ B\subset Y\subset X \cup Y}\), w efekcie również \(\displaystyle{ A \cup B \subset X \cup Y.}\)

Aby wykazać, że \(\displaystyle{ A \cup B}\) jest przedziałem w \(\displaystyle{ X \cup Y}\) ze sumą porządkową \(\displaystyle{ \le _{X\oplus Y}}\), to weźmy elementy \(\displaystyle{ x,y\in A\cup B}\), i weźmy element \(\displaystyle{ z\in X \cup Y,}\) taki, że \(\displaystyle{ x \le _{X\oplus Y} z \le _{X\oplus Y} y,}\) i pokażmy, że \(\displaystyle{ z\in A \cup B. }\)

Jeśli \(\displaystyle{ z\in B}\), to \(\displaystyle{ z\in A \cup B}\) i dowód jest zakończony. Załóżmy więc, że \(\displaystyle{ z\not\in B,}\) i pokażmy, że \(\displaystyle{ z\in A}\).

Mamy \(\displaystyle{ z\not\in B}\). Wtedy nawet \(\displaystyle{ z\not\in Y}\). Gdyby bowiem byłoby \(\displaystyle{ z\in Y}\), a mamy \(\displaystyle{ y\in A \cup B}\), więc:

Jeśli \(\displaystyle{ y\in A}\), to \(\displaystyle{ y\in X}\), \(\displaystyle{ z\in Y}\), i ponieważ, z definicji sumy porządkowej, każdy element \(\displaystyle{ X}\) jest mniejszy od każdego elementu \(\displaystyle{ Y}\), więc \(\displaystyle{ y \le _{X\oplus Y} z}\), a mamy \(\displaystyle{ z<_{X\oplus Y} y}\)-sprzeczność.

A jeśli \(\displaystyle{ y\in B}\), wtedy \(\displaystyle{ y\in Y, z\in Y}\), mamy \(\displaystyle{ z<_{X\oplus Y} y}\), więc, z definicji sumy porządkowej, musi zachodzić \(\displaystyle{ z \le _Y y\in B}\), a zbiór \(\displaystyle{ B}\) jest przedziałem początkowym w \(\displaystyle{ Y}\), więc wnioskujemy, że \(\displaystyle{ z\in B}\)- sprzeczność.

A zatem \(\displaystyle{ z\not\in Y}\), więc \(\displaystyle{ z\in X}\). Wtedy \(\displaystyle{ x\in X}\) (gdyby byłoby \(\displaystyle{ x\not\in X}\), to \(\displaystyle{ x\in Y}\), mamy \(\displaystyle{ z\in X}\), więc ponieważ, względem sumy porządkowej, każdy element \(\displaystyle{ X}\) jest mniejszy od każdego elementu \(\displaystyle{ Y,}\) więc \(\displaystyle{ z<_{X\oplus Y} x}\), a \(\displaystyle{ x<_{X\oplus Y} z}\)- sprzeczność). Zatem \(\displaystyle{ x\in X}\),\(\displaystyle{ z\in X}\) i \(\displaystyle{ x \le _{X\oplus Y} z}\), więc z definicji sumy porządkowej \(\displaystyle{ x \le _X z}\). Mamy \(\displaystyle{ x\in A \cup B}\), i \(\displaystyle{ x\not\in B}\) (gdyby \(\displaystyle{ x\in B}\), to \(\displaystyle{ x\in Y}\), mamy \(\displaystyle{ x\in X}\), więc \(\displaystyle{ x\in X \cap Y}\), a zbiory \(\displaystyle{ X,Y}\) są rozłączne- sprzeczność ). Zatem \(\displaystyle{ x\notin B}\), ale \(\displaystyle{ x\in A \cup B}\), więc \(\displaystyle{ x\in A}\). Ponieważ \(\displaystyle{ A\ni x \le_X z, z\in X}\), a zbiór \(\displaystyle{ A}\) jest resztą w \(\displaystyle{ X}\), więc wnioskujemy, że \(\displaystyle{ z\in A}\). Wobec czego \(\displaystyle{ z\in A \cup B}\), i zbiór \(\displaystyle{ A \cup B}\) jest przedziałem.\(\displaystyle{ \square}\)


Wykażemy jeszcze, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ A\subset X}\) przedziałem, a \(\displaystyle{ Y}\) podzbiorem zbioru \(\displaystyle{ X}\) z porządkiem \(\displaystyle{ \le }\) z \(\displaystyle{ X}\) zawężonym do podzbioru \(\displaystyle{ Y}\), oznaczmy go jako \(\displaystyle{ \le _Y}\), taki zbiór jest to, jako podzbiór zbioru liniowo uporządkowanego, jest zbiorem liniowo uporządkowanym, wtedy zbiór \(\displaystyle{ A \cap Y }\) jest przedziałem w \(\displaystyle{ \left( Y, \le _Y\right) }\).

PROSTY DOWÓD:

Niewątpliwie \(\displaystyle{ A \cap Y\subset Y}\), jak trzeba.

Aby wykazać, że ten zbiór jest przedziałem w \(\displaystyle{ Y}\), to weźmy elementy \(\displaystyle{ x,y\in A \cap Y}\), i weźmy element \(\displaystyle{ z\in Y}\), taki, że \(\displaystyle{ x<_Y z <_Y y}\), i pokażmy, że \(\displaystyle{ z\in A \cap Y}\). Mamy \(\displaystyle{ x\in A, y\in A}\), i \(\displaystyle{ x<_Y z <_Y y}\), ponieważ porządek \(\displaystyle{ \le}\) rozszerza porządek \(\displaystyle{ \le _Y}\), więc \(\displaystyle{ A\ni x \le z \le y\in A}\), a \(\displaystyle{ A}\) jest przedziałem w \(\displaystyle{ \left( X, \le\right) }\), więc wnioskujemy, że również \(\displaystyle{ z\in A}\). Mamy \(\displaystyle{ z\in Y}\), więc \(\displaystyle{ z\in A \cap Y}\), i zbiór \(\displaystyle{ A \cap Y}\) jest przedziałem. \(\displaystyle{ \square}\)

Można też łatwo udowodnić, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ A\subset X}\) przedziałem, to \(\displaystyle{ A}\) jest również przedziałem w \(\displaystyle{ X}\) względem porządku odwrotnego \(\displaystyle{ \le ^{-1}}\). To można bardzo prosto udowodnić.

[Jakub Gurak]

Udowodniłem [...], że jeśli mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right) ; \left( Y, \le _Y\right) }\) tak, że zbiory \(\displaystyle{ X, Y}\) są rozłączne (wtedy na \(\displaystyle{ X \cup Y}\) możemy rozważać sumę porządkową tych dwóch porządków), jeśli zbiór \(\displaystyle{ A\subset X}\) jest resztą w \(\displaystyle{ X}\), a zbiór \(\displaystyle{ B\subset Y}\) jest przedziałem początkowym w \(\displaystyle{ Y}\), to \(\displaystyle{ A \cup B}\) jest przedziałem w \(\displaystyle{ X \cup Y}\) ze sumą porządkową.

Widzę, że ani nie zilustrowałem tego faktu (co tym razem jest ciężko zrobić), ani go nie objaśniłem.

Już tłumaczę:

Definicja przedziału \(\displaystyle{ A \subset X}\), gdzie \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, mówi, że 'wchodząc do środka' zbioru, zbiór \(\displaystyle{ A}\) musi on zawierać, jako elementy, wszystkie elementy zbioru liniowo uporządkowanego \(\displaystyle{ X}\). A tu mamy sumę porządkową określoną na zbiorze \(\displaystyle{ X \cup Y}\), oraz mamy resztę \(\displaystyle{ A \subset X}\) i mamy przedział początkowy \(\displaystyle{ B \subset Y}\). Naszym zbiorem liniowo uporządkowanym jest tutaj \(\displaystyle{ X \cup Y}\) ze sumą porządkową, więc suma tej reszty i tego przedziału początkowego, 'wchodząc do jej środka', zawiera ona wszystkie elementy zbioru \(\displaystyle{ X \cup Y}\) (tego 'odstępu' między zbiorami \(\displaystyle{ X}\) a \(\displaystyle{ Y}\), nie rozważamy takich elementów , gdyż rozważamy tu jedynie zbiór \(\displaystyle{ X \cup Y}\) ), wtedy suma tej reszty i tego przedziału początkowego, wchodząc do jej środka, otrzymamy, że zawiera ona wszystkie elementy zbioru \(\displaystyle{ X \cup Y}\), naszego zbioru liniowo uporządkowanego, a więc ta suma jest przedziałem w \(\displaystyle{ X \cup Y}\).

Mamy też twierdzenie, mówiące, że jeśli mamy zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\), oraz mamy rodzinę \(\displaystyle{ \mathbb{B}}\) przedziałów w \(\displaystyle{ X}\) o niepustym przecięciu, to ich suma jest przedziałem.

Udało się wczoraj wzmocnić ten rezultat (choć pomysł ten pochodzi od zadania z książki z topologii dla zbiorów spójnych, postawiłem analogiczne zadanie dla przedziałów, bo zbiorami spójnymi na prostej są chyba, są nimi dokładnie przedziały, i uogólniłem je na dowolne przedziały w zbiorze liniowo uporządkowanym \(\displaystyle{ X}\), chodzi nie tylko o przedziały na prostej), do postaci:

Jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ \left( A_n\right) _{n \in \NN}}\), ciągiem przedziałów w \(\displaystyle{ X}\), takim, że każdy przedział z tego ciągu przecina się z następnym, tzn.: \(\displaystyle{ A _{n} \cap A _{n+1} \neq \left\{ \right\}}\), dla każdego \(\displaystyle{ n \in \NN}\) , to suma tych przedziałów \(\displaystyle{ \bigcup_{n \in \NN} A_n }\) jest przedziałem w \(\displaystyle{ X}\).

Przedstawię teraz krótki dowód tego faktu:

Przypomnijmy najpierw, że jeśli mamy zbiór liniowo uporządkowany \(\displaystyle{ \left( X, \le\right) }\), oraz mamy łańcuch \(\displaystyle{ \mathbb{B}}\), względem inkluzji, przedziałów w \(\displaystyle{ X}\), to suma \(\displaystyle{ \bigcup\mathbb{B}}\) jest przedziałem, co udowodniłem TUTAJ:

i ten fakt przyda nam się.

Przejdźmy do dowodu naszego faktu:

DOWÓD TEGO FAKTU:

Zdefiniujmy nowy ciąg podzbiorów zbioru \(\displaystyle{ X}\), w następujący sposób:

\(\displaystyle{ B_0= A_0}\);
\(\displaystyle{ B_1= A_0 \cup A_1}\);
\(\displaystyle{ \vdots}\)

tzn.:

\(\displaystyle{ B_n= \bigcup_{k=0}^{n} A_k.}\)

Wykażemy, że zbiór \(\displaystyle{ B_n}\) jest zawsze przedziałem.

Dowód jest indukcyjny:

Mamy, że zbiór \(\displaystyle{ B_0= A_0}\) jest przedziałem (z założenia).
Mamy \(\displaystyle{ B_1=A_0 \cup A_1}\), gdzie te obydwa składniki są przedziałami, i również, na mocy założenia, te dwa zbiory przecinają się, a zatem zbiór \(\displaystyle{ B_1}\) jest przedziałem, bo jak dwa przedziały mają niepuste przecięcie, to ich suma jest przedziałem, a zatem zbiór \(\displaystyle{ B_1}\) jest przedziałem.

Krok indukcyjny:

Przypuśćmy, że zbiór \(\displaystyle{ B_n}\) jest przedziałem.

Wtedy:

\(\displaystyle{ B _{n+1}= A_0 \cup A_1 \cup \ldots \cup A_n \cup A _{n+1}= B_n \cup A _{n+1}= }\)

gdzie pierwszy składnik tej sumy dwóch zbiorów jest przedziałem ( na mocy założenia indukcyjnego), i zbiór \(\displaystyle{ A _{n+1}}\) jest przedziałem.

Ponieważ zbiory \(\displaystyle{ A _{n+1}}\) i \(\displaystyle{ A_n}\) przecinają się, to również zbiory \(\displaystyle{ B_n}\) i \(\displaystyle{ A _{n+1}}\) przecinają się, a zatem zbiór \(\displaystyle{ B _{n+1}= B_n \cup A _{n+1}}\) jest przedziałem. Krok indukcyjny został dowiedziony.

Zasada indukcji matematycznej gwarantuje, że zbiór \(\displaystyle{ B_n}\) jest przedziałem, dla każdego \(\displaystyle{ n \in \NN.}\)

Widać, że zbiory \(\displaystyle{ B_n}\), na mocy ich definicji, gdyż są to coraz to dłuższe sumy skończonie wielu zbiorów , więc zbiory \(\displaystyle{ \left( B_n\right) _{n \in \NN}}\), tworzą łańcuch przedziałów w \(\displaystyle{ X}\). A zatem, na mocy faktu z podanego linku: suma \(\displaystyle{ \bigcup_{n \in \NN} B_n}\) jest przedziałem w \(\displaystyle{ X}\).

Ale:

\(\displaystyle{ \bigcup_{n \in \NN} B_n= B_0 \cup B_1 \cup B_2 \cup \ldots= A_0 \cup \left( A_0 \cup A_1\right) \cup \left( A_0 \cup A_1 \cup A_2\right) \cup \ldots= A_0 \cup A_1 \cup A_2 \cup \ldots= \bigcup_{n \in \NN} A_n,}\)

czyli również suma \(\displaystyle{ \bigcup_{n \in \NN} A_n}\) jest przedziałem w \(\displaystyle{ X.\square}\)


Na mocy faktu z linku, mówiącego, że w zbiorze liczb wymiernych zbiorami wypukłymi są dokładnie przedziały (w
\(\displaystyle{ \left(\QQ, \le \right)}\) ), więc, z powyższego twierdzenia, otrzymamy fakt, mówiący, że jeśli w zbiorze liczb wymiernych mamy ciąg zbiorów wypukłych, taki, że każdy zbiór wypukły z tego ciągu przecina się z następnym, to suma tego ciągu zbiorów jest zbiorem wypukłym.

Dodano po 1 miesiącu 8 dniach 20 godzinach 21 minutach 10 sekundach:

Udowodniłem [...], że jeśli mamy dwa zbiory liniowo uporządkowane \(\displaystyle{ \left( X, \le _X\right) ; \left( Y, \le _Y\right) }\) tak, że zbiory \(\displaystyle{ X, Y}\) są rozłączne (wtedy na \(\displaystyle{ X \cup Y}\) możemy rozważać sumę porządkową tych dwóch porządków), jeśli zbiór \(\displaystyle{ A\subset X}\) jest resztą w \(\displaystyle{ X}\), a zbiór \(\displaystyle{ B\subset Y}\) jest przedziałem początkowym w \(\displaystyle{ Y}\), to \(\displaystyle{ A \cup B}\) jest przedziałem w \(\displaystyle{ X \cup Y}\) ze sumą porządkową.

Widzę, że ani nie zilustrowałem tego faktu (co tym razem jest ciężko zrobić), ...

Okazuje się, że ten fakt da się zilustrować. Skoro rozważamy tutaj tylko sumę porządkową \(\displaystyle{ X \cup Y}\) zbiorów \(\displaystyle{ X}\) i \(\displaystyle{ Y}\) , to tych elementów 'na przerwie między nimi' nie ma. A skoro ich nie ma, to możemy 'zlepić' tą resztę z tym przedziałem początkowym otrzymując przedział, oto ilustracja tego faktu: \(\displaystyle{ \\}\)

Udowodniłem też ostatnio prawo zbiorów:

\(\displaystyle{ \left( X\oplus Y \right) \times Z = \left( X \times Z\right) \oplus \left( Y \times Z\right) ,}\)

wykorzystując proste prawo różnicy symetrycznej \(\displaystyle{ \left( A\oplus B\right) = \left( A \cup B\right) \setminus \left( A \cap B\right) }\), oraz wykorzystując znane prawa rozdzielności sumy, przekroju i różnicy względem iloczynu kartezjańskiego, oto:

DOWÓD TEGO FAKTU:

\(\displaystyle{ \left( X \times Z\right) \oplus \left( Y \times Z\right) \stackrel{A\oplus B=\left( A \cup B\right) \setminus \left( A \cap B\right) }{=} \left[ \left( X \times Z\right) \cup \left( Y \times Z\right) \right] \setminus \left[ \left( X \times Z\right) \cap \left( Y \times Z\right) \right]=\\ = \left[ \left( X \cup Y\right) \times Z\right] \setminus \left[ \left( X \cap Y\right) \times Z \right]= \left[ \left( X \cup Y\right) \setminus \left( X \cap Y\right) \right] \times Z= \left( X\oplus Y \right) \times Z. \square}\)