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

Teoria mocy zbiorów

Post autor: Jakub Gurak »

Podam parę ciekawych faktów z teorii mocy zbiorów.

Przypominam \(\displaystyle{ \NN \times \NN\sim\NN}\), \(\displaystyle{ 2^{\NN}=\left\{ 0,1\right\} ^{\NN}\sim\RR. }\)

\(\displaystyle{ A \times B\sim C \times D,}\) jeśli tylko \(\displaystyle{ A\sim C, B\sim D.}\)

Szkic dowodu:

Niech \(\displaystyle{ f:A \rightarrow C}\) będzie bijekcją, \(\displaystyle{ g:B \rightarrow D}\) będzie bijekcją. Rozważmy funkcję \(\displaystyle{ h:A \times B \rightarrow C \times D}\) określoną jako:

\(\displaystyle{ h(a,b)=\left( f(a),g(b)\right). }\)

Funkcja \(\displaystyle{ h}\) jest dobrze określona, i jest różnowartościowa, bo funkcje \(\displaystyle{ f,g}\) są różnowartościowe ( jako bijekcje). Aby pokazać, że jest 'na' zbiór \(\displaystyle{ C \times D}\), to niech \(\displaystyle{ \left( c,d\right)\in C \times D}\). Wtedy \(\displaystyle{ c\in C, d\in D}\). Ponieważ \(\displaystyle{ c\in C}\), a \(\displaystyle{ f:A \rightarrow C}\) jest 'na' zbiór \(\displaystyle{ C}\), to \(\displaystyle{ f(a)=c}\), dla pewnego \(\displaystyle{ a\in A.}\) Ponieważ \(\displaystyle{ d\in D}\), a \(\displaystyle{ g:B \rightarrow D}\) jest 'na' zbiór \(\displaystyle{ D}\), więc \(\displaystyle{ g(b)=d}\), dla pewnego \(\displaystyle{ b\in B}\). Wtedy \(\displaystyle{ h(a,b)=(f(a),g(b))=(c,d)}\), a więc para \(\displaystyle{ (c,d)}\) jest wartością funkcji \(\displaystyle{ h}\). Wobec dowolności wyboru takiej pary otrzymujemy, że \(\displaystyle{ h}\) jest 'na'. A więc \(\displaystyle{ h}\) jest bijekcją, i zbiory \(\displaystyle{ A\times B}\) i \(\displaystyle{ C \times D}\) są równoliczne. \(\displaystyle{ \square}\)

Kolejny fakt:

\(\displaystyle{ 2^X=\left\{ 0,1\right\} ^{X} \sim P(X). }\)

Dowód: Niech \(\displaystyle{ X}\) będzie zbiorem. Zdefiniujmy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{X} =2^X \rightarrow P(X)}\) jako:

\(\displaystyle{ \alpha \left( f\right)=\stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}. }\)

