Rodzina zbiorów zamknięta na sumę mnogościową uporządkowana inkluzją

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Jakub Gurak
Użytkownik
Użytkownik
Posty: 1392
Rejestracja: 20 lip 2012, o 21:19
Płeć: Mężczyzna
Lokalizacja: Rzeszów
Podziękował: 60 razy
Pomógł: 83 razy

Rodzina zbiorów zamknięta na sumę mnogościową uporządkowana inkluzją

Post autor: Jakub Gurak »

Udowodniłem ostatnio, że jeśli \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\) zamkniętą na sumę dwóch zbiorów, to w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B},\subset\right) }\), wtedy każdy skończony niepusty podzbiór ma supremum. Udowodniłem też, że jeśli \(\displaystyle{ X}\) zbiorem, a \(\displaystyle{ \mathbb{B}}\) rodziną zbiorów zamkniętą na sumę rodziny zbiorów, to w \(\displaystyle{ \left( \mathbb{B},\subset\right) }\) jest element największy, którym jest \(\displaystyle{ \bigcup\mathbb{B}}\). Podobnie, jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \mathbb{B}}\) niepustą rodziną zbiorów zamkniętą na przekroje rodziny zbiorów, to w \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\) jest element najmniejszy, jest nim \(\displaystyle{ \bigcap\mathbb{B}.}\) Udowodniłem też, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem uporządkowanym, to zbiór jego wszystkich elementów maksymalnych jest antyłańcuchem, podobnie zbiór wszystkich elementów minimalnych zbioru \(\displaystyle{ X}\) jest antyłańcuchem. Udowodniłem też prosto, że jeśli \(\displaystyle{ X}\) jest niepustym zbiorem, a rodzina \(\displaystyle{ \mathbb{B}}\) rozkładem zbioru \(\displaystyle{ X}\), to dla zbioru uporządkowanego \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\) mamy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest antyłańcuchem pod względem inkluzji. Przedstawię teraz dowody tych prostych faktów.

Przypomnijmy, rodzinę \(\displaystyle{ \mathbb{B}}\) podzbiorów zbioru \(\displaystyle{ X,}\) nazywamy zamkniętą na sumę dwóch zbiorów, gdy z każdymi dwoma zbiorami \(\displaystyle{ A,B\in\mathbb{B}}\) tej rodziny, również suma \(\displaystyle{ A \cup B}\) jest elementem \(\displaystyle{ \mathbb{B}.}\)

Wykażemy teraz, że jeśli \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\) zamkniętą na sumę dwóch zbiorów, to w zbiorze uporządkowanym \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\), każdy niepusty skończony podzbiór \(\displaystyle{ \mathbb{A}}\) ma supremum.

Niech \(\displaystyle{ \left\{ \right\} \neq \mathbb{A}}\) będzie niepustym skończonym podzbiorem.

Podajmy najpierw lemat.

Lemat 0. \(\displaystyle{ \bigcup\mathbb{A}\in\mathbb{B}.}\)

Dowód lematu.

Dowód jest indukcyjny ze względu na ilość elementów \(\displaystyle{ \mathbb{A}.}\)

Jeśli \(\displaystyle{ \left|\mathbb{A}\right| =1}\)- rodzina \(\displaystyle{ \mathbb{A}}\) ma tylko jeden zbiór, to niech \(\displaystyle{ \mathbb{A}=\left\{ A\right\}}\), wtedy \(\displaystyle{ \bigcup\mathbb{A}= \bigcup\left\{ A\right\} =A\in\mathbb{B}}\) (bo \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\)).

Jeśli \(\displaystyle{ \left| \mathbb{A}\right|=2}\), to niech \(\displaystyle{ \mathbb{A}=\left\{ A_1,A_2\right\}}\), gdzie \(\displaystyle{ A_1,A_2 \in\mathbb{B}}\), wtedy \(\displaystyle{ \bigcup\mathbb{A}= \bigcup\left\{ A_1,A_2\right\}=A_1 \cup A_2}\), i ponieważ \(\displaystyle{ A_1,A_2\in\mathbb{B}}\), a rodzina \(\displaystyle{ \mathbb{B}}\) jest zamknięta na sumę dwóch zbiorów, więc również \(\displaystyle{ A_1 \cup A_2 \in\mathbb{B}}\), czyli \(\displaystyle{ \bigcup\mathbb{A}\in\mathbb{B}.}\)

