Teoria mocy zbiorów

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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

No bo funkcja niemalejąca, to taka, że wraz ze wzrostem argumentu wartości funkcji rosną lub są równe, nie mogą zmaleć. Wystarczy zatem, że tylko w jednym punkcie dziedziny zmaleją wartości funkcji i już nie jest niemalejąca, nie znaczy to jednak, że jest malejąca, bo wtedy taka funkcja by musiała w każdym punkcie (wraz ze wzrostem argumentu ) maleć, więc jest to dużo silniejszy warunek, tak myślę.

Więc jako kontrprzykład wystarczy jako dziedzinę funkcji wziąć pewien zbiór trzy-elementowy, i funkcję która z pierwszego punktu dziedziny do drugiego maleje, a z drugiego punktu do trzeciego rośnie. Wtedy, ponieważ z pierwszego punktu dziedziny do drugiego funkcja zmalała, to nie jest niemalejąca, i oczywiście nie jest malejąca. 8-)
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

W ostatni czwartkowy wieczór udało się ukończyć pracę nad pewnym ciekawym problemem. Udowodniłem, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest skończonym niepustym zbiorem liniowo uporządkowanym \(\displaystyle{ n}\)-elementowym, to ilość rozkładów zbioru \(\displaystyle{ X}\) na przedziały wynosi dokładnie \(\displaystyle{ 2 ^{n-1}}\) (będzie można zastanowić się czy takie rozkłady odpowiadają wszystkim podzbiorom pewnego zbioru \(\displaystyle{ (n-1)}\)- elementowego). Przedstawię teraz poniżej dowód tego ciekawego faktu.


Niech \(\displaystyle{ \left( X, \le\right) }\) będzie skończonym niepustym zbiorem liniowo uporządkowanym \(\displaystyle{ n}\)-elementowym. Oznaczmy zatem \(\displaystyle{ X=\left\{ x_1, x_2, \ldots, x_n\right\}.}\) Rozważmy rodzinę rozkładów \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ \mathcal{R}: \ \mathcal{R} \hbox{ jest rozkładem zbioru } X \hbox{ na przedziały}\right\},}\)

rozkładem na przedziały, tzn. każdy zbiór \(\displaystyle{ A\in\mathcal {R}}\) jest przedziałem w \(\displaystyle{ X}\), gdyż przypominam, że w zbiorze liniowo uporządkowanym można rozważać pojęcie przedziału- zbiór \(\displaystyle{ A\subset X}\) jest przedziałem, gdy z każdymi dwoma elementami zbioru \(\displaystyle{ A}\), każdy pośredni element zbioru liniowo uporządkowanego \(\displaystyle{ X}\) należy do tego przedziału \(\displaystyle{ A}\).

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


DOWÓD:

Niech \(\displaystyle{ i\in \left\{ 1,2,\ldots, n\right\}}\), i rozważmy rodzinę \(\displaystyle{ \mathbb{B}_i}\), rodzinę rozkładów z \(\displaystyle{ \mathbb{B}}\) na dokładnie \(\displaystyle{ i}\) zbiorów, tzn.

\(\displaystyle{ \mathbb{B}_i=\left\{ \mathcal{R}\in\mathbb{B}\Bigl| \ \ \left| \mathcal {R}\right|=i \right\} .}\)

I rozważmy rodzinę \(\displaystyle{ i}\)-elementowych ciągów liczb naturalnych daną jako:

\(\displaystyle{ \mathbb{A}_i=\left\{ \left( a_1, a_2,\ldots, a_i\right)\Bigl| \ \ a_1+a_2+\ldots +a_i= n-i \right\} .}\)

I będziemy chcieli pokazać, że rodzina \(\displaystyle{ \mathbb{A}_i}\) jest równoliczna z rodziną \(\displaystyle{ \mathbb{B}_i}\), (no bo rozkład na \(\displaystyle{ i}\) zbiorów musi być rozkładem na zbiory niepuste, więc każdemu z tych \(\displaystyle{ i}\) zbiorów musimy przydzielić po przynajmniej jednym elemencie, ponieważ ma to być rozkład zbioru \(\displaystyle{ n}\)-elementowego, to w sumie musimy rozdzielić te \(\displaystyle{ n}\)-elementów na te \(\displaystyle{ i}\)-zbiorów, więc musimy przydzielić każdemu z tych \(\displaystyle{ i}\) zbiorów po jednym elemencie, a dalej elementy rozdzielić możemy w sposób dowolny, tylko tak, żeby wszystkie z tych \(\displaystyle{ n}\) elementów rozdzielić, czyli suma tych dodanych 'ilości' elementów musi dawać pozostałe elementy, których jest \(\displaystyle{ (n-i)}\) ).


Wykażemy, że \(\displaystyle{ \mathbb{A}_i\sim \mathbb{B}_i.}\)

W tym celu definiujemy funkcję \(\displaystyle{ \alpha : \mathbb{A}_i \rightarrow \mathbb{B}_i}\) w poniższy sposób:

Niech \(\displaystyle{ \left( a_1, a_2,\ldots, a_i\right) \in \mathbb{A}_i}\). Wtedy definiujemy zbiory \(\displaystyle{ B_1, B_2,\ldots, B_i}\), tzn.

\(\displaystyle{ B_1=\left[ x_1, x _{1+a_1} \right]= \left\{ x\in X: \ x_1 \le x \le x _{1+a_1} \right\}.}\)

Ponieważ \(\displaystyle{ a_1\in\NN}\), więc \(\displaystyle{ 1+a_1 \ge 1}\), i \(\displaystyle{ x_1 \le x _{1+a_1}}\), a więc jest to właściwy- tzn. niepusty- przedział domknięty w zbiorze \(\displaystyle{ X.}\)

Dalej zbiory \(\displaystyle{ B_k}\) definiujemy indukcyjnie. Tzn. przypuśćmy, że dla \(\displaystyle{ k<i}\) mamy zdefiniowany zbiór \(\displaystyle{ B_k =\left[ x _{c_k ^{-} }, x _{c_K ^{+} } \right]}\) , gdzie \(\displaystyle{ c _{k} ^{-}, c_k ^{+} \in \left\{ 1,2,\ldots, n\right\},}\) i \(\displaystyle{ c_k ^{-} \le c_k ^{+}}\), wtedy definiujemy zbiór \(\displaystyle{ B _{k+1}}\), dany jako:

\(\displaystyle{ B _{k+1}=\left[ x _{c_k ^{+} +1 }, x _{\left( c_k ^{+}+1+ a _{k+1} \right) } \right]. }\)

czyli: \(\displaystyle{ B_2=\left[ x _{a_1+2}, x _{\left( a_1+2+a_2\right) }=x _{\left( a_1+a_2+2\right) } \right]}\), i dalej

\(\displaystyle{ B_3=\left[ x _{\left( a_1+a_2+3\right) } , x _{\left( a_1+a_2+3+a_3\right) }= x _{\left( a_1+a_2+a_3+3\right) } \right]}\) ,

i łatwo pokazać przez indukcję ograniczoną (i przyjmując, że \(\displaystyle{ a_0=0}\) ), że dla każdego \(\displaystyle{ k \in \left\{ 1,2,\ldots, i\right\}}\), mamy :

\(\displaystyle{ B_k=\left[ x _{\left( a_0+a_1+\ldots + a _{k-1} \right)+k }, x _{\left( a_0+a_1+\ldots+ a_k\right)+k } \right].}\)

i mamy, ponieważ \(\displaystyle{ a_1+a_2+\ldots+a_i=n-i}\), więc:

\(\displaystyle{ 1 \le a_0+a_1+\ldots+a_k+k \le 0+\underbrace {a_1 +a_2+\ldots +a_i}_{=n-i}+k= \left( n-i\right)+k= n+\left( k-i\right) \stackrel{k \le i} { \le} n.}\)

A zatem \(\displaystyle{ 1 \le a_0+a_1+\ldots +a_k+k \le n}\), czyli dla zbioru \(\displaystyle{ B_k}\), przedziału domkniętego numer prawego końca tego przedziału, jego numer należy do zbioru \(\displaystyle{ \left\{ 1,2, \ldots,n\right\}}\), jak trzeba, i tym bardziej numer lewego końca tego przedziału należy do zbioru \(\displaystyle{ \left\{ 1,2,\ldots,n\right\}}\), jak trzeba, i ponieważ \(\displaystyle{ a_k\in\NN}\), więc numer lewego końca tego przedziału jest mniejszy lub równy od numeru prawego końca tego przedziału, a więc zbiór \(\displaystyle{ B_k }\) jest we właściwej postaci przedziału domkniętego, a więc zbiór \(\displaystyle{ B_k}\) jest przedziałem w zbiorze \(\displaystyle{ X}\).

I otrzymujemy, że skończony ciąg zbiorów \(\displaystyle{ B_1, B_2,\ldots, B_i}\) tworzy ciąg przedziałów w zbiorze \(\displaystyle{ X.}\)

I rozważmy rodzinę zbiorów \(\displaystyle{ \left\{ B_1, B_2,\ldots, B_i\right\}}\)- jest to rodzina podzbiorów zbioru \(\displaystyle{ X}\).

Wykażemy, że jest ona rozkładem zbioru \(\displaystyle{ X}\).

Mamy:

\(\displaystyle{ \bigcup \left\{ B_1, B_2,\ldots, B_i\right\}=B_1 \cup B_2 \cup \ldots \cup B_i=\left[ x_1, x _{\left( 1+a_1\right) } \right] \cup \left[ x _{\left( a_1+2\right) }, x _{\left( a_1+a_2+2\right) } \right] \cup \left[ x _{\left( a_1+a_2+3\right) } , x _{\left( a_1+a_2+a_3+3\right) } \right] \cup \ldots \\ \cup \left[ x _{\left( a_0+a_1+\ldots +a _{i-1} \right)+i }, x _{\left( a_0+a_1+\ldots +a_i +i\right) } \right]=}\),

i ponieważ \(\displaystyle{ a_0=0}\), a \(\displaystyle{ a_1+a+2+\ldots+a_i=n-i}\), więc dla tego ostatniego zbioru numer prawego końca tego przedziału domkniętego wynosi dokładnie \(\displaystyle{ n}\), więc cała ta suma wynosi:

\(\displaystyle{ =\left\{ x_1, x_2,\ldots, x_n\right\} =X.}\)

Czyli \(\displaystyle{ \bigcup\left\{ B_1, B_2,\ldots, B_i\right\}=X.}\)

Należy teraz pokazać, że zbiory \(\displaystyle{ B_j, B_k}\), dla \(\displaystyle{ j \neq k}\) są rozłączne.
Może w skrócie, gdyż bardziej jest to żmudne niż trudne. Jeśli \(\displaystyle{ j \neq k}\), to \(\displaystyle{ j<k}\) lub \(\displaystyle{ k<j}\).

Jeśli \(\displaystyle{ j<k}\), to oznaczając (upraszczając zapis) prawy koniec tego przedziału przez \(\displaystyle{ x _{j} ^{+}}\), a lewy koniec przedziału \(\displaystyle{ B_k}\) przez \(\displaystyle{ x_k ^{-}}\), to rozpisując ze wzoru indukcyjnego postaci tych przedziałów domkniętych pokazujemy, że \(\displaystyle{ x_j ^{+}<x_k ^{-}}\), a stąd łatwo, dowodem nie wprost pokazać, że zbiory \(\displaystyle{ B_j, B_k}\) są rozłączne.

Jeśli \(\displaystyle{ k<j}\), to rozumujemy analogicznie, tzn. pokazujemy, że \(\displaystyle{ x_k ^{+}<x_j ^{-}}\), i dalej łatwo nie wprost wykazać rozłączność zbiorów \(\displaystyle{ B_j, B_k}\).

Wobec czego zbiory \(\displaystyle{ B_j, B_k}\), dla \(\displaystyle{ j \neq k}\) są rozłączne.

Zauważmy, że zbiory \(\displaystyle{ B_k}\) są niepuste- są to przedziały domknięte niepuste, gdyż już uzasadniliśmy, że lewy koniec każdego z takich przedziałów jest nie większy od prawego końca.

Wobec czego rodzina \(\displaystyle{ \left\{ B_1, B_2,\ldots, B_i\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\). Ponadto jest to rozkład na przedziały, a zatem \(\displaystyle{ \left\{ B_1, B_2,\ldots, B_i\right\} \in \mathbb{B}.
}\)


Zauważmy, że dla liczb naturalnych \(\displaystyle{ j,k \in \left\{ 1,2,\ldots, i \right\},}\) takich, że \(\displaystyle{ j \neq k}\) zbiory \(\displaystyle{ B_j, B_k}\) są rozłączne i niepuste, a zatem różne. Czyli \(\displaystyle{ B_j \neq B_k}\), dla \(\displaystyle{ j \neq k}\). Wobec czego \(\displaystyle{ \left| \left\{ B_1, B_2, \ldots, B_i \right\} \right|= i.}\) Wobec czego rodzina \(\displaystyle{ \left\{ B_1,B_2, \ldots, B_i\right\} \in\mathbb{B}_i,}\) i funkcja

\(\displaystyle{ \left( a_1, a_2, \ldots, a_i\right) \in\mathbb{A}_i \stackrel{ \alpha }{\rightarrow} \left\{ B_1, B_2,\ldots, B_i\right\} \in\mathbb{B}_i,}\)

jest dobrze określona.


Wykażemy, że taka funkcja jest bijekcją.

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

W tym celu weźmy dwa dowolne różne ciągi \(\displaystyle{ \left( a_1^1, a_2^1,\ldots, a_i^1 \right);\left( a_1^2, a_2^2, \ldots, a_i^2\right) \in\mathbb{A}_i }\), i pokażmy, że przypisane im rozkłady są różne, tzn. że: \(\displaystyle{ \left\{ B_1^1, B_2^1,\ldots, B_i^1\right\} \neq \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\} .}\)

Ponieważ te ciągi są różne, więc dla pewnego \(\displaystyle{ k \in \left\{ 1,2,\ldots,i\right\}}\), mamy: \(\displaystyle{ a_k^1 \neq a_k^2.}\)

Rozważmy zbiór \(\displaystyle{ S}\), dany jako:

\(\displaystyle{ S=\left\{ k \in \left\{ 1,2,\ldots, i\right\}\Bigl| \ \ a_k ^{1} \neq a_k^2 \right\} \neq \left\{ \right\}.}\)

Ponieważ, mamy, że dla pewnego \(\displaystyle{ k \in \left\{ 1,2,\ldots,i\right\}}\), mamy: \(\displaystyle{ a_k^1 \neq a_k^2}\), więc zbiór \(\displaystyle{ S }\) jest niepusty. Ponieważ ten zbiór jest niepusty, więc ma element najmniejszy \(\displaystyle{ k\in S}\). Ponieważ \(\displaystyle{ k\in S}\), więc \(\displaystyle{ a_k^1 \neq a_k^2.}\)

Jeśli \(\displaystyle{ k=1}\), to \(\displaystyle{ a_1^1 \neq a_1^2}\). A zatem \(\displaystyle{ a_1^1<a_1^2}\) lub \(\displaystyle{ a_1^2<a_1^1.}\)

Jeśli \(\displaystyle{ a_1^1<a_1^2}\), to ponieważ \(\displaystyle{ B_1^1=\left[ x_1, x _{\left( 1+a_1^1\right) } \right]}\) oraz \(\displaystyle{ B_1^2=\left[ x_1, x _{\left( 1+a_1^2\right) } \right]}\), więc łatwo jest uzasadnić, że \(\displaystyle{ B_1^1\subsetneq B_1^2}\), a zatem \(\displaystyle{ B_1^1\not\in \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\}}\)-

-gdyby bowiem byłoby: \(\displaystyle{ B_1^1\in \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\} }\), to \(\displaystyle{ B_1^1= B_l^2}\), gdzie \(\displaystyle{ l \in \left\{ 1,2,\ldots, i\right\}.}\) Ponieważ \(\displaystyle{ B_1^1 \neq B_1^2}\), więc \(\displaystyle{ l \neq 1.}\) Wtedy zbiór \(\displaystyle{ B_1^2}\) jest rozłączny ze zbiorem \(\displaystyle{ B_l^2}\), a więc \(\displaystyle{ B_1^2 \cap B_l^2=\emptyset.}\) Tymczasem, ponieważ \(\displaystyle{ B_1^1\subset B_1^2}\), więc \(\displaystyle{ B_1^2 \cap B_l^2= B_1^2 \cap B_1^1= B_1^1}\). Czyli \(\displaystyle{ B_1^1=\emptyset}\), a to jest zbiór rozkładu, więc musi byc niepusty-sprzeczność.