Funkcja \(\displaystyle{ \alpha}\) jest dobrze zdefiniowana. Aby wykazać różnowartościowość, to niech funkcje \(\displaystyle{ f,g\in2^X}\), będą takie, że \(\displaystyle{ \alpha \left( f\right) = \alpha \left( g\right)}\). Wtedy \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}}\), i co za tym idzie \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 0\right\}=X \setminus \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=X \setminus\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}= \stackrel{ \rightarrow }{g ^{-1} }\left\{ 0\right\},}\) czyli \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 0\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 0\right\}}\) oraz \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=\stackrel{ \rightarrow }{g ^{-1} }\left\{ 1\right\}}\) ,a więc funkcje \(\displaystyle{ f,g}\) na każdym argumencie przyjmują te same wartości, skąd \(\displaystyle{ f=g}\), a więc \(\displaystyle{ \alpha}\) jest różnowartościowa. Aby wykazać, że jest 'na' to niech \(\displaystyle{ B\subset X}\), wtedy zdefiniujmy \(\displaystyle{ f:X \rightarrow \left\{ 0,1\right\}}\) jako: \(\displaystyle{ f(x)=1}\), jeśli \(\displaystyle{ x\in B}\), i \(\displaystyle{ f(x)=0}\)jeśli \(\displaystyle{ x\not\in B. }\)Otrzymujemy \(\displaystyle{ \alpha \left( f\right)=\stackrel{ \rightarrow }{f ^{-1} }\left\{ 1\right\}=B}\), a więc zbiór \(\displaystyle{ B}\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru takiego zbioru wnioskujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'. \(\displaystyle{ \square}\)

Przypominam ważny fakt, że dla dowolnych trzech zbiorów \(\displaystyle{ A,B,C}\)

\(\displaystyle{ \left( A^B\right) ^{C}=A ^{B \times C}. }\)

Możemy teraz wykazać bardzo prosto, że iloczyn kartezjański dowolnych dwóch zbiorów przeliczalnych (równolicznych z \(\displaystyle{ \NN}\)) jest zbiorem przeliczalnym.

Niech zbiory \(\displaystyle{ A,B\sim\NN}\). Wtedy na mocy prawa o równoliczności iloczynów kartezjańskich \(\displaystyle{ A \times B\sim \NN\times\NN\sim \NN}\), a więc \(\displaystyle{ A \times B\sim \NN}\), czyli zbiór \(\displaystyle{ A \times B}\) jest przeliczalny. \(\displaystyle{ \square}\) :D

Możemy wykazać, że \(\displaystyle{ 2^{\NN}\times 2 ^{\NN}\sim 2^{\NN}.}\)

Aby to wykazać rozważmy parę ciągów zero-jedynkowych \(\displaystyle{ f=(f_0,f_1,f_2,\ldots), g=(g_0,g_1,g_2,\ldots),}\) przypiszmy im ciąg

\(\displaystyle{ h=(f_0,g_0,f_1,g_1,f_2,g_2,\dots).}\)

Wtedy \(\displaystyle{ h\in \left( \left\{ 0,1\right\} \cup \left\{ 0,1\right\} \right) ^{\NN}=\left\{ 0,1\right\} ^{\NN}=2^ {\NN}. }\)

Pokażemy, że funkcja \(\displaystyle{ \alpha: 2^{\NN} \times 2 ^{\NN} \rightarrow 2^{\NN} }\) jest bijekcją.

Aby pokazać różnowartościowość, weźmy dwie różne pary ciągów \(\displaystyle{ \left( f_1,g_1\right);\left( f_2,g_2\right) }\), oznaczmy przypisane im ciągi jako odpowiednio \(\displaystyle{ h_1,h_2}\). Wiemy, że \(\displaystyle{ \left( f_1,g_1\right) \neq \left( f_2,g_2\right) }\),więc \(\displaystyle{ f _{1} \neq f _{2}}\) lub \(\displaystyle{ g _{1} \neq g _{2}}\). Jeśli \(\displaystyle{ f _{1} \neq f _{2}}\), to istnieje \(\displaystyle{ n}\) naturalne, takie, że \(\displaystyle{ f_1(n) \neq f_2\left( n\right)}\). Wtedy \(\displaystyle{ h _{1}\left( 2n\right)=f _{1}(n) \neq f_2\left( n\right)= h _{2}\left( 2n\right)}\), a więc \(\displaystyle{ h_1 \neq h_2}\). Drugi przypadek (tzn.\(\displaystyle{ g _{1} \neq g _{2}}\)) jest analogiczny. A więc jest to przekształcenie różnowartościowe. Aby wykazać, że jest 'na', niech \(\displaystyle{ h\in 2^{\NN}}\), tzn. \(\displaystyle{ h=\left( h_0,h_1,h_2,\ldots\right)}\), rozważmy podciągi \(\displaystyle{ f_n=h _{2n}=\left( h _{0},h _{2},h _{4},\ldots \right)}\); oraz \(\displaystyle{ g_n= h_{2n+1}=\left( h_1,h _{3},h _{5},\ldots \right)}\), wtedy \(\displaystyle{ \alpha \left( f,g\right)=\left( f_0,g_0,f_1,g_1,\ldots\right)=\left( h_0,h_1,h_2,h_3,\ldots \right)=h}\), a więc ciąg \(\displaystyle{ h}\) jest wartością funkcji \(\displaystyle{ \alpha }\). Otrzymujemy, że funkcja \(\displaystyle{ \alpha }\) jest 'na', a więc jest bijekcją. \(\displaystyle{ \square}\)

Wnioskiem z tego jest (oraz z tego, że \(\displaystyle{ 2^{\NN}}\) jest mocy continuum), mamy, że \(\displaystyle{ \RR \times \RR\sim\RR.}\)

Mamy bowiem \(\displaystyle{ \RR \times \RR \sim 2^{\NN} \times2^{\NN} \sim 2^{\NN}\sim\RR. \square}\)

A więc płaszczyzna kartezjańska jest równoliczna z prostą.

Na koniec podam ciekawy fakt, ze jeśli mamy dwie pary zbiorów, wraz z bijekcjami między nimi, to jeśli dziedziny tych funkcji są rozłączne i zbiory wartości tych funkcji są rozłączne, to suma mnogościowa tych bijekcji jest bijekcją ze sumy dziedzin w sumę zbiorów wartości. Jest to przydatny fakt. Dowód mogę podesłać zainteresowanym (ale z tego co kojarzę, to dowód jest trochę żmudny).

Więcej zadań z teorii mocy zbiorów można znaleźć też tutaj: Ciekawe zadania.
Awatar użytkownika
Gosda
Użytkownik
Użytkownik
Posty: 340
Rejestracja: 29 cze 2019, o 19:46
Płeć: Mężczyzna
Lokalizacja: Oulu
Podziękował: 42 razy
Pomógł: 60 razy

Re: Teoria mocy zbiorów

Post autor: Gosda »

Jakub Gurak pisze: 22 sty 2020, o 00:05 Na koniec podam ciekawy fakt, ze jeśli mamy dwie pary zbiorów, wraz z bijekcjami między nimi, to jeśli dziedziny tych funkcji są rozłączne i zbiory wartości tych funkcji są rozłączne, to suma mnogościowa tych bijekcji jest bijekcją ze sumy dziedzin w sumę zbiorów wartości. Jest to przydatny fakt. Dowód mogę podesłać zainteresowanym (ale z tego co kojarzę, to dowód jest trochę żmudny).
Nie jest żmudny. Niech \(\displaystyle{ f \colon A \to B}\), \(\displaystyle{ g \colon C \to D}\) będą bijekcjami, o których mówisz. Ich suma jest bijekcją, ponieważ:

- jest suriekcją. Jeżeli ustalimy \(\displaystyle{ y \in B \cup D}\), to (bez straty ogólności) \(\displaystyle{ y \in B}\) oraz możemy skorzystać, z tego, że \(\displaystyle{ f}\) jest bijekcją. Wtedy element \(\displaystyle{ x \in A}\), \(\displaystyle{ x = f^{-1}(y)}\) jest dobrze określony i \(\displaystyle{ (f \cup g)(x) = y}\). Dla \(\displaystyle{ y \in D}\) dowód przebiega analogicznie, wystarczy pozamieniać literki.

- jest injekcją. Jeżeli ustalimy \(\displaystyle{ x_1, x_2 \in A \cup C}\), to albo oba są elementami jednego ze zbiorów (bez straty ogólności, \(\displaystyle{ A}\)) i możemy skorzystać z tego, że obcięcie sumy funkcji do zbioru \(\displaystyle{ A}\) jest wyjściową funkcją \(\displaystyle{ f}\), która była infekcją; albo należą do różnych zbiorów, bez straty ogólności \(\displaystyle{ x_1 \in A, x_2 \in C}\): wtedy zaś ich obrazy \(\displaystyle{ f(x_1) \in B, f(x_2) \in D}\) są elementami rozłącznych zbiorów, zatem różne.
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 »

Jakbyś chciał to wszystko dokładnie zapisać, to nie byłoby tak łatwo...

Kolejne fakty:

Nie istnieje zbiór wszystkich zbiorów.

Dowód( w aksjomatycznej teorii mnogości):

Przypuśćmy nie wprost, że zbiór \(\displaystyle{ X}\) jest zbiorem wszystkich zbiorów. Wtedy z aksjomatu regularności (\(\displaystyle{ X\not\in X}\))- sprzeczność. Udowodnijmy to też w inny sposób przy pomocy teorii mocy. Niech \(\displaystyle{ X}\) będzie zbiorem wszystkich zbiorów. Rozważmy jego zbiór potęgowy \(\displaystyle{ P(X)}\). Wtedy \(\displaystyle{ P(X)\subset X}\), bo każdy podzbiór zbioru \(\displaystyle{ X}\) jest oczywiście zbiorem, zatem elementem zbioru wszystkich zbiorów. Równocześnie mamy \(\displaystyle{ \left| X\right| \le \left| P(X)\right| }\), gdyż możemy zdefiniować funkcję \(\displaystyle{ f:X \rightarrow P\left( X\right)}\) jako:

\(\displaystyle{ f\left( x\right)=\left\{ x\right\}. }\)

Jeśli \(\displaystyle{ x,y\in X}\), oraz \(\displaystyle{ x \neq y}\), to oczywiście \(\displaystyle{ \left\{ x\right\} \neq \left\{ y\right\} }\), czyli \(\displaystyle{ f(x) \neq f(y)}\). A więc \(\displaystyle{ f}\) jest różnowartościowa. A zatem \(\displaystyle{ \left| X\right| \le \left| P(X)\right|. }\)

Ponieważ \(\displaystyle{ \left| X\right| \le \left| P(X)\right| }\) i \(\displaystyle{ P(X)\subset X}\), to na podstawie twierdzenia Cantora-Bernsteina ( a właściwie równoważnej jej postaci) otrzymujemy, że \(\displaystyle{ X\sim P(X)}\), a na podstawie twierdzenia Cantora \(\displaystyle{ \left| X\right| < \left| P(X)\right| }\), a więc \(\displaystyle{ \left| X\right| \le \left| P(X)\right| }\) i \(\displaystyle{ X\not\sim P(X)}\)- sprzeczność. Zatem nie istnieje zbiór wszystkich zbiorów (w aksjomatycznej teorii mnogości). \(\displaystyle{ \square}\)

Można też argumentować w ten sposób, że gdyby zbiór \(\displaystyle{ X}\) byłby zbiorem wszystkich zbiorów, to wtedy moglibyśmy rozważyć \(\displaystyle{ \bigcup X}\). Taka suma jest nadzbiorem każdego zbioru rodziny \(\displaystyle{ X}\), czyli każdego zbioru. Skoro jest ich nadzbiorem, to jest od nich większej lub równej mocy, zatem jest największym zbiorem względem mocy. Tymczasem nie ma największego takiego zbioru, gdyż możemy zastosować twierdzenie Cantora, i znaleźć zbiór jeszcze większej mocy niż ta suma- sprzeczność.\(\displaystyle{ \square }\)

Wiemy, że (przy założeniu aksjomatu wyboru- wtedy bez problemu tak możemy powiedzieć), że zbiór liczb naturalnych jest najmniejszym, względem mocy, zbiorem nieskończonym. Z tego możemy wywnioskować bardzo ciekawy fakt, że każdy zbiór nieskończony zawiera podzbiór przeliczalny równoliczny z \(\displaystyle{ \NN}\), czyli w zbiorze nieskończonym możemy odnaleźć nieskończony zbiór przeliczalny.

PROSTY DOWÓD:

Ustalmy dowolny zbiór nieskończony \(\displaystyle{ X}\). Skoro zbiór \(\displaystyle{ X}\) jest nieskończony, a zbiór liczb naturalnych jest najmniejszym względem mocy zbiorem nieskończonym, to \(\displaystyle{ \left| \NN\right| \le \left| X\right| }\). A zatem istnieje funkcja różnowartościowa \(\displaystyle{ f:\NN \rightarrow X}\). Funkcja \(\displaystyle{ f}\) jest róznowartośściowa i 'na' zbiór wartości \(\displaystyle{ f_P}\), a zatem jest bijekcją między \(\displaystyle{ \NN}\) a tym zbiorem wartości \(\displaystyle{ f_P}\). A zatem zbiór \(\displaystyle{ f_P}\) jest zbiorem przeliczalnym, i ponieważ \(\displaystyle{ f:\NN \rightarrow X}\), to \(\displaystyle{ f_P\subset X}\), czyli zbiór \(\displaystyle{ f_P}\) jest podzbiorem zbioru \(\displaystyle{ X}\) przeliczalnym. \(\displaystyle{ \square}\) :lol:

Może teraz coś prostszego dodam:

Wiemy, że każdy przedział otwarty \(\displaystyle{ (a,b) \subset \RR}\) (gdzie \(\displaystyle{ a<b}\)) jest mocy continuum. Zatem możemy to mocno wzmocnić na podstawie twierdzenia Cantora-Bernsteina :

Jeżeli \(\displaystyle{ A\subset\RR}\) i \(\displaystyle{ A}\) zawiera pewien przedział otwarty, to \(\displaystyle{ A}\) jest mocy continuum

Dowód wynika z powyższego faktu, że każdy przedział otwarty jest mocy continuum oraz z twierdzenia Cantora-Bernsteina.

Wnioski: Każdy przedział (właściwy) otwarto-domknięty jest mocy continuum, każdy przedzial domknięto otwarty jest mocy continuum, każdy przedział domknęty \(\displaystyle{ \left[ a,b\right] }\), gdzie \(\displaystyle{ a<b}\) jest mocy continuum, każdy przedział postaci \(\displaystyle{ \left( - \infty ,a\right) }\) jest mocy continuum, każdy przedział postaci \(\displaystyle{ \left( - \infty ,a\right] }\) jest mocy continuum, każdy przedział postaci \(\displaystyle{ \left( a,+ \infty \right) }\) jest mocy continuum, każdy przedział postaci \(\displaystyle{ \left[ a,+ \infty \right) }\) jest mocy continuum, i wiele więcej.

Bardzo ciekawym, i wydawać się by mogło trudnym tym razem( przynajmniej początkowo wydawało mi się to bardzo trudne), jest zadanie: czy w przestrzeni trójwymiarowej można zmieścić nieprzeliczalnie wiele rozłącznych kul??

Nie można. Rozwiązanie jednak nie jest trudne. Wynika to z faktu, że pomiędzy dwoma liczbami rzeczywistymi jest liczba wymierna, oraz z tego, że zbiór liczb wymiernych jest przeliczalny.

Ustalmy dowolną niepustą rodzinę \(\displaystyle{ \mathbb{B} }\) rozłącznych kul. Pokażemy, że ta rodzina jest co najwyżej przeliczalna. Niech \(\displaystyle{ K\in\mathbb{B}}\) będzie kulą tej rodziny. Ponieważ kula musi mieć niezerową wielkość ( prawda, to należy wykluczyć, to by były punkty, nie kule), i ponieważ pomiędzy dwoma liczbami rzeczywistymi jest liczba wymierna, więc możemy tej kuli przypisać punkt o wszystkich trzech współrzędnych wymiernych, taki punkt jest elementem zbioru \(\displaystyle{ \left( \QQ \times \QQ\right) \times \QQ\sim\QQ \times \left( \QQ \times \QQ\right)\sim \NN,}\) gdyż zbór liczb wymiernych jest przeliczalny, i iloczyn kartezjański dwóch zbiorów przeliczalnych jest zbiorem przeliczalnym. Mamy zatem funkcję \(\displaystyle{ f:\mathbb{B} \rightarrow \QQ\times\QQ\times\QQ}\), która prowadzi w zbiór przeliczalny. Pozostaje wykazać, że jest różnowartościowa. Niech \(\displaystyle{ K_1,K_2\in\mathbb{B}}\) będą różne.Wtedy te kule \(\displaystyle{ K_1,K_2}\) są rozłączne. Oznaczmy \(\displaystyle{ f(K_1)=(x_1,y_1,z_1)=P_1, f(K_2)=(x_2,y_2,z_2)=P_2}\). Wtedy \(\displaystyle{ P_1\in K_1}\), a nawet \(\displaystyle{ P_1}\) należy do wnętrza kuli \(\displaystyle{ K_1}\), podobnie \(\displaystyle{ P_2\in K_2}\)( a nawet punkt \(\displaystyle{ P_2}\) należy do wnętrza kuli \(\displaystyle{ K_2}\)), gdyby \(\displaystyle{ P_1=P_2}\), to \(\displaystyle{ P_1\in K_1\cap K_2}\),co daje sprzeczność z tym, że kule \(\displaystyle{ K_1,K_2}\) jako różne są rozłączne. Zatem musi być\(\displaystyle{ P_1 \neq P_2}\), i funkcja \(\displaystyle{ f}\) jest różnowartościowa.\(\displaystyle{ \square}\) Łatwo też zmienić rozwiązanie, gdyby dopuścić tylko ponadto, że kule mogą mieć wspólny brzeg (ale gdy muszą mieć rozłączne wnętrza).

Można też rozważyć podobne zadanie z kołami na płaszczyźnie.
Jan Kraszewski
Administrator
Administrator
Posty: 34126
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: 8 lut 2020, o 01:43Jakbyś chciał to wszystko dokładnie zapisać, to nie byłoby tak łatwo...
To akurat jest zapisane dość dokładnie, brakuje tylko uzasadnienia, że suma tych funkcji jest funkcją.
Jakub Gurak pisze: 8 lut 2020, o 01:43Ponieważ kula musi mieć niezerową wielkość ( prawda, to należy wykluczyć, to by były punkty, nie kule), i ponieważ pomiędzy dwoma liczbami rzeczywistymi jest liczba wymierna, więc możemy tej kuli przypisać punkt o wszystkich trzech współrzędnych wymiernych,
Skoro lubisz być taki dokładny, to powinieneś wytłumaczyć, w jaki sposób w tej kuli znajdujesz punkt o wszystkich współrzędnych wymiernych. Jest to oczywiście konsekwencją tego, że liczby wymierne leżą gęsto w liczbach rzeczywistych, ale nie bezpośrednią.

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 »

No tak, ale chyba nie dam rady. :( Jakby się zagłębić, to samemu mi to jest ciężko sobie wyobrazić( widzę, że mam kłopot z wyobraźnią przestrzenną),z trudem chyba zrozumiałem, ale już wytłumaczyć to już w ogóle. Może ktoś inny ma pomysł??
Jan Kraszewski
Administrator
Administrator
Posty: 34126
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 »

Ale to jest dobry pomysł i uzasadnienie też nie jest trudne. Możesz zacząć od pokazania, że w każdym kole jest punkt o obu współrzędnych wymiernych, a potem z tego skorzystać.

JK
a4karo
Użytkownik
Użytkownik
Posty: 22173
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 38 razy
Pomógł: 3748 razy

Re: Teoria mocy zbiorów

Post autor: a4karo »

Albo tak: przez kulę przechodzi płaszczyzna o wymiernej współrzędnej `x` (znajdź proste uzasadnienie tego faktu).
Przekrój z tą płaszczyzną jest kołem, przez które przechodzi płaszczyzna o wymiernej współrzędnej `y` (już wiesz dlaczego). Przekrój obu tych płaszczyzn (czyli prosta) wycina z kuli odcinek, a na nim punkt o wymiernej współrzednej `z`.

Uogólnij to na `n` wymiarów.
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, od niedzieli się tym zajmowałem, że jeśli \(\displaystyle{ X}\) jest zbiorem przeliczalnym (równolicznym ze zbiorem liczb naturalnych), to rodzina wszystkich rozkładów zbioru \(\displaystyle{ X}\) ma moc continuum. Przedstawię teraz dowód tego faktu.


Przypomnę może najpierw, na ważniaku udowodnili, że jeśli \(\displaystyle{ X}\) jest zbiorem przeliczalnym, a \(\displaystyle{ \mathcal R}\) rozkładem zbioru \(\displaystyle{ X}\), to rozkład \(\displaystyle{ \mathcal {R}}\) jest co najwyżej przeliczalny.

Podajmy najpierw pewien lemat.

Lemat:

Jeśli zbiór \(\displaystyle{ Y}\) jest zbiorem mocy continuum, a \(\displaystyle{ \mathbb{A}}\) rodziną wszystkich niepustych co najwyżej przeliczalnych podzbiorów zbioru \(\displaystyle{ Y}\), to rodzina \(\displaystyle{ \mathbb{A}}\) też ma moc continuum.

DOWÓD LEMATU:

Wykorzystamy fakt z teorii mocy (trochę grubszy), że zbiór \(\displaystyle{ \RR ^{\NN}}\) jest mocy continuum- czyli, że zbiór wszystkich ciągów liczb rzeczywistych jest mocy continnum. W Guzickim wstępie do matematyki, chyba to udowodniono.

Ponieważ \(\displaystyle{ Y\sim \RR}\), to \(\displaystyle{ Y ^{\NN}\sim \RR ^{\NN} \sim \RR}\).

Rozważmy funkcję \(\displaystyle{ f:Y ^{\NN} \rightarrow \mathbb{A} }\) określoną jako :

\(\displaystyle{ f\left( a_n\right)=a_P\subset Y}\), czyli ta funkcja ciągowi elementów zbioru \(\displaystyle{ Y}\) przypisuję zbiór jego wartości, czyli zbiór jego wyrazów.

Zauważmy najpierw, że funkcja \(\displaystyle{ f}\) jest dobrze określona, gdyż \(\displaystyle{ a:\NN \rightarrow a_P}\) jest funkcją 'na' zbiór wartości \(\displaystyle{ a_P}\), a zatem \(\displaystyle{ \left| \NN\right| \ge \left| a_P\right|}\), a zatem zbiór \(\displaystyle{ a_P}\) jest co najwyżej przeliczalny, i oczywiście zbiór \(\displaystyle{ a_P}\), jako zbiór wyrazów ciągu, jest niepusty, a zatem \(\displaystyle{ a_P\in\mathbb{A}}\), i funkcja \(\displaystyle{ f}\) jest dobrze określona.


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

Niech \(\displaystyle{ A\in\mathbb{A}.}\) Wtedy zbiór \(\displaystyle{ A}\) jest podzbiorem zbioru \(\displaystyle{ Y}\) , i \(\displaystyle{ \left\{ \right\} \neq A}\) jest niepustym co najwyżej przeliczalnym zbiorem. Ponieważ zbiór \(\displaystyle{ A}\) jest co najwyżej przeliczalny, więc \(\displaystyle{ A}\) jest równoliczny z pewnym podzbiorem \(\displaystyle{ M}\) zbioru liczb naturalnych, tzn. \(\displaystyle{ A\sim M}\), gdzie \(\displaystyle{ M\subset \NN}\). Rozważmy teraz dwa przypadki:


Jeśli zbiór \(\displaystyle{ M}\) jest skończony, to \(\displaystyle{ M\sim n}\), gdzie \(\displaystyle{ n\in\NN}\) jest liczbą naturalną von Neumanna. A zatem istnieje bijekcja \(\displaystyle{ g:n \rightarrow M}\). Ponieważ \(\displaystyle{ M\sim A}\), więc istnieje bijekcja \(\displaystyle{ h:M \rightarrow A}\). Ponieważ złożenie bijekcji jest bijekcją, to funkcja \(\displaystyle{ \left( h\circ g\right): n \rightarrow A}\) jest bijekcją. Mamy \(\displaystyle{ A \neq \left\{ \right\}.}\) Ustalmy więc element \(\displaystyle{ a\in A}\). I rozważmy ciąg: \(\displaystyle{ a:\NN \rightarrow Y}\), zdefiniowany jako:

\(\displaystyle{ a(m)= \begin{cases} \left( h\circ g\right) \left( m\right),\hbox{ jeśli } m\in n; \\ a, \hbox{ jeśli } m \ge n.\end{cases} }\)

Mamy rzeczywiście, ponieważ \(\displaystyle{ (h\circ g ):n \rightarrow A\subset Y}\), i \(\displaystyle{ a\in A}\), więc jest to ciąg elementów zbioru \(\displaystyle{ Y}\). A zatem \(\displaystyle{ a\in Y ^{\NN}}\), i mamy:

\(\displaystyle{ f\left( a _{n}\right) =a_P=\stackrel { \rightarrow }{ a} \left( \NN\right) =\stackrel { \rightarrow } {a} \left( n \cup \left( \NN \setminus n \right) \right) =\stackrel { \rightarrow }{a} \left( n\right) \cup \stackrel { \rightarrow }{a}\left( \NN \setminus n\right)= \left[ \stackrel { \rightarrow }{\left( h\circ g\right) } \left( n\right) \right] \cup \left\{ a\right\} =\left[ \left( h\circ g\right)_P\right] \cup \left\{ a\right\}=}\) ,

i ponieważ funkcja \(\displaystyle{ (h\circ g)}\) jest bijekcją, a więc jest 'na' zbiór \(\displaystyle{ A}\), więc to jest równe \(\displaystyle{ A \cup \left\{ a\right\}\stackrel {a\in A}{=} A}\). Czyli \(\displaystyle{ f(a_n)=A.}\)


Jeśli zbiór \(\displaystyle{ M}\) jest nieskończony, a mamy, że \(\displaystyle{ M\subset \NN}\), to pewne twierdzenie mocy zbiorów daje, że zbiór \(\displaystyle{ M}\) musi być równoliczny z \(\displaystyle{ \NN}\). Istnieje więc bijekcja \(\displaystyle{ g:\NN \rightarrow M}\). Ponieważ \(\displaystyle{ M\sim A}\), więc istnieje bijekcja \(\displaystyle{ h:M \rightarrow A}\). Ponieważ złożenie bijekcji jest bijekcją, to funkcja \(\displaystyle{ (h\circ g):\NN \rightarrow A}\) jest bijekcją. Mamy \(\displaystyle{ A\subset Y}\), więc \(\displaystyle{ (h\circ g):\NN \rightarrow Y}\), więc \(\displaystyle{ \left( h\circ g\right) \in Y^\NN}\), i \(\displaystyle{ f\left( h\circ g\right)=\left( h\circ g\right)_P =}\) i ponieważ \(\displaystyle{ (h\circ g ):\NN \rightarrow A}\) jest bijekcją, więc ten zbiór wartości jest równy zbiorowi \(\displaystyle{ A}\), czyli \(\displaystyle{ f(h\circ g) =A}\), a więc zbiór \(\displaystyle{ A}\) jest wartością funkcji \(\displaystyle{ f}\).

W pierwszym przypadku też zbiór \(\displaystyle{ A}\) był wartością funkcji \(\displaystyle{ f}\). Z dowolności wyboru takiego zbioru wnioskujemy, że funkcja \(\displaystyle{ f}\) jest 'na'. A zatem \(\displaystyle{ \left| \mathbb{A}\right| \le \left| Y ^{\NN} \right|=\left| \RR\right|.}\)

Z drugiej jednak strony, zauważmy, że \(\displaystyle{ \mathbb{A}\supset \left\{ \left\{ y\right\}\Bigl| \ \ y\in Y \right\} \sim Y\sim \RR}\), a więc \(\displaystyle{ \left|\mathbb{A}\right| \ge \left| \RR\right|}\). A zatem, na podstawie twierdzenia Cantora-Bernsteina \(\displaystyle{ \left| \mathbb{A}\right|=\left| \RR\right|.\square}\)


Zauważmy, teraz, że jeśli \(\displaystyle{ \mathcal{R}\in\mathbb{B}}\), to \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ X\sim \NN}\), zatem ten rozkład jest co najwyżej przeliczalny, i \(\displaystyle{ \mathcal {R}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), zatem \(\displaystyle{ \mathcal {R}\subset P(X)}\), który to zbiór (gdyż \(\displaystyle{ X\sim \NN}\)) jest równoliczny z \(\displaystyle{ P\left( \NN\right) \sim \RR.}\)

Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich niepustych co najwyżej przeliczalnych podzbiorów zbioru \(\displaystyle{ P(X)}\). Wykażemy, że \(\displaystyle{ \mathbb{B}\subset \mathbb{A}}\).

Jeśli \(\displaystyle{ \mathcal{R}\in\mathbb{B}}\), to \(\displaystyle{ \mathcal R}\) jest rozkładem zbioru \(\displaystyle{ X\sim \NN}\), i \(\displaystyle{ \left| \mathcal {R}\right| \le \left| \NN\right|}\), a ponieważ \(\displaystyle{ \mathcal {R}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X}\), więc \(\displaystyle{ \mathcal {R}\subset P(X)}\), i mamy \(\displaystyle{ \mathcal {R} \neq \emptyset}\), gdyż (ponieważ \(\displaystyle{ \mathcal {R}}\) jest rozkładem zbioru \(\displaystyle{ X}\)), więc \(\displaystyle{ \bigcup \mathcal {R}=X \neq \emptyset}\), a \(\displaystyle{ \bigcup\emptyset=\emptyset}\). W takim razie mamy: \(\displaystyle{ \left| \mathcal {R}\right| \le \left| \NN\right|}\), \(\displaystyle{ \mathcal{R}\subset P(X)}\) i \(\displaystyle{ \mathcal {R} \neq \emptyset}\), skąd możemy wnioskować, że \(\displaystyle{ \mathcal {R}\in \mathbb{A}}\), i \(\displaystyle{ \mathbb{B}\subset \mathbb{A}.}\)

Ponieważ \(\displaystyle{ P(X)\sim P(\NN)\sim \RR}\), a \(\displaystyle{ \mathbb{A}}\) jest rodziną podzbiorów zbioru \(\displaystyle{ P(X)}\), rodziną wszystkich niepustych co najwyżej przeliczalnych podzbiorów zbioru \(\displaystyle{ P(X)}\), to na mocy lematu powyżej: \(\displaystyle{ \left| \mathbb{A}\right|=\left| \RR\right|.}\) Mamy \(\displaystyle{ \mathbb{B} \subset \mathbb{A}}\), zatem \(\displaystyle{ \left|\mathbb{B}\right| \le \left|\RR\right|.}\)



Wykażemy teraz nierówność mocy zbiorów w drugą stronę.

Podajmy najpierw prosty lemat:

Lemacik: Jeśli \(\displaystyle{ \left\{ \right\} \neq A \neq X}\) jest niepustym i różnym od całego zbioru \(\displaystyle{ X \sim \NN}\) podzbiorem zbioru \(\displaystyle{ X}\), to jeśli rozważymy dopełnienie \(\displaystyle{ A'=X \setminus A}\), to rodzina dwuzbiorowa \(\displaystyle{ \left\{ A,A'\right\}}\) jest rozkładem zbioru X.
PROSTY DOWÓD:    
Ustalmy na początek element \(\displaystyle{ x\in X \neq \left\{ \right\}.}\) Zauważmy, że jeśli \(\displaystyle{ \mathcal {R}\in\mathbb{B}}\) jest dowolnym ustalonym rozkładem, to istnieje dokładnie jeden zbiór \(\displaystyle{ A\in \mathcal {R}}\) tego rozkładu zawierający element \(\displaystyle{ x}\), tzn. taki, że \(\displaystyle{ x\in A. }\) Łatwo to można udowodnić. Dla rozkładu \(\displaystyle{ \mathcal {R}\in\mathbb{B}}\) jedyny taki zbiór będziemy oznaczać jako \(\displaystyle{ \left[ x\right] _{\mathcal {R}}.}\)