Krok indukcyjny: Przypuśćmy, że warunek zachodzi dla \(\displaystyle{ n \ge 2.}\) Pokażemy, że zachodzi dla \(\displaystyle{ (n+1).}\)

W tym celu załóżmy, że \(\displaystyle{ \left| \mathbb{A} \right| =n+1.}\) Niech \(\displaystyle{ \mathbb{A}=\left\{ A_1,A_2,\ldots,A_n,A_{n+1}\right\} \subset \mathbb{B}.}\) Wtedy \(\displaystyle{ \bigcup\mathbb{A}=A_1 \cup A_2 \cup \ldots \cup A_n \cup A_{n+1}=\left( A_1 \cup A_2\cup \ldots \cup A_n\right) \cup A_{n+1}= \bigcup\left\{ A_1,A_2,\ldots,A_n\right\} \cup A_{n+1}.}\) Teraz do rodziny \(\displaystyle{ \left\{ A_1,A_2, \ldots, A_n\right\}}\) możemy zastosować założenie indukcyjne i dostać, że \(\displaystyle{ \bigcup\left\{ A_1,A_2,\ldots,A_n\right\} \in\mathbb{B}}\), wtedy \(\displaystyle{ \bigcup\mathbb{A}= \bigcup\left\{ A_1,A_2,\ldots,A_n\right\} \cup A_{n+1},}\) i ponieważ również \(\displaystyle{ A_{n+1}\in\mathbb{B}}\), a rodzina \(\displaystyle{ \mathbb{B}}\) jest zamknięta na sumę, więc \(\displaystyle{ \bigcup\mathbb{A}\in\mathbb{B}}\). Krok indukcyjny został dowiedziony. Zasada indukcji matematycznej powoduje, że lemat jest udowodniony.

Łatwo teraz zakończyć nasz dowód:

Na mocy lematu 0: \(\displaystyle{ \bigcup\mathbb{A}\in\mathbb{B}}\), czyli suma \(\displaystyle{ \bigcup\mathbb{A}}\) jest elementem zbioru uporządkowanego \(\displaystyle{ \left( \mathbb{B}, \subset \right) }\), a zatem na mocy podstawowego faktu o tym, gdy suma rodziny zbiorów jest supremum, otrzymujemy, że: \(\displaystyle{ \bigcup \mathbb{A}= \bigvee \mathbb{A}}\)- suma rodziny \(\displaystyle{ \mathbb{A}}\) jest jej supremum. \(\displaystyle{ \square}\)

Przypomnijmy, że rodzina \(\displaystyle{ \mathbb{B}}\) podzbiorów zbioru \(\displaystyle{ X}\) jest zamknięta na dowolne sumowanie, gdy z każdym niepustym zbiorem \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) również \(\displaystyle{ \bigcup\mathbb{A}\in\mathbb{B}.}\)

Przykładem rodziny zamkniętej na dowolne sumowanie jest, dla zbioru \(\displaystyle{ X}\), jest nią rodzina wszystkich relacji symetrycznych w zbiorze \(\displaystyle{ X}\)( suma rodziny relacji symetrycznych jest relacją symetryczną). Nawiasem mówiąc, jest ona zamknięta na wszystkie działania mnogościowe (tzn. również na przekrój rodziny zbiorów, na różnicę, różnicę symetryczną i dopełnienie (do kwadratu \(\displaystyle{ X \times X}\)) ), i nie jest to zbiór potęgowy pewnego zbioru, jest to rodzina niektórych podzbiorów \(\displaystyle{ X \times X}\). Innym przykładem może być, dla zbioru liniowo uporządkowanego \(\displaystyle{ \left( X, \le\right), }\) można wziąć rodzinę wszystkich reszt w \(\displaystyle{ X}\) (suma niepustej rodziny reszt jest resztą).

Wykażemy teraz, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}}\) niepustą rodziną podzbiorów \(\displaystyle{ X}\) zamknięta na dowolne sumowanie, to w \(\displaystyle{ \left( \mathbb{B},\subset\right) }\) mamy:

\(\displaystyle{ \bigcup\mathbb{B}=\max \mathbb{B},}\)

czyli \(\displaystyle{ \bigcup\mathbb{B}}\) jest elementem największym \(\displaystyle{ \mathbb{B}}\).