Wobec czego \(\displaystyle{ B_1^1\not\in \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\}}\), a oczywiście \(\displaystyle{ B_1^1\in \left\{ B_1^1, B_2^1,\ldots, B_i^1\right\}}\), a więc \(\displaystyle{ \left\{ B_1^1, B_2^1,\ldots, B_i^1\right\} \neq \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\}}\), co należało pokazać.

Jeśli \(\displaystyle{ a_1^2<a_1^1}\), to podobnie \(\displaystyle{ B_1^2\subsetneq B_1^1}\), wtedy \(\displaystyle{ B_1^2\not\in \left\{ B_1^1, B_2^1,\ldots, B_i^1\right\}}\), a więc \(\displaystyle{ \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\} \neq \left\{ B_1^1, B_2^1, \ldots, B_i^1\right\}}\), co należało pokazać.

Jeśli \(\displaystyle{ k \neq 1.}\) To dla każdego \(\displaystyle{ l\in\NN}\) takiego, że \(\displaystyle{ 1 \le l<k}\) mamy \(\displaystyle{ l\not\in S}\), bo element \(\displaystyle{ k}\) jest najmniejszy w \(\displaystyle{ S}\), a zatem \(\displaystyle{ l\not\in S;}\) i \(\displaystyle{ l \in \left\{ 1,2,\ldots, i\right\} }\), więc z definicji zbioru \(\displaystyle{ S}\) musi być: \(\displaystyle{ a_l^1=a_l^2}\). Łatwo, ale żmudnie (rozpisując wzory na postacie takich przedziałów) można pokazać przez indukcję, że: dla każdego \(\displaystyle{ 1 \le l<k}\), mamy: \(\displaystyle{ B_l^1= B_l^2}\). Ponieważ \(\displaystyle{ k\in S}\), więc \(\displaystyle{ a_k^1 \neq a_k^2}\). A zatem \(\displaystyle{ a_k^1<a_k^2}\) lub \(\displaystyle{ a_k^1>a_k^2.}\)

Jeśli \(\displaystyle{ a_k^1<a_k^2}\), to znowu rozpisując wzory na postacie tych przedziałów uzasadniamy, że \(\displaystyle{ B_k^1\subsetneq B_k^2}\), a zatem \(\displaystyle{ B_k^1\not\in\left\{ B_1^2, B_2^2, \ldots, B_i^2\right\}}\), a \(\displaystyle{ B_k^1\in \left\{ B_1^1, B_2^1,\ldots, B_i^1\right\} }\), wobec czego \(\displaystyle{ \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\} \neq
\left\{ B_1^1, B_2^1,\ldots, B_i^1\right\}}\)
, co należało pokazać.

Jeśli \(\displaystyle{ a_k^1>a_k^2}\), to podobnie \(\displaystyle{ B_k^1\supsetneq B_k^2}\), wtedy \(\displaystyle{ B_k^2\not\in \left\{ B_1^1,B_2^1, \ldots, B_i^1\right\}}\) , a \(\displaystyle{ B_k^2 \in \left\{ B_1^2, B_2^2,\ldots, B_i^2\right\}}\), wobec czego \(\displaystyle{ \left\{ B_1^2, B_2^2, \ldots, B_i^2\right\} \neq \left\{ B_1^1 , B_2^1,\ldots, B_i^1\right\}}\) , co należało pokazać.

Wobec czego funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. :lol:


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

Niech \(\displaystyle{ \mathcal{R}\in \mathbb{B}_i.}\)

Zacznijmy od uporządkowania rozkładu \(\displaystyle{ \mathcal{R}}\), gdyż rozkład zbioru \(\displaystyle{ X}\), to rodzina podzbiorów zbioru \(\displaystyle{ X}\), a więc pewnego rodzaju zbiór takich podzbiorów, a każdy wie, że każdy zbiór, sam w sobie, jest nieuporządkowany. Musimy zatem tą rodzinę, ten rozkład, liniowo uporządkować. Definiujemy zatem relację \(\displaystyle{ \sqsubset}\) na tym rozkładzie \(\displaystyle{ \mathcal{R}.}\)

\(\displaystyle{ A \sqsubset B \Longleftrightarrow A\hbox{ poprzedza }B}\),

czyli jeden zbiór jest mniejszy od drugiego zbioru, gdy mniejszy zbiór poprzedza większy, tzn. zbiór \(\displaystyle{ A}\) poprzedza zbiór \(\displaystyle{ B,}\) gdy każdy element zbioru \(\displaystyle{ A}\) jest silnie mniejszy od każdego elementu zbioru \(\displaystyle{ B}\), względem naszego skończonego zbioru liniowo uporządkowanego \(\displaystyle{ X}\), tzn. ma zachodzić implikacja:

\(\displaystyle{ a\in A, b\in B \rightarrow a<b.}\)

Łatwo jest wykazać, że taka relacja jest relacją przeciwzwrotną i przechodnią. W związku z czym relacja \(\displaystyle{ \sqsubseteq}\) na rozkładzie \(\displaystyle{ \mathcal {R}}\), dana jako:

\(\displaystyle{ A\sqsubseteq B \Longleftrightarrow \hbox {zbiór } A \hbox{ poprzedza zbiór } B \hbox{ lub } A=B}\),

jest relacją porządku (jest to elementarna własność).

Wykażemy teraz, że relacja \(\displaystyle{ \sqsubseteq}\) jest relacją spójną.

Niech \(\displaystyle{ A,B\in\mathcal{R}}\), będą różnymi zbiorami. Ponieważ \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ X}\), to zbiory \(\displaystyle{ A,B}\) muszą być rozłączne. Jeśli zbiór \(\displaystyle{ A}\) poprzedza zbiór \(\displaystyle{ B}\), to \(\displaystyle{ A \sqsubseteq B}\), a więc te dwa zbiory da się porównać.

Jeśli zbiór \(\displaystyle{ A}\) nie poprzedza zbioru \(\displaystyle{ B}\), to ponieważ zbiory \(\displaystyle{ A, B}\), jako zbiory rozkładu, są niepuste, więc zaprzeczając temu warunkowi 'poprzedzania', więc otrzymujemy, że istnieje \(\displaystyle{ a\in A}\) takie, że istnieje \(\displaystyle{ b\in B}\), takie, że \(\displaystyle{ a\not< b}\). Ponieważ relacja \(\displaystyle{ \le}\) jest liniowym porządkiem, więc \(\displaystyle{ a \ge b}\). Ponieważ \(\displaystyle{ a\in A, b\in B}\), a zbiory \(\displaystyle{ A, B}\) są rozłączne, więc \(\displaystyle{ a \neq b}\), a więc \(\displaystyle{ a>b.}\) Wykażemy, że zbiór \(\displaystyle{ B}\) poprzedza zbiór \(\displaystyle{ A}\). W tym celu weźmy \(\displaystyle{ x\in A}\), oraz \(\displaystyle{ y\in B}\) i pokażmy, że \(\displaystyle{ y<x}\). Przypuśćmy, że tak nie jest. Wtedy \(\displaystyle{ y \ge x}\). Rozważmy kilka przypadków:

\(\displaystyle{ 1 ^{\circ}: x \ge b}\). Wtedy \(\displaystyle{ B\ni b\le x \le y\in B}\), a zbiór \(\displaystyle{ B}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ x\in B,}\) a \(\displaystyle{ x\in A}\), więc \(\displaystyle{ x\in A \cap B}\), a zbiory \(\displaystyle{ A}\) i \(\displaystyle{ B}\) są rozłączne- sprzeczność.

\(\displaystyle{ 2 ^{\circ}: x<b}\). Rozważmy podprzypadek gdy :

a) \(\displaystyle{ y \le a}\) , wtedy \(\displaystyle{ A\ni x \le y \le a\in A}\), a zbiór \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ y\in A}\), a \(\displaystyle{ y\in B}\) i zbiory \(\displaystyle{ A,B}\) są rozłączne- sprzeczność.

Pozostaje do rozważenia przyadek gdy:

b )\(\displaystyle{ x<b \hbox{ i } y>a}\), wtedy \(\displaystyle{ A\ni x<b<a\in A}\), a zbiór \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że: \(\displaystyle{ b\in A}\), a \(\displaystyle{ b\in B}\) i zbiory \(\displaystyle{ A, B}\) są rozłączne- sprzeczność.

Wobec czego musi być \(\displaystyle{ y<x}\), a więc zbiór \(\displaystyle{ B}\) poprzedza zbiór \(\displaystyle{ A}\). A więc \(\displaystyle{ B \sqsubseteq A}\). A więc zbiory \(\displaystyle{ A,B}\) da się porównać, i relacja \(\displaystyle{ \sqsubseteq}\) jest relacją spójną.

A więc relacja \(\displaystyle{ \sqsubseteq}\) jest liniowym porządkiem na rozkładzie \(\displaystyle{ \mathcal{R}}\), i para \(\displaystyle{ \left( \mathcal{R},\sqsubseteq \right)}\) jest zbiorem liniowo uporządkowanym.


Również \(\displaystyle{ \left| \mathcal{R}\right|= i}\). Zbiór \(\displaystyle{ C=\left\{ 1,2, \ldots, i\right\}}\) z naturalnym porządkiem jest zbiorem liniowo uporządkowanym mocy \(\displaystyle{ i }\). Zatem zbiór \(\displaystyle{ C}\) i rozkład \(\displaystyle{ \mathcal {R}}\) są równoliczne. A dwa zbiory liniowo uporządkowane skończone i równoliczne są podobne, wobec czego rozkład \(\displaystyle{ \mathcal {R}}\) jest podobny do zbioru \(\displaystyle{ C}\). Istnieje więc podobieństwo \(\displaystyle{ f:C=\left\{ 1,2,\ldots,i\right\} \rightarrow \mathcal{R}.}\) Wtedy \(\displaystyle{ f}\) jest bijekcją na zbiorze skończonym \(\displaystyle{ \left\{ 1,2,\ldots, i\right\}}\), oznaczmy więc \(\displaystyle{ \mathcal{R}=\left\{ B_1,B_2,\ldots, B_i\right\}}\), tzn. dla każdego \(\displaystyle{ j\in\left\{ 1,2,\ldots, i\right\} }\) oznaczmy:

\(\displaystyle{ f(j)=:B_j}\),

i nazwijmy taki zbiór \(\displaystyle{ j}\)-tym zbiorem rozkładu \(\displaystyle{ \mathcal {R}.}\)

Dla każdego ustalonego \(\displaystyle{ j \in \left\{ 1,2,\ldots, i \right\}}\) mamy, że zbiór \(\displaystyle{ B_j \neq \left\{ \right\}}\) jest niepustym podzbiorem zbioru \(\displaystyle{ X}\)- skończonego zbioru liniowo uporządkowanego, a zatem zbiór \(\displaystyle{ B_j}\) jest zbiorem skończonym i niepustym, więc zbiór \(\displaystyle{ B_j}\) ma element najmniejszy \(\displaystyle{ b_j ^{-} }\) i ma element największy \(\displaystyle{ b_j ^{+}}\), wtedy \(\displaystyle{ b_j ^{-}\in B_j\subset X}\) i \(\displaystyle{ b_j ^{+}\in B_j \subset X}\), oznaczmy więc \(\displaystyle{ b_j ^{-}= x _{k_j ^{-} }}\), i \(\displaystyle{ b_j ^{+}=x _{k_j ^{+} },}\) gdzie \(\displaystyle{ k_j ^{-} , k_j ^{+} \in \left\{ 1,2,\ldots, n\right\}}\). Ponieważ element \(\displaystyle{ b_j ^{-}}\) jest elementem najmniejszym zbioru \(\displaystyle{ B_j}\), więc \(\displaystyle{ b_j ^{-} \le b_j ^{+}}\), a więc \(\displaystyle{ k_j ^{-} \le k_j ^{+}}\), (gdyby byłoby \(\displaystyle{ k_j ^{-} >k_j ^{+}}\), to \(\displaystyle{ b_j ^{+}= x _{k_j ^{+} }< x _{k_j ^{-} }= b_j ^{-}}\), czyli \(\displaystyle{ b_j ^{+}< b _{j} ^{-}}\) -sprzeczność). Wobec czego \(\displaystyle{ k_j ^{-} \le k_j ^{+}}\), a więc:

\(\displaystyle{ \NN\ni a_j:= k_j ^{+}-k_j ^{-}}\),

i tak dla każdego \(\displaystyle{ j \in \left\{ 1,2,\ldots, i\right\} }\) definiujemy liczbę naturalną \(\displaystyle{ a_j}\), i otrzymujemy skończony ciąg:

\(\displaystyle{ \left( a_1,a_2,\ldots, a_i\right)\in\NN^i.}\)


Musimy teraz wykazać, że \(\displaystyle{ a_1+a_2+\ldots+a_i=n-i}\).

W tym celu wykażemy najpierw, że dla każdego \(\displaystyle{ j\in\left\{ 1,2,\ldots, i-1\right\}}\), mamy: \(\displaystyle{ 1+k_j ^{+}= k _{j+1} ^{-} }\).
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ a_1+a_2+\ldots+a_i= \sum_{j=1}^{i} a_j= \sum_{j=1}^{i} \left( k_j ^{+}-k_j ^{-} \right)=\left[ \sum_{j=1}^{i-1} \left( k _{j+1} ^{-}-1-k _{j} ^{-} \right) \right] +\left( k_i ^{+}-k_i ^{-} \right)=-\left( i-1\right) + \sum_{j=1}^{i-1} \left( k _{j+1} ^{-} -k_j ^{-} \right) +k_i ^{+}-k_i ^{-}= \\ =-\left( i-1\right) +\left[ \left( k_2 ^{-}- k_1 ^{-} \right) + \left( k_3 ^{-} -k_2 ^{-} \right)+\ldots+ \left( k_i ^{-} -k _{i-1} ^{-} \right) \right] + k_i ^{+}- k_i ^{-}= -i+1+\left[ k_i ^{-} -k_1 ^{-} \right] +k_i ^{+} -k_i ^{-}= -i+1-k_1 ^{-}+k_i ^{+} =}\)

Wykażemy jeszcze, że \(\displaystyle{ k_1 ^{-}=1.}\)
Dowód tego faktu::    
Analogicznie udowadniamy, że: \(\displaystyle{ k_i ^{+}=n.}\)

Wobec czego kontynuując otrzymywane równości otrzymujemy, że to jest równe :

\(\displaystyle{ =-i+1-1+n= n-i.}\)

a zatem \(\displaystyle{ a_1+a_2+\ldots+a_i= n-i }\), a więc \(\displaystyle{ \left( a_1,a_2,\ldots, a_i\right) \in \mathbb{A}_i.}\)