Rozważmy funkcję \(\displaystyle{ f}\) działającą jako:

\(\displaystyle{ \mathcal{R}\in\mathbb{B} \stackrel {f}{\rightarrow } [x] _{\mathcal R} \neq \left\{ \right\}.}\) Zauważmy, że ta funkcja jest o wartościach w zbiorze \(\displaystyle{ P(X) \setminus \left\{ \emptyset\right\}}\). Ale ponieważ \(\displaystyle{ P(X)\sim P(\NN)\sim \RR}\), to \(\displaystyle{ P(X)}\) jako zbiór mocy continuum jest nieskończony, więc \(\displaystyle{ S:= P(X) \setminus \left\{ \emptyset\right\}\sim P(X)\sim \RR.}\)

Podzielmy teraz rodzinę \(\displaystyle{ S}\) na dwie podrodziny \(\displaystyle{ S_1}\), \(\displaystyle{ S_2}\), dane jako:

\(\displaystyle{ S_1=\left\{ A\in S: \ x\in A \right\} ,}\) i
\(\displaystyle{ S_2=\left\{ A\in S: \ x\not\in A\right\}.}\)

Mamy \(\displaystyle{ f: \mathbb{B} \rightarrow P(X) \setminus \left\{ \emptyset\right\} =S}\), ale jeśli \(\displaystyle{ \mathcal{R} \in\mathbb{B}}\), to \(\displaystyle{ x\in [x] _{\mathcal{R}}}\), zatem mamy nawet \(\displaystyle{ f:\mathbb{B} \rightarrow S_1.}\) Wykażemy teraz, że jest to funkcja 'na' rodzinę \(\displaystyle{ S_1.}\)

Niech \(\displaystyle{ A\in S_1}\). Wtedy \(\displaystyle{ A\in S, x\in A.}\) Ponieważ \(\displaystyle{ A\in S}\), to \(\displaystyle{ A\subset X}\),i \(\displaystyle{ A \neq \emptyset.}\) Jeśli \(\displaystyle{ A=X}\), to \(\displaystyle{ \mathcal{R}=\left\{ X\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\), a zatem \(\displaystyle{ \mathcal{R}\in \mathbb{B} }\), i \(\displaystyle{ f\left( \mathcal{R}\right) =\left[ x\right] _{\mathcal{R}}}\), który to zbiór \(\displaystyle{ [x] _{\mathcal{R}} \in \mathcal{R}=\left\{ X\right\} }\) (na podstawie definicji tych zbiorów), a więc musi być \(\displaystyle{ \left[ x\right] _{\mathcal{R}}=X}\) , i \(\displaystyle{ f(\mathcal {R})=X=A}\), a więc zbiór \(\displaystyle{ A}\) jest wartością funkcji \(\displaystyle{ f.}\)

Jeśli \(\displaystyle{ A \neq X}\), mamy również \(\displaystyle{ A \neq \left\{ \right\}}\), i \(\displaystyle{ A\subset X}\), zatem na mocy lematu powyżej rodzina dwuzbiorowa \(\displaystyle{ \left\{ A,A'=X \setminus A\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\), a zatem \(\displaystyle{ \left\{ A,A'\right\} \in \mathbb{B} }\), i \(\displaystyle{ f\left( \left\{ A,A'\right\} \right)=\left[ x\right] _{\left\{ A,A'\right\} }}\), ktory to zbiór należy do zbioru \(\displaystyle{ \left\{ A,A'\right\}}\), ale mamy \(\displaystyle{ x\in A}\), i (co zatem idzie ) \(\displaystyle{ x\not\in A'}\), a ponieważ zbiór \(\displaystyle{ \left[ x\right] _{\left\{ A,A'\right\} }}\) musi zawierać element \(\displaystyle{ x}\), więc musi być \(\displaystyle{ \left[ x\right] _{\left\{ A,A'\right\} }=A}\), więc \(\displaystyle{ f\left( \left\{ A,A'\right\} \right)=A}\), a więc również zbiór \(\displaystyle{ A}\) jest wartością funkcji \(\displaystyle{ A. }\)

A zatem funkcja \(\displaystyle{ f}\) jest 'na' zbiór \(\displaystyle{ S_1.}\)


Wykażemy teraz, że \(\displaystyle{ S_1 \setminus \left\{ X\right\}\sim S_2}\).

Wystarczy rozważyć funkcję \(\displaystyle{ A\in S_1 \setminus \left\{ X\right\} \stackrel {g}{\rightarrow} A'=X \setminus A \subset X.}\)

Łatwo sprawdzić, że funkcja \(\displaystyle{ g}\) jest dobrze określona. Łatwo sprawdzić, że funkcja \(\displaystyle{ g}\) jest różnowartościowa. Wykażemy, że funkcja \(\displaystyle{ g}\) jest 'na' zbiór \(\displaystyle{ S_2}\).
DOWÓD TEGO FAKTU:    
A zatem \(\displaystyle{ g}\) jest bijekcją, i \(\displaystyle{ S_1 \setminus \left\{ X\right\}\sim S_2.}\)


Mamy oczywiście \(\displaystyle{ S=S_1 \cup S_2.}\)

Zauważmy, ze zbiór \(\displaystyle{ S_1}\) nie może być skończony, w przeciwnym razie, ponieważ \(\displaystyle{ S_2\sim S_1 \setminus \left\{ X\right\}}\), to zbiór \(\displaystyle{ S_2}\) byłby skończony, i w efekcie zbiór \(\displaystyle{ S}\), jako suma dwóch zbiorów skończonych, byłby zbiorem skończonym, a \(\displaystyle{ S\sim \RR}\), więc zbiór \(\displaystyle{ \RR}\) byłby skończony- sprzeczność.

Wobec czego zbiór \(\displaystyle{ S_1}\) musi być nieskończony, wobec czego \(\displaystyle{ S_1 \setminus \left\{ X\right\} \sim S_1}\) i \(\displaystyle{ S_2\sim S_1 \setminus \left\{ X\right\}\sim S_1}\), czyli \(\displaystyle{ S_2\sim S_1}\), poniewaz \(\displaystyle{ \RR\sim S=S_1 \cup S_2}\), więc zarówno \(\displaystyle{ \left| S_1\right| \le \left| \RR\right|,}\) jak i \(\displaystyle{ \left| S_2\right| \le \left| \RR\right|. }\)

Przypuśćmy, że \(\displaystyle{ \left| S_1\right|<\left| \RR\right|}\), czyli że, zbiór\(\displaystyle{ S_1}\) jest mocy silnie mniejszej od mocy continuum. Wiemy, że zbiór \(\displaystyle{ S_1}\) jest nieskończony, więc również zbiór \(\displaystyle{ S_2,}\) jako zbiór z nim równoliczny, jest nieskończony, a zatem \(\displaystyle{ S=S_1 \cup S_2\sim S_1}\), a ponieważ \(\displaystyle{ \left| S_1\right| <\left| \RR\right|}\), więc również \(\displaystyle{ \left| S\right| <\left| \RR\right|}\), a \(\displaystyle{ S\sim \RR}\)-sprzeczność.

A zatem \(\displaystyle{ \left| S_1\right|\not< \left|\RR\right|}\), ale \(\displaystyle{ \left| S_1\right| \le \left| \RR\right|}\) ,więc musi być \(\displaystyle{ S_1\sim \RR}\). Ponieważ \(\displaystyle{ f:\mathbb{B} \stackrel{NA}{\rightarrow } S_1}\) jest funkcją 'na' zbiór \(\displaystyle{ S_1}\), więc \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| S_1\right|=\left| \RR\right|.}\) Mamy \(\displaystyle{ \left|\mathbb{B} \right| \le \left| \RR\right|}\), a zatem, na podstawie twierdzenia Cantora-Bernsteina \(\displaystyle{ \left|\mathbb{B}\right|=\left| \RR\right|}\). Czyli rozkładów na zbiorze przeliczalnym jest dokładnie continuum\(\displaystyle{ .\square}\) 8-) :lol: :D


Udowodniłem też ostatnio, że jeśli \(\displaystyle{ X}\) jest zbiorem przeliczalnym, to bijekcji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\) jest continuum. Przedstawię jeszcze tutaj dowód tego faktu.

Przypominam- bijekcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum. To się dowodzi wskazując funkcję różnowartościową z \(\displaystyle{ 2^\NN}\) w zbiór wszystkich bijekcji na zbiorze liczb naturalnych. Jeśli \(\displaystyle{ f\in 2^\NN}\) jest ciągiem ciągiem zero-jedynkowym, to bijekcję \(\displaystyle{ f':\NN \rightarrow \NN}\) określamy tak, że w przypadku gdy \(\displaystyle{ f(n)=0}\), to \(\displaystyle{ f'(2n)=2n}\) i \(\displaystyle{ f'(2n+1)= 2n+1}\), a w przypadku gdy \(\displaystyle{ f(n)=1}\), to \(\displaystyle{ f'(2n)=2n+1}\) i \(\displaystyle{ f'(2n+1)=2n}\). Innymi słowy, jeżeli na pozycji \(\displaystyle{ n}\) ciąg zero-jedynkowy przyjmuję wartość \(\displaystyle{ 0}\), to liczby \(\displaystyle{ 2n}\) i \(\displaystyle{ 2n+1}\) pozostawiamy w naturalnym porządku, a jeżeli dla \(\displaystyle{ n}\) ciąg zero-jedynkowy przyjmuję wartość \(\displaystyle{ 1}\), to liczby naturalne \(\displaystyle{ 2n}\) i \(\displaystyle{ 2n+1}\) zamieniamy miejscami. Dla przykładu jeżeli \(\displaystyle{ f_n=\left( 0,1,1,0,0,0,0,\ldots\right)}\), to bijekcja \(\displaystyle{ f'}\) to ciąg liczb naturalnych \(\displaystyle{ (0,1,3,2,5,4,6,7,8,9,10,\ldots ).}\) Wykorzystamy ten fakt do udowodnienia, że na zbiorze przeliczalnym \(\displaystyle{ X}\) bijekcji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\) jest również continuum.

Wprowadźmy najpierw notację, że jeśli \(\displaystyle{ X}\) jest zbiorem, to przez \(\displaystyle{ \mathbb{B}_X}\) będziemy oznaczać zbiór wszystkich bijekcji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\), tzn.:

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

Ponieważ \(\displaystyle{ I_X}\) jest bijekcją, więc \(\displaystyle{ I_X\in \mathbb{B}_X}\), a więc rodzina \(\displaystyle{ \mathbb{B}_X}\) jest zawsze niepusta.


Wykażemy najpierw lemat:

Lemat: Jeśli \(\displaystyle{ X,Y}\) są zbiorami równolicznymi, to \(\displaystyle{ \mathbb{B}_X\sim \mathbb{B}_Y}\)- odpowiadające zbiory bijekcji \(\displaystyle{ \mathbb{B}_X}\) i \(\displaystyle{ \mathbb{B}_Y}\) są równoliczne.

Dowód tego faktu:

Ponieważ \(\displaystyle{ X\sim Y}\), więc istnieje bijekcja \(\displaystyle{ f:X \rightarrow Y.}\) Definiujemy funkcję \(\displaystyle{ \alpha :\mathbb{B}_X \rightarrow \mathbb{B}_Y}\). Dla dowolnej ustalonej bijekcji \(\displaystyle{ f_X\in\mathbb{B}_X}\), definiujemy:

\(\displaystyle{ \alpha \left( f_X\right) =f_Y}\), gdzie \(\displaystyle{ f_Y: Y \rightarrow Y}\) jest określona jako:

\(\displaystyle{ f_Y(y)=f( \ f_X \ ( f ^{-1} (y) \ ) \ ).}\)

Funkcja \(\displaystyle{ f_Y}\) jest dobrze określona (relacja odwrotna do bijekcji \(\displaystyle{ f}\) jest funkcją). Należy jeszcze wykazać, że funkcja \(\displaystyle{ f_Y}\) jest bijekcją. Zauważmy najpierw, że możemy równoważnie (innymi słowy) zdefiniować funkcję \(\displaystyle{ f_Y}\) jako:

\(\displaystyle{ f_Y=f\circ f_X\circ f ^{-1}.}\)

I ponieważ \(\displaystyle{ f}\) jest bijekcją, więc relacja odwrotna \(\displaystyle{ f^{-1}}\) jest bijekcją, mamy również, że \(\displaystyle{ f_X}\) jest bijekcją, więc ponieważ złożenie bijekcji jest bijekcją, więc funkcja \(\displaystyle{ f_Y}\) jest bijekcją, a więc \(\displaystyle{ f_Y\in\mathbb{B}_Y}\), i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.

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

Jeśli \(\displaystyle{ \alpha \left( f_X\right) = \alpha \left( g_X\right)}\) , to z definicji funkcji \(\displaystyle{ \alpha}\), otrzymujemy:

\(\displaystyle{ f\circ f_X\circ f ^{-1} =f\circ g_X\circ f^{-1}}\), więc również:

\(\displaystyle{ f ^{-1}\circ \left( f\circ f_X\circ f ^{-1}\right) \circ f= f ^{-1}\circ\left( f\circ g_X\circ f ^{-1} \right) \circ f}\),

i poniewaz \(\displaystyle{ f}\) jest bijekcją, tak więc \(\displaystyle{ f ^{-1}\circ f=I_X}\), więc otrzymujemy

\(\displaystyle{ I_X\circ f_X\circ I_X=I_X\circ g_X\circ I_X,}\)

a więc \(\displaystyle{ f_X=g_X}\). A więc funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa. Pokażemy teraz, że \(\displaystyle{ \alpha}\) jest funkcją 'na'.
DOWÓD TEGO FAKTU:    
A więc funkcja \(\displaystyle{ \alpha}\) jest bijekcją, i \(\displaystyle{ \mathbb{B}_X\sim \mathbb{B}_Y.\square}\)


Łatwo teraz będzie udowodnić, że wszystkich bijekcji na zbiorze przeliczalnym jest continuum.

Niech \(\displaystyle{ X}\) będzie zbiorem przeliczanym, tzn. takim, że \(\displaystyle{ X\sim\NN}\). Rozważmy rodzinę funkcji :

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

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

PROSTY DOWÓD:

Mamy \(\displaystyle{ X \sim \NN}\), a więc \(\displaystyle{ \mathbb{B}_X\sim \mathbb{B}_{\NN}.}\) Wiemy, że:

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

a zatem \(\displaystyle{ \mathbb{B}=\mathbb{B}_X\sim \RR}\), czyli rodzina \(\displaystyle{ \mathbb{B}}\) ma moc continuum\(\displaystyle{ .\square}\)


Możemy jeszcze udowodnić, że funkcji różnowartościowych na zbiorze przeliczalnym jest continuum. Czyli:

Jeśli zbiór \(\displaystyle{ X}\) jest równoliczny ze zbiorem liczb naturalnych, to rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) zdefiniowaną jako:

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

Wykażemy, że ta rodzina ma moc continuum.

Dowód:

Ponieważ \(\displaystyle{ X\sim \NN}\), więc \(\displaystyle{ X^X\sim \NN ^{\NN}\sim \RR}\) (gdyż wszystkich funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum, dowód jest w drugim linkowanym wątku zadań z teorii mocy, można w postach powyzej po prostu kliknąć na ten link). A więc \(\displaystyle{ X^X\sim \RR}\). Ponieważ \(\displaystyle{ \mathbb{B}\subset X^X}\), więc \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|.}\)