Prosty dowód:

Ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) jest zamknięta na dowolne sumowanie, więc \(\displaystyle{ \bigcup\mathbb{B}\in\mathbb{B}}\), czyli suma \(\displaystyle{ \bigcup\mathbb{B}}\) jest elementem zbioru uporządkowanego \(\displaystyle{ \left( \mathbb{B}, \subset\right) }\). Ponadto jeśli \(\displaystyle{ A\in\mathbb{B}}\), to z własności sumy: \(\displaystyle{ \bigcup\mathbb{B} \supset A}\), czyli \(\displaystyle{ \bigcup\mathbb{B}}\) jest większa pod względem inkluzki od \(\displaystyle{ A}\), co wobec dowolności \(\displaystyle{ A\in\mathbb{B},}\) oznacza, że \(\displaystyle{ \bigcup\mathbb{B}=\max \mathbb{B}}\)- jest to największy zbiór w \(\displaystyle{ \mathbb{B}.\square}\)

Zauważmy, że w rodzinie \(\displaystyle{ \mathbb{B}}\) zamkniętej na dowolne sumowanie, jeśli \(\displaystyle{ \left\{ \right\} \neq \mathbb{A}\subset \mathbb{B}}\) jest niepustym podzbiorem , to \(\displaystyle{ \mathbb{A}}\) ma supremum, gdyż ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) jest zamknięta na każde sumowanie, więc \(\displaystyle{ \bigcup\mathbb{A} \in\mathbb{B}}\), czyli suma \(\displaystyle{ \bigcup\mathbb{A} }\) jest elementem zbioru uporządkowanego \(\displaystyle{ \left( \mathbb{B},\subset\right) }\), a zatem \(\displaystyle{ \bigcup\mathbb{A}= \bigvee \mathbb{A}}\)- suma rodziny \(\displaystyle{ \mathbb{A}}\) jest jej supremum\(\displaystyle{ .\square}\)

Podobne fakty wykażemy dla rodziny zbiorów zamkniętej na dowolne przekroje mnogościowe. Przypomnijmy najpierw, że:

Jeśli \(\displaystyle{ \mathbb{B}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), to rodzina \(\displaystyle{ \mathbb{B}}\) jest zamknięta na dowolne przekroje mnogościowe, gdy z każdym niepustym zbiorem \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) również \(\displaystyle{ \bigcap\mathbb{A}\in\mathbb{B}.}\)

Przykładem rodziny zamkniętej na przekroje mnogościowe może być, jak już wspomniałem, rodzina wszystkich relacji symetrycznych zbioru \(\displaystyle{ X}\) (przekrój niepustej rodziny relacji symetrycznych jest relacją symetryczną), albo rodzina wszystkich relacji zwrotnych ( przekrój niepustej rodziny relacji zwrotnych oczywiście jest relacją zwrotną) albo dla zbioru liniowo uporządkowanego rodzina wszystkich jego przedziałów początkowych jest zamknięta na przekroje (przekrój niepustej rodziny przedziałów początkowych jest przedziałem początkowym).

Wykażemy teraz, że jeśli \(\displaystyle{ X}\) jest zbiorem, a \(\displaystyle{ \left\{ \right\} \neq \mathbb{B}}\) niepustą rodziną zbiorów zamkniętą na dowolne przekroje, to w zbiorze uporzadkowanym \(\displaystyle{ \left( \mathbb{B},\subset\right) }\), mamy:

\(\displaystyle{ \bigcap\mathbb{B}=\min \mathbb{B}}\),

przekrój całej rodziny \(\displaystyle{ \mathbb{B}}\) jest jej zbiorem najmniejszym.

Prosty dowód:

Ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) jest zamknięta na dowolne przekroje, więc \(\displaystyle{ \bigcap\mathbb{B}\in\mathbb{B}}\). A jeśli \(\displaystyle{ A\in \mathbb{B}}\), to z własności przekroju mnogościowego \(\displaystyle{ \bigcap\mathbb{B}\subset A}\). Czyli przekrój \(\displaystyle{ \bigcap\mathbb{B}}\) jest elementem \(\displaystyle{ \mathbb{B}}\) mniejszym, pod względem inkluzji, od każdego zbioru w \(\displaystyle{ \mathbb{B}}\), a zatem jest elementem najmniejszym \(\displaystyle{ \mathbb{B}.
}\)


Udowodnimy teraz, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem uporządkowanym, a \(\displaystyle{ A=\left\{ x\in X: \ \ x \hbox{ jest maksymalny } \right\}}\) zbiorem wszystkich elementów maksymalnych, to \(\displaystyle{ A}\) jest antyłańcuchem (nie koniecznie maksymalnym).

Dowód:

Niech \(\displaystyle{ a,b\in A}\) będą różnymi elementami \(\displaystyle{ A.}\)