A zatem funkcja \(\displaystyle{ \alpha}\), na tym ciągu, zwraca zatem pewien rozkład \(\displaystyle{ \mathcal {R} ^{'}=\left\{ A_1,A_2,\ldots, A_i\right\} \in\mathbb{B}_i.}\)

Formalnie tak, ale zauważmy, że zgodnie z naszą konstrukcją, otrzymujemy najpierw \(\displaystyle{ i }\)-elementowy ciąg zbiorów \(\displaystyle{ \left( A_1, A_2,\ldots, A_i\right),}\) a dopiero potem rozkład \(\displaystyle{ \left\{ A_1, A_2, \ldots, A_i\right\}}\).

Wykażemy teraz, że dla każdego \(\displaystyle{ j \in \left\{ 1,2,\ldots, i\right\}}\), mamy: \(\displaystyle{ A_j=B_j}\).
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ \left( A_1, A_2, \ldots, A_i\right) = \left( B_1, B_2,\ldots, B_i\right)}\),

a zatem

\(\displaystyle{ \left\{ A_1, A_2,\ldots, A_i\right\} =\left( A_1, A_2, \ldots, A_i\right)_P = \left( B_1, B_2,\ldots, B_i\right)_P=\left\{ B_1,B_2,\ldots, B_i \right\}= \mathcal {R},}\)

czyli \(\displaystyle{ \mathcal {R} =\left\{ A_1, A_2,\ldots, A_i\right\} = \alpha \left( \left( a_1, a_2,\ldots, a_i\right) \right)}\), a więc rozkład \(\displaystyle{ \mathcal {R}}\) jest wartością funkcji \(\displaystyle{ \alpha.}\) Z dowolności wyboru takiego rozkładu otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.


A więc \(\displaystyle{ \alpha}\) jest bijekcją, a więc \(\displaystyle{ \mathbb{A}_i \sim \mathbb{B}_i.}\)

A zatem, na mocy tego co wykazał użytkownik Tmkk TUTAJ otrzymujemy : \(\displaystyle{ \left| \mathbb{B}_i\right| =\left| \mathbb{A}_i\right| = {n-1 \choose i-1}}\) , dla każdego \(\displaystyle{ i \ge 2}\) takiego, że \(\displaystyle{ i \le n}\).

Dla \(\displaystyle{ i=1}\) mamy \(\displaystyle{ \left| \mathbb{B}_1\right| =1,}\) tzn. musi być \(\displaystyle{ \mathcal{R}=\left\{ X\right\}}\), gdyż rozważamy rozkład na tylko jeden zbiór, a jeśli \(\displaystyle{ \mathcal{R}=\left\{ A\right\}}\), gdzie \(\displaystyle{ A\subset X}\), to z własności rozkładu \(\displaystyle{ \bigcup\mathcal {R}=X}\), czyli \(\displaystyle{ \bigcup\mathcal{R}= \bigcup\left\{ A\right\} =A =X}\). Wobec czego \(\displaystyle{ \mathcal R=\left\{ A\right\} =\left\{ X\right\}}\) , i wtedy \(\displaystyle{ \mathbb{B}_1=\left\{ \mathcal{R} \right\} }\), czyli \(\displaystyle{ \left|\mathbb{B}_1 \right|=1.}\)

Zauważmy jeszcze, że jeśli mamy dwa rozkłady \(\displaystyle{ \mathcal{R}_i \in \mathbb{B}_i,}\) i \(\displaystyle{ \mathcal{R}_j\in\mathbb{B}_j,}\) oraz \(\displaystyle{ i \neq j}\), to \(\displaystyle{ \mathcal{R}_i \neq \mathcal{R}_j}\). Gdyż wtedy rodzina \(\displaystyle{ \mathcal{R}_i}\) ma \(\displaystyle{ i}\) zbiorów, a rodzina \(\displaystyle{ \mathcal{R}_j}\) ma \(\displaystyle{ j}\) zbiorów, i \(\displaystyle{ i \neq j}\), a więc te rodziny mają inną ilość elementów, są więc różne: \(\displaystyle{ \mathcal {R}_i \neq \mathcal{R}_j}\). Zauważmy też, że dla \(\displaystyle{ m\in\NN}\) takiego, że \(\displaystyle{ m>n}\)- wtedy nie da się zbioru \(\displaystyle{ X}\) rozłożyć na \(\displaystyle{ m}\) zbiorów, gdyż nasz zbiór \(\displaystyle{ X}\) ma tylko \(\displaystyle{ n}\)-elementów.

Wobec czego ilość wszystkich rozkładów zbioru \(\displaystyle{ X}\) na przedziały wynosi, zgodnie z tym co uzasadnił użytkownik Tmkk w tym samym wątku, więc ta ilość wynosi :

\(\displaystyle{ 1+ \sum_{k=2}^{n} {n-1 \choose k-1}= 1+\left( 2 ^{n-1} -1\right) = 2 ^{n-1},}\) dla \(\displaystyle{ n \ge 2}\).

(Zauważmy jeszcze, że dla \(\displaystyle{ n=1}\), mamy \(\displaystyle{ 2 ^{0}=1}\), i wtedy dla zbioru \(\displaystyle{ X}\) postaci \(\displaystyle{ X=\left\{ x\right\}}\), gdzie \(\displaystyle{ x}\) jest pewnym elementem, to musi być \(\displaystyle{ \mathcal {R}= \left\{ X\right\} }\), a więc mamy \(\displaystyle{ 1=2 ^{0}}\) rozkładów).


Czyli dla niepustego skończonego zbioru liniowo uporządkowanego \(\displaystyle{ n}\)-elementowego istnieje dokładnie \(\displaystyle{ 2 ^{n-1}}\) rozkładów tego zbioru na przedziały.\(\displaystyle{ \square}\) :D :lol: 8-)
Ostatnio zmieniony 22 lut 2022, o 20:15 przez Jakub Gurak, łącznie zmieniany 1 raz.
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski »

Czytać mi się nie chce, ale zaproponuję krótszy dowód tego faktu:

Dla uproszczenia będziemy dzielić na przedziały liniowo uporządkowany (przez standardowy porządek) zbiór liczb naturalnych \(\displaystyle{ X=\{1,...n\}}\). Oczywiste jest, że liczba \(\displaystyle{ 1}\) jest początkiem pierwszego przedziału, a liczba \(\displaystyle{ n}\) końcem ostatniego przedziału. Teraz w stosunku do każdej z liczb ze zbioru \(\displaystyle{ \{1,...n-1\}}\) podejmuję niezależną decyzję, czy jest ona końcem pewnego przedziału w oczekiwanym rozkładzie, czy nie. W związku z tym mam ciągi \(\displaystyle{ n-1}\) decyzji binarnych, każdy z nich wyznacza inny podział zbioru \(\displaystyle{ X}\) i każdy podział zbioru \(\displaystyle{ X}\) powstaje w wyniku pewnego ciągu decyzji. Ciągów decyzji jest \(\displaystyle{ 2^{n-1}}\), więc podziałów też.

JK
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

Nie rozumiem, za mało to konkretne.

Rozumiem, że przez ciąg decyzji formalnie Pan rozumie dowolną funkcję \(\displaystyle{ f:\left\{ 1,2,\ldots,n-1\right\} \rightarrow \left\{ 0,1\right\} }\) :?: I teraz jak Pan konkretnie definiuję rozkład na przedziały :?:
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 23 lut 2022, o 14:25 Nie rozumiem, za mało to konkretne.
Myślę, że wystarczająco konkretne.
Jakub Gurak pisze: 23 lut 2022, o 14:25 Rozumiem, że przez ciąg decyzji formalnie Pan rozumie dowolną funkcję \(\displaystyle{ f:\left\{ 1,2,\ldots,n-1\right\} \rightarrow \left\{ 0,1\right\} }\) :?: I teraz jak Pan konkretnie definiuję rozkład na przedziały :?:
Dla ciągu decyzji \(\displaystyle{ f}\) niech \(\displaystyle{ f^{-1}[\{1\}]=\{a_1,a_2...,a_k\}}\), gdzie \(\displaystyle{ a_1<a_2<...<a_k}\). Wtedy rozkład to \(\displaystyle{ \{[1,a_1],[a_1+1,a_2],...,[a_{k-1}+1,a_k],[a_k+1,n]\}.}\) (jeśli \(\displaystyle{ f^{-1}[\{1\}]=\emptyset}\), to mamy oczywiście rozkład trywialny \(\displaystyle{ \{[1,n]\}}\)).

JK
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

Zatem można jeszcze prościej to zadanie rozwiązać (choć dokładny dowód jest dosyć żmudny). Przypominam, dla skończonego niepustego zbioru liniowo uporządkowanego \(\displaystyle{ \left( X, \le\right), }\) zbioru \(\displaystyle{ n}\)-elementowego, oznaczmy więc \(\displaystyle{ X=\left\{ x_1, x_2, x_3,\ldots, x_n\right\}}\), wtedy rozważamy rodzinę wszystkich rozkładów zbioru \(\displaystyle{ X}\) na przedziały, i dowodzimy, że moc tej rodziny wynosi \(\displaystyle{ 2 ^{n-1}.}\)


Prostszym pomysłem jest więc rozważenie podzbiorów zbioru \(\displaystyle{ X_0=\left\{ x_1,x_2,\ldots, x _{n-1} \right\}.}\)

Dla dowolnego ustalonego podzbioru \(\displaystyle{ A\subset X_0}\), a więc dla elementu zbioru \(\displaystyle{ P(X_0)}\), przypisujemy mu rozkład na przedziały, w następujący sposób.

Jeśli \(\displaystyle{ A=\emptyset}\), to przypisujemy mu rozkład \(\displaystyle{ \mathcal{R}=\left\{ X\right\}, }\) rozkład na jeden cały zbiór, a więc jest to przedział początkowy, a więc przedział. A więc \(\displaystyle{ \mathcal {R}\in \mathbb{B};}\)

A jeśli \(\displaystyle{ A \neq \left\{ \right\}}\), czyli \(\displaystyle{ A=\left\{ x _{k_1}, x _{k_2},\ldots, x _{k_m} \right\}}\), gdzie \(\displaystyle{ k_i \in \left\{ 1,2,\ldots, n-1\right\},}\) i porządek na zbiorze numerów \(\displaystyle{ \left\{ k_1, k_2,\ldots, k_m\right\}}\) jest naturalny, to przypisujemy mu rozkład \(\displaystyle{ \mathcal{R}_A}\) dany jako:

\(\displaystyle{ \mathcal{R}_A=\left\{ \left[ x_1, x _{k_1} \right] ; \left[ x _{k_1+1} , x _{k_2} \right] ; \left[ x _{k_2+1}, x _{k_3} \right] ; \dots; \left[ , x _{k_m} \right]; \left[ x _{k_m+1}, x_n \right] \right\},}\)

czyli bierzemy jako pierwszy zbiór rozkładu przedział domknięty od pierwszego elementu \(\displaystyle{ x_1}\) do pierwszego elementu zbioru \(\displaystyle{ A}\), potem jako drugi zbiór rozkładu bierzemy przedział domknięty od następnego elementu zbioru do drugiego elementu zbioru \(\displaystyle{ A}\), i tak aż do przedziału domkniętego o prawym końcu w ostatnim elemencie zbioru \(\displaystyle{ A}\), i na koniec bierzemy przedział domknięty od następnego elementu do ostatniego elementu \(\displaystyle{ x_n.}\)

Jest to rozkład zbioru \(\displaystyle{ X}\) na przedziały, a więc \(\displaystyle{ \mathcal {R}_A\in \mathbb{B}.}\)

Otrzymujemy zatem funkcję \(\displaystyle{ \alpha :A\subset X_0 \rightarrow \mathcal{R}_A \in \mathbb{B}.}\)

Poniżej przedstawiam dowód, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.


DOWÓD TEGO FAKTU:

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

Weźmy dwa dowolne różne zbiory \(\displaystyle{ A,B\subset X_0.}\)

Jeśli \(\displaystyle{ B=\emptyset}\), to \(\displaystyle{ \alpha (B)= \alpha \left( \emptyset\right)= \mathcal {R}= \left\{ X\right\}.}\) Ponieważ \(\displaystyle{ A \neq \emptyset}\), to \(\displaystyle{ A}\) ma \(\displaystyle{ m\in\NN}\) elementów, gdzie \(\displaystyle{ m \ge 1}\), wtedy przypisany mu rozkład \(\displaystyle{ \mathcal{R}_A}\) ma \(\displaystyle{ (m+1)}\) zbiorów, gdzie \(\displaystyle{ m+1 \ge 2}\), a rozkład \(\displaystyle{ \mathcal {R}_{\emptyset}}\) ma tylko jeden zbiór, wobec czego \(\displaystyle{ \mathcal{R}_B= \mathcal{R} _{\emptyset} \neq \mathcal{R}_A.}\)

Jeśli \(\displaystyle{ A=\emptyset}\)- ten przypadek jest symetryczny do powyższego.

Załóżmy teraz, że \(\displaystyle{ \left\{ \right\} \neq A,B\subset X_0}\), i \(\displaystyle{ A \neq B}\). Ponieważ \(\displaystyle{ A \neq B}\), więc \(\displaystyle{ A\not\subset B}\) lub \(\displaystyle{ B\not\subset A.}\)\(\displaystyle{ }\)

Jeśli \(\displaystyle{ A\not\subset B}\), ponieważ zbiór pusty jest podzbiorem każdego zbioru, więc również \(\displaystyle{ \emptyset\subset B}\), a więc \(\displaystyle{ A \neq \emptyset}\), zaprzeczając zatem definicji inkluzji otrzymujemy, że istnieje element \(\displaystyle{ a\in A}\), taki, że \(\displaystyle{ a\not\in B}\). Ponieważ \(\displaystyle{ a\in A\subset X_0}\), to \(\displaystyle{ a=x_i}\), gdzie \(\displaystyle{ i\in\left\{ 1,2,\ldots,n-1\right\}}\). Niech \(\displaystyle{ A_i\in \mathcal {R}_A}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}_A}\) zawierającym element \(\displaystyle{ a}\) (tzn. takim, że \(\displaystyle{ a\in A_i}\))- taki zbiór jest dokładnie jeden, bo \(\displaystyle{ \mathcal{R}_A}\) jest rozkładem zbioru \(\displaystyle{ X=\left\{ x_1, x_2,\ldots, x_n\right\}.}\) Niech \(\displaystyle{ B_i \in\mathcal{R}_B}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}_B}\) zawierającym element \(\displaystyle{ a}\) (z podobnych przyczyn taki zbiór jest dokładnie jeden). Mamy, że element \(\displaystyle{ a=x_i}\) jest elementem największym zbioru \(\displaystyle{ A_i}\). Mamy \(\displaystyle{ a\in A_i}\), gdzie \(\displaystyle{ A_i\in\mathcal{R}_A;}\) oraz \(\displaystyle{ B_i\in\mathcal{R}_B}\). Wtedy \(\displaystyle{ B_i\not\in\mathcal{R}_A}\).
Gdyby byłoby \(\displaystyle{ B_i\in \mathcal{R}_A}\), ponieważ \(\displaystyle{ a\in B_i}\), więc \(\displaystyle{ a\in A_i \cap B_i}\), i ponieważ zbiory \(\displaystyle{ A_i, B_i}\) są zbiorami rozkładu \(\displaystyle{ \mathcal{R}_A}\), a to jest rozkład na zbiory rozłączne, w związku z czym, z warunku rozłączności, ponieważ zbiory\(\displaystyle{ A_i, B_i}\) się przecinają, więc musi być \(\displaystyle{ A_i=B_i}\). Ponieważ element \(\displaystyle{ a=x_i }\) jest elementem największym zbioru \(\displaystyle{ A_i=B_i\in \mathcal{R}_B}\) i \(\displaystyle{ a \neq x_n}\), więc ze sposobu konstrukcji funkcji \(\displaystyle{ \alpha}\) wnioskujemy, że \(\displaystyle{ a\in B}\)- sprzeczniość.
Wobec czego \(\displaystyle{ B_i\not\in \mathcal {R}_A}\), a \(\displaystyle{ B_i\in \mathcal {R}_B}\), wobec czego \(\displaystyle{ \mathcal{R}_A \neq \mathcal {R}_B.}\)

Jeśli \(\displaystyle{ B\not\subset A}\), ponieważ mamy \(\displaystyle{ B \neq \emptyset}\), więc zaprzeczając definicji inkluzji otrzymujemy pewien element \(\displaystyle{ b\in B}\) taki, że \(\displaystyle{ b\not\in A}\). Wtedy \(\displaystyle{ b\in B \subset X_0}\), a więc \(\displaystyle{ b=x_i}\), gdzie \(\displaystyle{ i\in \left\{ 1,2,\ldots, n-1\right\}.}\) Niech \(\displaystyle{ A_i\in \mathcal {R}_A}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal {R}_A}\) zawierającym element \(\displaystyle{ b}\) (taki zbiór jest dokładnie jeden, bo \(\displaystyle{ \mathcal {R}_A}\) jest rozkładem). Niech \(\displaystyle{ B_i\in \mathcal {R}_B}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal {R}_B}\) zawierającym element \(\displaystyle{ b}\) (z podobnych przyczyn taki zbiór jest dokładnie jeden). Wtedy element \(\displaystyle{ b=x_i}\) jest elementem największym zbioru \(\displaystyle{ B_i}\). Mamy \(\displaystyle{ B_i \in \mathcal {R}_B}\) i \(\displaystyle{ B_i\not\in \mathcal {R}_A}\).
Gdyby byłoby \(\displaystyle{ B_i\in \mathcal {R}_A}\), ponieważ \(\displaystyle{ A_i\in \mathcal {R}_A}\) i mamy \(\displaystyle{ b\in A_i \cap B_i}\), a zbiory \(\displaystyle{ A_i ,B_i}\) są zbiorami tego samego rozkładu \(\displaystyle{ \mathcal {R}_A}\), więc z warunku rozłączności otrzymujemy \(\displaystyle{ A_i=B_i}\). Ponieważ element \(\displaystyle{ b=x_i}\) jest elementem największym zbioru \(\displaystyle{ B_i=A_i}\), to element \(\displaystyle{ b=x_i}\) jest elementem najwięks\(\displaystyle{ }\)zym zbioru \(\displaystyle{ A_i\in \mathcal{R}_B,}\) i \(\displaystyle{ b=x_i \neq x_n}\), więc ze sposobu konstrukcji funkcji \(\displaystyle{ \alpha}\) możemy wnioskować, że ten element największy \(\displaystyle{ b\in A}\)- sprzeczność.
Wobec czego \(\displaystyle{ B_i\not\in \mathcal {R}_A}\), a \(\displaystyle{ B_i\in \mathcal {R}_B}\), a więc \(\displaystyle{ \mathcal {R}_A \neq \mathcal {R}_B }\).

A więc funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

Wykażemy teraz, że funkcja \(\displaystyle{ \alpha}\) jest funkcją 'na'.
DOWÓD TEGO FAKTU::    

A zatem funkcja \(\displaystyle{ \alpha}\) jest bijeckją.