W drugą stronę: Rozważmy rodzinę \(\displaystyle{ \mathbb{A}}\):

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

Wiemy, już, że ta rodzina ma moc continuum( wykazałem to powyżej), mamy \(\displaystyle{ \mathbb{A}\subset \mathbb{B}}\) (każda bijekcja jest funkcją różnowartościową), zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \mathbb{A}\right|=\left| \RR\right|}\) . A zatem, na podstawie twierdzenia Cantora-Bernsteina: \(\displaystyle{ \left| \mathbb{B}\right| =\left| \RR\right|. }\)

Podobnie można udowodnić, że jeśli \(\displaystyle{ X}\) jeśli zbiorem równolicznym z \(\displaystyle{ \NN}\), to wszystkich funkcji z \(\displaystyle{ X}\) do \(\displaystyle{ X }\) będącymi funkcjami 'na' \(\displaystyle{ X}\) jest continuum.(W jedną stronę ograniczamy z góry przez zbiór funkcji \(\displaystyle{ X^X\sim \NN ^{\NN}\sim \RR}\). W drugą stronę korzystamy z tego, że każda bijekcja jest funkcją 'na'. A takich bijekcji mamy continnum, więc funkcji 'na' mamy również co najmniej continuum ). :lol:
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 w ostatni poniedziałek, a właściwie już w niedzielę, że wszystkich funkcji na zbiorze liczb całkowitych i o wartościach też w nim, wszystkich funkcji silnie malejących jest dokładnie continuum. Udowodniłem też, że również tyle samo jest funkcji silnie rosnących na zbiorze liczb całkowitych, jak i funkcji słabo malejących, jak i funkcji słabo rosnących. Zauważmy, że sytuacja nie jest podobna w sytuacji gdybyśmy rozważali funkcje na zbiorze liczb naturalnych. Jak wykazałem, w podanym linku w pierwszym poście tego wątku( tam jest link, można kliknąć i tam to udowodniłem), wszystkich funkcji silnie rosnących na zbiorze liczb naturalnych jest dokładnie continuum. A ile jest funkcji silnie malejących na zbiorze liczb naturalnych i o wartościach w nim?? Czy również continuum :?: Okazuję się, że zbiór takich funkcji jest pusty :o , czyli nie ma takich funkcji silnie malejących( no bo gdyby istniała taka funkcja, na \(\displaystyle{ 0}\) przyjmuję jako wartość liczbę naturalną, nazwijmy ją \(\displaystyle{ n}\), funkcja jest silnie malejąca, więc na kolejnych liczbach naturalnych musi przyjmować coraz to mniejsze wartości, i po co najwyżej \(\displaystyle{ n}\) krokach dochodzimy do liczby naturalnej \(\displaystyle{ 0}\), a ponieważ funkcja jest silnie malejąca to powinna przyjmować dalej wartości ujemne, ale jest to funkcja o wartościach w zbiorze liczb naturalnych- sprzeczność. Wobec czego taka funkcja nie istnieje). Natomiast na zbiorze liczb całkowitych jest tyle samo funkcji silnie malejących, co funkcji silnie rosnących (continuum). W ogóle, udowodniłem tez taki przydatny tu fakt, że na podzbiorze \(\displaystyle{ A}\) zbioru liczb rzeczywistych, podzbiorze symetrycznym względem \(\displaystyle{ 0}\), wszystkich funkcji z \(\displaystyle{ A}\) do \(\displaystyle{ A}\) silnie rosnących jest tyle samo co wszystkich funkcji silnie malejących. Łatwo wykazałem, że istnieje co najmniej continuum funkcji silnie rosnących na zbiorze liczb rzeczywistych. Wykazałem również taki fakt (bardzo ciekawy), taki fakt, że jeśli dwa zbiory są równoliczne, to są one również równoliczne z bijekcją, która o tym świadczy. Przedstawię teraz dowody tych ciekawych faktów.


Rozważmy rodzinę funkcji:

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

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

Dowód:

Zauważmy, że \(\displaystyle{ \mathbb{B}\subset \ZZ^{\ZZ}}\), i ponieważ zbiór liczb całkowitych jest równoliczny ze zbiorem liczb naturalnych, więc to jest zbiór równoliczny z \(\displaystyle{ \NN ^{\NN}\sim \RR}\). A więc rodzina \(\displaystyle{ \mathbb{B}}\) ma moc co najwyżej continuum.