Przypuśćmy, że \(\displaystyle{ a<b}\). Ponieważ \(\displaystyle{ a,b\in A}\), to \(\displaystyle{ a}\) jest maksymalny, więc ponieważ \(\displaystyle{ b>a}\), i \(\displaystyle{ b\in X}\) otrzymujemy sprzeczność, gdyż, z definicji elementu maksymalnego \(\displaystyle{ a}\), nie ma elementów zbioru \(\displaystyle{ X}\) silnie większych od \(\displaystyle{ a}\)- a tu jest nim element \(\displaystyle{ b}\)- sprzeczność.

Jeśli \(\displaystyle{ b<a}\), to analogicznie otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ a\not<b}\) i \(\displaystyle{ b\not<a}\), czyli elementy \(\displaystyle{ a,b}\) są nieporównywalne. Z dowolności wyboru tych elementów otrzymujemy, że zbiór \(\displaystyle{ A}\) jest antyłańcuchem.

Wykażemy teraz, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem uporządkowanym, a \(\displaystyle{ A}\) zbiorem jego wszystkich elementów minimalnych, to \(\displaystyle{ A}\) jest antyłańcuchem (nie koniecznie maksymalnym).

Przypomnijmy najpierw prosty fakt, że jeśli \(\displaystyle{ (X,R)}\) jest zbiorem uporządkowanym, a zbiór \(\displaystyle{ A\subset X}\) jest antyłańcuchem względem \(\displaystyle{ R}\), to \(\displaystyle{ A}\) jest antyłańcuchem również względem porządku odwrotnego \(\displaystyle{ R^{-1}}\), łatwo to można sprawdzić.

Możemy zatem udowodnić nasz poprzedni fakt:

\(\displaystyle{ A=\left\{ x\in X: x \hbox{ jest minimalny }\right\}=\left\{ x\in X: x \hbox{ jest maksymalny względem } \le ^{-1} \right\}}\),

i teraz ponieważ \(\displaystyle{ (X, \le ^{-1} )}\) jest zbiorem uporządkowanym, więc z poprzednio powyżej udowodnionego faktu, więc ten zbiór jest antyłańcuchem względem \(\displaystyle{ \le ^{-1}}\), czyli \(\displaystyle{ A}\) jest antyłańcuchem względem \(\displaystyle{ \le ^{-1}}\), więc na mocy przytoczonego lematu powyżej zbiór \(\displaystyle{ A}\) jest antyłańcuchem względem \(\displaystyle{ \left( \le ^{-1}\right) ^{-1}= \le. \square}\)

Wykażemy teraz, że jeśli \(\displaystyle{ X}\) jest zbiorem niepustym, a rodzina \(\displaystyle{ \mathbb{B}}\) pozbiorów zbioru \(\displaystyle{ X}\) jest rozkładem, to zbiór uporządkowany \(\displaystyle{ (\mathbb{B},\subset)}\) jest antyłańcuchem( tzn. zbiór \(\displaystyle{ \mathbb{B}}\) jest antyłańcuchem względem inkluzji).

Niech zbiory \(\displaystyle{ A,B\in\mathbb{B}}\) będą różne-\(\displaystyle{ A \neq B.}\) Ponieważ \(\displaystyle{ \mathbb{B}}\) jest rozkladem, to zbiory \(\displaystyle{ A,B}\) są rozłączne, a zatem \(\displaystyle{ A \cap B=\emptyset.}\)

Jeśli \(\displaystyle{ A\subset B}\), to \(\displaystyle{ A \cap B=A=\emptyset}\), ale \(\displaystyle{ A\in\mathbb{B}}\), a rodzina \(\displaystyle{ \mathbb{B}}\) jest rozkładem, więc zbiór \(\displaystyle{ A}\) musi być niepusty- sprzeczność.

Jeśli \(\displaystyle{ B\subset A}\), to analogicznie otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ A\not\subset B}\) i \(\displaystyle{ B\not\subset A}\), czyli zbiory \(\displaystyle{ A,B}\) są nieporównywalne pod względem inkluzji. Z dowolności wyboru tych zbiorów otrzymujemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest antyłańcuchem.

Na koniec podam taki prosty fakt, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem liniowo uporządkowanym, a para jego podzbiorów \(\displaystyle{ (A,B)}\) jest przekrojem Dedekinda, to rodzina dwuzbiorowa \(\displaystyle{ \left\{ A,B\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\).
Dowód i wyjaśnienie:    
:lol: :D
ODPOWIEDZ