A zatem \(\displaystyle{ P(X_0)\sim \mathbb{B}}\). A zatem \(\displaystyle{ \left| \mathbb{B}\right| = \left| P(X_0)\right| \stackrel{X_0 \sim (n-1)} = 2 ^{n-1}}\).

Wobec czego \(\displaystyle{ \left| \mathbb{B}\right| =2 ^{n-1}}\), dla każdego \(\displaystyle{ n \ge 1. \square }\) :D :lol: 8-)
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 5 mar 2022, o 14:14Prostszym pomysłem jest więc rozważenie podzbiorów zbioru \(\displaystyle{ X_0=\left\{ x_1,x_2,\ldots, x _{n-1} \right\}.}\)
To jest ten sam dowód, modulo standardowe utożsamienie \(\displaystyle{ P(X_0)}\) z \(\displaystyle{ \{0,1\}^{n-1}}\).

JK
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

Udowodniłem wczoraj, że dowolna rodzina podzbiorów zbioru liczb całkowitych, rodzina zbiorów rozłącznych, jest co najwyżej przeliczalna. Przedstawię teraz dowód tego ciekawego faktu.


Niech \(\displaystyle{ \mathbb{B}\subset P(\ZZ)}\) będzie dowolną rodziną podzbiorów zbioru \(\displaystyle{ \ZZ}\), rodziną zbiorów rozłącznych, czyli taką, że każde dwa różne zbiory tej rodziny są rozłączne. Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}}\) jest co najwyżej przeliczalna.


DOWÓD TEGO FAKTU:

Jeśli \(\displaystyle{ \mathbb{B}=\emptyset}\), to ta rodzina \(\displaystyle{ \mathbb{B}}\) jest co najwyżej przeliczalna.

Jeśli rodzina \(\displaystyle{ \mathbb{B}}\) jest jednozbiorowa, tzn. gdy jest mocy \(\displaystyle{ 1}\), to rodzina \(\displaystyle{ \mathbb{B}}\) jest co najwyżej przeliczalna.


Pozostaje założyć, że moc tej rodziny wynosi co najmniej \(\displaystyle{ 2}\).

Jeśli zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge 2}\). To \(\displaystyle{ \left| \mathbb{B} \setminus \left\{ \emptyset\right\} \right| \ge 1}\). Ustalmy zatem zbiór \(\displaystyle{ A_0\in \mathbb{B} \setminus \left\{ \emptyset\right\} \neq \emptyset}\). Wtedy \(\displaystyle{ A_0 \neq \emptyset.}\)

Rozważmy funkcję:

\(\displaystyle{ f: \bigcup\mathbb{B} \rightarrow \mathbb{B} \setminus \left\{ \emptyset\right\}}\), daną jako:

\(\displaystyle{ (x,A) \in f\Longleftrightarrow x\in A.}\)

Jeśli \(\displaystyle{ x\in \bigcup\mathbb{B}}\), to \(\displaystyle{ x\in A}\), gdzie \(\displaystyle{ A\in\mathbb{B}}\), wtedy \(\displaystyle{ A \neq \emptyset}\), a więc \(\displaystyle{ A\in\mathbb{B}\setminus \left\{ \emptyset\right\}}\), i \(\displaystyle{ x\in A}\), a więc \(\displaystyle{ f(x)=A}\), czyli każdemu elementowi \(\displaystyle{ x \in \bigcup \mathbb{B}}\) jest przypisany co najmniej jeden zbiór \(\displaystyle{ A\in\mathbb{B} \setminus \left\{ \emptyset\right\}}\).

A jeśli \(\displaystyle{ \left( x,A_1\right)\in f}\) i \(\displaystyle{ (x,A_2)\in f}\) , to \(\displaystyle{ x\in A_1}\) i \(\displaystyle{ x\in A_2}\), a ponieważ \(\displaystyle{ A_1, A_2\in \mathbb{B}}\), a \(\displaystyle{ \mathbb{B}}\) jest rodziną zbiorów rozłącznych i \(\displaystyle{ x\in A_1 \cap A_2}\), więc z warunku rozłączności otrzymujemy: \(\displaystyle{ A_1=A_2}\).

Wobec czego relacja \(\displaystyle{ f}\) jest funkcją częściową ,i relacja \(\displaystyle{ f}\) jest funkcją ze zbioru \(\displaystyle{ \bigcup\mathbb{B}}\) w zbiór \(\displaystyle{ \mathbb{B} \setminus \left\{ \emptyset\right\}. }\)

Wykażemy, że jest to funkcja 'na' .
DOWÓD TEGO FAKTU::    
Jeśli \(\displaystyle{ \bigcup\mathbb{B}=\ZZ}\), to \(\displaystyle{ f:\ZZ \stackrel{NA}{\rightarrow} \mathbb{B} \setminus \left\{ \emptyset\right\}}\), a zatem \(\displaystyle{ \left| \mathbb{B} \setminus \left\{ \emptyset\right\} \right| \le \left| \ZZ\right|=\left| \NN\right|}\), a zatem \(\displaystyle{ \left| \mathbb{B} \setminus \left\{ \emptyset\right\} \right| \le \left| \NN\right|}\), a zatem rodzina \(\displaystyle{ \mathbb{B}\setminus \left\{ \emptyset\right\} }\) jest co najwyżej przeliczalna, i rodzina \(\displaystyle{ \mathbb{B}}\) jest co najwyżej przeliczalna, co należało pokazać.

Jeśli \(\displaystyle{ \bigcup\mathbb{B} \neq \ZZ}\), to \(\displaystyle{ \bigcup\mathbb{B}\not\subset\ZZ}\) lub \(\displaystyle{ \ZZ\not\subset \bigcup\mathbb{B}}\).
Ale suma \(\displaystyle{ \bigcup\mathbb{B}}\), jako suma podzbiorów zbioru \(\displaystyle{ \ZZ}\), jest podzbiorem zbioru \(\displaystyle{ \ZZ}\), wobec czego musi być: \(\displaystyle{ \ZZ\not\subset \bigcup\mathbb{B}}\). Zaprzeczając zatem definicji zawierania, otrzymujemy pewien element \(\displaystyle{ x\in\ZZ}\), taki, że \(\displaystyle{ x\not\in \bigcup\mathbb{B}}\). Wtedy \(\displaystyle{ x\in \ZZ \setminus \bigcup\mathbb{B}}\), a więc zbiór \(\displaystyle{ X_0:=\ZZ \setminus \bigcup\mathbb{B}}\) jest niepusty.

A zatem funkcja (przypominam zbiór \(\displaystyle{ A_0}\) jest ustalonym zbiorem rodziny \(\displaystyle{ \mathbb{B} \setminus \left\{ \emptyset\right\} \neq \emptyset}\)), rozważmy więc funkcję

\(\displaystyle{ f_0:X_0 \rightarrow \left\{ A_0\right\}}\),

daną oczywiście jako:

\(\displaystyle{ f_0(x)=A_0.}\)

Wtedy, oczywiście, jest to funkcja 'na'.


Rozważmy sumę funkcji \(\displaystyle{ f}\) i \(\displaystyle{ f_0}\). Ponieważ, dla każdego \(\displaystyle{ x\in\left( \bigcup\mathbb{B} \right) \cap X_0=\emptyset}\), mamy: \(\displaystyle{ f(x)=f_0(x)}\) -prawda formalna, czyli w przekroju dziedzin tych funkcji, funkcje te się pokrywają, w związku z czym, suma tych dwóch funkcji jest funkcją ze sumy dziedzin tych funkcji w sumę przeciwdziedzin ( jest to dość prosty fakt). Czyli \(\displaystyle{ g:=f_0 \cup f}\) jest funkcją ze zbioru \(\displaystyle{ \left( X_0=\ZZ \setminus \bigcup\mathbb{B}\right) \cup \bigcup\mathbb{B}=\ZZ}\) w zbiór \(\displaystyle{ \left\{ A_0\right\} \cup \left( \mathbb{B} \setminus \left\{ \emptyset\right\} \right)\stackrel{A_0\in \mathbb{B} \setminus \left\{ \emptyset\right\} } = \mathbb{B} \setminus \left\{ \emptyset\right\}}\). Ponieważ funkcja \(\displaystyle{ f_0}\) jest 'na', poniewaz funkcja \(\displaystyle{ f}\) jest 'na' , to funkcja \(\displaystyle{ g}\), jako suma dwóch funkcji 'na', jest funkcją 'na'- jest to prosty fakt.

Czyli \(\displaystyle{ g:\ZZ \stackrel{NA}{\rightarrow} \mathbb{B} \setminus \left\{ \emptyset\right\}}\).

A zatem \(\displaystyle{ \left| \NN\right|=\left| \ZZ\right| \ge \left|\mathbb{B} \setminus \left\{\emptyset\right\} \right|}\), czyli \(\displaystyle{ \left| \mathbb{B} \setminus \left\{ \emptyset\right\} \right| \le \left| \NN\right|}\), a więc rodzina \(\displaystyle{ \mathbb{B} \setminus \left\{ \emptyset\right\}}\) jest co najwyżej przeliczalna, i rodzina \(\displaystyle{ \mathbb{B} }\) jest co najwyżej przeliczalna. \(\displaystyle{ \square}\) :D

Zauważmy jeszcze, że rodzina podzbiorów zbioru \(\displaystyle{ \ZZ}\), rodzina zbiorów rozłącznych może być też dokładnie przeliczalnej mocy, np. \(\displaystyle{ \left\{ \left\{ n\right\}\Bigl| \ n\in \NN \right\} \sim \NN}\), i jest to rodzina zbiorów rozłącznych, bo różne zbiory jednoelementowe są rozłączne.

Może też być dowolnej skończonej mocy- dla zbioru \(\displaystyle{ X=\left\{ 1,2,\ldots, n \right\},}\) podobnie możemy rozważyć:

\(\displaystyle{ \left\{ \left\{ 1\right\}, \left\{ 2\right\}, \ldots, \left\{ n\right\} \right\}\sim X\sim n,}\)

i różne zbiory jednoelementowe są rozłączne, wobec czego istnieją rodziny zbiorów rozłącznych dowolnej skończonej, dodatniej mocy.


Zauważmy też, że dowolna rodzina \(\displaystyle{ \mathbb{B}}\), tym razem podzbiorów zbioru liczb naturalnych, rodzina zbiorów rozłącznych, jest co najwyżej przeliczalna.
DOWÓD TEGO FAKTU::    
I może być też dokładnie przeliczalna- wystarczy rozważyć rodzinę:

\(\displaystyle{ \mathbb{B}= \left\{ \left\{ n\right\}\Bigl| \ n\in\NN \right\} \sim \NN,}\)

i jest to rodzina zbiorów rozłącznych, bo różne zbiory jednoelementowe są rozłączne.


I dla zbioru \(\displaystyle{ \ZZ_- \cup \left\{ 0\right\},}\) dowolna rodzina \(\displaystyle{ \mathbb{B}}\) podzbiorów rozłącznych, jest co najwyżej przeliczalna.

Dla dowodu, wystarczy zauważyć, że jest to rodzina podzbiorów zbioru \(\displaystyle{ \ZZ_- \cup {0} \subset\ZZ}\), a więc jest to rodzina podzbiorów zbioru \(\displaystyle{ \ZZ}\), rodzina zbiorów rozłącznych, a zatem, na mocy naszego dowodu: rodzina \(\displaystyle{ \mathbb{B}}\) jest co najwyżej przeliczalna.

I może być też dokładnie przeliczalna- wystarczy rozważyć:

\(\displaystyle{ \mathbb{B}=\left\{ \left\{ n\right\}\Bigl| \ \ n=0,-1,-2,-3,\ldots \right\} \sim \ZZ_- \cup \left\{ 0\right\}\sim \NN}\),

a więc \(\displaystyle{ \mathbb{B}\sim \NN}\), i zbiory jednoelementowe są rozłączne.\(\displaystyle{ \square}\) :D
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

Udowodniłem wczoraj, że jeśli \(\displaystyle{ X}\) jest skończonym niepustym zbiorem- \(\displaystyle{ n}\)-elementowym, to istnieje dokładnie \(\displaystyle{ 2 ^{n-1}-1 }\) rozkładów tego zbioru \(\displaystyle{ X}\) na dwa podzbiory. Przedstawię teraz dowód tego ciekawego faktu.


Niech \(\displaystyle{ X \neq \left\{ \right\}}\) będzie skończonym niepustym zbiorem, \(\displaystyle{ n}\)-elementowym. Rozważmy rodzinę rozkładów \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ \mathcal{R}: \ \ \mathcal{R} \hbox{ jest rozkładem zbioru } X\hbox{ i } \left| \mathcal{R}\right|=2 \right\}.}\)

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

Podajmy najpierw pewien prosty lemat.

Lemat. Jeśli \(\displaystyle{ X \neq \left\{ \right\}}\) jest niepustym zbiorem, a \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) jego podzbiorem, niepustym i różnym od całego zbioru \(\displaystyle{ X}\), to rodzina dwuzbiorowa \(\displaystyle{ \left\{ A, \left( A':= X \setminus A\right) \right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\).
DOWÓD TEGO FAKTU::    

Przejdźmy do naszego zadania.

DOWÓD (zachowując wprowadzone oznaczenia):

Niech \(\displaystyle{ \mathbb{S}=P(X) \setminus \left\{ \emptyset, X\right\}}\)- jest to zbiór wszystkich podzbiorów zbioru \(\displaystyle{ X}\) niepustych i różnych od całego zbioru \(\displaystyle{ X}\).

Na początek ustalmy element \(\displaystyle{ x\in X \neq \left\{ \right\}}\), i podzielmy rodzinę \(\displaystyle{ \mathbb{S}}\) na dwie podrodziny, dane jako:

\(\displaystyle{ \mathbb{S}_1=\left\{ A\in\mathbb{S}: \ x\in A\right\}}\), i

\(\displaystyle{ \mathbb{S}_2=\left\{ A\in\mathbb{S}: \ x\not\in A \right\} .}\)

Czyli pierwsza rodzina, to rodzina zbiorów z \(\displaystyle{ \mathbb{S}}\) zawierających ustalony element \(\displaystyle{ x}\), a rodzina \(\displaystyle{ \mathbb{S}_2}\) to rodzina zbiorów z \(\displaystyle{ \mathbb{S}}\) nie zawierających elementu \(\displaystyle{ x}\).

Wtedy oczywiście: \(\displaystyle{ \mathbb{S}_1 \cup \mathbb{S}_2=\mathbb{S}. }\)

Wykażemy, że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{B}}\), oraz, że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{S}_2}\).

Dość łatwo jest pokazać ostatni fakt, tzn., że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{S}_2}\).

W tym celu definiujemy funkcję \(\displaystyle{ g}\), działająco w następujący sposób:

\(\displaystyle{ A\in \mathbb{S}_1 \stackrel{g}{ \rightarrow } A'=X \setminus A \subset X.}\)

Na początek uzasadnijmy, że funkcja \(\displaystyle{ g}\) jest dobrze określona.

Jeśli \(\displaystyle{ A\in\mathbb{S}_1}\), to \(\displaystyle{ A\in \mathbb{S}}\), a zatem \(\displaystyle{ A \neq \emptyset}\) i \(\displaystyle{ A \neq X}\). Wtedy \(\displaystyle{ A' \neq \emptyset}\) i \(\displaystyle{ A' \neq X}\). Aby uzasadnić pierwszy z tych dwóch faktów, to gdyby byłoby \(\displaystyle{ A'=\emptyset}\), to \(\displaystyle{ A=(A')'=\emptyset'=X}\), czyli \(\displaystyle{ A=X}\)- sprzeczność. Wobec czego \(\displaystyle{ A' \neq \emptyset}\). I w podobny sposób możemy uzasadnić, że \(\displaystyle{ A' \neq X}\) (bo \(\displaystyle{ A \neq \emptyset}\)). A zatem \(\displaystyle{ A'\subset X}\),i \(\displaystyle{ A' \neq X,\emptyset}\), a zatem \(\displaystyle{ A'\in\mathbb{S}}\). Ponieważ \(\displaystyle{ A\in \mathbb{S}_1}\), to \(\displaystyle{ x\in A}\), i mamy \(\displaystyle{ x\in X}\), a zatem \(\displaystyle{ x\not\in A'=X \setminus A}\), wobec czego \(\displaystyle{ A'\in\mathbb{S}_2}\) i funkcja \(\displaystyle{ g:\mathbb{S}_1 \rightarrow\mathbb{S}_2}\) jest dobrze określona.

Wykażemy, że funkcja \(\displaystyle{ g}\) jest bijekcją.
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ \mathbb{S}_1\sim \mathbb{S}_2}\).


Wykażemy teraz, że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{B}}\).