Aby wykazać, że rodzina \(\displaystyle{ \mathbb{B}}\) ma moc co najmniej continuum rozważmy zbiór \(\displaystyle{ \left\{ 0,1\right\} ^{\ZZ} =2^{\ZZ}\sim 2 ^{\NN} =\left\{ 0,1\right\} ^{\NN} \sim \RR.}\) I dla dowolnej ustalonej funkcji \(\displaystyle{ f \in \left\{ 0,1\right\} ^{\ZZ}}\) , rozważmy funkcję \(\displaystyle{ f':\ZZ \rightarrow \ZZ}\), daną jako:

\(\displaystyle{ f'(x)=-2x-f(x)= -x-x-f(x).}\) Zauważmy, że zawsze \(\displaystyle{ f(x) \in \left\{ 0,1\right\}}\), i funkcja \(\displaystyle{ f'}\) jest dobrze określona.

Funkcja \(\displaystyle{ f'}\) będzie silnie malejąca, gdyż dla \(\displaystyle{ x_1,x_2\in\ZZ}\), takich, że \(\displaystyle{ x_1<x_2}\), mamy: \(\displaystyle{ f'(x_1)=-2x _{1} -f(x_1)}\), i ponieważ \(\displaystyle{ f(x_1)\in\left\{ 0,1\right\} }\), więc to jest istotnie większe od: \(\displaystyle{ -2x_1-2= -2(x_1+1)}\), i ponieważ \(\displaystyle{ x_1<x_2}\), a \(\displaystyle{ x_1, x_2}\) są liczbami całkowitymi, więc \(\displaystyle{ (x_1 +1) \le x_2}\), i dalej to jest większe lub równe od: \(\displaystyle{ -2x_2 \ge -2x_2- \underbrace{ f(x_2) }_{ \in \left\{ 0,1\right\} }= f'(x_2)}\), czyli \(\displaystyle{ f'(x_1)>f'(x_2)}\), i \(\displaystyle{ f' }\) jest silnie malejąca, i \(\displaystyle{ f'\in\mathbb{B}.}\)

Należy teraz wykazać, że funkcja \(\displaystyle{ f \in \left\{ 0,1\right\} ^{\ZZ} \stackrel{\alpha} {\rightarrow} f' \in\mathbb{B}}\), jest funkcją różnowartościową.

Niech zatem funkcje \(\displaystyle{ f,g\in \left\{ 0,1\right\} ^{\ZZ}}\), tzn. funkcję \(\displaystyle{ f,g:\ZZ \rightarrow \left\{ 0,1\right\}}\) , będą różne. Wtedy dla pewnego \(\displaystyle{ x\in\ZZ}\): \(\displaystyle{ f(x) \neq g(x)}\) (gdyby dla każdego \(\displaystyle{ x\in\ZZ}\), byłoby \(\displaystyle{ f(x)=g(x)}\), to moglibyśmy wnioskować, że \(\displaystyle{ f=g}\)- sprzeczność) . Ponieważ zbiór \(\displaystyle{ \ZZ}\) jest niepusty, (więc działa prawo zaprzeczania kwantyfikatorowi ogólnemu, w rodzinie pustej nie działa), więc otrzymujemy, że dla pewnego \(\displaystyle{ x\in\ZZ}\), mamy: \(\displaystyle{ f(x) \neq g(x)}\), więc łatwo, nie wprost udowodnić, że wtedy\(\displaystyle{ f'(x)=-2x-f(x) \neq -2x-g(x)= g'(x)}\), czyli \(\displaystyle{ f'(x) \neq g'(x)}\) , a więc \(\displaystyle{ f' \neq g'.}\) Otrzymujemy zatem, że funkcja \(\displaystyle{ f \stackrel{ \alpha }{\rightarrow} f'\in\mathbb{B}}\), jest funkcją różnowartościową.

A zatem \(\displaystyle{ \left| \RR\right| =\left\{ 0,1\right\} ^{\ZZ} \le \left| \mathbb{B}\right| .}\) Mamy \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|}\), a zatem na podstawie twierdzenia Cantora-Bernsteina \(\displaystyle{ \mathbb{B}\sim \RR.\square}\)


Nim przejdziemy dalej udowodnimy teraz , że na zbiorze \(\displaystyle{ A\subset \RR,}\) na zbiorze symetrycznym względem \(\displaystyle{ 0,}\) wszystkich funkcji silnie rosnących jest tyle samo co wszystkich funkcji silnie malejących.

Powiemy, że zbiór \(\displaystyle{ A\subset \RR}\) jest zbiorem symetrycznym względem \(\displaystyle{ 0}\), gdy z każdym swoim elementem zawiera również liczbę przeciwną, tzn. gdy zachodzi implikacja:

\(\displaystyle{ x\in A \rightarrow (-x)\in A.}\)

Prosta obserwacja: Jeśli zbiory \(\displaystyle{ A,B\subset \RR}\) są zbiorami symetrycznymi względem \(\displaystyle{ 0}\), to ich suma \(\displaystyle{ A \cup B}\) jest symetryczna względem \(\displaystyle{ 0}\).
PROSTY DOWÓD:    
Jeszcze jeden prosty fakt: Przekrój dwóch zbiorów symetrycznych względem \(\displaystyle{ 0}\) jest zbiorem symetrycznym względem \(\displaystyle{ 0}\).
PROSTY DOWÓD:    
Podajmy teraz pewien lemat.

LEMAT: Jeśli zbiór \(\displaystyle{ A\subset \RR}\) jest zbiorem symetrycznym względem \(\displaystyle{ 0}\), to rodziny funkcji dane jako :

\(\displaystyle{ \mathbb{B}_+=\left\{ f:A \rightarrow A\Bigl| \ \ f \hbox{ jest silnie rosnąca} \right\} }\), oraz
\(\displaystyle{ \mathbb{B}_-=\left\{ f:A \rightarrow A\Bigl| \ \ f \hbox{ jest silnie malejąca} \right\}}\),

takie rodziny funkcji są równoliczne, czyli na zbiorze symetrycznym względem \(\displaystyle{ 0}\) jest tyle samo funkcji silnie rosnących co funkcji silnie malejących.

DOWÓD:

Jeśli \(\displaystyle{ A=\emptyset}\), to rodzina \(\displaystyle{ \mathbb{B}_+}\) jest jednoelementowa złożona z funkcji pustej, i \(\displaystyle{ \mathbb{B}_-}\) też jest zbiorem jednoelementowym złożonym z funkcji pustej, a więc \(\displaystyle{ \mathbb{B}_+\sim \mathbb{B}_-}\). Załóżmy więc dalej , że zbiór \(\displaystyle{ A}\) jest niepusty.

Jeśli \(\displaystyle{ f\in\mathbb{B}_+}\), czyli \(\displaystyle{ f:A \rightarrow A}\), i \(\displaystyle{ f}\) jest funkcją silnie rosnącą, to przypisujemy jej funkcję \(\displaystyle{ f'}\), gdzie \(\displaystyle{ f':A \rightarrow A}\), dana jest jako:

\(\displaystyle{ f'(x)=-f(x).}\)

Ponieważ zawsze \(\displaystyle{ f(x)\in A}\), a zbiór \(\displaystyle{ A}\) jest symetryczny względem \(\displaystyle{ 0}\), więc również \(\displaystyle{ \left[ -f(x)\right]\in A}\), i funkcja \(\displaystyle{ f':A \rightarrow A}\) jest dobrze określona. Ponieważ \(\displaystyle{ f}\) jest silnie rosnąca, więc łatwo pokazać, że funkcja \(\displaystyle{ f' }\) o wartościach przeciwnych do wartości funkcji \(\displaystyle{ f}\), taka funkcja \(\displaystyle{ f'}\) jest silnie malejąca. A zatem \(\displaystyle{ f'\in\mathbb{B}_-. }\)

I rozważmy funkcję \(\displaystyle{ \alpha}\) , działającą w poniższy sposób: \(\displaystyle{ f\in\mathbb{B}_+ \stackrel{ \alpha }{\rightarrow } f'\in\mathbb{B}_-.}\)

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

Niech funkcje \(\displaystyle{ f,g\in\mathbb{B}_+}\), a więc funkcje \(\displaystyle{ f,g:A \rightarrow A}\), będą różne. Jeśli dla każdego \(\displaystyle{ x\in A}\): \(\displaystyle{ f(x)=g(x)}\), to możemy wnioskować, że \(\displaystyle{ f=g}\)-sprzeczność. Wobec czego, i ponieważ zbiór \(\displaystyle{ A}\) jest niepusty, więc dla pewnego \(\displaystyle{ x\in A}\), mamy: \(\displaystyle{ f(x) \neq g(x)}\). Wtedy \(\displaystyle{ -f(x) \neq -g(x) }\)(łatwo to nie wprost udowodnić), wobec czego \(\displaystyle{ f'(x)=-f(x) \neq -g(x)=g'(x)}\), czyli \(\displaystyle{ f'(x) \neq g'(x)}\), gdzie \(\displaystyle{ x\in A}\), więc \(\displaystyle{ f' \neq g'.}\) A więc funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

Pokażemy, że \(\displaystyle{ \alpha}\) jest funkcją 'na'.
DOWÓD TEGO FAKTU:    
A zatem \(\displaystyle{ \alpha}\) jest bijekcją, i \(\displaystyle{ \mathbb{B}_+\sim \mathbb{B}_-.\square}\)


Łatwo będzie teraz udowodnić, że wszystkich funkcji na zbiorze liczb całkowitych i o wartościach też w nim, wszystkich takich funkcji silnie rosnących jest dokładnie continuum.


Czyli rodzina funkcji :

\(\displaystyle{ \mathbb{B}_+ =\left\{ f:\ZZ \rightarrow \ZZ\Bigl| \ \ f \hbox{ jest silnie rosnąca}\right\} ,}\)

ma moc continuum.

PROSTY DOWÓD:

Zauważmy, że zbiór liczb całkowitych jest zbiorem symetrycznym względem \(\displaystyle{ 0}\), a zatem na mocy lematu powyżej:

\(\displaystyle{ \left\{ f:\ZZ \rightarrow \ZZ\Bigl| \ \ f \hbox{ jest silnie rosnąca } \right\} \sim \left\{ f:\ZZ \rightarrow \ZZ\Bigl| \ \ f \hbox{ jest silnie malejąca }\right\} .}\)

Ale wykazałem, na początku tego postu, że funkcji silnie malejących na zbiorze liczb całkowitych jest dokładnie continuum, wobec powyższego
również funkcji silnie rosnących na zbiorze liczb całkowitych jest dokładnie continuum\(\displaystyle{ .\square}\)

Odpowiedzmy teraz na pytanie: ile jest funkcji na zbiorze liczb całkowitych słabo malejących albo słabo rosnących.

Tzn. rozważmy rodzinę funkcji

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

Wykażemy, że ta rodzina ma moc również continuum.

PROSTY DOWÓD:

Rozważmy rodzinę wszystkich funkcji na zbiorze liczb całkowitych, rodzinę wszystkich funkcji silnie malejących, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}_-}\) dana jako:

\(\displaystyle{ \mathbb{B}_-=\left\{ f:\ZZ \rightarrow \ZZ\Bigl| \ \ f\hbox{ jest silnie malejąca} \right\} .}\)

(Wiemy już, że ta rodzina ma moc continuum).

Łatwo jest wykazać, że \(\displaystyle{ \mathbb{B}_-\subset\mathbb{B}}\), bo jeśli \(\displaystyle{ f\in\mathbb{B}_-}\), to \(\displaystyle{ f:\ZZ \rightarrow \ZZ}\) i \(\displaystyle{ f}\) jest silnie malejąca. Ponieważ \(\displaystyle{ f}\) jest silnie malejąca, to w szczególności \(\displaystyle{ f}\) jest słabo malejąca, a zatem \(\displaystyle{ f\in\mathbb{B}}\), i \(\displaystyle{ \mathbb{B}_-\subset\mathbb{B}}\). Ponieważ rodzina \(\displaystyle{ \mathbb{B}_-}\) ma moc continuum, więc rodzina \(\displaystyle{ \mathbb{B}}\) ma moc co najmniej continuum.

Ale \(\displaystyle{ \mathbb{B} \subset \ZZ ^{\ZZ}}\), który to zbiór funkcji jest równoliczny ze zbiorem (gdyż \(\displaystyle{ \ZZ\sim \NN}\)) , więc jest to zbiór równoliczny z \(\displaystyle{ \NN ^{\NN}\sim\RR.}\) W takim razie rodzina \(\displaystyle{ \mathbb{B}}\) ma moc co najwyżej continuum, i na podstawie twierdzenia Cantora-Bernsteina rodzina \(\displaystyle{ \mathbb{B}}\) ma moc continuum.

W podobny sposób możemy udowodnić, że wszystkich funkcji na zbiorze liczb całkowitych wszystkich funkcji słabo rosnących jest dokładnie continuum ( wiemy, że funkcji silnie rosnących na zbiorze liczb całkowitych jest continuum, a każda funkcja silnie rosnąca jest funkcją słabo rosnącą, wobec czego funkcji słabo rosnących mamy co najmniej continuum, a w drugą stronę ograniczamy przez zbiór wszystkich funkcji z \(\displaystyle{ \ZZ}\) do \(\displaystyle{ \ZZ}\), który jest mocy continuum).


Wykażemy jeszcze, że funkcji silnie rosnących z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\) jest co najmniej continnum.

Dowod:

Dla dowolnego \(\displaystyle{ a\in\RR_+}\), definiujemy funkcję \(\displaystyle{ f_a:\RR \rightarrow \RR}\), jako:

\(\displaystyle{ f_a(x)=x+a.}\)

Oczywiście jest to funkcja silnie rosnąca.

I jeśli \(\displaystyle{ a_1,a_2\in\RR_+,}\) i \(\displaystyle{ a_1 \neq a_2}\), to przypisane im funkcję (oznaczmy je po prostu jako odpowiednio \(\displaystyle{ f_1, f_2}\)), takie funkcje są różne. Mamy:

\(\displaystyle{ f_1(x)=x+a_1}\), i
\(\displaystyle{ f_2(x)=x+a_2.}\)

Wobec czego \(\displaystyle{ f_1(0)=a_1 \neq a_2=f_2(0)}\), wobec czego \(\displaystyle{ f_2 \neq f_1}\).

A zatem zbiór \(\displaystyle{ \left\{ f:\RR \rightarrow \RR\Bigl| \ \ f \hbox{ jest silnie rosnąca }\right\}}\) ma moc co najmniej taką jak moc zbioru \(\displaystyle{ \RR_+}\) czyli continuum, czyli mamy przynajmniej continuum funkcji silnie rosnących na zbiorze liczb rzeczywistych.\(\displaystyle{ \square}\)


Również mamy przynajmniej continuum funkcji silnie malejących na zbiorze liczb rzeczywistych.

Dowód:

Wystarczy zauważyć, że zbiór \(\displaystyle{ \RR}\) jest symetryczny względem \(\displaystyle{ 0}\), więc tyle samo jest wszystkich funkcji na \(\displaystyle{ \RR}\) silnie malejących co wszystkich funkcji silnie rosnących. Tych ostatnich, jak wykazałem powyżej, jest ich co najmniej continuum, więc również funkcji silnie malejących jest przynajmniej continuum.

Odpowiedzmy jeszcze na dwa pytania: ile jest funkcji słabo rosnących na zbiorze liczb rzeczywistych i ile jest funkcji słabo malejących na zbiorze liczb rzeczywistych??

Niech \(\displaystyle{ \mathbb{A}=\left\{ f:\RR \rightarrow \RR\Bigl| \ f \hbox{ jest słabo rosnąca}\right\} }\). Wykażemy, że ta rodzina ma moc co najmniej continuum.

Dowód:

Rozważmy rodzinę funkcji na \(\displaystyle{ \RR}\) silnie rosnących, tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\) daną jako:

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

(Wiemy, że ta rodzina ma moc co najmniej continuum).

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

Niech \(\displaystyle{ f\in\mathbb{B}.}\) Wtedy \(\displaystyle{ f:\RR \rightarrow \RR}\),i \(\displaystyle{ f}\) jest silnie rosnąca. Skoro \(\displaystyle{ f}\) jest silnie rosnąca, to również \(\displaystyle{ f}\) jest słabo rosnąca, zatem \(\displaystyle{ f\in \mathbb{A}}\). A zatem \(\displaystyle{ \mathbb{B}\subset \mathbb{A}}\) .

Ponieważ rodzina \(\displaystyle{ \mathbb{B}}\) ma moc przynajmniej continuum, z przechodniości nierówności mocy (co odpowiada faktowi, że złożenie funkcji różnowartościowych jest funkcją różnowartościową, co jest prostym faktem), więc rodzina \(\displaystyle{ \mathbb{A}}\) ma moc co najmniej continuum.

I podobnie możemy udowodnić, że funkcji na zbiorze liczb rzeczywistych słabo malejących jest co najmniej continuum( każda funkcja silnie malejąca jest funkcją słabo malejącą, a funkcji silnie malejących mamy co najmniej continuum, więc funkcji słabo malejących mamy co najmniej continuum).

Na koniec wykażemy, że jeżeli dwa zbiory są równoliczne, czyli istnieje pomiędzy nimi bijekcja, to są one również równoliczne z bijekcją, która o tym świadczy. Czyli

Jeśli zbiory \(\displaystyle{ X,Y}\) są równoliczne,tzn. istnieje bijekcja \(\displaystyle{ f:X \rightarrow Y,}\) to \(\displaystyle{ X\sim f}\) oraz \(\displaystyle{ Y \sim f.}\)

Dowód:

Rozważmy funkcję \(\displaystyle{ \alpha :X \rightarrow f}\), daną jako:

\(\displaystyle{ x\in X \stackrel{ \alpha }{\rightarrow } \left( x, f(x)\right) \in f}\),

Przypominam, z definicji funkcji, element \(\displaystyle{ f(x)}\), to jedyny element \(\displaystyle{ y\in Y}\), taki, że \(\displaystyle{ (x,y)\in f}\), więc należenie \(\displaystyle{ (x,y) \in f,}\) oznacza to to samo, co przynależność \(\displaystyle{ (x, f(x)) \in f}\). Wykażemy, ze funkcja \(\displaystyle{ \alpha}\) jest bijekcją.
Dowód tego faktu::    
Wobec czego \(\displaystyle{ Y\sim X\sim f}\) (więc również \(\displaystyle{ Y \sim f}\)).\(\displaystyle{ \square }\)

Mamy też taki fakt, że jeśli \(\displaystyle{ X}\) jest zbiorem, jeśli rozważymy kwadrat \(\displaystyle{ X \times X}\), oraz jego przekątną, czyli relację identyczności \(\displaystyle{ \mathbb{I}_X}\), to dany zbiór \(\displaystyle{ X}\) jest równoliczny z przekątną, czyli z relacją identyczności \(\displaystyle{ \mathbb{I}_X.}\)

Dla dowodu tego ciekawego faktu wystarczy określić funkcję, daną jako:

\(\displaystyle{ x\in X\stackrel {f}{\rightarrow} (x,x)\in \mathbb{I}_X}\).

Bardzo łatwo jest sprawdzić, że taka funkcja jest różnowartościowa i 'na', a zatem jest bijekcją, i \(\displaystyle{ X\sim\mathbb{I}_X.\square}\) :lol:
Jan Kraszewski
Administrator
Administrator
Posty: 34126
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: 16 gru 2021, o 00:44Wykazałem również taki fakt (bardzo ciekawy), taki fakt, że jeśli dwa zbiory są równoliczne, to są one również równoliczne z bijekcją, która o tym świadczy.
No cóż, skoro twierdzenia (a w zasadzie dość trywialne obserwacje), że każda funkcja jest równoliczna ze swoją dziedziną, a każda funkcja różnowartościowa - ze swoim zbiorem wartości (a bijekcjami są rzuty na osie), uważasz za bardzo ciekawe, to ja mam wrażenie dewaluacji znaczenia tego przymiotnika.

JK
Math_Logic
Użytkownik
Użytkownik
Posty: 73
Rejestracja: 8 paź 2021, o 20:06
Płeć: Mężczyzna
Podziękował: 2 razy
Pomógł: 14 razy

Re: Teoria mocy zbiorów

Post autor: Math_Logic »

Proszę zapytać swoich studentów dlaczego "fakt, że jeśli dwa zbiory są równoliczne, to są one również równoliczne z bijekcją, która o tym świadczy" jest prawdziwy. Polecam również na korytarzu zaczepić kolegę zajmującego się inną dziedziną matematyki.
A potem na podstawie tych doświadczeń stwierdzić czy jest to "trywialne" i dla kogo. Problem w zależności od jego sformułowania jest różnie odbierany, na przykład jako ciekawy (co jest całkowicie subiektywne).
Awatar użytkownika
AiDi
Moderator
Moderator
Posty: 3841
Rejestracja: 25 maja 2009, o 22:58
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 45 razy
Pomógł: 702 razy

Re: Teoria mocy zbiorów

Post autor: AiDi »

Math_Logic pisze: 17 gru 2021, o 12:09 A potem na podstawie tych doświadczeń stwierdzić czy jest to "trywialne" i dla kogo.
Chyba brakuje Tobie kontekstu: prześledź posty Jakuba Guraka, zwracając szczególną uwagę na jego fascynację teorią mnogości. Wypada on z kategorii zwykłego studenta, jak i "kolegi zajmującego się inną dziedziną matematyki" (swoją drogą polecam przeczytać co autor sądzi o innych dziedzinach matematyki).
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 »

Inne działy matematyki nie są mi do niczego potrzebne, a w samych podstawach matematyki atrakcji jest aż nadmiar. Poza tym uważam, że specjalistyczna matematyka to zajęcie na wieczność, więc ja wolę, póki co, zajmować się jedynie podstawami matematyki, a nie grzęznąć w jednym dziale nie mając pojęcia co się dzieje w ogólności, czyli wolę zajmować się przeróżnymi atrakcjami ogólnej teorii mnogości. 8-)


Zauważmy, że jeśli mamy dwa podzbiory zbioru liczb rzeczywistych, dwa zbiory skończone, to możemy rozważać funkcję rosnące malejące z pierwszego zbioru skończonego w drugi zbiór zbiór skończony. :o

To chyba dla dwóch dowolnych ustalonych podzbiorów zbioru liczb rzeczywistych możemy rozważać funkcję rosnące, malejące z pierwszego podzbioru w drugi. Dla dwóch zbiorów \(\displaystyle{ A,B\subset \RR}\) możemy rozważać zbiór funkcji \(\displaystyle{ B ^A}\), i ponieważ cały zbiór \(\displaystyle{ \RR}\) jest liniowo uporządkowany, to podzbiory \(\displaystyle{ A,B}\) są również liniowo uporządkowane przez naturalny porządek na nich, więc możemy chyba wybrać ze zbioru \(\displaystyle{ B^A}\) funkcję rosnące albo malejące albo słabo rosnące albo słabo malejące. Udowodniłem w sobotę wieczorem, że jeśli mamy dwa zbiory skończone \(\displaystyle{ X,Y\subset \RR}\)- zbiór \(\displaystyle{ X}\)- zbiór \(\displaystyle{ n}\)-elementowy, zbiór \(\displaystyle{ Y}\)- zbiór \(\displaystyle{ m}\)-elementowy, i gdy tylko \(\displaystyle{ n \le m}\), czyli drugi zbiór \(\displaystyle{ Y}\) jest co najmniej tak liczny jak zbiór pierwszy, to ilość funkcji silnie rosnących z pierwszego zbioru w drugi jest równa: \(\displaystyle{ {m \choose n}= \left[ \frac{m!}{ n! \left( m-n\right)! } \right] \in \NN }\), gdzie przypominam, jakby ktoś nie pamiętał (ja na razie pamiętam, bo dopiero to co używałem, może to mi niedługo ulecieć, taki sztuczny fakt nie trzyma się mojej pamięci), mamy: \(\displaystyle{ 0!=1}\). Z pomocą użytkownika Tmkk udało się to udowodnić, sam chyba bym nie wpadł na taki dziwny wzór. Udowodniłem też, że funkcji silnie malejących ze zbioru \(\displaystyle{ n}\)-elementowego, gdzie \(\displaystyle{ n\in\NN,}\) w zbiór \(\displaystyle{ m}\)-elementowy, gdzie \(\displaystyle{ m\in\NN}\), i gdy \(\displaystyle{ n \le m}\)- funkcji silnie malejących jest tyle samo co funkcji silnie rosnących, czyli \(\displaystyle{ {m \choose n}}\). Niedawno udowodniłem też, że jeśli \(\displaystyle{ X}\) jest zbiorem skończonym \(\displaystyle{ n}\)-elementowym, to wszystkich bijekcji z \(\displaystyle{ X}\) do \(\displaystyle{ X}\) jest \(\displaystyle{ n!}\), gdzie przypominam: \(\displaystyle{ 0!=1}\). Przedstawię teraz dowody powyższych faktów.


Niech \(\displaystyle{ X,Y\subset \RR}\) będą dwoma zbiorami skończonymi.

Przypuśćmy, że zbiór \(\displaystyle{ X}\) ma \(\displaystyle{ n}\)-elementów: \(\displaystyle{ X=\left\{ x_1, x_2,\ldots, x_n\right\} }\), a zbiór \(\displaystyle{ Y}\) ma \(\displaystyle{ m}\)-elementów: \(\displaystyle{ Y=\left\{ y_1, y_2,\ldots, y_m\right\} }\). Rozważmy rodzinę funkcji \(\displaystyle{ \mathbb{B},}\) rodzinę wszystkich funkcji silnie rosnących z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), daną jako:

\(\displaystyle{ \mathbb{B}=\left\{ f:X \rightarrow Y\Bigl | f \hbox{ jest silnie rosnąca }\right\} =\left\{ f:X \rightarrow Y\Bigl| \ \bigwedge\limits_{a,b\in X} \left[ a<b \rightarrow f(a)<f(b)\right] \right\}. }\)

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


Zauważmy, że jeśli rodzina \(\displaystyle{ \mathbb{B}}\) jest niepusta, to istnieje funkcja \(\displaystyle{ f\in B}\). Wtedy funkcja \(\displaystyle{ f}\) jest silnie rosnąca, a zatem \(\displaystyle{ f}\) jest różnowartościowa, a zatem \(\displaystyle{ \left| X\right| \le \left| Y\right|}\), czyli \(\displaystyle{ n \le m}\).

Zatem jeśli \(\displaystyle{ n>m}\), to \(\displaystyle{ \mathbb{B}=\emptyset}\), i takich funkcji silnie rosnących nie ma.

Załóżmy dalej, że \(\displaystyle{ n \le m}\), czyli, że zbiór \(\displaystyle{ Y}\) jest co najmniej tak liczny jak zbiór \(\displaystyle{ X}\).

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

Załóżmy dalej, że zbiór \(\displaystyle{ X}\) jest niepusty.


Rozważmy rodzinę \(\displaystyle{ \mathbb{A}, }\) rodzinę \(\displaystyle{ n}\)-elementowych ciągów liczb naturalnych, tzn.:

\(\displaystyle{ \mathbb{A} =\left\{ \left( a_1, a_2,\ldots, a_n\right)\in \NN^n\Bigl| \ \ a_1+a_2+\ldots+a_n \le m-n \right\}}\),

gdzie \(\displaystyle{ (m-n)\in\NN}\), bo założyliśmy, że \(\displaystyle{ n \le m.}\)

Będziemy chcieli pokazać, że nasza rodzina \(\displaystyle{ \mathbb{B}}\) funkcji silnie rosnących jest równoliczna z rodziną ciągów \(\displaystyle{ \mathbb{A}}\). A przy zliczaniu funkcji silnie rosnących istotne są tylko różnicę numerów przyjmowanych wartości ( chodzi o różnicę, poza pierwszą wartością, większe od \(\displaystyle{ 1}\), bo funkcja jest silnie rosnąca, więc te różnice muszą wynosić co najmniej jeden) , i tak żeby ta funkcja pomieściła się w naszym zbiorze \(\displaystyle{ m}\)-elementowym, więc suma tych różnic musi znajdować się w zakresie od \(\displaystyle{ 0}\), (wtedy ostatnia wartość to \(\displaystyle{ y_n}\)) do \(\displaystyle{ m-n.}\)

Wykażemy, że rodzina funkcji \(\displaystyle{ \mathbb{B}}\) jest równoliczna z rodziną ciągów \(\displaystyle{ \mathbb{A}}\).


Definiujemy funkcję \(\displaystyle{ \alpha:\mathbb{B} \rightarrow \mathbb{A}}\), w następujący sposób:

Jeśli \(\displaystyle{ f\in\mathbb{B}}\), wtedy \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest silnie rosnąca.

Jeśli \(\displaystyle{ f(x_1)=y_s}\), gdzie \(\displaystyle{ s\in \left\{ 1,2,\ldots,m\right\}}\), to definiujemy \(\displaystyle{ a_1=(s-1) \in\NN .}\)

Jeśli dla \(\displaystyle{ i\in\NN}\), \(\displaystyle{ i<n}\), oznaczymy \(\displaystyle{ f(x_i)= y _{k_i}}\), gdzie \(\displaystyle{ k_i\in\left\{ 1,2,\ldots, m\right\}}\) , a \(\displaystyle{ f(x _{i+1} ) = y _{k _{i+1} } }\), gdzie \(\displaystyle{ k _{i+1}\in \left\{1,2,\ldots,m \right\}}\) , to definiujemy \(\displaystyle{ a _{i+1} =k _{i+1}-k_i -1}\), i otrzymujemy ciąg \(\displaystyle{ \left( a_1,a_2,\ldots, a_n\right).}\)

Uzasadnijmy jeszcze, że każda współrzędna tego ciągu jest liczbą naturalną.

Mamy \(\displaystyle{ a_1\in\NN}\). Dla \(\displaystyle{ i<n}\), mamy \(\displaystyle{ i<i+1}\), więc ponieważ uporządkowaliśmy zbiór \(\displaystyle{ X}\) naturalnym porządkiem, więc: \(\displaystyle{ x_i<x_{i+1} }\), i ponieważ funkcja \(\displaystyle{ f}\) jest silnie rosnąca, więc \(\displaystyle{ y _{k_i} =f\left( x_i\right) < f\left( x _{i+1} \right) = y _{k _{i+1} }}\) . Wtedy \(\displaystyle{ k_i < k_{i+1} }\) ( gdyby byłoby \(\displaystyle{ k _{i+1} \le k_i}\), to albo \(\displaystyle{ k _{i+1} =k_i}\), i wtedy \(\displaystyle{ y _{k_i} =y _{k _{i+1} } \not > y _{k_i}}\)- sprzeczność, albo \(\displaystyle{ k _{i+1}<k_i}\), a zatem \(\displaystyle{ y _{k _{i+1}} <y _{k_i}}\) -sprzeczność). Wobec czego \(\displaystyle{ k _{i+1} \not\le k_i, }\) i \(\displaystyle{ k _{i+1}> k_i}\), a zatem \(\displaystyle{ a _{i+1}= k _{i+1}-k_i-1 \ge 0}\), i \(\displaystyle{ a _{i+1} \in \NN.}\)

Uzasadnijmy, że \(\displaystyle{ a_1+a_2+\ldots +a_n \le m-n.}\)

Mamy:

\(\displaystyle{ a_1+a_2+\ldots +a_n+n=(s-1)+ \sum_{i=1}^{n-1} a _{i+1} +n= (s-1) + \sum_{i=1}^{n-1} \left( k _{i+1}-k_i-1 \right) +n= (s-1)-\left( n-1\right) +n+ \sum_{i=1}^{n-1} \left( k _{i+1} -k_i\right) = \\ =s+ \sum_{i=1}^{n-1} \left( k _{i+1}-k_i \right) = s+\left( k_2-k_1\right) +\left( k_3-k_2\right) +\ldots +\left( k_n-k _{n-1} \right)= s-k_1+k_n\stackrel {k_1=s}{=} k_n \le m. }\)

Wobec czego \(\displaystyle{ a_1+a_2+\ldots +a_n+n \le m}\), a zatem \(\displaystyle{ a_1+a_2+\ldots +a_n \le m-n.}\)

Wobec czego \(\displaystyle{ \left( a_1, a_2,\ldots, a_n\right) \in \mathbb{A}}\), i funkcja \(\displaystyle{ \alpha}\) jest dobrze określona.


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

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

Weźmy dwie dowolne różne funkcje \(\displaystyle{ f_1, f_2\in \mathbb{B}}\). Wtedy \(\displaystyle{ f_1, f_2 :X \rightarrow Y}\). Wtedy: dla pewnego \(\displaystyle{ x\in X}\), mamy: \(\displaystyle{ f_1(x) \neq f_2(x)}\)- gdyby, dla każdego \(\displaystyle{ x\in X,}\) byłoby \(\displaystyle{ f_1(x)=f_2(x)}\), to moglibyśmy wnioskować, że \(\displaystyle{ f_1=f_2}\)- sprzeczność z założeniem. Wobec czego, i ponieważ zbiór \(\displaystyle{ X}\) jest niepusty, więc otrzymujemy, że dla pewnego \(\displaystyle{ x\in X}\): \(\displaystyle{ f_1(x) \neq f_2 (x).}\) Rozważmy teraz zbiór:

\(\displaystyle{ X_0= \left\{ l \in \left\{ 1,2,\ldots, n\right\}: \ f_1(x_l) \neq f_2(x_l) \right\} \neq \left\{ \right\}. }\)

Zbiór taki jest niepusty, a zatem ma liczbę najmniejszą \(\displaystyle{ l\in X_0}\).

Jeśli \(\displaystyle{ l=1}\), to oznaczmy \(\displaystyle{ f_1\left( x_1\right) =y ^{1} _{k_1}}\), gdzie \(\displaystyle{ k_1 \in \left\{ 1,2,\ldots, m \right\};}\) oraz oznaczmy: \(\displaystyle{ f_2(x_1)=y ^{2} _{k_2} }\), gdzie \(\displaystyle{ k_2\in\left\{ 1,2,\ldots, m\right\}.}\) Wtedy \(\displaystyle{ y ^{1} _{k_1}=f_1\left( x_1\right) \neq f_2\left( x_1\right) =y ^{2} _{k_2}.}\) Wtedy \(\displaystyle{ k_1 \neq k_2}\), a więc również \(\displaystyle{ k_1-1 \neq k_2-1}\), czyli \(\displaystyle{ a ^{1} _{1} \neq a_1^2}\), a więc \(\displaystyle{ \alpha \left( f_1\right) =\left( a_1^1, a_2^1,\ldots, a_n^1\right) \neq \left( a_1^2, a_2^2,\ldots , a_n^2\right) = \alpha (f_2)}\), czyli \(\displaystyle{ \alpha \left( f_1\right) \neq \alpha (f_2).}\)

Jeśli \(\displaystyle{ l \neq 1}\), to \(\displaystyle{ (l-1) \in \left\{ 1,2,\ldots,n\right\}}\). Wtedy \(\displaystyle{ l-1<l}\), zatem \(\displaystyle{ (l-1)\not\in X_0}\) ( gdyby \(\displaystyle{ (l-1) \in X_0}\), ponieważ element \(\displaystyle{ l}\) jest najmniejszy w \(\displaystyle{ X_0,}\) więc moglibyśmy wnioskować, że: \(\displaystyle{ l \le l-1 }\)- sprzeczność). Wobec czego \(\displaystyle{ (l-1)\not\in X_0 }\), ale \(\displaystyle{ (l-1)\in \left\{ 1,2,\ldots,n\right\}}\), a więc, na podstawie definicji zbioru \(\displaystyle{ X_0,}\) musi być: \(\displaystyle{ f_1\left( x _{l-1} \right)= f_2\left( x _{l-1} \right)}\). Ponieważ \(\displaystyle{ l\in X_0}\), więc \(\displaystyle{ f_1\left( x_l\right) \neq f_2(x_l)}\). Oznaczmy \(\displaystyle{ f_1\left( x_l\right)=y^1 _{k_l}, }\) i \(\displaystyle{ f_2\left( x_l\right)=y _{k_i}}\), gdzie \(\displaystyle{ k_l , k_i \in \left\{ 1,2,\ldots,m\right\}. }\) Wtedy \(\displaystyle{ a ^{1} _l= k_l-k _{l-1} -1,}\) i \(\displaystyle{ a_l^2= k_i-k _{l-1} -1}\), wtedy \(\displaystyle{ k_l \neq k_i }\)( gdyby byłoby \(\displaystyle{ k_l=k_i}\), to \(\displaystyle{ f_1(x_l)= y _{k_l}=y _{k_i}=f_2\left( x_l\right)}\), czyli \(\displaystyle{ f_1\left( x_l\right)=f_2\left( x_l\right) }\)-sprzeczność), wobec czego \(\displaystyle{ k_l \neq k_i}\), a zatem \(\displaystyle{ a_l^1=k_l-k _{l-1} -1 \neq k_i-k _{l-1}-1= a_l^2}\), czyli \(\displaystyle{ a_l^1 \neq a_l^2}\), a więc \(\displaystyle{ \alpha \left( f_1\right)=\left( a_1^1, a_2^1, \ldots, a_l^1,\ldots, a_n^1\right) \neq \left( a_1^2, a_2^2,\ldots, a_l ^{2},\ldots, a_n ^{2} \right) = \alpha \left( f_2\right)}\) , czyli \(\displaystyle{ \alpha \left( f_1\right) \neq \alpha \left( f_2\right).}\)

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


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

Niech \(\displaystyle{ \left( a_1,a_2,\ldots, a_n \right) \in\mathbb {A}}\). Wtedy każda współrzędna \(\displaystyle{ a_i}\) jest liczbą naturalną, i ich suma jest mniejsza lub równa od \(\displaystyle{ (m-n)}\). Definiujemy funkcję \(\displaystyle{ f:X \rightarrow Y}\), w sposób poniższy:

\(\displaystyle{ f(x_1)=y _{1+a_1} \in Y.}\)

Dalej definiujemy tą funkcję indukcyjnie:

Przypuśćmy, że zdefiniowaliśmy dla \(\displaystyle{ i<n }\) wartość funkcji \(\displaystyle{ f(x_i)= y _{k_i} }\), gdzie \(\displaystyle{ k_i\in \left\{ 1,2,\ldots,m\right\}}\). Wtedy definiujemy \(\displaystyle{ f(x _{i+1} )= y _{k_i +a _{i+1} +1} .}\)

Czyli \(\displaystyle{ f(x_2)= y _{1+a_1+a_2+1}= y _{a_1+a_2+2}}\) , i dalej

\(\displaystyle{ f(x_3)=y _{\left( a_1+a_2+2\right) +a_3+1}= y _{a_1+a_2+a_3+3} }\),

i jeśli \(\displaystyle{ f(x_i)=y _{a_1+a_2+\ldots +a_i +i}}\), to

\(\displaystyle{ f(x _{i+1} )= y _{\left( a_1+a_2+\ldots +a_i +i\right) + a _{i+1}+1 }= y _{\left( a_1+a_2+\ldots +a _{i+1} \right)+(i+1) }.}\)

Wobec czego ten wzór zachodzi dla każdego \(\displaystyle{ i\in \left\{ 1,2,\ldots, n\right\}.}\)

I ponieważ \(\displaystyle{ a_1+a_2+\ldots +a_n \le m-n}\), więc dla \(\displaystyle{ i<n}\), mamy:

\(\displaystyle{ \left( a_1+a_2+\ldots +a _{i+1} \right)+ (i+1) \le \underbrace{\left( a_1+a_2+\ldots + a_n\right)}_{\le m-n} + \underbrace{\left( i+1\right)}_{ \le n} \le \left( m-n\right) +n=m.}\)

Więc ponieważ \(\displaystyle{ f\left( x _{i+1} \right)=y_{ a_1+a_2+\ldots+ a _{i+1}+(i+1) }}\), a ten numer należy do zbioru \(\displaystyle{ \left\{ 1,2,\ldots, m \right\}}\), więc \(\displaystyle{ f(x _{i+1} )\in Y.}\)

Wobec czego funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest dobrze określona.


Wykażemy, że jest to funkcja silnie rosnąca.

W tym celu wykażemy, że dla każdego \(\displaystyle{ i \in \left\{ 1,2,\ldots, n\right\}}\), i jeśli \(\displaystyle{ i<n}\), to \(\displaystyle{ f\left( x_i\right)< f\left( x _{i+1} \right).}\)

Mamy \(\displaystyle{ f(x_i)= y _{k_i}}\), gdzie \(\displaystyle{ k_i \in \left\{ 1,2, \ldots,m\right\}}\), wtedy \(\displaystyle{ f\left( x _{i+1} \right)= y _{\left( k_i +a _{i+1}+1 \right) }}\), ponieważ \(\displaystyle{ a _{i+1}\in\NN}\), to ten numer jest silnie większy od numeru \(\displaystyle{ k_i}\), i dalej \(\displaystyle{ f\left( x _{i+1} \right)= y _{\left( k_i+a _{i+1} +1\right) }> y _{k_i}= f\left( x_i\right) }\), czyli \(\displaystyle{ f\left( x_i\right)< f\left( x _{i+1} \right)}\).

Łatwo teraz pokazać, że funkcja \(\displaystyle{ f}\) jest silnie rosnąca. W tym celu weźmy \(\displaystyle{ a,b\in X}\), takie, że \(\displaystyle{ a<b,}\) i pokażmy, że \(\displaystyle{ f(a)<f(b).}\)

Mamy \(\displaystyle{ a,b\in X}\), więc \(\displaystyle{ a=x_i}\), \(\displaystyle{ b=x_j}\), gdzie \(\displaystyle{ i,j \in \left\{ 1,2,\ldots,n\right\}}\). Ponieważ \(\displaystyle{ a<b}\), więc \(\displaystyle{ i<j}\), mamy \(\displaystyle{ f(a)= f(x_i)}\), gdzie \(\displaystyle{ i<n}\), więc na mocy faktu udowodnionego powyżej, \(\displaystyle{ f(a)=f(x_i)< f\left( x _{i+1} \right) \le f(x_j)= f(b)}\), czyli \(\displaystyle{ f(a)<f(b),}\) i funkcja \(\displaystyle{ f}\) jest silnie rosnąca. Wobec czego \(\displaystyle{ f \in \mathbb{B}.}\)


Zatem funkcja \(\displaystyle{ \alpha}\) zwraca pewien ciąg \(\displaystyle{ \left( b_1, b_2,\ldots, b_n\right)}\), tzn. mamy: \(\displaystyle{ \alpha \left( f\right) =\left( b_1, b_2,\ldots, b_n \right).}\) Wykażemy, że ciąg \(\displaystyle{ \left( b_1, b_2,\ldots, b_n\right)}\) jest równy ciągowi \(\displaystyle{ \left( a_1,a_2,\ldots, a_n\right).}\)

Wyznaczmy wartość \(\displaystyle{ b_1}\). Ponieważ \(\displaystyle{ f(x_1)=y _{1+a_1}}\), więc: \(\displaystyle{ b_1=1+a_1-1 =a_1}\), co należało pokazać.

Przypuśćmy teraz, że \(\displaystyle{ b_i=a_i}\), dla \(\displaystyle{ i<n}\), i pokażmy, że: \(\displaystyle{ b _{i+1}=a _{i+1}.}\) Jeśli \(\displaystyle{ f(x_i)= y _{k_i},}\) i \(\displaystyle{ f\left( x _{i+1} \right)=y _{k _{i+1} }}\), gdzie \(\displaystyle{ k_i\in \left\{ 1,2,\ldots, m\right\},}\) i \(\displaystyle{ k _{i+1} \in \left\{ 1,2,\ldots,m\right\}}\), to \(\displaystyle{ b _{i+1}= k _{i+1} -k_i-1=k_i+a _{i+1}+1-k_i -1 =a _{i+1}}\), czyli \(\displaystyle{ b _{i+1}=a _{i+1}.}\)

A zatem \(\displaystyle{ \alpha (f)=\left( b_1, b_2,\ldots, b_n \right) =\left( a_1,a_2,\ldots, a_n\right)}\), czyli ciąg \(\displaystyle{ \left( a_1, a_2, \ldots, a_n\right) }\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru takiego ciągu otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.


A zatem \(\displaystyle{ \alpha}\) jest bijekcja, więc nasza rodzina \(\displaystyle{ \mathbb{B}}\) funkcji silnie rosnących jest równoliczna z rodziną ciągów liczb naturalnych \(\displaystyle{ \mathbb{A}}\), której moc, na mocy tego co wykazał użytkownik Tmkk TUTAJ, W OSTATNIM POŚCIE wynosi: \(\displaystyle{ \NN\ni{n+m-n \choose n}= {m \choose n}= \frac{m!}{n!\left( m-n\right)! }}\), gdzie \(\displaystyle{ 0!=1}\) , i to zachodzi dla dowolnych liczb naturalnych takich, że: \(\displaystyle{ n \le m}\) i \(\displaystyle{ n \neq 0.}\) Dla \(\displaystyle{ n=0}\), mamy dokładnie jedną taką funkcję- funkcję pustą, a \(\displaystyle{ {m \choose 0}= \frac{m!}{0! \left( m-0\right)! }= \frac{m!}{1 \cdot m!}=1}\), czyli dla \(\displaystyle{ n=0}\) wzór również zachodzi.

Czyli jeśli \(\displaystyle{ X\subset \RR}\) jest zbiorem skończonym \(\displaystyle{ n}\)-elementowym, a \(\displaystyle{ Y\subset \RR}\) zbiorem skończonym \(\displaystyle{ m}\)-elementowym, i zbiór \(\displaystyle{ Y}\) jest co najmniej tak liczny jak zbiór \(\displaystyle{ X}\), to ilość funkcji \(\displaystyle{ f:X \rightarrow Y}\) silnie rosnących jest równa: \(\displaystyle{ \NN\ni{m \choose n}= \frac{m!}{ n!\left( m-n\right)! }}\), gdzie \(\displaystyle{ 0!=1. \square }\)


Wykażemy jeszcze, że jeśli \(\displaystyle{ X,Y\subset \RR}\) są zbiorami skończonymi (zachowując powyższe oznaczenia), to funkcji \(\displaystyle{ f:X \rightarrow Y }\) silnie malejących jest tyle samo co funkcji \(\displaystyle{ f:X \rightarrow Y}\) silnie rosnących (a tych już wiemy ile jest).

Tzn. rozważmy rodzinę

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

i rozważmy rodzinę

\(\displaystyle{ \mathbb{B}_{-} =\left\{ f:X \rightarrow Y\Bigl| \ \ f \hbox{ jest silnie malejąca} \right\}=\left\{ f:X \rightarrow Y\Bigl| \ \ \bigwedge\limits _{a,b\in X} \left[ a<b \rightarrow f(a)>f(b)\right] \right\}. }\)

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

DOWÓD TEGO FAKTU:

Zauważmy, że jeśli zbiór \(\displaystyle{ X}\) jest pusty, to istnieje dokładnie jedna funkcja pusta, która jest funkcja silnie malejąca i która jest funkcją silnie rosnącą. Obydwie rodziny są więc jednoelementowe, a więc są równoliczne. Załóżmy dalej, że zbiór \(\displaystyle{ X}\) jest niepusty.

Definiujemy bijekcję:

\(\displaystyle{ \alpha :\mathbb{B} \rightarrow \mathbb{B} _{-} }\) w sposób poniższy:

\(\displaystyle{ \alpha (f)= f'}\), gdzie \(\displaystyle{ f':X \rightarrow Y}\) jest określona w następujący sposób:

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

a zatem \(\displaystyle{ f':X \rightarrow Y.}\)

Wykażemy, że funkcja \(\displaystyle{ f'}\) jest silnie malejąca.

W tym celu weźmy \(\displaystyle{ a,b\in X}\), takie, że \(\displaystyle{ a<b,}\) i pokażmy, że \(\displaystyle{ f'(b)<f'(a)}\).

Ponieważ \(\displaystyle{ f:X \rightarrow Y}\), to oznaczmy \(\displaystyle{ f(a)= y_k}\), gdzie \(\displaystyle{ k\in\left\{ 1,2,\ldots,m\right\}}\) oraz \(\displaystyle{ f(b)=y_l}\), gdzie \(\displaystyle{ l\in\left\{ 1,2,\ldots,m\right\} .}\) Mamy \(\displaystyle{ a,b\in X}\), \(\displaystyle{ a<b}\), a funkcja \(\displaystyle{ f}\) jest silnie rosnąca. Ponieważ funkcja \(\displaystyle{ f}\) jest silnie rosnąca, więc \(\displaystyle{ y_k=f(a)<f(b)=y_l}\). Mamy \(\displaystyle{ f'(b)= y _{m-l+1}}\) i \(\displaystyle{ f'(a)=y _{m-k+1}.}\) Ponieważ \(\displaystyle{ y_k<y_l}\), więc również \(\displaystyle{ k<l}\), więc \(\displaystyle{ m-l+1<m-k+1}\), więc:

\(\displaystyle{ f'(a)=y _{m-k+1}> y _{m-l+1}=f'(b)}\), czyli \(\displaystyle{ f'(a)>f'(b)}\), i funkcja \(\displaystyle{ f'}\) jest silnie malejąca.

A zatem \(\displaystyle{ f' \in\mathbb{B} _{-} }\), i funkcja \(\displaystyle{ \alpha : \mathbb{B}\rightarrow \mathbb{B} _{-} }\) jest dobrze określona.


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

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

W tym celu pokażemy, że jeśli \(\displaystyle{ f,g \in \mathbb{B}}\) i \(\displaystyle{ f \neq g}\), to \(\displaystyle{ f'\neq g'.}\)

Jeśli \(\displaystyle{ f,g\in\mathbb{B}}\) i \(\displaystyle{ f \neq g}\), to \(\displaystyle{ f,g:X \rightarrow Y}\), ale \(\displaystyle{ f \neq g}\), więc (i ponieważ zbiór \(\displaystyle{ X}\) jest niepusty), więc dla pewnego \(\displaystyle{ x\in X}\), mamy: \(\displaystyle{ f(x) \neq g(x)}\). Wtedy \(\displaystyle{ f(x)= y_k}\), gdzie \(\displaystyle{ k \in \left\{ 1,2,\ldots,m\right\}}\), i \(\displaystyle{ g(x)= y_l}\), gdzie \(\displaystyle{ l \in \left\{ 1,2,\ldots,m\right\}}\). Ponieważ \(\displaystyle{ f(x) \neq g(x)}\), więc \(\displaystyle{ k \neq l}\), więc \(\displaystyle{ m-k+1 \neq m-l+1}\) (łatwo to można nie wprost udowodnić), i ponieważ uporządkowaliśmy naturalnym porządkiem i ponumerowaliśmy zbiór \(\displaystyle{ Y}\), więc również \(\displaystyle{ f'(x)=y _{m-k+1} \neq y _{m-l+1}= g'(x)}\), czyli \(\displaystyle{ f'(x) \neq g'(x)}\), gdzie \(\displaystyle{ x\in X}\), a zatem \(\displaystyle{ f' \neq g'}\). A zatem funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


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

Niech \(\displaystyle{ g \in \mathbb{B} _{-} }\). Wtedy \(\displaystyle{ g:X \rightarrow Y,}\) i ta funkcja \(\displaystyle{ g}\) jest silnie malejąca. Definiujemy funkcję \(\displaystyle{ f:X \rightarrow Y}\), w następujący sposób:

Jeśli, dla \(\displaystyle{ x\in X}\), mamy \(\displaystyle{ g(x)= y_k}\), gdzie \(\displaystyle{ k\in\left\{ 1,2,\ldots, m \right\}}\), to \(\displaystyle{ f(x)= y _{m-k+1}}\), który to numer elementu \(\displaystyle{ y}\) należy do zbioru \(\displaystyle{ \left\{ 1,2,\ldots,m \right\}}\), a więc to \(\displaystyle{ f(x)\in Y.}\)

A zatem funkcja \(\displaystyle{ f}\) jest dobrze określona.

Należy teraz pokazać, że jest to funkcja silnie rosnąca. Ponieważ funkcja \(\displaystyle{ g}\) jest silnie malejąca, to analogicznie jak w dowodzie poprawności definicji funkcji \(\displaystyle{ \alpha}\), analogicznie pokazujemy, że funkcja \(\displaystyle{ f}\) jest silnie rosnąca, a zatem \(\displaystyle{ f\in\mathbb{B}.}\)

Wtedy funkcja \(\displaystyle{ \alpha}\) zwraca pewną funkcję \(\displaystyle{ f'}\), tzn. mamy \(\displaystyle{ \alpha (f)=f'}\), gdzie \(\displaystyle{ f' \in \mathbb{B}_{-}}\). Wtedy \(\displaystyle{ f':X \rightarrow Y}\), mamy też \(\displaystyle{ g:X \rightarrow Y.}\) Pokażemy, że \(\displaystyle{ f'=g}\).

Niech \(\displaystyle{ x\in X}\). Wtedy \(\displaystyle{ g(x)=y_k}\), gdzie \(\displaystyle{ k \in \left\{ 1,2,\ldots,m\right\}}\), wtedy \(\displaystyle{ f(x)= y _{m-k+1}}\), i dalej \(\displaystyle{ f'(x)= y _{m-\left( m-k+1\right)+1 }=y_k=g(x)}\), czyli \(\displaystyle{ f'(x)= g(x)}\), a z\(\displaystyle{ }\)atem (z dowolności wyboru \(\displaystyle{ x\in X}\)), otrzymujemy: \(\displaystyle{ f'=g}\).

A zatem \(\displaystyle{ \alpha \left( f\right)= f' =g}\), a więc funkcja \(\displaystyle{ g}\) jest wartością funkcji \(\displaystyle{ \alpha}\). Z dowolności wyboru funkcji \(\displaystyle{ g}\) otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.


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

A zatem \(\displaystyle{ \left| \mathbb{B}_{-}\right|= {m \choose n}}\), dla \(\displaystyle{ n \le m.\square }\)


Wykażemy jeszcze, że bijekcji na zbiorze \(\displaystyle{ n}\)-elementowym jest dokładnie \(\displaystyle{ n! }\)

Nim to zrobimy, przypomnijmy, udowodniłem to niedawno, może nie będę teraz tego udowadniał , może jak ktoś będzie bardzo chciał to potem napiszę, nie mam teraz czasu ani sił, a intuicyjnie jest to zrozumiale, że wszystkich funkcji różnowartościowych ze zbioru skończonego \(\displaystyle{ n}\)-elementowego w drugi zbiór skończony \(\displaystyle{ m}\)-elementowy, i gdy \(\displaystyle{ m \ge n}\), to ilość takich funkcji różnowartościowych jest równa: \(\displaystyle{ \underbrace {m \cdot (m-1) \cdot \ldots \cdot \left( m-n+1\right)}_{n}= \frac{m!}{(m-n)! }}\) , gdzie \(\displaystyle{ 0!=1}\).

Wykorzystamy ten fakt aby udowodnić, że bijekcji zbioru \(\displaystyle{ n}\)-elementowego jest dokładnie \(\displaystyle{ n!}\). Tzn.:

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

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

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

DOWÓD TEGO FAKTU:

Rozważmy rodzinę funkcji różnowartościowych:

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

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

Jeśli \(\displaystyle{ f\in\mathbb{B}}\), to \(\displaystyle{ f:X \rightarrow X}\) i funkcja \(\displaystyle{ f}\) jest bijekcją, zatem funkcja \(\displaystyle{ f}\) jest różnowartościowa, a zatem \(\displaystyle{ f\in\mathbb{A}}\), tak więc \(\displaystyle{ \mathbb{B}\subset \mathbb{A}.}\)

Niech teraz \(\displaystyle{ f\in\mathbb{A}}\). Wtedy \(\displaystyle{ f:X \rightarrow X}\) i funkcja \(\displaystyle{ f}\) jest różnowartościowa. Przypuśćmy, że \(\displaystyle{ f}\) nie jest funkcją 'na'. Wtedy zbiór wartości \(\displaystyle{ f_P\subsetneq X}\). Wtedy \(\displaystyle{ f: X \stackrel {1-1} {\mathop {\rightarrow}_{NA} } f_P}\), a zatem jest to bijekcja, i \(\displaystyle{ n\sim X\sim f_P}\), a więc \(\displaystyle{ f_P\sim n}\). Mamy \(\displaystyle{ f_P\subsetneq X}\), tak więc \(\displaystyle{ X\not\subset f_P.}\) Ale ponieważ zbiór pusty jest podzbiorem każdego zbioru, więc w szczególności \(\displaystyle{ \emptyset \subset f_P}\) , a \(\displaystyle{ X\not\subset f_P}\) , więc \(\displaystyle{ X \neq \emptyset}\). Mamy \(\displaystyle{ X\not\subset f_P}\), więc zaprzeczając definicji inkluzji otrzymujemy, że istnieje element \(\displaystyle{ x\in X}\), taki, że \(\displaystyle{ x\not\in f_P.}\) Ponieważ jednocześnie \(\displaystyle{ X\supset f_P\sim n}\), to otrzymujemy, że zbiór \(\displaystyle{ X}\) ma co najmniej \(\displaystyle{ (n+1)}\) elementów, a \(\displaystyle{ X\sim n}\), czyli zbiór \(\displaystyle{ X}\) ma tylko \(\displaystyle{ n}\)-elementów-sprzeczność. Wobec czego funkcja \(\displaystyle{ f}\) musi być 'na'. A zatem \(\displaystyle{ f}\) jest bijekcją i \(\displaystyle{ f\in \mathbb{B}. }\)

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

A zatem, na podstawie przytoczonego wzoru o liczności zbioru funkcji różnowartościowych, otrzymujemy, że:

\(\displaystyle{ \left| \mathbb{B}\right|=\left| \mathbb{A}\right| =\left| \mathbb{B} _{n,n} \right| = \frac{n!}{\left( n-n\right)! } = \frac{n!}{1}=n!.\square}\) :lol: :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 »

Po wysłaniu tego postu, ta ilość funkcji silnie rosnących ze zbioru \(\displaystyle{ n}\)-elementowego w zbiór \(\displaystyle{ m}\)-elementowy, równa \(\displaystyle{ {m \choose n}- }\) zacząłem się zastanawiać, czy ta rodzina funkcji nie odpowiada pewnej rodzinie \(\displaystyle{ n}\)-elementowych podzbiorów pewnego zbioru \(\displaystyle{ m}\)-elementowego (gdyż takich zbiorów jest dokładnie \(\displaystyle{ {m \choose n}}\) ). Dzisiaj to w końcu udowodniłem. Rozwiązanie jest już dużo prostsze.


Niech \(\displaystyle{ X,Y\subset \RR}\) będą dwoma zbiorami skończonymi .

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

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

Wykażemy, że jeśli zbiór \(\displaystyle{ Y}\), zbiór \(\displaystyle{ m}\)-elementowy, jest co najmniej tak liczny jak zbiór \(\displaystyle{ X}\)- zbiór \(\displaystyle{ n}\)-elementowy, to ilość takich funkcji silnie rosnących wynosi dokładnie \(\displaystyle{ {m \choose n}}\).

PROSTSZY DOWÓD TEGO FAKTU:

Zauważmy, że jeśli \(\displaystyle{ n=0}\), to podany wzór zachodzi. Załóżmy dalej, że zbiór \(\displaystyle{ X}\) jest niepusty.

Zauważmy, że jeśli \(\displaystyle{ f\in\mathbb{B}}\), to funkcja \(\displaystyle{ f}\) jest silnie rosnąca, a zatem funkcja \(\displaystyle{ f}\) jest różnowartościowa, i jest 'na' zbiór wartości, wobec czego funkcja \(\displaystyle{ f:X \rightarrow f_P}\) jest bijekcją, i \(\displaystyle{ n\sim X\sim f_P}\), a zatem \(\displaystyle{ f_P\sim n}\), i zbiór \(\displaystyle{ f_P}\) ze swej natury jest podzbiorem zbioru \(\displaystyle{ Y,}\) zbioru \(\displaystyle{ m}\)-elementowego.

Rozważmy rodzinę \(\displaystyle{ \mathbb{A}}\)- rodzinę zbiorów wartości kolejnych funkcji z rodziny \(\displaystyle{ \mathbb{B}.}\)

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

I rozważmy rodzinę wszystkich \(\displaystyle{ n}\)-elementowych podzbiorów zbioru \(\displaystyle{ Y}\)- zbioru \(\displaystyle{ m}\)-elementowego, tzn.:

\(\displaystyle{ \mathbb{B} _{n,m} =\left\{ B\subset Y \Bigl| \ \ \left| B\right|=n \right\} .}\)

Na mocy uzasadnienia powyżej \(\displaystyle{ \mathbb{A}\subset \mathbb{B} _{n,m}.}\) Wykażemy teraz inkluzję w drugą stronę.

Niech \(\displaystyle{ B\in\mathbb{B} _{n,m}}\). Wtedy \(\displaystyle{ B\subset Y}\), i \(\displaystyle{ \left| B\right|=n}\). Oznaczmy \(\displaystyle{ B=\left\{ y _{k_1}, y _{k_2}, \ldots, y _{k_n} \right\} }\), gdzie \(\displaystyle{ k_i \in \left\{ 1,2,\ldots, m\right\}}\), i gdzie porządek na zbiorze numerów \(\displaystyle{ \left\{ k_1, k_2,\ldots, k_n\right\}}\) jest naturalny, oraz gdzie \(\displaystyle{ y _{k_i} \neq y _{k_j}}\), dla dowolnych \(\displaystyle{ i,j}\), takich, że \(\displaystyle{ i \neq j.}\) Definiujemy teraz funkcję \(\displaystyle{ f:X \rightarrow Y}\), w poniższy sposób:

\(\displaystyle{ f(x_1)= y _{k_1},}\)
\(\displaystyle{ f(x_2)= y _{k_2}, }\)
\(\displaystyle{ \vdots}\)
\(\displaystyle{ f(x_i)= y _{k_i}\in B\subset Y.}\)

A zatem \(\displaystyle{ f(x_i)\in Y}\), i funkcja \(\displaystyle{ f:X \rightarrow Y}\) jest dobrze określona. Wykażemy, że jest to funkcja silnie rosnąca.
DOWÓD TEGO FAKTU::    
A zatem \(\displaystyle{ f\in\mathbb{B}}\), a zatem \(\displaystyle{ f_P\in\mathbb{A}}\). Wykażemy teraz, że \(\displaystyle{ f_P=B}\). To jednak jest proste gdyż:

\(\displaystyle{ f_P=\stackrel{\rightarrow }{f} (X)=\left\{ f(x_1), f(x_2),\ldots, f(x_n)\right\} =\left\{ y _{k_1}, y _{k_2},\ldots, y _{k_n} \right\}= B}\).

A zatem \(\displaystyle{ \mathbb{A}\ni f_P=B}\), czyli \(\displaystyle{ B\in\mathbb{A}}\). A zatem \(\displaystyle{ \mathbb{B} _{n,m}=\mathbb{A}}\).

A zatem, ponieważ rodzina \(\displaystyle{ \mathbb{B} _{n,,m}}\) jest rodziną wszystkich podzbiorów \(\displaystyle{ n}\)-elementowych zbioru \(\displaystyle{ Y}\)- zbioru \(\displaystyle{ m}\)-elementowego, więc: \(\displaystyle{ \left| \mathbb{B} _{n,m} \right| =\left| \mathbb{A}\right|= {m \choose n}.}\)


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

W tym celu rozważmy funkcję \(\displaystyle{ \alpha}\) , która funkcji \(\displaystyle{ f \in \mathbb{B}}\) przypisuję zbiór jej wartości, tzn.:

\(\displaystyle{ f \in \mathbb{B}\stackrel {\alpha} {\rightarrow} f_P\in\mathbb{A}.}\)

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


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

W tym celu weźmy dwie dowolne różne funkcje \(\displaystyle{ f,g \in \mathbb{B}.}\) Wtedy \(\displaystyle{ f,g:X \rightarrow Y.}\) Ponieważ te funkcję są różne, i ponieważ ich dziedzina \(\displaystyle{ X}\) jest zbiorem niepustym, więc otrzymujemy, że dla pewnego \(\displaystyle{ x\in X}\), mamy: \(\displaystyle{ f(x) \neq g(x)}\). Rozważmy teraz zbiór \(\displaystyle{ X_0}\), dany jako:

\(\displaystyle{ X_0=\left\{ l\in\left\{ 1,2,\ldots,n\right\}: \ f\left( x_l\right) \neq g\left( x_l\right) \right\} \neq \left\{ \right\}. }\)

Ponieważ \(\displaystyle{ f(x) \neq g(x)}\), więc zbiór \(\displaystyle{ X_0}\) jest niepusty. Ponieważ zbiór \(\displaystyle{ X_0}\) jest niepusty, a zatem ma liczbę najmniejszą \(\displaystyle{ i\in X_0}\). Ponieważ \(\displaystyle{ i \in X_0}\), więc \(\displaystyle{ f(x_i) \neq g(x_i)}\). A zatem (ponieważ zbiór liczb rzeczywistych \(\displaystyle{ \RR}\) jest liniowo uporządkowany przez zwykły porządek), więc: \(\displaystyle{ f(x_i)< g(x_i)}\) lub \(\displaystyle{ f(x_i)> g(x_i).}\)

Jeśli \(\displaystyle{ f(x_i)< g(x_i)}\), to dla dowolnego \(\displaystyle{ 0<j<i}\), mamy, że \(\displaystyle{ j\not\in X_0 }\) (gdyby \(\displaystyle{ j\in X_0}\), ponieważ numer \(\displaystyle{ i}\) jest najmniejszy w \(\displaystyle{ X_0}\), więc możemy wnioskować, że \(\displaystyle{ i \le j}\), a \(\displaystyle{ j<i}\)- sprzeczność). Wobec czego \(\displaystyle{ j\not\in X_0}\), ale \(\displaystyle{ i\in X_0}\), i \(\displaystyle{ i \in \left\{ 1,2,\ldots, n\right\}}\), i \(\displaystyle{ j \in \left\{ 1,2,\ldots,n\right\} }\), więc ponieważ \(\displaystyle{ j\not\in X_0}\), więc z definicji zbioru \(\displaystyle{ X_0}\) musi być: \(\displaystyle{ f(x_j)=g(x_j)}\). Zauważmy teraz, będziemy chcieli pokazać, że element \(\displaystyle{ f(x_i)}\) nie jest wartością funkcji \(\displaystyle{ g}\), więc, zauważmy, że: Dla dowolnego \(\displaystyle{ j>i}\), mamy \(\displaystyle{ g(x_j)>f(x_i)}\). Ponieważ \(\displaystyle{ g\in \mathbb{B}}\), to funkcja \(\displaystyle{ g}\) jest silnie rosnąca, a zatem \(\displaystyle{ g(x_j)> g(x_i)> f(x_i)}\), czyli \(\displaystyle{ g(x_j)> f(x_i)}\). Dla \(\displaystyle{ j=i,}\) mamy oczywiście: \(\displaystyle{ g(x_j)=g(x_i)> f(x_i)}\). A dla dowolnego \(\displaystyle{ j<i}\), mamy \(\displaystyle{ g(x_j)= f(x_j)}\). Ponieważ \(\displaystyle{ f\in\mathbb{B}}\), to funkcja \(\displaystyle{ f}\) jest silnie rosnąca, a zatem jest to funkcja różnowartościowa, a zatem: \(\displaystyle{ g(x_j)= f(x_j) \neq f(x_i).}\)
A zatem wnioskujemy, że \(\displaystyle{ f(x_i)\not\in g_P}\), ale \(\displaystyle{ f(x_i)\in f_P}\), a zatem \(\displaystyle{ f_P \neq g_P}\), co należało pokazać.

Jeśli \(\displaystyle{ f(x_i)> g(x_i)}\), to podobnie element \(\displaystyle{ g(x_i)}\) nie jest wartością funkcji \(\displaystyle{ f}\), gdyż:
Dla każdego \(\displaystyle{ j>i}\), ponieważ \(\displaystyle{ f\in\mathbb{B}}\), więc funkcja \(\displaystyle{ f}\) jest silnie rosnąca, więc: \(\displaystyle{ f(x_j)> f(x_i)>g(x_i).}\)
A dla \(\displaystyle{ j<i}\), mamy, ponieważ numer \(\displaystyle{ i}\) jest najmniejszy w \(\displaystyle{ X_0}\), więc z definicji tego zbioru, mamy, dla każdego \(\displaystyle{ j<i}\), mamy: \(\displaystyle{ f(x_j)= g(x_j)}\), i ponieważ funkcja \(\displaystyle{ g}\) jest silnie rosnąca, zatem funkcja \(\displaystyle{ g}\) jest różnowartościowa, więc \(\displaystyle{ f(x_j)=g(x_j) \neq g(x_i)}\).
Wnioskujemy stąd, że \(\displaystyle{ g(x_i)\not\in f_P}\), a mamy \(\displaystyle{ g(x_i)\in g_P}\), a zatem \(\displaystyle{ f_P \neq g_P.}\)

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

Bardzo łatwo jest sprawdzić, że jest to funkcja 'na', zatem \(\displaystyle{ \alpha :\mathbb{B} \rightarrow \mathbb{A}}\) jest bijekcją, a zatem \(\displaystyle{ \mathbb{B}\sim \mathbb{A}}\).

A zatem \(\displaystyle{ \left| \mathbb{B}\right|=\left| \mathbb{A}\right|= {m \choose n}}\), dla \(\displaystyle{ n \le m.\square}\) :lol:


Na koniec dodam taką ciekawą zagadkę:

Czy jeśli funkcja \(\displaystyle{ f:A\subset \RR \rightarrow \RR}\) nie jest funkcją niemalejącą, to czy jest funkcją malejącą :?: Pozory mogą mylić. 8-)
Jan Kraszewski
Administrator
Administrator
Posty: 34126
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: 13 lut 2022, o 23:05Na koniec dodam taką ciekawą zagadkę:

Czy jeśli funkcja \(\displaystyle{ f:A\subset \RR \rightarrow \RR}\) nie jest funkcją niemalejącą, to czy jest funkcją malejącą :?: Pozory mogą mylić. 8-)
Ty tak na poważnie :?:

JK
ODPOWIEDZ