Niech \(\displaystyle{ \mathcal{R}\in\mathbb{B}}\). Wtedy, ponieważ \(\displaystyle{ \mathcal{R}}\) jest rozkładem, więc istnieje dokładnie jeden zbiór \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in \mathcal{R}}\) tego rozkładu zawierający nasz ustalony element \(\displaystyle{ x}\). Taki zbiór będziemy oznaczać jako: \(\displaystyle{ \left[ x\right] _{\mathcal{R}}}\)- więc jest to taki zbiór \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in\mathcal{R}}\), taki, że: \(\displaystyle{ x\in\left[ x\right] _{\mathcal{R}}}\)- taki zbiór jest dokładnie jeden, bo \(\displaystyle{ \mathcal{R}}\) jest rozkładem.

Wtedy oczywiście \(\displaystyle{ \left[ x\right] _{\mathcal{R}}}\) jest zbiorem niepustym, i \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \neq X}\)- gdyby bowiem byłoby \(\displaystyle{ \left[ x\right] _{\mathcal{R}}=X}\), ponieważ \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in\mathcal{R}}\), a \(\displaystyle{ \mathcal{R}\in\mathbb{B}}\), a zatem \(\displaystyle{ \left|\mathcal{R}\right|=2}\), a zatem istnieje niepusty zbiór \(\displaystyle{ A\in\mathcal{R}}\) różny od drugiego zbioru tego rozkładu, równemu zbiorowi \(\displaystyle{ X}\). Wtedy \(\displaystyle{ A \cap X=A \neq \left\{ \right\}}\) , a zatem istnieje element \(\displaystyle{ y\in A \cap X}\), ale \(\displaystyle{ A\in\mathcal{R}, X\in \mathcal{R}}\) i \(\displaystyle{ A \neq X}\), więc zbiory \(\displaystyle{ A}\) i \(\displaystyle{ X}\) powinny być rozłączne, a nie są- element \(\displaystyle{ y}\) jest wspólnym elementem-sprzeczność.

Wobec czego \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \neq X}\), \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \neq \left\{ \right\}}\) i \(\displaystyle{ \left[ x\right] _{\mathcal{R}} \subset X}\), skąd możemy wnioskować, że: \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in \mathbb{S}}\), i oczywiście mamy: \(\displaystyle{ x \in \left[ x\right] _{\mathcal{R}}}\), a zatem \(\displaystyle{ \left[ x\right] _{\mathcal{R}}\in\mathbb{S}_1}\), i otrzymujemy, że funkcja:

\(\displaystyle{ \alpha :\mathcal{R} \in \mathbb{B} \rightarrow \left[ x\right] _{\mathcal{R}}\in \mathbb{S}_1,}\)

jest dobrze określona.

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.


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

Jeśli \(\displaystyle{ \alpha \left( \mathcal{R}_1\right) = \alpha \left( \mathcal{R}_2\right)}\), to oznacza, z definicji tej funkcji, że:

\(\displaystyle{ \left[ x\right] _{\mathcal{R}_1}=\left[ x\right] _{\mathcal{R}_2}}\),

wtedy ponieważ \(\displaystyle{ \mathcal{R}_1 \in \mathbb{B}}\), to \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem zbioru \(\displaystyle{ X}\) i \(\displaystyle{ \left| \mathcal{R}_1\right|= 2}\). Podobnie, ponieważ \(\displaystyle{ \mathcal{R}_2 \in \mathbb{B}}\), to \(\displaystyle{ \mathcal{R}_2}\) jest rozkładem zbioru \(\displaystyle{ X}\) i \(\displaystyle{ \left| \mathcal{R}_2\right|=2}\).

A zatem \(\displaystyle{ \mathcal{R}_1=\left\{ A_1,B_1\right\}}\), gdzie pewne zbiory \(\displaystyle{ A_1, B_1}\) są różne; oraz \(\displaystyle{ \mathcal{R}_2=\left\{ A_2,B_2\right\}}\) , gdzie pewne zbiory \(\displaystyle{ A_2,B_2}\) są różne.

Ponieważ \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem zbioru \(\displaystyle{ X}\), a więc \(\displaystyle{ \bigcup\mathcal{R}_1=X}\), a zatem:

\(\displaystyle{ X= \bigcup\mathcal{R}_1= \bigcup\left\{ A_1,B_1\right\} =A_1 \cup B_1}\), czyli \(\displaystyle{ A_1 \cup B_1=X.}\)

Podobnie, ponieważ \(\displaystyle{ \mathcal{R}_2}\) jest rozkładem zbioru \(\displaystyle{ X}\), a więc \(\displaystyle{ \bigcup\mathcal{R}_2=X}\), a zatem:

\(\displaystyle{ X= \bigcup\mathcal{R}_2= \bigcup\left\{ A_2,B_2\right\}=A_2 \cup B_2=X.}\)

Czyli \(\displaystyle{ A_2 \cup B_2=X=A_1 \cup B_1.}\)

Ponieważ \(\displaystyle{ \left[ x\right] _{\mathcal{R}_1} =\left[ x\right] _{\mathcal{R}_2}}\), i \(\displaystyle{ \left[ x\right] _{\mathcal{R}_1} \in \mathcal{R}_1=\left\{ A_1, B_1\right\}}\), i \(\displaystyle{ \left[ x\right] _{\mathcal{R}_2} \in \mathcal{R}_2 =\left\{ A_2, B_2\right\}}\),

to formalnie musimy rozważyć cztery przypadki (jeszcze nie widziałem czegoś takiego- choć tak prostego, to tak żmudnego ), i jeśli:

\(\displaystyle{ \left[ x\right] _{\mathcal{R}_1}=A_1 \left[ x\right] _{\mathcal{R}_2} =A_2}\), to \(\displaystyle{ A_2=A_1}\), oznaczmy ten zbiór jako \(\displaystyle{ A}\). Ponieważ \(\displaystyle{ A_1 \neq B_1}\), i \(\displaystyle{ A_1,B_1 \in \mathcal{R}_1}\), a \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem, więc zbiory \(\displaystyle{ A_1}\) i \(\displaystyle{ B_1}\) są rozłączne, podobnie ponieważ \(\displaystyle{ A_2, B_2\in\mathcal{R}_2}\), a \(\displaystyle{ \mathcal{R}_2}\) jest to rozkład, i \(\displaystyle{ A_2 \neq B_2}\), a więc zbiory \(\displaystyle{ A_2}\) i \(\displaystyle{ B_2}\) są rozłączne. W związku z czym:

\(\displaystyle{ A_1 \cup B_1=A \cup B_1= A_2 \cup B_2=A \cup B_2}\), i dalej :

\(\displaystyle{ \left( B_1 \cup A\right) \setminus A=\left( A \cup B_1\right) \setminus A=\left( A \cup B_2\right) \setminus A=\left( B_2 \cup A\right) \setminus A}\),

i ponieważ zbiory \(\displaystyle{ B_2}\) i \(\displaystyle{ A_2=A}\) są rozłączne, więc to jest równe:

\(\displaystyle{ =B_2.}\)

A zatem:

\(\displaystyle{ B_2= \left( B_1 \cup A\right) \setminus A=}\)

i ponieważ zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ A=A_1}\) są rozłączne, więc to jest równe:

\(\displaystyle{ =B_1}\).

Tak więc \(\displaystyle{ B_2=B_1}\), a zatem \(\displaystyle{ \mathcal{R}_1=\left\{ A_1, B_1\right\}= \left\{ A_2, B_2\right\} =\mathcal{R}_2}\), czyli \(\displaystyle{ \mathcal{R}_1=\mathcal{R}_2}\), co należało pokazać.


Rozważmy jeszcze jeden przypadek, gdy: \(\displaystyle{ \left[ x\right] _{\mathcal{R}_1}=A_1}\) i \(\displaystyle{ \left[ x\right] _{\mathcal{R}_2}=B_2}\), wtedy \(\displaystyle{ A_1=B_2}\), oznaczmy więc ten zbiór jako \(\displaystyle{ C}\). Wtedy: \(\displaystyle{ C \cup B_1=A_2 \cup C=C \cup A_2.}\)

I wtedy:

\(\displaystyle{ \left( B_1 \cup C\right) \setminus C= \left( C \cup B_1\right) \setminus C=\left( C \cup A_2\right) \setminus C=\left( A_2 \cup C\right) \setminus C= \left( A_2 \cup B_2\right) \setminus B_2=}\)

i ponieważ \(\displaystyle{ A_2, B_2\in\mathcal{R}_2}\) i \(\displaystyle{ A_2 \neq B_2}\), więc zbiory \(\displaystyle{ A_2}\) i \(\displaystyle{ B_2}\) są rozłączne, więc to jest równe:

\(\displaystyle{ =A_2.}\)

A zatem \(\displaystyle{ A_2=\left( B_1 \cup C\right) \setminus C= \left( B_1 \cup A_1\right) \setminus A_1=}\)

i ponieważ \(\displaystyle{ B _1,A_1 \in \mathcal{R}_1}\) i \(\displaystyle{ B_1 \neq A_1}\), więc zbiory \(\displaystyle{ B_1}\) i \(\displaystyle{ A_1}\) są rozłączne, więc to jest równe:

\(\displaystyle{ =B _1.}\)

Czyli \(\displaystyle{ A_2=B_1}\). Wobec czego:

\(\displaystyle{ \mathcal{R}_1=\left\{ A_1, B_1\right\}=\left\{ B_2,A_2\right\}=\left\{ A_2, B_2\right\} =\mathcal{R}_2}\), czyli

\(\displaystyle{ \mathcal{R}_1=\mathcal{R}_2}\), co należało pokazać.

Przypadki \(\displaystyle{ \left[ x\right] _{\mathcal{R}_1}=B_1}\), \(\displaystyle{ \left[ x\right] _{\mathcal{R}_2}=B_2,A_2}\) sprawdzamy analogicznie.

Wobec czego funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


Oh, po tych trudach chyba łatwo będzie wykazać, że jest to funkcja 'na' (choć będę musiał jedną rzecz poprawić, gdyż wcześniej zapomniałem zapisać pewnej drobnej uwagi, z której skorzystałem w tym dowodzie, więc będę musiał się tu poprawić).

Niech \(\displaystyle{ A\in\mathbb{S}_1}\). Wtedy \(\displaystyle{ A\in\mathbb{S}}\) i \(\displaystyle{ x\in A}\). Ponieważ \(\displaystyle{ A\in\mathbb{S}}\), to \(\displaystyle{ A\subset X}\), i \(\displaystyle{ A \neq \emptyset,X}\).

Wtedy na mocy naszego Lematu rodzina dwuzbiorowa \(\displaystyle{ \left\{ A,A'=X \setminus A\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\).

Uzasadnijmy jeszcze, że \(\displaystyle{ A \neq A'}\). Mamy \(\displaystyle{ \emptyset=A \cap A'}\), a więc zbiory \(\displaystyle{ A}\) i \(\displaystyle{ A'}\) są zbiorami rozłącznymi, i \(\displaystyle{ A \neq \emptyset}\), więc jeśli \(\displaystyle{ A'=\emptyset}\), to \(\displaystyle{ A \neq A'=\emptyset}\), co chciałem pokazać, a jeśli \(\displaystyle{ A' \neq \left\{ \right\}}\), to zbiory \(\displaystyle{ A}\) i \(\displaystyle{ A}\)' są niepuste i rozłączne a zatem różne, co należało pokazać.

Wobec czego \(\displaystyle{ \left| \left\{ A,A'\right\} \right|=2}\), i \(\displaystyle{ \left\{ A,A'\right\} \in\mathbb{B}}\). Możemy zatem wyliczyć wartość funkcji \(\displaystyle{ \alpha}\) na tym rozkładzie, tzn. mamy:

\(\displaystyle{ \alpha \left( \left\{ A,A'\right\} \right)= \left[ x\right] _{\left\{ A,A'\right\} } =}\)

i ponieważ \(\displaystyle{ x\in A}\), a \(\displaystyle{ x\not\in A'}\), więc to jest równe zbiorowi \(\displaystyle{ A}\), czyli:

\(\displaystyle{ \alpha \left( \left\{ A,A'\right\} \right)=A}\),

a więc zbiór \(\displaystyle{ A}\) jest wartością funkcji \(\displaystyle{ \alpha}\) . Z dowolności wyboru takiego zbioru otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.

A zatem \(\displaystyle{ \alpha}\) jest bijekcją, i \(\displaystyle{ \mathbb{B}\sim \mathbb{S}_1}\).


Mamy \(\displaystyle{ \mathbb{S}_1\sim\mathbb{S}_2.}\) I mamy \(\displaystyle{ \mathbb{S}_1 \cup \mathbb{S}_2=\mathbb{S}=P(X) \setminus \left\{ \emptyset,X\right\}}\); ponieważ zbiór \(\displaystyle{ X}\) ma dokładnie \(\displaystyle{ n}\)-elementów, i \(\displaystyle{ X \neq \left\{ \right\}}\), więc \(\displaystyle{ \left| \mathbb{S}\right|=2 ^{n}-2}\). A więc rodzina \(\displaystyle{ \mathbb{S}}\) jest zbiorem skończonym.

Ponieważ \(\displaystyle{ \mathbb{S}_1\subset \mathbb{S}}\), a \(\displaystyle{ \mathbb{S}}\) jest zbiorem skończonym, więc również rodzina \(\displaystyle{ \mathbb{S}_1}\) jest zbiorem skończonym, tzn. przyjmijmy, że \(\displaystyle{ \left| \mathbb{S}_1\right|=m}\), gdzie \(\displaystyle{ m\in\NN.}\) Wtedy \(\displaystyle{ \left| \mathbb{S}_1 \cup \mathbb{S}_2\right|=\left| \mathbb{S}\right|}\). Ponieważ \(\displaystyle{ \mathbb{S}_2\sim \mathbb{S}_1}\), to \(\displaystyle{ \left| \mathbb{S}_2\right|=m}\), i \(\displaystyle{ \mathbb{S}= \mathbb{S}_1 \cup \mathbb{S}_2}\), gdzie rodziny zbiorów \(\displaystyle{ \mathbb{S}_1}\) i \(\displaystyle{ \mathbb{S}_2}\) są zbiorami rozłącznymi (na podstawie ich definicji). A zatem \(\displaystyle{ \left| \mathbb{S}_1 \cup \mathbb{S}_2\right|=\left| \mathbb{S}\right| = m+m=2m}\). Ale wiemy już że: \(\displaystyle{ \left| \mathbb{S}\right|=2 ^{n}-2}\). Wobec czego \(\displaystyle{ m=2 ^{n-1}-1.}\)

Wobec czego \(\displaystyle{ \left| \mathbb{S}_1\right| =m=2 ^{n-1}-1}\). Ponieważ \(\displaystyle{ \mathbb{B}\sim \mathbb{S}_1}\), więc:

\(\displaystyle{ \left| \mathbb{B}\right|=2 ^{n-1}-1}\), gdzie \(\displaystyle{ n \ge 1}\)( w szczególności dla \(\displaystyle{ n=1}\) nie ma rozkładów na dwa zbiory, a więc jest \(\displaystyle{ 2 ^{1-1}-1=0}\) rozkładów na dwa zbiory) \(\displaystyle{ .\square}\) :lol: :D
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 10 kwie 2022, o 00:39 Udowodniłem wczoraj, że jeśli \(\displaystyle{ X}\) jest skończonym niepustym zbiorem- \(\displaystyle{ n}\)-elementowym, to istnieje dokładnie \(\displaystyle{ 2 ^{n-1}-1 }\) rozkładów tego zbioru \(\displaystyle{ X}\) na dwa podzbiory. Przedstawię teraz dowód tego ciekawego faktu.
No ale to jest oczywiste i nie wymaga tak przerażająco długiego dowodu: taki podział jest wyznaczony przez właściwy niepusty podzbiór zbioru \(\displaystyle{ X}\) (których jest \(\displaystyle{ 2^n-2}\)). Wyznaczenie to nie jest jednoznaczne, bo każdy taki zbiór wyznacza ten sam podział, co jego dopełnienie i dlatego musimy jeszcze tę liczbę podzielić przez dwa: \(\displaystyle{ \frac{2^n-2}{2}=2^{n-1}-1.}\)

JK
matmatmm
Użytkownik
Użytkownik
Posty: 2282
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 88 razy
Pomógł: 351 razy

Re: Teoria mocy zbiorów

Post autor: matmatmm »

Jakub Gurak pisze: 10 kwie 2022, o 00:39 Na początek ustalmy element \(\displaystyle{ x\in X \neq \left\{ \right\}}\), i podzielmy rodzinę \(\displaystyle{ \mathbb{S}}\) na dwie podrodziny, dane jako:

\(\displaystyle{ \mathbb{S}_1=\left\{ A\in\mathbb{S}: \ x\in A\right\}}\), i

\(\displaystyle{ \mathbb{S}_2=\left\{ A\in\mathbb{S}: \ x\not\in A \right\} .}\)

Czyli pierwsza rodzina, to rodzina zbiorów z \(\displaystyle{ \mathbb{S}}\) zawierających ustalony element \(\displaystyle{ x}\), a rodzina \(\displaystyle{ \mathbb{S}_2}\) to rodzina zbiorów z \(\displaystyle{ \mathbb{S}}\) nie zawierających elementu \(\displaystyle{ x}\).

Wtedy oczywiście: \(\displaystyle{ \mathbb{S}_1 \cup \mathbb{S}_2=\mathbb{S}. }\)

Wykażemy, że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{B}}\), oraz, że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{S}_2}\).
Dowód przez równoliczności z takimi zbiorami jest zupełnie niepotrzebny.
Oznaczając \(\displaystyle{ \xi(A):=\{A,X\setminus A\}}\) dla \(\displaystyle{ A\in \mathcal{P}(X)\setminus\{\emptyset, X\}}\), wystarczy pokazać, że \(\displaystyle{ \mathbb{B}}\) jest zbiorem wartości \(\displaystyle{ \xi}\) oraz wszystkie włókna odwzorowania \(\displaystyle{ \xi}\) są dokładnie dwuelementowe.

Formalnie można wtedy napisać:

\(\displaystyle{ \left| \mathcal{P}(X)\setminus\{\emptyset, X\}\right| =\left| \bigcup_{\mathcal{R}\in \mathbb B}\xi^{-1}[\{\mathcal{R}\}]\right| =
\sum_{\mathcal{R}\in \mathbb B}\left| \xi^{-1}[\{\mathcal{R}\}]\right| = 2|\mathbb{B}| }\)


Jest to bardziej ścisły opis tego, co zauważył Jan Kraszewski.
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

Udowodniłem wczoraj, że jeśli mamy dwa podzbiory zbioru liczb rzeczywistych: zbiór \(\displaystyle{ X}\)- zbiór podobny do zbioru liczb naturalnych; oraz niepusty zbiór skończony \(\displaystyle{ Y,}\) to (poza przypadkiem gdy zbiór \(\displaystyle{ Y}\) jest jednoelementowy), to ilość wszystkich funkcji niemalejących z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) jest dokładnie przeliczalna ( tzn. jest to zbiór równoliczny z \(\displaystyle{ \NN}\) ). Podobny fakt zachodzi również dla funkcji nierosnących. Udowodniłem też że nie ma, przy tych samych założeniach jeśli chodzi o dziedzinę i przeciwdziedzinę funkcji, to nie ma ani jednej funkcji silnie rosnącej z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). Udowodniłem też, że istnieje dokładnie continuum funkcji słabo rosnących ze zbioru liczb całkowitych w zbiór liczb naturalnych. Przedstawię teraz dowody tych ciekawych faktów.


Rozważmy dwa zbiory \(\displaystyle{ X,Y\subset \RR}\)- zbiór \(\displaystyle{ X}\), zbiór podobny do \(\displaystyle{ \NN}\); i zbiór \(\displaystyle{ Y}\)- niepusty zbiór skończony.

I rozważmy rodzinę funkcji niemalejących, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ f:X \rightarrow Y\Bigl| \ \ f \hbox{ jest } niemalejąca\right\} .}\)

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

Wykażemy, że (poza przypadkiem gdy zbiór \(\displaystyle{ Y}\) jest jednoelementowy), to rodzina \(\displaystyle{ \mathbb{B}}\) jest dokładnie przeliczalna.


DOWÓD TEGO FAKTU (postaram się, od teraz, nie przesadzać z dokładnością, ale czasem będę musiał dokładniej, taka niestaranność co po niektórych, to mnie gryzie, ale poza tym to postaram się normalnie, bez przesadyzmu):

Jeśli \(\displaystyle{ \left| Y\right| =1}\), tzn. \(\displaystyle{ Y=\left\{ y\right\} }\), gdzie \(\displaystyle{ y}\) jest pewnym elementem, to mamy dokładnie jedną funkcję z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\)- funkcję stale równą \(\displaystyle{ y}\), która jest, formalnie rzecz biorąc, funkcją niemalejącą. A więc wtedy: \(\displaystyle{ \left| \mathbb{B}\right|=1.}\)

Jeśli \(\displaystyle{ \left| Y\right| \ge 2}\). Wtedy istnieją dwa różne elementy \(\displaystyle{ a,b\in Y}\). Ponieważ \(\displaystyle{ Y\subset \RR}\), to \(\displaystyle{ a,b\in\RR}\), a więc \(\displaystyle{ a<b}\) lub \(\displaystyle{ b<a}\).

Aha, zapomniałem wprowadzić pewne oznaczenia służące ponumerowaniu zbiorów \(\displaystyle{ X}\) i \(\displaystyle{ Y}\). Ponieważ zbiór \(\displaystyle{ X}\) jest podobny do \(\displaystyle{ \NN}\) więc istnieje podobieństwo \(\displaystyle{ f_X:\NN \rightarrow X}\), i oznaczmy (dla dowolnego \(\displaystyle{ n\in\NN}\)) :

\(\displaystyle{ f_X\left( n\right) =:x _{n}.}\)

Ponieważ zbiór \(\displaystyle{ Y}\) jest skończony i co najmniej dwuelementowy, to \(\displaystyle{ Y\sim \left\{ 1,2,\ldots, k\right\}}\), dla pewnego \(\displaystyle{ k\in\NN}\). Zbiór \(\displaystyle{ Y}\) z naturalnym porządkiem jest liniowo uporządkowany (i również zbiór \(\displaystyle{ \left\{ 1,2,\ldots, k\right\}}\) jest liniowo uporządkowany ). A dwa zbiory liniowo uporządkowane skończone i równoliczne są podobne. Wobec czego \(\displaystyle{ Y \approx \left\{ 1,2, \ldots, k\right\}}\)- te dwa zbiory są podobne, istnieje więc podobieństwo \(\displaystyle{ f_Y:\left\{ 1,2,\ldots, k\right\} \rightarrow Y}\), i oznaczmy (dla dowolnego \(\displaystyle{ m\in \left\{ 1,2,\ldots, k\right\}}\) ) oznaczmy:

\(\displaystyle{ f_Y(m)=:y_m.}\)

Dzięki tym zabiegom mamy ponumerowany zbiór \(\displaystyle{ X=\left\{ x_0, x_1,x_2,\ldots\right\};}\) oraz mamy również ponumerowany zbiór \(\displaystyle{ Y=\left\{ y_1,y_2,\ldots, y_k\right\}.}\)

Wracając do dowodu, jeśli \(\displaystyle{ a<b,}\) to definiujemy ciąg funkcji \(\displaystyle{ f_n:X \rightarrow Y,}\) w następujący sposób:

\(\displaystyle{ f_n\left( x\right)= \begin{cases} b, \hbox{ dla } x \ge x_n;\\ a,\hbox{ dla } x<x_n.\end{cases} }\)

Wykażemy, że jest to ciąg funkcji niemalejących.

Niech \(\displaystyle{ n\in\NN,}\) i niech \(\displaystyle{ x,y\in X}\) będą takie, że \(\displaystyle{ x<y.}\) Pokażemy, że \(\displaystyle{ f_n(x) \le f_n(y)}\).

Jeśli \(\displaystyle{ y \ge x_n}\), to \(\displaystyle{ f_n(y)= b \ge f_n(x) \in \left\{ a,b\right\}.}\)

A jeśli \(\displaystyle{ y<x_n}\), to \(\displaystyle{ f_n(y)=a}\), wtedy \(\displaystyle{ x<y<x_n}\), czyli \(\displaystyle{ x<x_n}\), a zatem \(\displaystyle{ f_n(x)=a \le f_n(y)=a.}\)

A zatem funkcja \(\displaystyle{ f_n}\) jest niemalejąca, i \(\displaystyle{ f_n\in \mathbb{B}.}\)

Łatwo jest pokazać, że funkcja \(\displaystyle{ \alpha}\) działająca w następujący sposób:

\(\displaystyle{ n\in\NN \stackrel{ \alpha }{\rightarrow } f_n \in \mathbb{B},}\)

jest różnowartościowa.

A zatem \(\displaystyle{ \left| \NN\right| \le \left| \mathbb{B}\right|.}\)


Jeśli \(\displaystyle{ b<a}\), to analogicznie definiujemy ciag funkcji \(\displaystyle{ f_n:X \rightarrow Y;}\) w następujący sposób:

\(\displaystyle{ f_n\left( x\right)= \begin{cases} a,\hbox { dla } x \ge x_n;\\ b, \hbox{ dla } x<x_n. \end{cases} }\)

Wobec czego \(\displaystyle{ \left| \NN\right| \le \left| \mathbb{B}\right|.}\)


Zauważmy, że jeśli \(\displaystyle{ f\in\mathbb{B}}\), to \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest niemalejąca, wtedy ponieważ zbiór \(\displaystyle{ X}\) jest niepusty, to również zbiór wartości \(\displaystyle{ f_P}\) jest niepusty i jest zbiorem skończonym, a więc zbiór \(\displaystyle{ f_P}\) ma element największy \(\displaystyle{ y\in f_P}\). Wtedy \(\displaystyle{ y=f(x)}\), gdzie \(\displaystyle{ x\in X}\), a więc \(\displaystyle{ y=f (x_n)}\), dla pewnego \(\displaystyle{ n\in\NN}\). Łatwo jest więc pokazać, ponieważ funkcja \(\displaystyle{ f}\) jest niemalejąca, że \(\displaystyle{ f(x_m)= y}\), dla każdego \(\displaystyle{ m \ge n}\), czyli, że poczynając od numeru \(\displaystyle{ m=n}\) funkcja \(\displaystyle{ f}\) jest stale równa elementowi \(\displaystyle{ y}\).

Wobec czego, aby wykazać nierówność mocy w drugą stronę, podzielmy rodzinę \(\displaystyle{ \mathbb{B}}\) na podrodziny \(\displaystyle{ \mathbb{B} _{n,m}}\) , tzn. dla dowolnych \(\displaystyle{ n\in\NN}\), \(\displaystyle{ m\in \left\{ 1,2,\ldots, k\right\},}\) zdefiniujmy:

\(\displaystyle{ \mathbb{B} _{n,m}=\left\{ f\in \mathbb{B}: \ f\left( x_n\right)= \max\left( f_P\right)= y_m \right\} .}\)

Łatwo zauważyć, że :

\(\displaystyle{ \bigcup_{n\in\NN} \bigcup_{m=1}^{k} \mathbb{B} _{n,m}=\mathbb{B}}\),

gdyż każda funkcja \(\displaystyle{ f\in \mathbb{B}}\) ma w zbiorze wartości dokładnie jeden element największy.

Wykażemy, że rodzina \(\displaystyle{ \mathbb{B} _{n,m}}\) jest zawsze zbiorem skończonym.

W tym celu definiujemy funkcję:

\(\displaystyle{ \alpha :\mathbb{B} _{n,m} \rightarrow \left\{ y_1,y_2,\ldots, y_m\right\} ^{\left\{ x_0, x_1, x_2,\ldots, x_n\right\}=:X_n }}\), w następujący sposób:

funkcji \(\displaystyle{ f \in \mathbb{B} _{n,m}}\) przypisujemy jej obcięcie do zbioru \(\displaystyle{ X_n=\left\{ x_0, x_1, x_2,\ldots, x_n\right\}.}\)

Wtedy ponieważ \(\displaystyle{ \max (f_P)= y_m}\), to \(\displaystyle{ f _{|\left\{ x_0,x_1, x_2,\ldots, x_n\right\} } : X_n \rightarrow \left\{ y_1, y_2,\ldots, y_m\right\}.}\)

A więc \(\displaystyle{ \alpha :\mathbb{B} _{n,m} \rightarrow \left\{ y_1, y_2,\ldots, y_m\right\} ^{X_n}. }\)

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.
DOWÓD TEGO FAKTU::    
A więc funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. A zatem \(\displaystyle{ \left| \mathbb{B} _{n,m} \right| \le \left| \left\{ y_1, y_2,\ldots, y_m\right\} ^{X_n}\right| }\), który to zbiór po prawej stronie nierówności mocy jest skończony, więc również zbiór \(\displaystyle{ \mathbb {B} _{n,m},}\) jako zbiór mocy nie większej niż moc zbioru skończonego, jest zbiorem skończonym.
DOWÓD TEGO FAKTU::    

A zatem zbiór \(\displaystyle{ \mathbb{B} _{n,m}}\) jest zbiorem skończonym, i otrzymujemy, że to zachodzi dla dowolnych \(\displaystyle{ n,m}\).

Ponieważ zbiór \(\displaystyle{ \NN \times \left\{ 1,2,\ldots, k\right\}\sim \NN}\), to rodzina \(\displaystyle{ \mathbb{B},}\) jako suma przeliczalnie wielu zbiorów skończonych, jest co najwyżej przeliczalna. Mamy \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \NN \right|}\), a zatem na mocy twierdzenia Cantora- Bernsteina \(\displaystyle{ \left| \mathbb{B}\right| =\left| \NN\right|}\), dla zbiorów \(\displaystyle{ Y}\): \(\displaystyle{ \left| Y\right| \ge 2.\square }\) :D


Rozważymy (w skrócie) analogiczny problem dla funkcji nierosnących. Tzn.:

Rozważmy dwa zbiory \(\displaystyle{ X, Y\subset \RR}\): tzn. zbiór \(\displaystyle{ X}\) podobny do \(\displaystyle{ \NN}\), oraz zbiór \(\displaystyle{ Y}\)- niepusty zbiór skończony \(\displaystyle{ Y\subset \RR}\). Rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) funkcji nierosnących, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ f:X \rightarrow Y\Bigl| \ \ f \hbox{ jest nierosnąca}\right\}.}\)

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

ROZWIĄZANIE (W SKRÓCIE):

Jeśli zbiór \(\displaystyle{ Y}\) jest jednoelementowy, to funkcja \(\displaystyle{ f:X \rightarrow Y}\) musi być stała. Wtedy funkcja \(\displaystyle{ f}\) jest nierosnąca, a więc \(\displaystyle{ \mathbb{B}=\left\{ f\right\}}\) i \(\displaystyle{ \left| \mathbb{B} \right| =1.}\)

Numerujemy najpierw zbiory \(\displaystyle{ Y=\left\{ y_1, y_2,\ldots, y_k\right\};}\) oraz \(\displaystyle{ X=\left\{ x_0, x_1,x_2,\ldots\right\}. }\)

Jeśli \(\displaystyle{ \left| Y\right| \ge 2}\), istnieją wtedy dwa różne elementy \(\displaystyle{ a,b\in Y}\). Ponieważ \(\displaystyle{ Y\subset \RR}\), to \(\displaystyle{ a<b}\) lub \(\displaystyle{ b<a.}\)

Jeśli \(\displaystyle{ a<b}\), to definiujemy ciąg funkcji \(\displaystyle{ f_n: X \rightarrow Y}\) w poniższy sposób:

\(\displaystyle{ f_n(x)= \begin{cases} a, \hbox{ dla } x \ge x_n; \\ b, \hbox{ dla } x<x_n. \end{cases}}\)

Wtedy, ponieważ \(\displaystyle{ a<b}\), to funkcja \(\displaystyle{ f_n}\) jest nierosnąca i \(\displaystyle{ f_n\in\mathbb{B}.}\)

Jeśli \(\displaystyle{ b<a}\), to podobnie określamy ciąg funkcji nierosnących \(\displaystyle{ f_n:X \rightarrow Y}\) w poniższy sposób:

\(\displaystyle{ f_n(x)= \begin{cases} b,\hbox{ dla } x \ge x_n;\\ a, \hbox{ dla } x<x_n. \end{cases} }\)

Wtedy funkcja \(\displaystyle{ n\in\NN \stackrel{ \alpha }{\rightarrow} f_n\in\mathbb{B}}\),

jest różnowartościowa.

A więc rodzina \(\displaystyle{ \mathbb{B}}\) jest co najmniej przeliczalna.

Aby wykazać, ze rodzina \(\displaystyle{ \mathbb{B}}\) jest co najwyżej przeliczalna, zauważmy najpierw, że jeśli \(\displaystyle{ f\in\mathbb{B}}\) to istnieje dokładnie jeden element najmniejszy zbioru wartości \(\displaystyle{ f_P}\), który będziemy oznaczać jako \(\displaystyle{ \min\left( f_P\right)}\). Podzielmy więc rodzinę \(\displaystyle{ \mathbb{B}}\) na podrodziny \(\displaystyle{ \mathbb{B} _{n,m} }\) , tzn. dla dowolnych \(\displaystyle{ n\in\NN}\), i \(\displaystyle{ m\in \left\{ 1,2,\ldots, k\right\},}\) zdefiniujmy:

\(\displaystyle{ \mathbb{B} _{n,m} =\left\{ f\in\mathbb{B}: \ f(x_n)=min \left( f_P\right)=y_m \right\}.}\)

Łatwo wtedy zauważyć, że:

\(\displaystyle{ \bigcup_{n\in\NN} \bigcup_{m=1}^{k} \mathbb{B} _{n,m} =\mathbb{B}.}\)

Wtedy rodzina \(\displaystyle{ \mathbb{B} _{n,m}}\) jest zawsze zbiorem skończonym, bo począwszy od argumentu w którym wartość funkcji jest najmniejsza, ponieważ jest to funkcja nierosnąca, więc dalej funkcja będzie stała, więc możliwości tworzenia różnych funkcji jest tylko na skończenie wielu pierwszych argumentach, i przeciwdziedzina funkcji jest również zbiorem skończonym, więc tych możliwości będzie jedynie skończenie wiele. A więc rodzina \(\displaystyle{ \mathbb{B} _{n,,m}}\) jest zawsze zbiorem skończonym.

Ponieważ \(\displaystyle{ \NN \times \left\{ 1,2,,\ldots, k\right\}\sim \NN}\), więc rodzina \(\displaystyle{ \mathbb{B},}\) jako przeliczalna suma zbiorów skończonych, jest co najwyżej przeliczalna. A zatem, na mocy twierdzenia Cantora-Bernsteina: \(\displaystyle{ \left| \mathbb{B}\right| =\left| \NN\right| }\), dla zbiorów \(\displaystyle{ Y:\left| Y\right| \ge 2.\square }\)


Rozważmy teraz (przy tych samych założeniach i tych samych oznaczeniach), rozważmy rodzinę funkcji silnie rosnących, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ f:X \rightarrow Y\Bigl| \ f\hbox { jest silnie rosnąca}\right\}.}\)

Gdzie przypomnę może jednak: \(\displaystyle{ X\subset \RR}\) jest zbiorem podobnym do \(\displaystyle{ \NN}\), a \(\displaystyle{ Y\subset \RR}\) jest niepustym zbiorem skończonym. Wykażemy, że rodzona \(\displaystyle{ \mathbb{B}}\) jest pusta, tzn. że nie ma ani jednej takiej funkcji silnie rosnącej.

DOWÓD TEGO FAKTU:

Na początek ponumerujmy zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), tzn. niech: \(\displaystyle{ X=\left\{ x_0, x_1,x_2,\ldots\right\};}\) oraz \(\displaystyle{ Y=\left\{ y_1,y_2,\ldots, y_k\right\}.}\)

Przypuśćmy nie wprost, że istniej funkcja \(\displaystyle{ f\in\mathbb{B}}\). Wtedy \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest silnie rosnąca. Rozważmy zbiór wartości \(\displaystyle{ f_P\subset Y}\). Wtedy zbiór \(\displaystyle{ f_P}\) jest zbiorem skończonym i niepustym, bo zbiór \(\displaystyle{ X}\) jest niepusty. A zatem zbiór \(\displaystyle{ f_P}\) ma element największy \(\displaystyle{ y\in f_P.}\) Wtedy \(\displaystyle{ y=f(x)}\), gdzie \(\displaystyle{ x\in X}\), czyli \(\displaystyle{ y=f\left( x_n\right)}\), dla pewnego \(\displaystyle{ n}\). Ponieważ funkcja \(\displaystyle{ f}\) jest silnie rosnąca, więc \(\displaystyle{ f(x_ {n+1} )>f \left( x_n\right)= y}\), a \(\displaystyle{ y}\) jest elementem największym zbioru \(\displaystyle{ f_P}\), a \(\displaystyle{ f\left( x _{n+1} \right) \in f_P}\)- więc otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ \mathbb{B}=\emptyset}\), i nie ma takich funkcji silnie rosnących.


Również nie ma funkcji silnie malejących z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), tzn. rodzina \(\displaystyle{ \mathbb{D}}\) dana jako:

\(\displaystyle{ \mathbb{D}=\left\{ f:X \rightarrow Y\Bigl| \ f \hbox{ jest silnie malejąca}\right\},}\)

jest pusta.

DOWÓD TEGO FAKTU:

Przypuśćmy nie wprost, że istnieje funkcja \(\displaystyle{ f\in\mathbb{D}.}\) Wtedy \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest silnie malejąca.

Rozważmy funkcje \(\displaystyle{ f': X \rightarrow Y}\), określoną następująco:

jeśli (dla \(\displaystyle{ x\in X}\)) \(\displaystyle{ f(x)= y_l}\), gdzie \(\displaystyle{ l \in \left\{ 1,2,\ldots, k\right\}}\) , to \(\displaystyle{ f'(x)= y _{\left( k-l+1\right) } .}\)

Zauważmy, że numer \(\displaystyle{ \left( k-l+1\right) \in \left\{ 1,2,\ldots, k\right\}}\), a więc \(\displaystyle{ f'(x)\in Y}\) i \(\displaystyle{ f' :X \rightarrow Y.}\) Jest to funkcja o "przeciwnych" wartościach. Wykażemy, że wtedy funkcja \(\displaystyle{ f'}\) jest silnie rosnąca.
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ f' \in \mathbb{B}}\), a więc rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta- jest to sprzeczność z poprzednim faktem.

Wobec czego również rodzina \(\displaystyle{ \mathbb{D}}\) jest pusta, i nie ma takich funkcji malejących.\(\displaystyle{ \square}\)

Zauważmy, że nie ma również funkcji ze zbioru liczb całkowitych w zbiór liczb naturalnych silnie rosnących. Bo taka funkcja na liczbie \(\displaystyle{ 0}\) by musiała przyjąć jako wartość pewną liczbę naturalną \(\displaystyle{ n}\), i ponieważ funkcja jest silnie rosnąca, to wraz ze spadkiem argumentu wartości funkcji muszą maleć. Więc idąc po liczbach całkowitych ujemnych, dla \(\displaystyle{ x=-n-1}\) powinna funkcja przyjąć wartość ujemną, a jest to funkcja o wartościach w zbiorze liczb naturalnych- sprzeczność. Wobec czego nie ma takich funkcji. Podobne nie istnieje funkcja silnie malejąca ze zbioru liczb całkowitych w zbiór liczb naturalnych( podobnie, tym razem, poczynając od \(\displaystyle{ 0}\), trzeba 'iść' tym razem po argumentach dodatnich).


Na koniec wykażemy, że istnieje dokładnie continuum funkcji ze zbioru liczb całkowitych w zbiór liczb naturalnych funkcji słabo rosnących. Tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ f:\ZZ \rightarrow \NN\Bigl| \ \ f \hbox{ jest słabo rosnąca} \right\}.}\)

I wykażemy, że \(\displaystyle{ \left| \mathbb{B} \right| = \left| \RR\right|.}\)

DOWÓD TEGO FAKTU:

Rozważmy rodzinę:

\(\displaystyle{ \mathbb{A}=\left\{ f:\NN \rightarrow \NN\Bigl| \ \ f \hbox{ jest słabo rosnąca} \right\}.}\)

Przypominam wszystkich funkcji na zbiorze liczb naturalnych silnie rosnących jest continuum, na ważniaku to udowodnili, ja chyba też to udowodniłem na forum. A zatem rodzina \(\displaystyle{ \mathbb{D}}\), dana jako:


\(\displaystyle{ \mathbb{D}= \left\{ f:\NN \rightarrow \NN\Bigl| \ f \hbox{ jest silnie rosnąca}\right\}}\),

jest mocy continuum.

Ponieważ \(\displaystyle{ \mathbb{D}\subset \mathbb{A}}\) (każda funkcja silnie rosnąca jest funkcją słabo rosnącą), więc rodzina \(\displaystyle{ \mathbb{A}}\) ma moc co najmniej continuum. Ale \(\displaystyle{ \mathbb{A}\subset \NN ^{\NN}}\), a takich funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum. A zatem, na mocy twierdzenia Cantora- Bernsteina, rodzina \(\displaystyle{ \mathbb{A}}\) jest mocy continuum. Nas jednak interesuje moc rodziny \(\displaystyle{ \mathbb{B}}\).

Wykażemy teraz, że \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \mathbb{A}\right|}\). W tym celu definiujemy funkcję \(\displaystyle{ \alpha}\) działającą w nastepujący sposób:

\(\displaystyle{ f\in \mathbb{A}\stackrel{ \alpha }{ \rightarrow } f'\in \mathbb{B}}\), gdzie funkcja \(\displaystyle{ f':\ZZ \rightarrow \NN}\) jest określona w poniższy sposób:

\(\displaystyle{ f'(x)= \begin{cases} f(x), \hbox{ dla } x\in\NN; \\ 0, \hbox{ dla } x<0.\end{cases}}\)

Ponieważ funkcja \(\displaystyle{ f}\) jest słabo rosnąca, to łatwo jest sprawdzić, że również funkcja \(\displaystyle{ f'}\) jest słabo rosnąca, a zatem \(\displaystyle{ f'\in \mathbb{B}}\),i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.

I bardzo łatwo jest wykazać, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. A zatem \(\displaystyle{ \left| \RR\right|= \left| \mathbb{A}\right| \le \left| \mathbb{B}\right|.}\) Z drugiej zaś strony \(\displaystyle{ \mathbb{B}\subset \NN ^{\ZZ}\sim \NN ^{\NN}\sim \RR}\). A zatem, na mocy twierdzenia Cantora-Bernsteina, rodzina \(\displaystyle{ \mathbb{B}}\) ma moc continuum\(\displaystyle{ .\square}\) :D 8-)
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski »

Jakub Gurak pisze: 23 kwie 2022, o 21:37 Gdzie przypomnę może jednak: \(\displaystyle{ X\subset \RR}\) jest zbiorem podobnym do \(\displaystyle{ \NN}\), a \(\displaystyle{ Y\subset \RR}\) jest niepustym zbiorem skończonym. Wykażemy, że rodzona \(\displaystyle{ \mathbb{B}}\) jest pusta, tzn. że nie ma ani jednej takiej funkcji silnie rosnącej.

DOWÓD TEGO FAKTU:

Na początek ponumerujmy zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), tzn. niech: \(\displaystyle{ X=\left\{ x_0, x_1,x_2,\ldots\right\};}\) oraz \(\displaystyle{ Y=\left\{ y_1,y_2,\ldots, y_k\right\}.}\)

Przypuśćmy nie wprost, że istniej funkcja \(\displaystyle{ f\in\mathbb{B}}\). Wtedy \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest silnie rosnąca. Rozważmy zbiór wartości \(\displaystyle{ f_P\subset Y}\). Wtedy zbiór \(\displaystyle{ f_P}\) jest zbiorem skończonym i niepustym, bo zbiór \(\displaystyle{ X}\) jest niepusty. A zatem zbiór \(\displaystyle{ f_P}\) ma element największy \(\displaystyle{ y\in f_P.}\) Wtedy \(\displaystyle{ y=f(x)}\), gdzie \(\displaystyle{ x\in X}\), czyli \(\displaystyle{ y=f\left( x_n\right)}\), dla pewnego \(\displaystyle{ n}\). Ponieważ funkcja \(\displaystyle{ f}\) jest silnie rosnąca, więc \(\displaystyle{ f(x_ {n+1} )>f \left( x_n\right)= y}\), a \(\displaystyle{ y}\) jest elementem największym zbioru \(\displaystyle{ f_P}\), a \(\displaystyle{ f\left( x _{n+1} \right) \in f_P}\)- więc otrzymujemy sprzeczność.

Wobec czego \(\displaystyle{ \mathbb{B}=\emptyset}\), i nie ma takich funkcji silnie rosnących.
Ten dowód powinien mieć jedną linijkę:

Każda funkcja ściśle rosnąca jest różnowartościowa. Nie ma funkcji różnowartościowych ze zbioru nieskończonego w zbiór skończony.

JK
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

Re: Teoria mocy zbiorów

Post autor: Jakub Gurak »

Udowodniłem przedwczoraj, że jeśli \(\displaystyle{ X}\) jest niepustym skończonym zbiorem \(\displaystyle{ n}\)-elementowym, to dobrych porządków na zbiorze \(\displaystyle{ X}\) jest tyle, ile bijekcji na zbiorze \(\displaystyle{ \left\{ 1,2,\ldots,n\right\}}\), czyli dokładnie \(\displaystyle{ n!.}\) Przedstawię teraz dowód tego ciekawego faktu.


Niech \(\displaystyle{ X}\) będzie niepustym zbiorem skończonym, \(\displaystyle{ n}\)-elementowym, oznaczmy więc: \(\displaystyle{ X=\left\{ x_1,x_2,\ldots, x_n\right\}.}\)

Rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ \le : \ \ \le \hbox{ jest dobrym porządkiem na zbiorze X}\right\}.}\)

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

Wykażemy, że \(\displaystyle{ \left| \mathbb{B}\right| =n! . }\)

DOWÓD TEGO FAKTU:

Rozważmy rodzinę \(\displaystyle{ \mathbb{A}}\), daną jako:

\(\displaystyle{ \mathbb{A}=\left\{ f:\left\{ 1,2,\ldots, n\right\} \rightarrow \left\{ 1,2,\ldots, n\right\} \Bigl| \ \ f\hbox { jest bijekcją} \right\}.}\)

Wykażemy, że \(\displaystyle{ \mathbb{A}\sim \mathbb{B}.}\)

W tym celu określamy funkcję \(\displaystyle{ \alpha :\mathbb{A} \rightarrow \mathbb{B},}\) określoną w następujący sposób:

jeśli \(\displaystyle{ f\in\mathbb{A}}\), wtedy \(\displaystyle{ f}\) jest bijekcją z \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\) w ten sam zbiór, wtedy również \(\displaystyle{ f ^{-1}}\) jest bijekcją z \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\) w siebie.

I definiujemy porządek \(\displaystyle{ \le_f}\) na \(\displaystyle{ X=\left\{ x_1, x_2,\ldots, x_n\right\},}\) w następujący sposób:

\(\displaystyle{ x_k \le_f x_L \Longleftrightarrow f ^{-1} (k) \le f ^{-1} (l).}\)

(Bijekcja przestawia elementy zbioru \(\displaystyle{ \left\{ 1,2, \ldots, n\right\}}\), na ciąg elementów tego zbioru \(\displaystyle{ \left( f_1, f_2, \ldots, f_n\right)}\) , i my określamy porządek: \(\displaystyle{ x _{f_1}< x _{f_2}<\ldots< x _{f_n}}\) ) .

Łatwo sprawdzić, że jest to liniowy porządek, sprawdźmy dla przykładu antysymetrię:

Jeśli \(\displaystyle{ x_k \le_f x_l}\) i \(\displaystyle{ x _{l} \le_f x_k}\), to \(\displaystyle{ f ^{-1}(k) \le f ^{-1}(l)}\) i \(\displaystyle{ f ^{-1}(l) \le f ^{-1}(k),}\) i ponieważ te wartości funkcji odwrotnej są elementami zbioru \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\), więc \(\displaystyle{ f ^{-1}(k)= f ^{-1}(l)}\) , i ponieważ \(\displaystyle{ f ^{-1}}\) jest bijekcją, więc z jej różnowartościowości otrzymujemy, że: \(\displaystyle{ k=l}\), i \(\displaystyle{ x_k=x_l}\), co należało pokazać dla dowodu antysymetrii.

Łatwo sprawdzić pozostałe własności relacji liniowego porządku.

Mamy również :

\(\displaystyle{ x _{k} \le _f x_l \Leftrightarrow f ^{-1}(k) \le f ^{-1} (l) \Leftrightarrow k \le l}\),

a więc ten porządek jest podobny do zwykłego porządku na \(\displaystyle{ \left\{ 1,2,\ldots, n\right\}}\) . Ponieważ jest to dobry porządek, to również porządek doń podobny \(\displaystyle{ \le _f }\) jest dobrym porządkiem na \(\displaystyle{ X}\), a więc \(\displaystyle{ \left( \le _f\right) \in \mathbb{B}}\), i funkcja:

\(\displaystyle{ \alpha : f\in \mathbb{A} \rightarrow \left( \le _{f} \right) \in \mathbb{B},}\)

jest dobrze określona.


Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest bijekcją.

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. W tym celu weźmy dwie różne funkcję \(\displaystyle{ f_1, f_2\in \mathbb{A}}\), i pokażmy, że przypisane im porządki są różne.

Wtedy \(\displaystyle{ f_1,f_2:\left\{ 1,2,\ldots, n\right\} \rightarrow \left\{ 1,2,\ldots, n\right\}}\), więc ponieważ te funkcję są różne, więc \(\displaystyle{ f_1(m) \neq f_2(m)}\), dla pewnego \(\displaystyle{ m \in \left\{ 1,2,\ldots, n \right\} }\). Niech \(\displaystyle{ m \in \left\{ 1,2,\ldots, n\right\}}\) będzie najmniejszym takim numerem, że \(\displaystyle{ f_1(m) \neq f_2(m).}\)

Jeśli \(\displaystyle{ m=1}\), to \(\displaystyle{ x _{m_1}:=x _{\left( f_1(m)\right) }}\) jest elementem najmniejszym zbioru \(\displaystyle{ X}\) względem \(\displaystyle{ \le _{f_1}}\), oraz

\(\displaystyle{ x _{m_2}:= x _{\left( f_2(m)\right) }}\) jest elementem najmniejszym zbioru \(\displaystyle{ X}\) względem \(\displaystyle{ \le _{f_2},}\)

Ponieważ \(\displaystyle{ f_1(m) \neq f_2(m)}\), to również \(\displaystyle{ x _{m_1} \neq x _{m_2}}\) ( ponumerowaliśmy zbiór \(\displaystyle{ X}\), więc nie może na różnych numerach być osiągana ta sama wartość), a więc również \(\displaystyle{ x _{m_1} \neq x _{m_2}}\), a zatem porządki \(\displaystyle{ \le _{f_1}}\) i \(\displaystyle{ \le _{f_2} }\) na \(\displaystyle{ X}\) mają różne elementy najmniejsze, a więc są różne, czyli \(\displaystyle{ \left( \le _{f_1}\right) \neq \left( \le _{f_2} \right)}\), co należało pokazać.

Jeśli \(\displaystyle{ m \ge 2}\). Wtedy \(\displaystyle{ \left( m-1\right) \in \left\{ 1,2,\ldots, n\right\}.}\) Ponieważ \(\displaystyle{ m}\) jest najmniejszym numerem gdzie funkcje się różnią co do wartości, a więc: \(\displaystyle{ f_1\left( m-1\right)= f_2\left( m-1\right)}\) na mniejszym numerze funkcje muszą być równe. Przypuśćmy nie wprost, że \(\displaystyle{ \left( \le _{f_1}\right) =\left( \le _{f_2} \right) }\), oznaczmy ten porządek jako \(\displaystyle{ \le _f. }\) Wtedy oznaczając: \(\displaystyle{ x _{m_1}:= x _{f_1\left( m-1\right) } = x _{f_2 \left( m-1 \right) }=:x _{m_2}.}\) Wtedy element \(\displaystyle{ x _{m _{1} }}\) nie jest największy, a zatem ma następnik, i ponieważ mamy ten sam porządek na \(\displaystyle{ X}\) i ten sam element, wiec jest to następnik elementu \(\displaystyle{ x _{m_2}}\), czyli \(\displaystyle{ x _{f_{1} }^{+}= x _{f_2 } ^{+} = x_k}\), gdzie \(\displaystyle{ k \in \left\{ 1,2,\ldots, n\right\}}\). Wtedy \(\displaystyle{ \left( f_1\left( m-1\right)\right) ^{+} = k = \left( f_2\left( m-1\right)\right) ^{+}}\), a więc \(\displaystyle{ f_1(m)= f_2(m)}\)- sprzeczność.

Wobec czego \(\displaystyle{ \left( \le _{f_1} \right) \neq \left( \le _{f_2} \right)}\), i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


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

Niech \(\displaystyle{ \left( \le \right) \in \mathbb{B}}\). Wtedy porządek jest dobrym porządkiem na \(\displaystyle{ X}\). Wtedy niepusty zbiór \(\displaystyle{ X}\) ma element najmniejszy \(\displaystyle{ x\in X}\). Wtedy \(\displaystyle{ x=x _{k_1}}\), gdzie \(\displaystyle{ k_1 \in \left\{ 1,2,\ldots,n\right\}.}\) Również skończony niepusty zbiór \(\displaystyle{ X}\) ma element największy \(\displaystyle{ x _{k_n}}\), gdzie \(\displaystyle{ k_n \in \left\{ 1,2,\ldots, n\right\}.}\)

Definiujemy funkcję \(\displaystyle{ f:\left\{ 1,2,\ldots, n\right\} \rightarrow \left\{ 1,2,\ldots,n\right\}}\) w poniższy sposób:

\(\displaystyle{ f(1)=k_1}\),

przypuśćmy dalej, że zdefiniowaliśmy ( :!: dla \(\displaystyle{ l<n}\) ) \(\displaystyle{ f_l=k_l}\), gdzie \(\displaystyle{ k_l \in \left\{ 1,2,\ldots, n\right\}}\). Ponieważ \(\displaystyle{ l<n}\), to element \(\displaystyle{ x _{k_l}}\) nie jest największy, a zatem mam następnik \(\displaystyle{ x _{k _{l+1} }}\), gdzie \(\displaystyle{ k _{l+1}\in \left\{ 1,2,\ldots,n\right\}}\), wtedy definiujemy \(\displaystyle{ f\left( l+1\right)=k _{\left( l+1\right) }}\), i postępując w ten sposób poprzez rekurencję skończoną (ograniczoną) otrzymujemy funkcję \(\displaystyle{ f:\left\{ 1,2,\ldots, n\right\} \rightarrow \left\{ 1,2,\ldots, n\right\}.}\)

Wykażemy, że funkcja \(\displaystyle{ f}\) jest różnowartościowa.
DOWÓD TEGO FAKTU::    
Wykażemy teraz, że funkcja \(\displaystyle{ f}\) jest 'na'.

Niech \(\displaystyle{ y\in \left\{ 1,2,\ldots,n\right\}.}\)

Zaczniemy od zdefiniowania \(\displaystyle{ n}\)-wyrazowego ciągu 'kolejnych elementów' tego dobrego porządku.

Niech \(\displaystyle{ y_1}\) będzie elementem najmniejszym \(\displaystyle{ X}\) względem \(\displaystyle{ \le }\),
Niech \(\displaystyle{ y_2= y'_1}\) ( jest to następnik elementu \(\displaystyle{ y_1}\));
\(\displaystyle{ y_3=y'_2, \ldots, y _{n}= y'_{n-1}, }\)

dokładniej, dla \(\displaystyle{ l<n}\) definiujemy:

\(\displaystyle{ y _{l+1}= \left( y_l\right)'.}\)

I postępując w ten sposób otrzymujemy ciąg:

\(\displaystyle{ \left( y_1,y_2,\ldots, y_n\right).}\)

Wykażemy teraz, że każdy element \(\displaystyle{ x\in X}\) jest równy: \(\displaystyle{ x=y_l}\), dla pewnego \(\displaystyle{ l \in \left\{ 1,2,\ldots,n\right\}.}\)

W tym celu wykażemy, że zbiór \(\displaystyle{ y_P=\left\{ y_l: l=1,2,\ldots, n\right\}=X}\).

Dowód będzie indukcyjny (wszak zasada indukcji obowiązuje również w niepustych skończonych :o zbiorach dobrze uporządkowanych).

Wykażemy indukcyjnie, że: \(\displaystyle{ X \cap y_P=X.}\)

Jeśli \(\displaystyle{ x\in X}\), i \(\displaystyle{ x}\) jest elementem najmniejszym zbioru \(\displaystyle{ X}\), to mamy \(\displaystyle{ y_1=x}\), a więc \(\displaystyle{ x\in X \cap y_P.}\)

Niech \(\displaystyle{ z\in X}\). Niech \(\displaystyle{ A=\left\{ y\in X: y<z\right\}}\) będzie dowolnym podzbiorem zbioru \(\displaystyle{ y_P}\), i pokażemy, że \(\displaystyle{ z\in y_P.}\)

Zbiór \(\displaystyle{ A}\) jest niepusty (należy do niego element najmniejszy ), i zbiór \(\displaystyle{ A}\) jest skończony, a zatem zbiór \(\displaystyle{ A}\) ma element największy \(\displaystyle{ a\in A}\). Ponieważ \(\displaystyle{ a\in A}\), więc \(\displaystyle{ a\in X,}\) i \(\displaystyle{ a<z}\). Ponieważ \(\displaystyle{ a\in A\subset y_P}\), więc \(\displaystyle{ a=y_l}\), gdzie \(\displaystyle{ l=1,2,\ldots, n}\). Pokażemy, że \(\displaystyle{ z=a'.}\)

W tym celu weźmy element \(\displaystyle{ y\in X}\) taki, że \(\displaystyle{ y>a}\), i pokażmy, że \(\displaystyle{ y \ge z}\). Przypuśćmy, że tak nie jest. Wtedy \(\displaystyle{ y<z}\), a stąd możemy wnioskować, że \(\displaystyle{ y\in A}\), a ponieważ element \(\displaystyle{ a}\) jest największy w \(\displaystyle{ A}\), więc \(\displaystyle{ y \le a}\), a mamy \(\displaystyle{ y>a}\)- sprzeczność. Wobec czego \(\displaystyle{ z=a'. }\)\(\displaystyle{ }\)

A zatem \(\displaystyle{ z= \left( y_l\right)'=y _{l+1}}\) , a zatem \(\displaystyle{ z\in y_P.}\)

Na mocy zasady indukcji dla dobrych porządków: \(\displaystyle{ A=X}\).

Ponieważ \(\displaystyle{ A\subset y_P}\),( a \(\displaystyle{ y_P\subset X}\)), więc \(\displaystyle{ X=y_P}\).

Niech (przypomnę może: ustaliliśmy dowolny element \(\displaystyle{ y \in \left\{ 1,2,\ldots,n\right\},}\) i chcemy pokazać, że jest on wartością funkcji \(\displaystyle{ f}\)).

Wtedy \(\displaystyle{ x _{y}\in X=y_P}\), niech więc \(\displaystyle{ l \in \left\{1,2,\ldots, n\right\}}\) będzie takim numerem, że \(\displaystyle{ y_l= x _{y}.}\)

Jeśli \(\displaystyle{ y_l= y_1}\), a \(\displaystyle{ y_1}\) jest elementem najmniejszym zbioru \(\displaystyle{ X}\), więc z definicji funkcji \(\displaystyle{ f}\) otrzymujemy: \(\displaystyle{ f(1)=y}\), a więc numer \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ f}\).

A jeśli \(\displaystyle{ y_l \neq y_1}\), wtedy \(\displaystyle{ l \neq 1}\), wtedy \(\displaystyle{ \left( l-1\right) \in \left\{ 1,2,\ldots, n-1\right\}}\), a ponieważ \(\displaystyle{ y_l= \left( y _{l-1} \right)'}\), więc wtedy \(\displaystyle{ y_l= x_y}\), a więc z definicji funkcji \(\displaystyle{ f}\) otrzymujemy: \(\displaystyle{ f(l)=y}\), a więc również element \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ f.}\) A zatem funkcja \(\displaystyle{ f}\) jest 'na'.

A zatem \(\displaystyle{ f\in\mathbb{A}}\).

A zatem funkcja \(\displaystyle{ \alpha}\) zwraca na tej funkcji pewien dobry porządek, tzn. mamy:

\(\displaystyle{ \alpha \left( f\right) =\left( \le _{f} \right)\in\mathbb{B}.}\)

Jest to dobry porządek na zbiorze \(\displaystyle{ X}\). Również porządek \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ X}\). Wykażemy teraz, że te dwa porządki są równe.

Niech \(\displaystyle{ x,y\in X}\). Wtedy \(\displaystyle{ x=x_l, y=x_m}\), gdzie \(\displaystyle{ l,m\in \left\{ 1,2,\ldots,n\right\}}\).

I wtedy oznaczając (w uproszczeniu) ten porządek \(\displaystyle{ \le _f}\) jako: \(\displaystyle{ x _{p_1}<x _{p_2}<\ldots < x _{p_n}}\), gdzie zawsze \(\displaystyle{ p_i\in \left\{ 1,2,\ldots,n\right\}}\), to mamy:

\(\displaystyle{ x \le _f y \Leftrightarrow x_l \le _f x_m \Leftrightarrow x _{p_l} \le x _{p_m} \Leftrightarrow f ^{-1}(p_l)= l \le m =f ^{-1} (p_m).}\)

Z drugiej strony oznaczając porządek \(\displaystyle{ \le}\) jako: \(\displaystyle{ x _{k_1} < x _{k_2}<\ldots <k _{k_n}}\), gdzie \(\displaystyle{ k_i\in \left\{ 1,2,\ldots,n\right\}}\), to mamy:

\(\displaystyle{ x \le y \Leftrightarrow x _l \le x_m \Leftrightarrow x _{k_l} \le x _{k_m} \Leftrightarrow l \le m \Leftrightarrow f ^{-1} \left( k_l\right) \le f ^{-1} \left( k_m\right).}\)

A zatem mamy:

\(\displaystyle{ x \le _f y \Leftrightarrow l \le m \Leftrightarrow x \le y. }\)

A zatem te dwa porządki są równe, czyli:

\(\displaystyle{ \alpha (f)=\left( \le _{f} \right) =\left( \le \right)}\),

a więc porządek \(\displaystyle{ \le}\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru takiego porządku otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.


A zatem \(\displaystyle{ \mathbb{A}\sim \mathbb{B}}\).

Ponieważ \(\displaystyle{ \left| \mathbb{A}\right| =n!}\) (bijekcji na zbiorze \(\displaystyle{ n}\)-elementowym jest \(\displaystyle{ n!}\)), to również \(\displaystyle{ \left| \mathbb{B}\right|= n!}\), dla \(\displaystyle{ n>0. \square}\) :D


Wykażemy jeszcze, że liniowych porządków na zbiorze skończonym \(\displaystyle{ n}\)-elementowym jest dokładnie \(\displaystyle{ n!}\). Tzn.

Niech \(\displaystyle{ X}\) będzie zbiorem skończonym \(\displaystyle{ n}\)-elementowym. Rozważmy rodzinę liniowych porządków \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ \le : \ \le \hbox{ jest liniowym porządkiem na zbiorze } X\right\} .}\)

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

Wykażemy, że również \(\displaystyle{ \left| \mathbb{B}\right|= n! .}\)

DOWÓD TEGO FAKTU:

Jeśli \(\displaystyle{ X=\emptyset}\), to rodzina \(\displaystyle{ \mathbb{B}}\) jest jednoelementowa (złożona z porządku pustego ), a więc \(\displaystyle{ \left| \mathbb{B}\right|=1=0!.}\)

Jeśli \(\displaystyle{ X \neq \emptyset}\), to rozważmy rodzinę dobrych porządków \(\displaystyle{ \mathbb{A}}\), daną jako:

\(\displaystyle{ \mathbb{A}=\left\{ \le : \ \le \hbox{ jest dobrym porządkiem na } X\right\}.}\)

Wykażemy, że: \(\displaystyle{ \mathbb{A}=\mathbb{B}}\).

Niewątpliwie \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) (dobry porządek jest liniowy).

Niech teraz \(\displaystyle{ \left( \le \right) \in \mathbb{B}.}\) Wtedy porządek \(\displaystyle{ \le}\) jest porządkiem liniowym na \(\displaystyle{ X}\). Aby wykazać, że jest dobry, to niech \(\displaystyle{ A \neq \left\{ \right\}}\) będzie niepustym podzbiorem zbioru \(\displaystyle{ X}\). Wykażemy, że zbiór \(\displaystyle{ A}\) ma elementy najmniejszy. Wtedy \(\displaystyle{ A}\) jest zbiorem skończonym i niepustym, a zatem pewien prosty fakt odnośnie skończonych podzbiorów zbiorów liniowo uporządkowanych, daje, że zbiór \(\displaystyle{ A}\) ma element najmniejszy. A wiec \(\displaystyle{ \le}\) jest dobrym porządkiem, i \(\displaystyle{ \left( \le \right) \in \mathbb{A}. }\)

A zatem: \(\displaystyle{ \mathbb{A}=\mathbb{B}.}\)

Ponieważ udowodniłem powyżej, że dobrych porządków na skończonym niepustym zbiorze jest \(\displaystyle{ n!}\), więc również:

\(\displaystyle{ \left| \mathbb{B}\right| =\left| \mathbb{A}\right|= n!}\), dla \(\displaystyle{ n>0}\),

i dla \(\displaystyle{ n=0}\) również wzór zachodzi.\(\displaystyle{ \square }\)
Jan Kraszewski
Administrator
Administrator
Posty: 34125
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 3 razy
Pomógł: 5192 razy

Re: Teoria mocy zbiorów

Post autor: Jan Kraszewski »

Uch...

Łatwo zauważyć, że każdy porządek liniowy na zbiorze skończonym jest dobry (bo np. w każdym skończonym zbiorze częściowo uporządkowanym jest element minimalny). Porządków dobrych na zbiorze skończonym jest zatem tyle, ile jest na nim porządków liniowych, a te wszystkie są ze sobą izomorficzne i różnią się tylko kolejnością elementów. Zatem na zbiorze \(\displaystyle{ n}\)-elementowym jest \(\displaystyle{ n!}\) dobrych porządków.

To samo, ale w trzech linijkach...

JK
ODPOWIEDZ