Teoria mocy zbiorów

[a4karo]

Uch...

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

To samo, ale w trzech linijkach...

JK

Ale jakże nieformalnie. I nie cieszy tak, jak porządny dowód

[Jakub Gurak]

Mam teraz pytanie, może ktoś pomoże:

Ile jest bijekcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\)

Myślę, że potrafię uzasadnić, że jest ich co najmniej continuum.

PRÓBA DOWODU::    

Dla dowolnej ustalonej liczby rzeczywistej \(\displaystyle{ x}\) różnej od zera, rozważmy funkcję \(\displaystyle{ f_x}\) z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\), która zerze przypisuje liczbę \(\displaystyle{ x}\), a liczbie \(\displaystyle{ x}\) przypisuje \(\displaystyle{ 0}\), a na pozostałych argumentach jest identycznością. Ponieważ identyczność na zbiorze jest zawsze bijekcją, więc również \(\displaystyle{ f_x}\) jest bijekcją. I tak dla dowolnego \(\displaystyle{ x \neq 0}\) rozważamy bijekcję \(\displaystyle{ f_x}\).

I jeśli \(\displaystyle{ x_1 \neq x _{2}}\), to \(\displaystyle{ f _{x_1}\left( 0\right) = x _{1} \neq x_2=f _{x_2}(0)}\), a więc \(\displaystyle{ f _{x_1} \neq f _{x_2}. }\) A zatem tych bijekcji jest co najmniej tyle ile elementów zbioru \(\displaystyle{ \RR \setminus \left\{ 0\right\},}\) czyli continuum.

Pytanie jest teraz takie, czy nie ma tych bijekcji, czy nie ma ich więcej niż continuum, gdyż wszystkich funkcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\) jest \(\displaystyle{ 2 ^{\left| \RR\right| } }\). Nie wiem jak się za to zadanie zabrać, metoda ze zliczania bijekcji na zbiorze liczb naturalnych może tu nie podziałać, gdyż zbiór liczb rzeczywistych jest nieprzeliczalny. Pomoże ktoś???

[Jan Kraszewski]

Ile jest bijekcji z \(\displaystyle{ \RR}\) do \(\displaystyle{ \RR}\)

\(\displaystyle{ 2^{\mathfrak{c}}}\)

Pomyśl o odwzorowaniach, które przeprowadzają \(\displaystyle{ 0}\) na \(\displaystyle{ 0}\), a każdą dodatnią liczbę rzeczywistą zamieniają miejscami z liczbą do niej przeciwną - albo nie zamieniają. Masz continuum wiele decyzji (dla każdej dodatniej liczby rzeczywistej), czy zamienić ją miejscami z liczbą do niej przeciwną, czy też zostawić je nieruszone. Każdy układ takich decyzji zadaje inną bijekcję \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\).

Jak chcesz to formalizować, to jest to injekcja z \(\displaystyle{ \{0,1\}^{(0,+\infty)}}\) w zbiór bijekcji \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\), co daje Ci pożądane oszacowanie od dołu.

JK

[a4karo]

Da się to nawet prostym wzorkiem napisać: dla dowolnego `A\subset [0,\infty)`, funkcja `f(x)=(2\chi_A(|x|)-1)x` jest bijekcją.

Dodano po 2 minutach 54 sekundach:
PS wiem, że Janusz Tracz napisze, że to nie funkcja lecz ewaluacja i będzie miał rację

[Jan Kraszewski]

To nie funkcja, tylko wzór funkcji (ale to nie rozwiązanie, tylko wskazówka, więc jest OK) .

JK

[Jakub Gurak]

Pomyśl o odwzorowaniach, które przeprowadzają \(\displaystyle{ 0}\) na \(\displaystyle{ 0}\), a każdą dodatnią liczbę rzeczywistą zamieniają miejscami z liczbą do niej przeciwną - albo nie zamieniają. Masz continuum wiele decyzji (dla każdej dodatniej liczby rzeczywistej), czy zamienić ją miejscami z liczbą do niej przeciwną, czy też zostawić je nieruszone. Każdy układ takich decyzji zadaje inną bijekcję \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\).

Jak chcesz to formalizować, to jest to injekcja z \(\displaystyle{ \{0,1\}^{(0,+\infty)}}\) w zbiór bijekcji \(\displaystyle{ \RR}\) w \(\displaystyle{ \RR}\), co daje Ci pożądane oszacowanie od dołu.

JK

Nie wiem czy dobrze to rozumiem.

Rozumiem, że definiujemy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{\RR _{+} } \rightarrow \mathbb{B}, }\) gdzie \(\displaystyle{ \mathbb {B} }\) jest naszą rodziną wszystkich bijekcji, tak, że jeśli \(\displaystyle{ f:\RR _{+} \rightarrow \left\{ 0,1\right\}}\), to \(\displaystyle{ \alpha \left( f\right) = f'}\), gdzie:

\(\displaystyle{ f':\RR \rightarrow \RR,}\)

jest tak określona, że:

\(\displaystyle{ f'(0)=0;}\)

I jeśli (dla \(\displaystyle{ x \in\RR_+}\)): \(\displaystyle{ f(x)=1}\), to \(\displaystyle{ f'(x)=- x}\) i \(\displaystyle{ f' (-x)=x}\) (w ten sposób funkcja \(\displaystyle{ f'}\) jest określona na \(\displaystyle{ 0}\), na argumentach dodatnich i na argumentach do nich przeciwnych, czyli na całym \(\displaystyle{ \RR}\));

a jeśli \(\displaystyle{ f(x)=0}\), to funkcja \(\displaystyle{ f'}\) ma punkty stałe, czyli: \(\displaystyle{ f'(x)=x}\), i \(\displaystyle{ f'(- x)=- x}\), oto chodzi

[Jan Kraszewski]

Rozumiem, że definiujemy funkcję \(\displaystyle{ \alpha :\left\{ 0,1\right\} ^{\RR _{+} } \rightarrow \mathbb{B}, }\) gdzie \(\displaystyle{ \mathbb {B} }\) jest naszą rodziną wszystkich bijekcji, tak, że jeśli \(\displaystyle{ f:\RR _{+} \rightarrow \left\{ 0,1\right\}}\), to \(\displaystyle{ \alpha \left( f\right) = f'}\), gdzie:

\(\displaystyle{ f':\RR \rightarrow \RR,}\)

jest tak określona, że:

\(\displaystyle{ f'(0)=0;}\)

I jeśli (dla \(\displaystyle{ x \in\RR_+}\)): \(\displaystyle{ f(x)=1}\), to \(\displaystyle{ f'(x)=- x}\) i \(\displaystyle{ f' (-x)=x}\) (w ten sposób funkcja \(\displaystyle{ f'}\) jest określona na \(\displaystyle{ 0}\), na argumentach dodatnich i na argumentach do nich przeciwnych, czyli na całym \(\displaystyle{ \RR}\));

a jeśli \(\displaystyle{ f(x)=0}\), to funkcja \(\displaystyle{ f'}\) ma punkty stałe, czyli: \(\displaystyle{ f'(x)=x}\), i \(\displaystyle{ f'(- x)=- x}\), oto chodzi

Tak, o to chodzi.

JK

[Jakub Gurak]

Przed chwilą udało się ukończyć dowód faktu, że na zbiorze przeliczalnym (równolicznym ze zbiorem liczb naturalnych) istnieje dokładnie continuum dobrych porządków. Jest to o tyle zaskakujące, że dobre porządki na zbiorze przeliczalnym mogą być bardzo długie( chyba mogą sięgać, o krok wcześniej, od najmniejszej liczby nieprzeliczalnej, o której nie wiemy, czy jest równa continuum, czy może jest mniejsza, zgodnie z wiedzą odnośnie hipotezy continuum). A jednak, z przyczyn formalnych, łatwo jest udowodnić, że dobrych porządków na zbiorze przeliczalnym jest co najwyżej continuum. Wykazałem też ostatnio, że dla funkcji między dwoma zbiorami, dla dwóch podzbiorów dziedziny tej funkcji, wtedy obraz różnicy symetrycznej tych dwóch podzbiorów jest nadzbiorem różnicy symetrycznej obrazów tych dwóch podzbiorów. Przedstawię teraz dowody tych ciekawych faktów.


Podajmy najpierw pewien Lemat.

Lemat 1. Niech \(\displaystyle{ X}\) będzie zbiorem; a \(\displaystyle{ Y_1, Y_2}\) niech będą zbiorami równolicznymi ze zbiorem \(\displaystyle{ X}\). Wykażemy, że tyle samo jest bijekcji z \(\displaystyle{ X}\) do \(\displaystyle{ X,}\) co bijekcji z \(\displaystyle{ Y_1}\) do \(\displaystyle{ Y_2.}\)

Tzn. niech:

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

I niech:

\(\displaystyle{ \mathbb{B} _{Y_{1}, Y_{2} }=\left\{ f:Y_1 \rightarrow Y_2\Bigl| \ f \hbox{ jest bijekcją } \right\}.}\)

I wykażemy, że:

\(\displaystyle{ \mathbb{B}_X\sim \mathbb{B} _{Y _{1}, Y _{2} }.}\)

DOWÓD LEMATU:

Jeśli \(\displaystyle{ g\in \mathbb{B}_X}\), wtedy \(\displaystyle{ g:X \rightarrow X,}\) i funkcja \(\displaystyle{ g}\) jest bijekcją. Ponieważ \(\displaystyle{ Y_1\sim X}\), więc istnieje miedzy nimi bijekcja, nazwijmy ją \(\displaystyle{ f_1}\). Podobnie, niech \(\displaystyle{ f_2:X \rightarrow Y_2}\) będzie bijekcją (uzyskaną na podstawie równoliczności zbioru \(\displaystyle{ X}\) i zbioru \(\displaystyle{ Y_2}\)). Definiujemy funkcję \(\displaystyle{ \alpha}\) w poniższy sposób:

\(\displaystyle{ \alpha \left( g\right) = g'=f_2\circ g \circ f_1}\).

Wtedy \(\displaystyle{ g': Y_1 \rightarrow Y_2,}\) i funkcja \(\displaystyle{ g'}\) jest bijekcją (jako złożenie bijekcji), a więc \(\displaystyle{ g'\in\mathbb{B} _{Y_1,Y_2}.}\)

I otrzymujemy, że funkcja:

\(\displaystyle{ \alpha :\mathbb{B}_X \rightarrow \mathbb{B} _{Y_1, Y_2}}\) jest dobrze określona.


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

Wykażemy, że \(\displaystyle{ \alpha}\) jest funkcją różnowartościową.

Jeśli \(\displaystyle{ \alpha \left( g_1\right)= \alpha \left( g_2\right)}\), to, z definicji tej funkcji \(\displaystyle{ \alpha,}\) oznacza, że:

\(\displaystyle{ f_2\circ g_1\circ f_1= f_2\circ g_2\circ f_1}\), ponieważ funkcje \(\displaystyle{ f_2, f_1}\) są bijekcjami, więc relacje odwrotne \(\displaystyle{ f_2 ^{-1}}\) i \(\displaystyle{ f_1 ^{-1}}\) są również bijekcjami. I wtedy:

\(\displaystyle{ f_2 ^{-1} \circ\left( f_2\circ g_1\circ f_1\right) \circ f_1 ^{-1} = f_2 ^{-1} \circ \left( f_2\circ g_2\circ f_1\right) \circ f_1 ^{-1} }\), czyli (z łączności złożenia funkcji) otrzymujemy:

\(\displaystyle{ \left( f_2 ^{-1}\circ f_2 \right) \circ g_1\circ \left( f_1\circ f_1 ^{-1} \right) = \left( f_2 ^{-1}\circ f_2 \right) \circ g_2\circ \left( f_1\circ f_1 ^{-1} \right)}\), i ponieważ funkcje \(\displaystyle{ f_2}\) i \(\displaystyle{ f_1}\) są bijekcjami, a więc:

\(\displaystyle{ I_X\circ g_1\circ I_X= g_1= I_X\circ g_2\circ I_X= g_2}\),

czyli \(\displaystyle{ g_1=g_2}\), i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.


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

Niech \(\displaystyle{ f\in \mathbb{B} _{Y_1,Y_2}.}\) Wtedy \(\displaystyle{ f:Y_1 \rightarrow Y_2}\) i funkcja \(\displaystyle{ f}\) jest bijekcją.

Zdefiniujmy:

\(\displaystyle{ g= f _{2} ^{-1}\circ f\circ f_{1} ^{-1}.}\)

Wtedy \(\displaystyle{ g:X \rightarrow X}\), i ponieważ również relacje odwrotne \(\displaystyle{ f_1 ^{-1}}\) i \(\displaystyle{ f_2 ^{-1}}\) są bijekcjami, to \(\displaystyle{ g}\) jest bijekcją (jako złożenie bijekcji). A zatem \(\displaystyle{ g\in \mathbb{B}_X}\). I wtedy:

\(\displaystyle{ \alpha \left( g\right) = g'=f_2\circ g\circ f_1=f_2\circ \left( f_2 ^{-1}\circ f\circ f_1 ^{-1} \right) \circ f_1= \left( f_2\circ f_2 ^{-1} \right)\circ f\circ \left( f_1 ^{-1}\circ f_1 \right)=f,}\)

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

A zatem:

\(\displaystyle{ \mathbb{B}_X\sim \mathbb{B} _{Y_1,Y_2}}\),

co kończy dowód tego lematu.\(\displaystyle{ \square}\)


Przejdźmy do naszego problemu:

Niech \(\displaystyle{ X}\) będzie zbiorem równolicznym z \(\displaystyle{ \NN}\). Rozważmy rodzinę dobrych porządków \(\displaystyle{ \mathbb{B}}\), daną jako:

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

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

Wykażemy, że jest to rodzina mocy continuum.


DOWÓD TEGO FAKTU:

Łatwo, z przyczyn formalnych, łatwo jest pokazać, że ta rodzina \(\displaystyle{ \mathbb{B} }\) ma moc co najwyżej continuum, gdyż:

jeśli \(\displaystyle{ \left( \le \right)\in \mathbb{B}}\), wtedy \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ X}\), a więc \(\displaystyle{ \le}\) jest relacją porządku na \(\displaystyle{ X}\), w szczególności jest relacją w zbiorze \(\displaystyle{ X}\), a więc

\(\displaystyle{ \left( \le \right) \subset X \times X\stackrel{X\sim \NN} {\sim} \NN \times \NN\sim \NN}\),

a więc \(\displaystyle{ \mathbb{B}\subset P(X \times X) \sim P(\NN)\sim \RR.}\)

a więc \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|.}\)


Aby pokazać nierówność mocy w drugą stronę, to niech:

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

(przypominam bijekcji na zbiorze liczb naturalnych jest continuum- to się uzasadnia, w taki ciekawy sposób, że dla dowolnego ciągu zerojedynkowego \(\displaystyle{ f}\) definiuje się bijekcję na \(\displaystyle{ \NN}\), w taki sposób, że jeśli \(\displaystyle{ f(n)=1}\), to liczby \(\displaystyle{ 2n}\) i \(\displaystyle{ 2n+1}\) zamieniamy miejscami, a jeśli \(\displaystyle{ f(n)= 0}\) to zostawiamy je w naturalnym porządku, i uzasadniamy, że jest to przekształcenie różnowartościowe; a z drugiej strony wszystkich funkcji z \(\displaystyle{ \NN}\) do \(\displaystyle{ \NN}\) jest continuum, a więc tych bijekcji jest continuum).

A zatem, na mocy Lematu 1, rodzina:

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

jest równoliczna z rodziną \(\displaystyle{ \mathbb{A}}\), a więc jest mocy continuum.

Definiujemy teraz funkcję:

\(\displaystyle{ \alpha :\mathbb{B} _{\NN, X} \rightarrow \mathbb{B}}\), w następujący sposób:

Jeśli \(\displaystyle{ f:\NN \rightarrow X}\) jest bijekcją, to definiujemy porządek \(\displaystyle{ \le}\) na \(\displaystyle{ X}\), jako:

\(\displaystyle{ f(0)< f(1)<f(2) < \ldots}\)

otrzymując liniowy porządek na \(\displaystyle{ X}\), i jest to porządek podobny do zwykłego porządku \(\displaystyle{ \le _{\NN}}\) na \(\displaystyle{ \NN}\).

Ponieważ \(\displaystyle{ \le _{\NN}}\) jest dobrym porządkiem, więc również porządek doń podobny \(\displaystyle{ \le}\) jest dobrym porządkiem na \(\displaystyle{ X}\), i \(\displaystyle{ \left( \le \right) \in \mathbb{B}}\), i w ten sposób otrzymujemy funkcję:

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

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

DOWÓD TEGO FAKTU::    

Weźmy dwie różne funkcje \(\displaystyle{ f_1, f_2 \in \mathbb{B} _{\NN,X}.}\) I pokażmy, że również przypisane odpowiednio im porządki \(\displaystyle{ \le _1}\) i \(\displaystyle{ \le _2}\) są różne.

Wtedy \(\displaystyle{ f_1,f_2:\NN \rightarrow X}\), a ponieważ \(\displaystyle{ f_1 \neq f_2}\), a a więc dla pewnego \(\displaystyle{ n\in\NN}\): \(\displaystyle{ f_1(n) \neq f_2(n).}\) Niech \(\displaystyle{ n\in \NN}\) będzie najmniejszą taką liczba naturalną gdzie funkcję \(\displaystyle{ f_1}\) i \(\displaystyle{ f_2}\) różnią się co do wartości.

Jeśli \(\displaystyle{ n=0}\), wtedy \(\displaystyle{ f _{1} (0) \neq f_2\left( 0\right)}\). Łatwo zauważyć, że wtedy element \(\displaystyle{ f_1\left( 0\right)}\) jest elementem najmniejszym \(\displaystyle{ X}\) względem \(\displaystyle{ \le _{1}}\), i podobnie element \(\displaystyle{ f_2 \left( 0\right) }\) jest elementem najmniejszym \(\displaystyle{ X}\) względem \(\displaystyle{ \le _2}\). Ponieważ porządki \(\displaystyle{ \le _1}\) i \(\displaystyle{ \le _2}\) mają różne elementy najmniejsze, a zatem są różne, czyli \(\displaystyle{ \left( \le _{1} \right) \neq \left( \le _{2} \right).}\)

A jeśli \(\displaystyle{ n>0}\), wtedy \(\displaystyle{ \left( n-1\right)\in\NN}\). Ponieważ \(\displaystyle{ n}\) jest najmniejszym numerem gdzie: \(\displaystyle{ f_1\left( n\right) \neq f_2(n)}\), a więc \(\displaystyle{ f_1\left( n-1\right) = f_2(n-1). }\)

Wtedy element \(\displaystyle{ f_1(n)}\) jest następnikiem elementu \(\displaystyle{ f_1(n-1)}\), i podobnie element \(\displaystyle{ f_2(n)}\) jest następnikiem elementu \(\displaystyle{ f_2\left(n-1 \right)}\). Przypuśćmy nie wprost, że \(\displaystyle{ \left( \le _{1}\right) =\left( \le _{2} \right)}\), oznaczmy ten porządek jako \(\displaystyle{ \le}\) . Oznaczmy \(\displaystyle{ f_1\left( n-1\right)= f_2\left( n-1\right) =: x _{n-1}}\), a zatem ponieważ mamy ten sam porządek i ten sam element \(\displaystyle{ x _{n-1} }\), więc również tylko jeden jego następnik, czyli:

\(\displaystyle{ f_1(n)=\left( f_1\left( n-1\right) \right) ^{+} =x _{n-1} ^{+} = \left( f_2\left( n-1\right) \right) ^{+}= f_2(n)}\),

czyli \(\displaystyle{ f_1(n)= f_2(n)}\)- sprzeczność.

Wobec czego musi być:

\(\displaystyle{ \left( \le _{1} \right) \neq \left( \le _{2} \right)}\),

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

A zatem \(\displaystyle{ \left| \RR\right| =\left| \mathbb{B} _{\NN,X} \right|\le \left| \mathbb{B}\right| }\). A zatem, na mocy twierdzenia Cantora-Bernsteina:

\(\displaystyle{ \left| \mathbb{B}\right| =\left| \RR\right|}\),

czyli istnieje dokładnie continuum dobrych porządków na zbiorze przeliczalnym\(\displaystyle{ .\square}\)


Rozważmy jeszcze dwa zbiory \(\displaystyle{ X}\) i \(\displaystyle{ Y}\), i funkcję \(\displaystyle{ f:X \rightarrow Y}\), i rozważmy dwa podzbiory dziedziny funkcji \(\displaystyle{ A,B\subset X}\). Wykażemy, że obraz różnicy symetrycznej tych dwóch podzbiorów jest nadzbiorem różnicy symetrycznej obrazów tych dwóch zbiorów tzn.:

\(\displaystyle{ \stackrel{ \rightarrow }{f} \left( A\oplus B\right)\supset \stackrel { \rightarrow } {f} \left( A\right) \oplus \stackrel { \rightarrow }{f}(B).}\)

DOWÓD TEGO FAKTU:

Mamy:

\(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A\oplus B\right) =\stackrel{ \rightarrow }{f}\left( \left( A \setminus B\right) \cup \left( B\setminus A \right) \right) =\underbrace{ \stackrel{ \rightarrow }{f} \left( A \setminus B\right) }_{\supset \stackrel { \rightarrow } {f} \left( A\right) \setminus \stackrel { \rightarrow } {f} \left( B\right) } \cup \underbrace{ \stackrel{ \rightarrow }{f} \left( B \setminus A\right) }_{\supset \stackrel { \rightarrow } {f} \left( B\right) \setminus \stackrel { \rightarrow } {f} \left( A\right) } \supset \left( \stackrel { \rightarrow } {f} \left( A\right) \setminus \stackrel { \rightarrow } {f} \left( B\right) \right) \cup \left( \stackrel { \rightarrow } {f} \left( B\right) \setminus \stackrel { \rightarrow } {f} \left( A\right)\right) =\stackrel { \rightarrow } {f} \left( A\right) \oplus \stackrel { \rightarrow }{f}(B).\square }\)

[Jan Kraszewski]

Jest to o tyle zaskakujące, że dobre porządki na zbiorze przeliczalnym mogą być bardzo długie( chyba mogą sięgać, o krok wcześniej, od najmniejszej liczby nieprzeliczalnej,

Nie ma czegoś takiego jak "o krok wcześniej od najmniejszej liczby nieprzeliczalnej" z tej prostej przyczyny, że \(\displaystyle{ \aleph_1}\) jest graniczną liczbą porządkową.

JK

[Jakub Gurak]

Udowodniłem w poniedziałek, po kilku dniach pracy, że istnieje dokładnie continuum rozkładów zbioru liczb rzeczywistych na przedziały. Udowodniłem też, już kilka dni wcześniej, że istnieje (co najmniej) \(\displaystyle{ 2 ^{\left| \RR\right| }}\) wszystkich rozkładów zbioru liczb rzeczywistych, jak też wtedy (chyba nawet w ten sam dzień ) udowodniłem, że w (nieskończonym) zbiorze liniowo uporządkowanym może istnieć istotnie więcej przedziałów początkowych niż elementów tego danego zbioru. Wynika stąd, że istnieje wtedy istotnie więcej wszystkich przedziałów niż elementów danego zbioru. Przedstawię teraz dowody tych ciekawych faktów.


Przypomnijmy może najpierw ogólny, prosty fakt:

Jesli \(\displaystyle{ X}\) jest niepustym zbiorem, a \(\displaystyle{ \left\{ \right\} \neq A \subset X}\) niepustym i róznym od całego zbioru \(\displaystyle{ X}\) podzbiorem zbioru \(\displaystyle{ X}\) , to rodzina dwuzbiorowa \(\displaystyle{ \left\{ A,A'=X \setminus A\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\)- jest to prosty fakt.


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

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

Wykazemy, że: \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{\left| \RR\right| } . }\)

DOWÓD TEGO FAKTU:

Rozwazmy podrodzinę \(\displaystyle{ \mathbb{B}_0}\) rodziny \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B}_0=\left\{ \mathcal{R}\in\mathbb{B}: \left| \mathcal{R}\right|=2 \right\}}\),

złoŻoną z rozkładów na dwa zbiory.

Niech \(\displaystyle{ \mathbb{S}= P(\RR) \setminus \left\{\emptyset ,\RR\right\} \sim 2 ^{\RR}. }\)

(jest to rodzina niepustych i róznych od całego zbioru liczb rzeczywistych rodzina wszystkich takich jego podzbiorów). Podzielmy tą rodzinę \(\displaystyle{ \mathbb{S}}\) na dwie podrodziny, tzn. niech:

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

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

Wtedy \(\displaystyle{ \mathbb{S} =\mathbb{S}_1 \cup \mathbb{S}_2.}\)

Łatwo jest wykazać, że \(\displaystyle{ \mathbb{S}_1\sim \mathbb{S}_2.}\)

W tym celu definiujemy funkcję \(\displaystyle{ g: \mathbb{S}_1 \rightarrow \mathbb{S} _2}\), jako:

\(\displaystyle{ g(A)=A'=\RR \setminus A.}\)

Łatwo jest pokazać, że jest to dobrze określona funkcja, oraz, że jest to funkcja różnowartościowa. Wykażemy teraz, że jest to funkcja 'na'.

DOWÓD TEGO FAKTU::    

Niech \(\displaystyle{ A\in\mathbb{S}_2}\). Wtedy \(\displaystyle{ A\in\mathbb{S}}\) i \(\displaystyle{ 0\not\in A}\). Ponieważ \(\displaystyle{ A\in\mathbb{S}}\), to \(\displaystyle{ A\subset \RR}\) i \(\displaystyle{ A \neq \emptyset, \RR}\). Rozważmy dopełnienie zbioru \(\displaystyle{ A}\): \(\displaystyle{ A'\subset \RR}\), wtedy ponieważ \(\displaystyle{ A}\) jest zbiorem niepustym i różnym od całego zbioru \(\displaystyle{ \RR}\), to jego dopełnienie jest również zbiorem różnym od zbioru liczb rzeczywistych i różnym od zbioru pustego. A zatem \(\displaystyle{ A'\in\mathbb{S}}\) , a ponieważ \(\displaystyle{ 0\not\in A}\), to \(\displaystyle{ 0\in A'.}\) A zatem \(\displaystyle{ A'\in \mathbb{S}_1}\), i wtedy:

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

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

A zatem \(\displaystyle{ \mathbb{S}_1\sim \mathbb{S}_2.}\)

Jesli \(\displaystyle{ A\in\mathbb{S}_1;}\) wtedy \(\displaystyle{ A\subset \RR}\) , \(\displaystyle{ A \neq \left\{ \right\} }\), \(\displaystyle{ A \neq \RR}\) i \(\displaystyle{ 0\in A}\), i wtedy przypisujemy mu zbiór, poprzez funkcję \(\displaystyle{ \alpha}\), w poniższy sposóbr:

\(\displaystyle{ A \in \mathbb{S}_1 \stackrel{ \alpha }{ \rightarrow } \left\{ A, A'\right\} \in \mathbb{B}_0.}\)

Na mocy przytoczonego faktu rodzina dwuzbiolaowa \(\displaystyle{ \left\{ A,A' \right\}}\) jest rozkładem zbioru liczb rzeczywistych, a zatem \(\displaystyle{ \left\{ A,A'\right\} \in \mathbb{B}}\), łatwo jest też udowodnić, ze zbiory \(\displaystyle{ A}\) i \(\displaystyle{ A' }\) są różne. A zatem \(\displaystyle{ \left| \left\{ A,A'\right\} \right|=2}\), i \(\displaystyle{ \left\{ A,.A'\right\} \in \mathbb{B}_0.}\)

I otrzymujemy, że funkcja \(\displaystyle{ \alpha :\mathbb{S}_1 \rightarrow \mathbb{B}_0}\) jest dobrze określona.


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

Niech \(\displaystyle{ A,B\in \mathbb{S}_1.}\) Wtedy \(\displaystyle{ 0\in A}\) i \(\displaystyle{ 0\in B}\), i

Jeśli \(\displaystyle{ \alpha \left( A\right)= \alpha (B)}\), wtedy, z definicji tej funkcji , otrzymujemy: \(\displaystyle{ \left\{ A,A'\right\} =\left\{ B,B'\right\}}\) , a zatem, z zasady równości zbiorów: \(\displaystyle{ A\in \left\{ B,B'\right\}}\) , a zatem \(\displaystyle{ A=B}\) lub \(\displaystyle{ A=B'.}\)

Przypuścmy, że' \(\displaystyle{ A=B'}\) , wtedy poniewaz \(\displaystyle{ 0\in A=B' }\), a więc \(\displaystyle{ 0\not\in B}\)- sprzeczność.

Wobec czego \(\displaystyle{ A \neq B'}\) , a zatem pozoastaje jedynie możliwośc: \(\displaystyle{ A=B}\). A zatem funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

A zatem \(\displaystyle{ \left| \mathbb{S}_1\right| \le \left| \mathbb{B}_0\right|.}\)

Zbiór \(\displaystyle{ \mathbb{S} _1}\) musi być nieskończony, gdyż gdyby był skończony, to również zbiór \(\displaystyle{ \mathbb{S}_2\sim \mathbb{S} _1}\) byłby skończony, i wtedy zbiór \(\displaystyle{ \mathbb{S}=\mathbb{S}_1 \cup \mathbb{S}_2}\), jako suma dwóch zbiorów skończonych, byłby zbiorem skończonym, a ponieważ \(\displaystyle{ \mathbb{S}\sim 2 ^{\RR}}\), to zbiór \(\displaystyle{ 2 ^{\RR}}\) byłby skończony- sprzeczność.

Wobeec czego zbiór \(\displaystyle{ \mathbb{S}_1 }\) musi być nieskończony, i gdyby był mocy silnie mniejszej niż zbiór \(\displaystyle{ 2 ^{\RR}}\), to \(\displaystyle{ \mathbb{S}=\mathbb{S}_1 \cup \mathbb{S}_2 \sim\mathbb{S}_1}\) i mamy: \(\displaystyle{ \left| \mathbb{S} _{1} \right| <\left| 2 ^{ \RR }\right| }\), a więc \(\displaystyle{ \left| \mathbb{S}\right| < \left| 2 ^{\RR}\right| }\) - więc otrzymujemy sprzeczność. Wobec czego \(\displaystyle{ \left|\mathbb{S}_1\right|\not < \left| 2 ^{\RR} \right|. }\)

Ponieważ \(\displaystyle{ \mathbb{S}_1\subset \mathbb{S} }\), to \(\displaystyle{ \left| \mathbb{S}_1\right| \le \left| \mathbb{S}\right|= \left| 2 ^{\RR} \right| .}\) Ale \(\displaystyle{ \left| \mathbb{S}_1\right|\not <\left| 2 ^{\RR} \right| = \left|\mathbb{S}\right|}\), wobec czego zbiór \(\displaystyle{ \mathbb{S}_1}\) musi być równoliczny ze zbiorem \(\displaystyle{ \mathbb{S}}\), ktory to zbiór jest równoliczny ze biortem \(\displaystyle{ 2 ^{\RR}.}\)

A zatem \(\displaystyle{ \mathbb{S}_1\sim 2 ^{\RR} .}\)

A zatem \(\displaystyle{ \left| \mathbb{B}_0\right| \ge \left| \mathbb{S}_1\right| =\left| 2 ^{\RR }\right|}\). Ponieważ \(\displaystyle{ \mathbb{B}\supset \mathbb{B}_ 0}\), to \(\displaystyle{ \left| \mathbb{B}\right| \ge \left| \mathbb{B}_0\right| \ge \left| 2 ^{\RR} \right|}\) , a więc \(\displaystyle{ \left| \mathbb{B}\right| \ge 2 ^{\left| \RR\right|} .\square}\)


Przejdźmy do głównego naszego problemu.

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

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

chodzi o rozkład na przedzialy, tzn. tak, że każdy zbiór \(\displaystyle{ A\in \mathcal{R}}\) jest przedziałem w \(\displaystyle{ \RR }\).

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

Przypomnę może taki trochę grubszy fakt z teorii mocy ( choć dla mistrzów teorii mocy, to pewnie jest to pryszcz), że zbiór \(\displaystyle{ \RR ^{\NN}}\) jest zbiorem mocy continuum, czyli zbiór wszystkich ciągów liczb rzeczywistych jest mocy continuum (dowód tego faktu, o ile dobrze pamiętam, znajduję się w Guzickim "Wstępie do matematyki").

Przejdźmy do naszego problemu:

DOWÓD NASZEGO FAKTU:

Niech \(\displaystyle{ \mathcal{R}\in \mathbb{B}}\). Wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ \RR}\) na przedziały. Podzielmy rozkład \(\displaystyle{ \mathcal{R}}\) na dwie podrodziny \(\displaystyle{ \mathcal{R}_-}\) i \(\displaystyle{ \mathcal{R}_+}\), dane jako:

\(\displaystyle{ \mathcal{R}_-=\left\{ A\in \mathcal{R}: \ \ A=\left\{ a\right\}, \hbox{ dla pewnej liczby rzeczywistej } a\in\RR\right\} }\), i

\(\displaystyle{ \mathcal{R} _{+}= \left\{ A\in\mathcal{R}: \ \hbox{ zbiór } A \hbox{ jest co najmniej dwuelementowy }\right\} .}\)

Jeśli \(\displaystyle{ A \in \mathcal{R},}\) ponieważ jest to rozkład, to zbiór \(\displaystyle{ A}\) musi być niepusty, a więc ma co najmniej jeden element, skąd \(\displaystyle{ \mathcal{R} _- \cup \mathcal{R}_+=\mathcal{R}.}\)

Wykazemy, że jesli \(\displaystyle{ \mathcal{R}\in\mathbb{B}}\), to zbiór \(\displaystyle{ \mathcal{R}_+}\) jest co najwyżej przeliczalny.

DOWÓD TEGO FAKTU::    

Jesli \(\displaystyle{ A\in \mathcal{R}_+}\), wtedy \(\displaystyle{ A\in \mathcal{R}}\) i zbiór \(\displaystyle{ A}\) jest przedziałem i \(\displaystyle{ \left| A\right| \ge 2}\). A zatem istnieją dwa różne elementy \(\displaystyle{ a,b\in A}\). Ponieważ \(\displaystyle{ A\subset \RR}\), więc \(\displaystyle{ a<b}\) lub \(\displaystyle{ b<a.}\)

Jeśli \(\displaystyle{ a<b}\), wtedy istnieje liczba wymierna \(\displaystyle{ c\in\QQ}\), taka, że: \(\displaystyle{ a<c<b}\). Wtedy \(\displaystyle{ A\ni a<c<b\in A}\), a zbiór \(\displaystyle{ A}\) jest przedzaiłem, wiec wnioskujemy, że \(\displaystyle{ c\in A}\), i \(\displaystyle{ c\in A \cap \QQ}\), i przypisujemy zbiorowi \(\displaystyle{ A \rightarrow c\in A \cap \QQ}\) (stosując, być moze, aksjomat wyboru)).

Jeśli \(\displaystyle{ b<a}\), to podobnie , wtedy istnieje liczba wymierna \(\displaystyle{ c\in\QQ}\), taka, że: \(\displaystyle{ b<c<a.}\) Wtedy \(\displaystyle{ A\ni b<c<a\in A}\), a zbiór \(\displaystyle{ A}\) jest przedziałem, więc wnioskujemy, że \(\displaystyle{ c\in A}\) , i \(\displaystyle{ c\in A \cap \QQ}\), i zbiorowi \(\displaystyle{ A}\) przypisujemy element \(\displaystyle{ c\in A \cap \QQ}\).

I stosując twierdzenie o funkcji wyboru otrzymujemy funkcję

\(\displaystyle{ f:\mathcal{R} _+ \rightarrow \QQ.}\)

przypisującą zbiorom rodziny \(\displaystyle{ \mathcal{R}_+}\) po jednym elemencie.

Wykazemy, że funkcja \(\displaystyle{ f}\) jest róznowartościowa.

W tym celu weźmy dwa zbiory \(\displaystyle{ A,B\in \mathcal{R}_+}\)- dwa zbiory różne- i przypuścmy nie wprost, ze \(\displaystyle{ f(A)= f(B).}\) Wtedy \(\displaystyle{ f(A)\in A}\), i \(\displaystyle{ f(B)\in B}\), a zatem \(\displaystyle{ fA)=f(B) \in A \cap B}\), a zbiory \(\displaystyle{ A,B\in \mathcal{R}}\), gdzie \(\displaystyle{ \mathcal{R}}\) jest rozkładem, i zbiory \(\displaystyle{ A,B}\) tego rozkładu poniewaz są różne, to powinny być rozłączne, a tu nie są rozłączne- sprzeczność.

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

A zatem: \(\displaystyle{ \left| \mathcal{R}_+\right| \le \left| \QQ\right| =\left| \NN\right|}\), czyli zbikór \(\displaystyle{ \mathcal{R}_+}\) jest co najwyzej przeliczalny\(\displaystyle{ .\square}\)

Nim przejdziemy dalej, przypomnijmy pewien fakt nie podając jego dowodu( móglbym poszukać dowód gdzieś w swoich postach i podać link, ale można tylko dwa odnośniki dać, a to byłby trzeci, ale nie jest to bardzo trudny fakt, który kiedyś udowodniłem) , że jeśli mamy rodzinę zbiorów rozłącznych \(\displaystyle{ \mathbb{A}}\), oraz dwie podrodziny zbiorów \(\displaystyle{ \mathbb{A}_1, \mathbb{A}_2\subset \mathbb{A}}\) , to suma uogólniona różnicy takich dwóch podrodzin jest różnicą sum uogólnionych: \(\displaystyle{ \bigcup\left( \mathbb{A} _{1} \setminus \mathbb{A} _2\right) = \left( \bigcup \mathbb{A} _{1}\right) \setminus \left( \bigcup \mathbb{A} _{2} \right). }\)

Ale to zachodzi, dla rodziny \(\displaystyle{ \mathbb{A}}\) zbiorów rozłącznych. Wtedy również zachodzi podobny fakt dla sumy uogólnionej przekroju tych dwóch podrodzin.

Wynika stąd, tzn. z tego faktu z różnicą, wtedy łatwo wynika stąd , że dla rodziny zbiorów rozłącznych \(\displaystyle{ \mathbb{A}}\), oraz dla podrodziny \(\displaystyle{ \mathbb{D}\subset \mathbb{A}}\), wtedy suma uogólniona dopełnienia tej podrodziny jest dopełnieniem sumy uogólnionej, tzn.: \(\displaystyle{ \bigcup \left( \mathbb{D}':= \mathbb{A} \setminus \mathbb{D}\right) = \left( \bigcup \mathbb{D}\right) '= \left( \bigcup\mathbb{A}\right) \setminus \left( \bigcup\mathbb{D}\right) }\),

wynika to od razu z tego faktu z różnicą , wystarczy tylko zauważyć, że spełnione są założenia tego faktu, poprzez \(\displaystyle{ \mathbb{A}\subset \mathbb{A}}\), \(\displaystyle{ \mathbb{D}\subset \mathbb{A}}\), i zastosować wzór dla różnicy sum uogólnionych. Ten fakt, dla dopełnienia, nam się przyda.

Wracając do naszego problemu:

Ponieważ \(\displaystyle{ \mathcal{R}_+\subset \mathcal{R}}\), a \(\displaystyle{ \mathcal{R},}\) jako rozkład, jest rodziną zbiorów rozłącznych, to na mocy faktu wspomnianego powyżej dla dopełnienia \(\displaystyle{ \mathcal{R} _{+} ^{'} = \mathcal{R} \setminus \mathcal{R}_+ =\mathcal{R}_-}\), wtedy suma uogólniona takiego dopełnienia jest dopełnieniem sumy uogólnionej, tzn.:

\(\displaystyle{ \bigcup\mathcal{R}_{+}^{'}= \left( \bigcup\mathcal{R}\right) \setminus \left( \bigcup\mathcal{R}_+\right) =}\),

i ponieważ jest to rozkład zbioru liczb rzeczywistych, a zatem \(\displaystyle{ \bigcup\mathcal{R}=\RR}\), a zatem to jest równe:

\(\displaystyle{ = \RR \setminus \bigcup\mathcal{R}_+.}\)

A zatem poniewaz \(\displaystyle{ \mathcal{R}_{-}= \mathcal {R}_{+} ^{'} }\), więc również mamy równość:

\(\displaystyle{ \bigcup\mathcal{R}_{-}= \bigcup\mathcal {R} _{+} ^{'} = \RR \setminus \bigcup\mathcal{R}_{+}.}\)

czyli :

\(\displaystyle{ \bigcup\mathcal{R}_-= \RR \setminus \bigcup\mathcal{R} _+= \left( \bigcup \mathcal{R}_+\right)'.
}\)


Niech \(\displaystyle{ \mathbb{A}}\) będzie rodziną wszystkich przedziałów w \(\displaystyle{ \RR}\). Taka rodzina ma moc continuum, gdyż wynika to z twierdzenia, które udowodniłem ostatnio: TUTAJ, W OSTATNIM POŚCIE .

Niech \(\displaystyle{ \left[ \mathbb{A}\right] ^{\NN}}\) będzie rodziną wszystkich co najwyżej przeliczalnych podzbiorów zbioru \(\displaystyle{ \mathbb{A}.}\)

Rozważmy funkcję \(\displaystyle{ \alpha}\) działającą w następujący sposób:

\(\displaystyle{ \mathcal{R} \in \mathbb{B} \stackrel{ \alpha }{\rightarrow }\mathcal{R}_+.}\)

Wtedy rodzina \(\displaystyle{ \mathcal{R}_+}\) jest rodziną przedziałów , i wiemy już, że jest to zbiór co najwyżej przeliczalny, a zatem \(\displaystyle{ \left( \mathcal{R}_+\right) \in \left[ \mathbb{A}\right] ^{\NN}}\), i otrzymujemy, że funkcja \(\displaystyle{ \alpha : \mathbb{B} \rightarrow \left[ \mathbb{A}\right] ^{\NN} }\) jest dobrze określona.

Wykażemy, że jest to funkcja różnowartościowa.

Podajmy najpierw pewien lemat.

Jeśli \(\displaystyle{ \mathcal{R}\in\mathbb{B}}\), to oznaczmy:

\(\displaystyle{ X _{\mathcal{R}}= \bigcup\mathcal{R}_+}\), i dalej
\(\displaystyle{ \overline {X} _{\mathcal{R} }= \RR \setminus X _{\mathcal{R}} .}\)

I wykażemy, że:

LEMAT. \(\displaystyle{ \mathcal{R}_-=\left\{ \left\{ a\right\}\Bigl| \ \ a\in \overline{X} _{\mathcal{R} } \right\} .}\)

DOWÓD TEGO FAKTU::    

Jesli mamy zbiór z rodziny zbiorów po prawej stronie równości, tzn. zbior postaci \(\displaystyle{ \left\{ a\right\}}\), gdzie \(\displaystyle{ a\in \overline {X} _{\mathcal{R} }}\), wtedy \(\displaystyle{ a\in\RR}\) i \(\displaystyle{ a\not\in X _{\mathcal{R}} .}\) Wtedy \(\displaystyle{ a\in\RR= \bigcup\mathcal{R}}\). Więc \(\displaystyle{ a\in A}\), gdzie zbiór \(\displaystyle{ A\in \mathcal{R}. }\)

Pokażemy, że zbiór \(\displaystyle{ A}\) jest jednoelementowy. Mamy \(\displaystyle{ a\in A.}\)

Przypuśćmy nie wprost, że istnieje element \(\displaystyle{ b\in A}\) różny od \(\displaystyle{ a}\). Wtedy ponieważ \(\displaystyle{ A\in \mathcal{R}}\) i \(\displaystyle{ \left| A\right| \ge 2}\), to \(\displaystyle{ A\in \mathcal{R}_+}\), a ponieważ \(\displaystyle{ a\in A}\), to \(\displaystyle{ a\in \bigcup\mathcal{R}_+= X _{\mathcal{R}} -}\) sprzeczność.

Wobec czego \(\displaystyle{ \left\{ a\right\} =A\in \mathcal{R}}\), a więc \(\displaystyle{ \left\{ a\right\} \in \mathcal{R}_-.}\)

Aby pokazać inkluzję w drugą stronę, to jeśli \(\displaystyle{ A\in \mathcal{R}_-}\), to \(\displaystyle{ A\in \mathcal{R}}\) i \(\displaystyle{ A=\left\{ a\right\} }\), gdzie \(\displaystyle{ a\in\RR}\). Ponieważ zbiór \(\displaystyle{ A}\) ma tylko jeden element, to \(\displaystyle{ A\not\in \mathcal{R}_+.}\) Wtedy \(\displaystyle{ a\not\in \bigcup\mathcal{R}_+.}\)

Gdyby bowiem byłoby \(\displaystyle{ a\in \bigcup\mathcal{R}_+}\), to \(\displaystyle{ a\in B}\), gdzie zbiór \(\displaystyle{ B\in\mathcal{R}_+}\); wtedy \(\displaystyle{ B\in \mathcal{R}}\) i \(\displaystyle{ \left| B\right| \ge 2}\). Ponieważ \(\displaystyle{ a\in A\in\mathcal{R},}\) oraz \(\displaystyle{ a\in B\in\mathcal{R}}\), to \(\displaystyle{ a\in A \cap B}\), a \(\displaystyle{ \mathcal{R}}\) jest rozkładem, więc z warunku rozłączności zbiorów otrzymujemy, że \(\displaystyle{ A=B}\). Ponieważ \(\displaystyle{ A\not\in \mathcal{R}_+}\), to \(\displaystyle{ B\not\in\mathcal{R}_+}\)- sprzeczność.

Wobec czego \(\displaystyle{ a\not\in \bigcup\mathcal{R}_+= X_{\mathcal{R} }}\), a więc \(\displaystyle{ a\in \overline {X} _{\mathcal{R} } }\), a zatem \(\displaystyle{ A=\left\{ a\right\} \in \left\{ \left\{ b\right\}\Bigl| \ \ b\in \overline {X} _{\mathcal{R} }\right\} .}\)

A zatem:

\(\displaystyle{ \mathcal{R}_-=\left\{ \left\{ a\right\}\Bigl| \ \ a\in \overline {X} _{\mathcal{R} }\right\}.\square}\)

Jeśli \(\displaystyle{ \alpha \left( \mathcal{R}\right) = \alpha \left( \mathcal{S}\right) }\), wtedy to oznacza, że:

\(\displaystyle{ \mathcal{R}_+= \mathcal{S}_+}\), a zatem również zachodzi równość: \(\displaystyle{ \bigcup\mathcal{R}_+= \bigcup\mathcal{S}_+.}\)

Na mocy lematu powyżej:

\(\displaystyle{ \mathcal{R}_-=\left\{ \left\{ a\right\} \Bigl| \ \ a\in \overline {X} _{\mathcal{R} }\right\} }\), oraz

\(\displaystyle{ \mathcal{S}_-=\left\{ \left\{ a\right\} \Bigl| \ \ a\in\overline {X} _{\mathcal{S} } \right\}.}\)

Ponieważ \(\displaystyle{ \bigcup\mathcal{R}_+ = \bigcup\mathcal{S}_+}\), więc to oznacza, z definicji zbiorów \(\displaystyle{ X_\mathcal{R}}\), \(\displaystyle{ X_\mathcal{S}}\), że \(\displaystyle{ X_\mathcal{R} =X_\mathcal{S}}\), a zatem również:

\(\displaystyle{ \overline {X} _{\mathcal{R} }=\left( X_\mathcal{R}\right) '= \left( X_\mathcal{S}\right) '=\overline {X} _{\mathcal{S} }.}\)

Oznaczmy ten zbiór jako \(\displaystyle{ X.}\)

Wtedy :

\(\displaystyle{ \mathcal{R}_-=\left\{ \left\{ a\right\}\Bigl| \ \ a\in \overline {X} _{\mathcal{R} } \right\} = \left\{ \left\{ a\right\}\Bigl| \ \ a\in X\right\} = \left\{ \left\{ a\right\}\Bigl| \ \ \ a\in \overline {X} _{\mathcal{S} }\right\} = \mathcal{S}_-.}\)

Czyli \(\displaystyle{ \mathcal{R}_-=\mathcal{S}_-.}\)

A zatem:

\(\displaystyle{ \mathcal{R}=\mathcal{R}_- \cup \mathcal{R}_+ = \mathcal{S}_- \cup\mathcal{S}_+=\mathcal{S}.}\)

Czyli \(\displaystyle{ \mathcal{R}=\mathcal{S}, }\) i funkcja \(\displaystyle{ \alpha}\) jest różnowartościowa.

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


Wykażemy teraz pewien lemat.

Lemat 2. Jeśli zbiór \(\displaystyle{ X}\) jest zbiorem mocy continuum, a \(\displaystyle{ \left[ X\right] ^{\NN}}\) jest rodziną wszystkich co najwyżej przeliczalnych i niepustych podzbiorów zbioru \(\displaystyle{ X}\), to:

\(\displaystyle{ \left| \left[ X\right] ^{\NN} \right| \le \left| X ^{\NN}\right| ,}\)

czyli, wszystkich takich podzbiorów, jest co najwyżej tyle, ile ciągów elementów zbioru \(\displaystyle{ X}\).

DOWÓD TEGO FAKTU::    

Definiujemy funkcję:

\(\displaystyle{ \alpha : f\in X ^{\NN} \rightarrow f_P,}\)

która ciągowi elementów zbioru \(\displaystyle{ X,}\) przypisuję zbiór jego wartości.

Wtedy ten zbiór wartości \(\displaystyle{ f_P}\) jest niepustym podzbiorem zbioru \(\displaystyle{ X.}\)

Ponieważ wtedy \(\displaystyle{ f:\NN \rightarrow X}\), to \(\displaystyle{ f_P= \stackrel{ \rightarrow }{f} \left( \NN\right)}\) ma moc nie większą od dziedziny \(\displaystyle{ \NN}\), czyli zbiór \(\displaystyle{ f_P}\) jest co najwyżej przeliczalny. A zatem \(\displaystyle{ f_P\in \left[ X\right] ^{\NN}}\), i funkcja

\(\displaystyle{ \alpha : X ^{\NN} \rightarrow \left[ X\right] ^{\NN}}\),

jest dobrze określona.

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

DOWÓD TEGO FAKTU::    

Niech \(\displaystyle{ A\in \left[ X\right] ^{\NN} .}\) Wtedy \(\displaystyle{ A \neq \left\{ \right\}}\), \(\displaystyle{ A\subset X}\) i \(\displaystyle{ \left| A\right| \le \left| \NN\right|.}\) Ponieważ zbiór \(\displaystyle{ A}\) jest zbiorem co najwyzej przeliczalnym, to jest równoliczny z pewnym podzbiorem \(\displaystyle{ M}\) zbioru liczb naturalnych \(\displaystyle{ M}\), gdzie \(\displaystyle{ M\subset \NN}\). Zatem istnieje bijekcja \(\displaystyle{ g:M \rightarrow A}\). Ponieważ zbiór \(\displaystyle{ A}\) jest niepusty, to zbiór \(\displaystyle{ M}\) również jest niepusty.

Jesli zbiór \(\displaystyle{ M}\) jest skończony, tzn. \(\displaystyle{ M\sim n}\), dla pewnej liczby naturalnej von Neumanna \(\displaystyle{ n}\); wtedy \(\displaystyle{ n \neq 0}\), bo zbiór \(\displaystyle{ M}\) jest niepusty. Niech \(\displaystyle{ h:n \rightarrow M}\) będzie bijekcją. Ustalmy element \(\displaystyle{ a\in A \neq \left\{ \right\}.}\) Wtedy \(\displaystyle{ g\circ h:n \rightarrow A}\) jako złozenie bijekcji jest bijekcją.

Określmy funkcję \(\displaystyle{ f:\NN \rightarrow X}\), jako:

\(\displaystyle{ f(m)= \begin{cases} \left( g\circ h\right) \left( m\right) , \hbox{ dla } m<n,\\ a, \hbox{ dla } m \ge n.\end{cases} }\)

Wtedy \(\displaystyle{ f\in X ^{\NN} }\), i wtedy

\(\displaystyle{ \alpha \left( f\right)=f_P= \left\{ f_0, f_1, f_2,\ldots\right\} = \left\{ \left( g\circ h\right)\left( 0\right) ,\left( g\circ h\right)\left( 1\right) ;\ldots; \left( g\circ h\right)\left( n-1\right) ; a \right\} =\left( g\circ h\right)_{P} \cup \left\{ a\right\} = A \cup \left\{ a\right\}\stackrel {a\in A}{=}A , }\)

czyli \(\displaystyle{ \alpha (f)=A}\), a więc zbiór \(\displaystyle{ A}\) jest wartością funkcji \(\displaystyle{ \alpha . }\)

Jesli zbiór \(\displaystyle{ M}\) jest nieskończony, ale \(\displaystyle{ M\subset \NN}\), wobec czego pewien fakt teorii mocy gwarantuje, że zbiór \(\displaystyle{ M}\) jest równolicxny z \(\displaystyle{ \NN}\). Zatem istnieje bijekcja \(\displaystyle{ g:\NN \rightarrow M}\). Poniewaz \(\displaystyle{ A\sim M}\), więc istnieje bijekcja \(\displaystyle{ h:M \rightarrow A}\), wtedy \(\displaystyle{ f=h\circ g :\NN \rightarrow A}\) jako złozenie bijekcji jest bijekcją, i wtedy funkcja \(\displaystyle{ f:\NN \rightarrow X }\), wtedy \(\displaystyle{ f\in X ^{\NN}}\), i wtedy:

\(\displaystyle{ \alpha \left( f\right) =f_P= \stackrel{ \rightarrow }{f} (\NN)= A }\),

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

A zatem \(\displaystyle{ \left| X ^{\NN } \right| \ge \left| \left[ X\right] ^{\NN } \right|.\square }\)

Mamy:

\(\displaystyle{ \left| \mathbb{B}\right| \le \left| \left[ \mathbb{A}\right] ^{\NN} \right|\stackrel{ \mathbb{A}\sim \RR} {=} \left| \left[ \mathbb{A}\right] ^{\NN} \setminus \left\{ \emptyset\right\} \right| \le \left| \mathbb{A}^{\NN} \right| \stackrel{\mathbb{A} \sim \RR}{=} \left| \RR^{\NN} \right|=\left| \RR\right|,}\)

a zatem:

\(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|.}\)


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

Nim to zrobimy, przypomnijmy ogólny fakt, że jeśli w zbiorze liniowo uporządkowanym \(\displaystyle{ \left( X, \le\right) }\) mamy niepusty przedział \(\displaystyle{ A}\), to (przy pewnych jeszcze drobnych założeniach, jest ich sporo, ale nie są one silne, tu podaje uproszczoną wersję tego twierdzenia, zaraz podam link do dokładnej jej wersji), to rodzina trzyzbiorowa złożona ze zbioru lewostronnego przedziału \(\displaystyle{ A}\), czyli zbioru jego wszystkich ograniczeń dolnych, tego przedziału \(\displaystyle{ A}\) i jego zbioru prawostronnego, czyli zbioru jego ograniczeń górnych, taka rodzina trzyzbiorowa tworzy rozkład zbioru \(\displaystyle{ X}\) na przedziały, co udowodniłem TUTAJ, proszę popatrzeć na poprawkę w ostatnim poście, tam zostało to dopowiedziane co brakuje.

Wróćmy do naszego zadania.

Wykażemy, że rodzina \(\displaystyle{ \mathbb{B}}\) ma moc co najmniej taką, jak odcinek domknięty \(\displaystyle{ \left[ 1,2\right]}\) .

Dla dowolnej liczby rzeczywistej \(\displaystyle{ x \in \left[ 1,2\right],}\) definiujemy zbiór \(\displaystyle{ A_X,}\) jako odcinek otwarty:

\(\displaystyle{ A_x=\left( 0,x\right) .}\)

Ponieważ \(\displaystyle{ \left( \RR, \le \right) }\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ \frac{1}{2}\in A_x,}\) a więc jest to niepusty przedział, nie będący przedziałem początkowym (\(\displaystyle{ -1\not\in A_x}\)), ani resztą, bez elementu najmniejszego ani największego, to zgodnie z przytoczonym faktem, rodzina trzyzbiorowa:

\(\displaystyle{ \mathcal{R}_x= \left\{ A_{x} ^{-}, A_x, A _{x} ^{+} \right\}}\),

tworzy rozkład zbioru \(\displaystyle{ \RR}\) na przedziały.

A zatem \(\displaystyle{ \mathcal{R}_X\in \mathbb{B}}\),

i funkcja \(\displaystyle{ \alpha,}\) działającą w poniższy sposób:

\(\displaystyle{ x\in \left[ 1,2\right] \stackrel{ \alpha } { \rightarrow } \mathcal{R}_x\in \mathbb{B},}\) jest dobrze określona.

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

W tym celu weźmy dwie dowolne różne liczby rzeczywiste \(\displaystyle{ x_1, x_2 \in \left[ 1,2\right]}\). Wtedy \(\displaystyle{ x_1<x_2}\) lub \(\displaystyle{ x_2<x_1.}\)

Jeśli \(\displaystyle{ x_1<x_2}\), to \(\displaystyle{ x_1\in \left( 0, x_2\right) = A _{x_2}}\), a \(\displaystyle{ x_1\not\in \left( 0,x_1\right) =A _{x_1}}\), a więc \(\displaystyle{ A _{x_2} \neq A _{x_1}.}\)

Wtedy \(\displaystyle{ \left( \RR_- \cup \left\{ 0\right\} \cup A _{x_1} \right) \neq \left( \RR_- \cup \left\{ 0\right\} \cup A _{x_2} \right) }\), a więc dla dopełnień tych zbiorów mamy:

\(\displaystyle{ A _{x_1} ^{+}= \left( \RR_- \cup \left\{ 0\right\} \cup A _{x_1} \right) ' \neq \left( \RR_- \cup \left\{ 0\right\} \cup A _{x_2} \right)'= A _{x_2} ^{+}.}\)

czyli: \(\displaystyle{ A _{x_1} ^{+} \neq A _{x_2} ^{+} .}\)

Ponieważ:

\(\displaystyle{ \mathcal{R} _{x_1}=\left\{ \RR_- \cup \left\{ 0\right\} , A _{x_1} , A _{x_1} ^{+} \right\}}\), oraz

\(\displaystyle{ \mathcal{R} _{x_2}=\left\{ \RR_- \cup \left\{ 0\right\} , A _{x_2} , A _{x_2} ^{+} \right\}}\),

A ponieważ \(\displaystyle{ \frac{1}{2} \in A _{x_1} }\), a \(\displaystyle{ \frac{1}{2}\not\in A _{x_2} ^{+}}\) , a zatem \(\displaystyle{ A_{x_1} \neq A _{x_2} ^{+}. }\)

A zatem \(\displaystyle{ A _{x_1} \not\in \mathcal{R} _{x_2}}\), a oczywiście \(\displaystyle{ A _{x_1} \in \mathcal{R} _{x_1}}\) , wobec czego \(\displaystyle{ \mathcal{R} _{x_1} \neq \mathcal{R} _{x_2} . }\)

Jeśli \(\displaystyle{ x_2<x_1}\) to w sposób symetryczny uzasadniamy, że \(\displaystyle{ \mathcal{R} _{x_1} \neq \mathcal{R} _{x_2} .}\)

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

Wobec czego \(\displaystyle{ \left| \RR\right| =\left| \left[ 1,2\right] \right| \le \left| \mathbb{B}\right|}\). Mamy \(\displaystyle{ \left| \mathbb{B}\right| \le \left| \RR\right|}\) , a zatem, na mocy twierdzenia Cantora -Bernsteina: \(\displaystyle{ \left| \mathbb{B}\right|=\left| \RR\right|}\), czyli istnieje dokładnie continuum rozkładów zbioru \(\displaystyle{ \RR}\) na przedziały\(\displaystyle{ .\square}\)


Uzasadnijmy jeszcze, że w nieskończonym zbiorze liniowo uporządkowanym może istnieć istotnie więcej przedziałów początkowych niż elementów tego danego zbioru.

Wystarczy rozważyć zbiór liczb wymiernych z naturalnym porządkiem \(\displaystyle{ \left( \QQ, \le\right)}\) , i dla dowolnej ustalonej liczby niewymiernej \(\displaystyle{ x,}\) rozważmy zbiór \(\displaystyle{ B_x}\)- zbiór wszystkich liczb wymiernych mniejszej od niej, tzn.:

\(\displaystyle{ B_x=\left\{ y\in\QQ: \ y<x \right\} \subset \QQ.}\)

Musimy udowodnić, że jest to przedział początkowy w \(\displaystyle{ \QQ}\). Niewątpliwie zbiór:

\(\displaystyle{ O(x)= \left\{ y\in\RR: y<x\right\} }\),

jest przedziałem początkowym w \(\displaystyle{ \RR}\), bo zbiory w takiej postaci są zawsze przedziałami początkowymi. Ponieważ, jak mamy zbiór liniowo uporządkowany, oraz podzbiór liniowo uporządkowany, oraz przedział początkowy w nadzbiorze, to zawężenie przedziału początkowego do podzbioru liniowo uporządkowanego jest przedziałem początkowym w tym podzbiorze- jest to prosty fakt, a więc zbiór:

\(\displaystyle{ B_x=O(x) \cap \QQ,}\)

jest przedziałem początkowym w \(\displaystyle{ \QQ}\). A zatem:

\(\displaystyle{ B_x\in \mathbb{B}:=\left\{ A\subset \QQ: \ \ A \hbox{ jest przedziałem początkowym }\right\},}\)

i funkcja \(\displaystyle{ \alpha : \RR \setminus \QQ \rightarrow \mathbb{B},}\) jest dobrze określona.

Wykażemy, że jest to funkcja różnowartościowa.

W tym celu weźmy dwie różne liczby niewymierne \(\displaystyle{ x_1,x_2\in\RR \setminus \QQ}\). Wtedy \(\displaystyle{ x_1<x_2}\) lub \(\displaystyle{ x_2<x_1}\).

Jeśli \(\displaystyle{ x_1<x_2}\), wtedy istnieje liczba wymierna \(\displaystyle{ x\in\ \QQ,}\) leżąca pomiędzy tymi dwoma liczbami, tzn. taka, ze:

\(\displaystyle{ x_1<x<x_2 .}\)

Wtedy \(\displaystyle{ x\in B _{x_2}}\), a \(\displaystyle{ x\not\in B _{x_1}}\), bo \(\displaystyle{ x\not<x_1}\), a zatem \(\displaystyle{ B _{x_2} \neq B _{x_1}.}\)

Jeśli \(\displaystyle{ x_2<x_1,}\) to w sposób symetryczny udowadniamy, że \(\displaystyle{ B _{x_1} \neq B _{x_2}. }\)

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

A zatem \(\displaystyle{ \left| \mathbb{B}\right| \ge \left|\RR \setminus \QQ \right| = \left| \RR\right| > \left| \QQ \right|}\) , czyli

\(\displaystyle{ \left| \mathbb{B}\right| >\left| \QQ\right|}\), czyli w zbiorze \(\displaystyle{ \QQ}\) istnieje istotnie więcej przedziałów początkowych niż elementów zbioru \(\displaystyle{ \QQ}\), gdzie \(\displaystyle{ \left( \QQ, \le\right) }\) jest zbiorem liniowo uporządkowanym, nieskończonym\(\displaystyle{ .\square}\)


Również wtedy, tzn. w zbiorze \(\displaystyle{ \left( \QQ, \le\right), }\) istnieje istotnie więcej wszystkich przedziałów niż elementów zbioru \(\displaystyle{ \QQ}\), tzn. rozważmy rodzinę przedziałów \(\displaystyle{ \mathbb{A}}\), daną jako:

\(\displaystyle{ \mathbb{A} =\left\{ A\subset \QQ\Bigl| \ \ A \hbox{ jest przedziałem} \right\}.}\)

Wykażemy, że \(\displaystyle{ \left| \mathbb{A}\right| >\left| \QQ\right| .}\)

DOŚĆ OCZYWISTY DOWÓD:

Jeśli \(\displaystyle{ \mathbb{B}}\) jest rodzina wszystkich przedziałów początkowych w \(\displaystyle{ \QQ,}\) którą rozważaliśmy przed chwilą, i ona jest liczniejsza od zbioru \(\displaystyle{ \QQ}\), więc ponieważ \(\displaystyle{ \mathbb{A}\supset \mathbb{B} }\) (każdy przedzial początkowy jest przedziałem), a zatem \(\displaystyle{ \left| \mathbb{A}\right| \ge \left| \mathbb{B}\right|>\left| \QQ\right|}\), a zatem \(\displaystyle{ \left| A\right|>\left| \QQ\right|}\) , czyli w zbiorze \(\displaystyle{ \QQ}\) istnieje istotnie więcej przedziałów niż elementów zbioru \(\displaystyle{ \QQ}\), gdzie \(\displaystyle{ (\QQ , \le )}\) jest zbiorem liniowo uporządkowanym, nieskończonym \(\displaystyle{ . \square}\)


Na koniec wykażemy, że jeśli mamy zbiór \(\displaystyle{ X,}\) oraz relację antysymetryczną \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), to relacja \(\displaystyle{ R \setminus I_X}\) jest relacją silnie antysymetryczną.

DOWÓD TEGO FAKTU::    

Musimy pokazać, że jeśli para \(\displaystyle{ \left( x,y\right)\in R \setminus I_X,}\) to para \(\displaystyle{ \left( y,x\right) \not\in R \setminus I_X}\).

Przypuśćmy nie wprost, że obie pary należą do relacji \(\displaystyle{ R \setminus I_X}\). Wtedy \(\displaystyle{ \left( x,y\right) \in R}\), \(\displaystyle{ \left( x,y\right)\not\in I_X}\), oraz \(\displaystyle{ \left( y,x\right) \in R}\) i \(\displaystyle{ \left( y,x\right) \not\in I_X.}\)

Ponieważ \(\displaystyle{ (x,y)\in R}\) i \(\displaystyle{ \left( y,x\right)\in R}\), a relacja \(\displaystyle{ R}\) jest antysymetryczna, a więc \(\displaystyle{ x=y}\). Ponieważ \(\displaystyle{ \left( x,y\right) \not\in I_X}\), to \(\displaystyle{ \left( x,x\right)\not\in I_X}\), a mamy \(\displaystyle{ x\in X}\), więc powinno być, zgodnie z definicją relacji identyczności, więc powinno być : \(\displaystyle{ \left( x,x\right) \in I_X}\), więc otrzymujemy sprzeczność.

Wobec czego relacja \(\displaystyle{ R \setminus I_X}\) jest relacją silnie antysymetryczną \(\displaystyle{ .\square }\)

[Jakub Gurak]

Udalo się przedwczoraj zliczyć, z pomocą użytkownika Janusza Tracza, funkcje słabo rosnące (i funkcje słabo malejące, gdyż jest ich tyle samo, udowodnilem to przedwczoraj sobie na dobranoc) pomiędzy dwoma skończonymi podzbiorami zbioru liczb rzeczywistych.

Tzn. udowodnilem, że jesli mamy dwa zbiory \(\displaystyle{ X,Y\subset \RR}\), dwa zbiory skończone i drugi zbiór \(\displaystyle{ Y}\) jest niepusty, \(\displaystyle{ m}\)-elementowy, a pierwszy zbiór \(\displaystyle{ X}\) jest \(\displaystyle{ n}\)-elementowy, to ilość funkcji \(\displaystyle{ f:X \rightarrow Y}\), funkcji słabo rosnących jest równa: \(\displaystyle{ {n+m-1 \choose m-1}}\), dla \(\displaystyle{ m \neq 0}\); i tyle samo jest funkcji słabo malejących pomiędzy tymi zbiorami skończonymi. Przedstawię teraz dowody tych ciekawych faktów.


Niech \(\displaystyle{ X,Y \subset \RR}\) będą dwoma zbiorami skończonymi, takimi, że drugi zbiór \(\displaystyle{ Y}\) jest niepusty. Rozwazmy rodzinę funkcji \(\displaystyle{ \mathbb{B}}\), daną jako:

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

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

Podajmy najpierw pewien, związany z tym faktem, pewien lemat.


LEMAT. Jeśli \(\displaystyle{ f \in \mathbb{B}}\), wtedy \(\displaystyle{ f:X \rightarrow Y,}\) i funkcja \(\displaystyle{ f}\) jest słabo rosdnąca, i wykazemy, że rodzina wszystkich przeciwobrazów jednoelementowych podzbiorów zbioru wartości tej funkcji, tzn. rodzina \(\displaystyle{ \mathbb{B}_f}\), dana jako:

\(\displaystyle{ \mathbb{B}_ f=\left\{ \stackrel{ \rightarrow } {f ^{-1}} \left\{ y\right\} \Bigl| \ \ y\in f_P\right\},}\)

tworzy rozkład zbioru \(\displaystyle{ X}\) na przedziały ( tzn. przedziały w naszym skończonym zbiorze \(\displaystyle{ X}\)), tzn. rodzina \(\displaystyle{ \mathbb{B}_f }\) jest rozkładem zbioru \(\displaystyle{ X}\), będącym jednoczesnie rodziną przedziałów w zbiorze \(\displaystyle{ X.}\)

DOWÓD TEGO FAKTU:

Zauważmy najpierw, że rodzina \(\displaystyle{ \mathbb{B}_f}\) jest rodziną podzbiorów zbioru \(\displaystyle{ X.}\)

I mamy:

\(\displaystyle{ \bigcup\mathbb{B}_f = \bigcup_{y\in f_P} \stackrel { \rightarrow }{f ^{-1} } \left\{ y\right\} = \stackrel { \rightarrow }{f ^{-1} } \left( \bigcup_{y\in f_P} \left\{ y\right\} \right) = \stackrel { \rightarrow }{f ^{-1} } \left( f_P\right) \stackrel{ f:X \rightarrow Y}
{=}X.}\)

I niewątpliwie, przeciwobrazy róznych zbiorów jednoelementowych są rozłączne.

Pozostaje pokazać, że jest to rodzina zbiorów niepustych.
Jeśli mamy zbiór \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left\{ y\right\} }\), gdzie \(\displaystyle{ y\in f_P}\), wtedy \(\displaystyle{ y=f(x)}\), gdzie \(\displaystyle{ x\in X}\), wtedy \(\displaystyle{ f(x)= y \in \left\{ y\right\} }\), a więc, na podstawie definicji przeciwobrazu: \(\displaystyle{ x\in \stackrel{ \rightarrow }{f ^{-1} } \left\{ y\right\} }\) , a więc ten przeciwobraz jest zbiorem niepustym, i rodzina \(\displaystyle{ \mathbb{B}_f}\) jest rodziną zbiorów niepustych.

A więc rodzina \(\displaystyle{ \mathbb{B}_f}\) jest rozkładem zbioru \(\displaystyle{ X}\).

Wykazemy teraz, że jest to rodzna przedziałów.

Niech \(\displaystyle{ A\in \mathbb{B}_f}\) . Wykazemy, że zbiór \(\displaystyle{ A}\) jest przedziałem.
Mamy, z definicji rodziny \(\displaystyle{ \mathbb{B}_f}\), mamy: \(\displaystyle{ A=\stackrel { \rightarrow }{f ^{-1} } \left\{ y\right\} }\), gdzie \(\displaystyle{ y\in f_P}\). Aby wykazać, że zbiór \(\displaystyle{ A}\) jest przedziałem, to niech: \(\displaystyle{ x_1,x_2\in A}\) , i niech \(\displaystyle{ x\in X}\) będzie taką liczxbą (posrtednią), tzn. taką, że \(\displaystyle{ x_1<x<x_2}\), i pokazmy, że \(\displaystyle{ x\in A.}\)

Mamy \(\displaystyle{ x_1, x_2\in \stackrel{ \rightarrow }{f ^{-1} } \left\{ y\right\}}\) , a więc, z definicji przeciwobrazu: \(\displaystyle{ f(x_1), f(x_2) \in \left\{ y\right\} }\), czyli \(\displaystyle{ f(x_1)= y =f(x_2)}\). Poniewaz \(\displaystyle{ x, x_1 \in X}\) i \(\displaystyle{ x_1<x}\), a funkcja \(\displaystyle{ f}\) jest słabo rosnąca, więc \(\displaystyle{ f(x) \ge f(x_1),=y}\).. Podobnie, ponieważ \(\displaystyle{ x<x_2}\), a funkcja \(\displaystyle{ f}\) jest słabo rosnąca, to : \(\displaystyle{ y=f(x_2) \ge f(x)}\). A zatem \(\displaystyle{ y \ge f(x) \ge y}\), a więc \(\displaystyle{ f(x)= y}\), a zatem, z definicji przeciwobrazu wnioskujemy, że: \(\displaystyle{ x\in \stackrel { \rightarrow } {f ^{-1} } \left\{ y\right\} =A}\), i zbiór \(\displaystyle{ A}\) jest przedziałem.

A więc rodzina \(\displaystyle{ \mathbb{B}_f }\) jest rodziną przedziałów\(\displaystyle{ .\square}\)

Zauwazmy, że jesli \(\displaystyle{ (X, \le )}\) jest skończonym niepustym zbiorem liniowo uporządkowanym \(\displaystyle{ n}\)-elemen towym, a \(\displaystyle{ m}\) liczbą naturalną, taką, że: \(\displaystyle{ 1 \le m \le n}\), to rodzina \(\displaystyle{ \mathbb{B} }\) wszystkich rozkładów zbioru \(\displaystyle{ X}\) na \(\displaystyle{ m}\) przedziałów, tzn. rodzina \(\displaystyle{ \mathbb{B}}\) dana jako:

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

dla \(\displaystyle{ m=1}\) , ta rodzina ma również moc równą jeden - łatwo jest to udowodnić,

a dla \(\displaystyle{ m \ge 2}\) ta rodzina jest równoliczna (dowód tego faktu można znaleźć na drugiej stronie tego wątku, ale uwaga- trzeba odrobinę poczytać, nie jest to w tytule postu tylko w środku jednego z dowodów, ale wystarczy odrobinę poczytać drugą stronę tego wątku żeby znależć ten fakt, no i dowód tego faktu jest dłuższy)z rodziną pewnych \(\displaystyle{ m}\)-elementowych ciągów liczb naturalnych, tzn. z rodziną:

\(\displaystyle{ \mathbb{A}_m=\left\{ \left( a_1,a_2,\ldots, a_m \right)\Bigl| \ \ a_1+a_2+\ldots+a_m=n-m \right\} ,}\)

której moc wynosi, ta moc jest równa: \(\displaystyle{ {n-1 \choose m-1}}\), dla \(\displaystyle{ m \ge 2}\).

Czyli również \(\displaystyle{ \left| \mathbb{B}\right|= {n -1\choose m-1} }\), dla \(\displaystyle{ m \ge 2.}\)

Przypomnijmy jeszcze:

Lemat 2. Jeśli \(\displaystyle{ \left( X, \le \right)}\) jest zbiorem liniowo uporządkowanym, a \(\displaystyle{ \left\{ \right\} \neq A\subset X}\) niepustym podzbiorem, a \(\displaystyle{ \mathcal{R}}\) rozkładem podzbioru \(\displaystyle{ A}\) na przediziały, to te przedziały można liniowo uporządkować- i to w sposób konkretny, tzn. relacja \(\displaystyle{ \sqsubseteq}\) na tym rozkładzie \(\displaystyle{ \mathcal{R}}\), dana jako:

\(\displaystyle{ B \sqsubseteq C \Leftrightarrow \left[ B \hbox{ poprzedza }C \hbox{ lub }B=C\right] }\),

gdzie relacja mówiąca, że zbiór \(\displaystyle{ B}\) poprzedza zbiór \(\displaystyle{ C}\) oznacza, że każdy element zbioru \(\displaystyle{ B}\) jest silnie mniejszy od każdego elemnentu zbioeru \(\displaystyle{ C}\),

jest to liniowy porzadek, i wtedy para \(\displaystyle{ \left( \mathcal {R}, \sqsubseteq\right)}\) jest zbiorem liniowo uporządkowanym- jest to w miarę prosty fakt.


Przejdźmy do naszego problemu:

DOWÓD TEGO FAKTU (ZACHOWUJĄC WPROWADZONE OZNACVZENIA):

Jeśli zbiór \(\displaystyle{ X}\) jest zbiorem pustym, to, to istnije dokładnie jedna funkcja pusta, która jest słabo rosnąca, a więc \(\displaystyle{ \left| \mathbb{B}\right|=1.}\)\(\displaystyle{ }\)

Rozwazmy dalej przypadek gdy zbior \(\displaystyle{ X}\) jest niepusty.

Skonczony zbiór \(\displaystyle{ X}\) ma \(\displaystyle{ n}\)-elementów, oznaczmy więc \(\displaystyle{ X=\left\{ x_1, x_2, x_3,\ldots, x_n\right\}}\). Podobnie zbiór \(\displaystyle{ Y}\) ponumerujmy \(\displaystyle{ Y=\left\{ y_1, y_2, \ldots, y_m\right\} .}\)

Zauważmy, że jeśli \(\displaystyle{ f\in\mathbb{B}}\), to \(\displaystyle{ \mathbb{B}_f\sim f_P,}\) wystarczy rozwazyć bijekcję \(\displaystyle{ \alpha}\) działającą w poniższy sposób:

\(\displaystyle{ y\in f_P \ \stackrel { \alpha }{ \rightarrow } \ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y\right\} \in \mathbb{B}_f.}\)

Łatwo jest sprawdzić, że to jest bijekcja, a zatem \(\displaystyle{ f_P\sim \mathbb{B}_f. }\)

Niech:

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

I dla dowolnego ustalonego \(\displaystyle{ i=1,2,\ldots, n}\) rozważmy jej podrodzinę złozoną z rozkładów na \(\displaystyle{ i}\) zbiorów,, tzn.:

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

I, zgodnie z przytoczonym wzorem, mamy:

\(\displaystyle{ \left| \mathbb{A}_i\right| = {n-1 \choose i-1}}\), dla\(\displaystyle{ i \ge 2}\), a dla \(\displaystyle{ i=1}\), mamy: \(\displaystyle{ \left| \mathbb{A}_1\right| =1. }\)

Niech:

\(\displaystyle{ P_n\left( Y\right) =\left\{ A\subset Y\Bigl| 0<\left| A\right| \le n \right\} }\),

i dla \(\displaystyle{ i=1,2,\ldots, min\left( n,m\right), }\)

gdzie \(\displaystyle{ min \left( n,m\right)}\) oznacza mniejszą z liczb \(\displaystyle{ n,m}\), dalej rozważmy jej podrodzinę \(\displaystyle{ \mathbb{S}_i}\) złożoną ze zbiorów mocy \(\displaystyle{ i}\), tzn.:

\(\displaystyle{ \mathbb{S}_i=\left\{ A\in P_n\left( Y\right) \Bigl| \ \left| A\right|=i \right\} .}\)

Wtedy \(\displaystyle{ \bigcup_{i=1}^{min \left( n,m\right) } \mathbb{S}_i= P_n\left( Y\right),}\)

i ponieważ \(\displaystyle{ \left| Y\right|=m}\), to \(\displaystyle{ \left| \mathbb{S}_i\right| = {m \choose i}. }\)

Dla \(\displaystyle{ i=1,2,\ldots, min\left( n,m\right)}\) naszą rozwazaną rodzinę funkcji podzielmy na podrodziny \(\displaystyle{ \mathbb{B}_i}\), tzn. niech:

\(\displaystyle{ \mathbb{B}_i=\left\{ f\in\mathbb{B}: \ \left| f_P\right|=i \right\} }\)

złożoną z tych funkcji, której zbiór wartości ma dokładnie \(\displaystyle{ i}\)-elementów.

Wtedy \(\displaystyle{ \bigcup_{i=1}^{min \left( n,m\right) } \mathbb{B}_i=\mathbb{B}.}\)

Wykazemy, że dla \(\displaystyle{ i=1,2, \ldots, min \left( n,m\right) }\), mamy:

\(\displaystyle{ \mathbb{B}_i\sim \mathbb{S_i} \times \mathbb{A}_i.}\)

No bo żeby opisać nasze funkcję, których zbiór wartosci ma dokładnie \(\displaystyle{ i}\) elementów, musimy ustalić czym jest ten \(\displaystyle{ i}\)-elemtowy zbiór wartości, oraz odpowiednio poprzesuwać na zbiorze \(\displaystyle{ X}\) miejsca w których jest ten wzrost warości , czyli zależy to jeszcze od możliwych rozkładow na przedziały tej dziedziny \(\displaystyle{ X.}\)

W tym celu definiujemy funkcję \(\displaystyle{ \alpha :\mathbb{S}_i \times \mathbb{A}_i \rightarrow \mathbb{B}_i}\) określoną w poniższy następujący sposób:

Jeśli \(\displaystyle{ A\in \mathbb{S}_i}\),\(\displaystyle{ \mathcal{R}\in \mathbb{A}_i}\), wtedy \(\displaystyle{ A\subset Y}\) i \(\displaystyle{ \left| A\right|=i}\); oraz \(\displaystyle{ \mathcal{R}\in\mathbb{A}}\) i \(\displaystyle{ \left| \mathcal{R}\right| =i}\). Wtedy \(\displaystyle{ \mathcal{R}}\) jest rozkładem zbioru \(\displaystyle{ X}\) na przedziały.

Niech \(\displaystyle{ A= \left\{ y _{k_1}, y _{k_2}, \ldots, y _{k_i} \right\}}\) , gdize \(\displaystyle{ k_j\in \left\{ 1,2,\ldots, m\right\}}\) i gdzie \(\displaystyle{ k_1<k_2<\ldots <k_i.}\)

Wtedy, na mocy LEMATU 2, relacja \(\displaystyle{ \sqsubseteq}\) na rozkładzie \(\displaystyle{ \mathcal{R}}\), dana jako:

\(\displaystyle{ B \sqsubseteq C \Leftrightarrow \left[ B \hbox{ poprzedza }C \hbox{ lub }B=C\right] }\)

jest liniowym porządkiem, i para \(\displaystyle{ \left( \mathcal{R}, \sqsubseteq \right) }\) jest zbiorem liniowo uporządkowanym.

Ten rozkład jest mocy \(\displaystyle{ i}\), równeiż zbiór liniowo uporządkowany \(\displaystyle{ \left\{ 1,2,\ldots, i\right\} }\) jest zbiorem liniowo uporządkowanym mocy \(\displaystyle{ i}\). A dwa zbiory liniowo uporządkowane skończone i równoliczne są podobne, wobec czego rozkład \(\displaystyle{ \mathcal{R}}\) jest podobny do zbioru \(\displaystyle{ \left\{ 1,2,\ldots, i\right\} }\). Istnieje zatem podobieństwo \(\displaystyle{ h:\left\{ 1,2,\ldots, i\right\} \rightarrow \mathcal{R},}\) i dla \(\displaystyle{ j \in \left\{ 1,2,\ldots, i \right\} }\) wartość:

\(\displaystyle{ h(j) =:B_j \in\mathcal{R},}\)

ten zbiór nazwijmy \(\displaystyle{ j}\)-ym zbiorem rozkładu \(\displaystyle{ \mathcal{R}.}\)

Definiujemy teraz funkcję \(\displaystyle{ f:X \rightarrow Y}\) w poniższy następujący sposób:

jesli \(\displaystyle{ x\in B_j}\), dla pewnego \(\displaystyle{ j\in \left\{ 1,2,\ldots, i\right\} }\), to definiujemy \(\displaystyle{ f(x)= y _{k_j} }\),

tzn. jesli element \(\displaystyle{ x}\) należy do \(\displaystyle{ j}\)-tego zbioru rozkładu to przypisujemy mu \(\displaystyle{ j}\)-y element zbioru \(\displaystyle{ A}\), który jest podzbiorem zbioru \(\displaystyle{ Y.}\)

Zauważmy, że ponieważ \(\displaystyle{ \mathcal{R}=\left\{ B_1, B_2, \ldots, B_i\right\}}\) jest rozkładem zbioru \(\displaystyle{ X}\), to istnieje dokładnie jeden zbiór \(\displaystyle{ B_j}\), taki, że \(\displaystyle{ x\in B_j}\), i wtedy \(\displaystyle{ f(x)= y _{k_j}\in A\subset Y}\), a więc \(\displaystyle{ f:X \rightarrow Y.}\) Wykazemy, że funkcja \(\displaystyle{ f}\) jest słabo rosnąca.

DOWÓD TEGO OCZYWISTSTEGO FAKTU::    

Niech \(\displaystyle{ x' , x''\in X}\), będą takie, ze \(\displaystyle{ x'<x''.}\) Niech \(\displaystyle{ B _{j''} }\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R}}\) zawierającym elment \(\displaystyle{ x'}\), tzn. takim, że \(\displaystyle{ x'\in B_j'.}\) Niech \(\displaystyle{ B _{j''}}\) będzie zbiorem tego rozkładu zawierajacym element \(\displaystyle{ x'''. }\) Wtedy \(\displaystyle{ j' \le j''.}\) Przypuśćmy na moment, że tak nie jest. Wtedy \(\displaystyle{ j' > j''' }\), wtedy \(\displaystyle{ B _{j'' } \sqsubseteq B _{j'} }\), i te zbiory są rózne, bo \(\displaystyle{ j' \neq j'',}\) a podobieństwo \(\displaystyle{ h}\) jest funkcją róznowartościową. A zatem \(\displaystyle{ B _{j''} \sqsubset B _{j'}}\), a zatem zbiór \(\displaystyle{ B _{j''}}\) poprzedza zbiór \(\displaystyle{ B _{j'}}\) , a ponieważ \(\displaystyle{ x'\in B _{j'}}\) i \(\displaystyle{ x''\in B _{j''}}\), to możemy wnioskować, że \(\displaystyle{ x'' \le x'}\)- sprzeczność.

Wobec czego \(\displaystyle{ j' \le j''}\), i dalej \(\displaystyle{ k _{j'} \le k _{j''},}\) i \(\displaystyle{ y _{k _{j'} } \le y _{k _{j''} }}\) . Ponieważ \(\displaystyle{ x'\in B _{j' } }\), to z definicji funkcji \(\displaystyle{ f}\) otrzymujemy, że \(\displaystyle{ f\left( x'\right) =y _{k _{j'} } \le y _{k _{j''} } .}\) I ponieważ \(\displaystyle{ x''\in B _{j''} }\), to podobnie \(\displaystyle{ f\left( x''\right) = y _{k _{j''} } }\), a zatem \(\displaystyle{ f\left( x''\right) \ge f\left( x'\right)}\) , i funkcja \(\displaystyle{ f}\) jest słabo rosnąca\(\displaystyle{ .\square}\)

A zatem \(\displaystyle{ f \in\mathbb{B}}\), i \(\displaystyle{ \left| f_P\right| =i}\), a zatem \(\displaystyle{ f \in \mathbb{B}_i}\), i otrzymujemy, że funkcja:

\(\displaystyle{ \alpha :\mathbb{S}_i \times \mathbb{A}_i \rightarrow \mathbb{B}_i }\),

jest dobrze określona.


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

Wykazemy, że funkcja \(\displaystyle{ \alpha}\) jest róznowartościowa.

W tym celu weźmy dwie różne pary \(\displaystyle{ \left( A_1, \mathcal{R} _1\right); \left( A_2, \mathcal{R}_2\right) \in \mathbb{S}_i \times \mathbb{A_i}}\) , i pokażmy, że przypisane im funkcję, oznaczmy je odpoweidnio jako \(\displaystyle{ f_1}\) i \(\displaystyle{ f_2,}\) pokazmy, że są różne.

Mamy \(\displaystyle{ A_1 \neq A_2}\) lub \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2.}\)

Jeśli \(\displaystyle{ A_1 \neq A_2}\), to \(\displaystyle{ A_1\not\subset A_2}\) lub \(\displaystyle{ A_2\not\subset A_1.}\)

Jeśli \(\displaystyle{ A_1\not\subset A_2}\), wtedy, na podsawie definicji inkluzji i prawa zaprzeczania ograniczonemu kwantyfikatorowi ogólnemu, otrzyumuemy pewien element \(\displaystyle{ a\in A_1}\), taki, że \(\displaystyle{ a\not\in A_2 }\).

Mamy \(\displaystyle{ a\in A_1=\left\{ y _{k_1} ^{1}, y _{k_2} ^{1},\ldots, y _{k_i} ^{1}\right\} }\), a więc \(\displaystyle{ a= y _{k_j} ^{1} }\), niech \(\displaystyle{ B_j ^{1}}\) będzie \(\displaystyle{ j}\)-ym zbiorem rozkładu \(\displaystyle{ \mathcal{R}_1}\). Wtedy jest to zbiór niepusty, jako zbiór rozkładu. Niech \(\displaystyle{ x\in B_j ^{1}}\), wtedy \(\displaystyle{ f_1(x)=y _{k_j} ^{1}=a.}\)

Uzasadnijmy, że \(\displaystyle{ f_2\left( x\right) \neq a}\). Niech \(\displaystyle{ A_2=\left\{ y _{k_1} ^{2}, y _{k_2} ^{2}, \ldots, y _{k_i} ^{2} \right\}}\) , wtedy \(\displaystyle{ f_2(x)\in A_2}\), a \(\displaystyle{ a\not\in A_2}\), wobec czego \(\displaystyle{ f_2(x) \neq a = f_1(x) }\), a więc \(\displaystyle{ f_1 \neq f_2.}\)

Jesli \(\displaystyle{ A_2\not\subset A_1}\), to podobnie otrzymujemy pewiemn element \(\displaystyle{ a\in A_2}\), taki, że \(\displaystyle{ a\not\in A_1}\), i w analogiczny sposób uzasadniamy, że \(\displaystyle{ f_1 \neq f_2.}\)

Pozostaje rozważyć przypadek gdy \(\displaystyle{ A_1=A_2}\), i \(\displaystyle{ \mathcal{R}_1 \neq \mathcal{R}_2}\) i pokazać, że \(\displaystyle{ f_1 \neq f_2}\).

Przypuśćmy nie wprost, że \(\displaystyle{ f_1=f_2}\) oznaczmy tą funkcję jako \(\displaystyle{ f}\). Wtedy \(\displaystyle{ f:X \rightarrow Y}\) i ( \(\displaystyle{ f\in \mathbb{B}}\)), a zatem, na mocy pierwszego lematu, rodzina \(\displaystyle{ \mathbb{B}_f}\), dana jako:

\(\displaystyle{ \mathbb{B}_f=\left\{ \stackrel{ \rightarrow } {f ^{-1} } \left\{ y\right\} \Bigl| \ \ y\in f_P\right\} ,}\)

jest rozkładem zbioru \(\displaystyle{ X}\) na przedziały.

A zatem \(\displaystyle{ \mathbb{B}_f \in \mathbb{A}}\), i mamy \(\displaystyle{ \left| \mathbb{B}_f \right| =\left| f_P\right|=i}\), a zatem \(\displaystyle{ \mathbb{B}_f \in \mathbb{A}_i.}\)

Pokazemy teraz, że \(\displaystyle{ \mathcal{R}_1= \mathbb{B} _{f_1}}\) i \(\displaystyle{ \mathcal{R} _2= \mathbb{B} _{f_2} .}\)

Rozważmy relację równoważności \(\displaystyle{ \sim _1}\) na zbiorze \(\displaystyle{ X}\), określoną w poniższy sposób:

\(\displaystyle{ x_1\sim _1 x_2 \Leftrightarrow f(x_1)= f(x_2).}\)

Jak łatwo sprawdzić taka relacja jest zwrotna, symetryczna i przechodnia, wobec czego jest relacją równoważności na zbiorze \(\displaystyle{ X}\).

Rozważmy drugą relację równoważności \(\displaystyle{ \sim _2}\) na zbiorze \(\displaystyle{ X}\), określoną w następujący sposób:

\(\displaystyle{ x_1\sim_2 x_2 \Leftrightarrow x_1,x_2\in C\hbox{ dla pewnego } C\in\mathcal{R}_1.}\)

Ponieważ rodzina \(\displaystyle{ \mathcal{R}_1}\) jest rozkładem zbioru \(\displaystyle{ X}\), to ta relacja jest relacją równoważności na \(\displaystyle{ X}\), i zbiór wszystkich klas równoważności jest równy rozkladowi \(\displaystyle{ \mathcal{R}_1}\), tzn. mamy:

\(\displaystyle{ X _{/ \sim _2} = \mathcal{R}_1.}\)

Wykażemy teraz, że: \(\displaystyle{ \left( \sim _1\right) =\left( \sim _2\right) .}\)

Niech \(\displaystyle{ x_1, x_2\in X .}\)

Jeśli \(\displaystyle{ x_1\sim_2 x_2}\), to \(\displaystyle{ x_1,x_2 \in C}\), dla pewnego zbioru \(\displaystyle{ C\in \mathcal{R}_1}\), wtedy \(\displaystyle{ C\in \left\{ B_1, B_2,\ldots, B_i\right\} }\), a wiec \(\displaystyle{ C=B_j}\), dla pewnego j. Wtedy \(\displaystyle{ x_1, x_2\in B_j}\), i oznaczając \(\displaystyle{ A_1=A_2=: A= \left\{ y _{k_1} , y _{k_2} , \ldots, y _{k_i} \right\}}\) , wtedy \(\displaystyle{ f(x_1)= y _{k_j} = f(x_2)}\), a więc \(\displaystyle{ x_1\sim _1 x_2.}\)

Jeśli \(\displaystyle{ x_1\sim_1 x_2}\), to \(\displaystyle{ f(x_1)= f(x_2).}\)

Niech \(\displaystyle{ C_1\in \mathcal{R}_1}\) będzie zbiorem rozkladu \(\displaystyle{ \mathcal{R}_1}\), zawierającym element \(\displaystyle{ x_1}\) (ponieważ \(\displaystyle{ \mathcal {R}_1}\) jest rozkladem zbioru \(\displaystyle{ X}\), więc taki zbiór jest dokładnie jeden). Niech \(\displaystyle{ C_2}\) będzie zbiorem rozkładu \(\displaystyle{ \mathcal{R} _1}\) zawierającym element \(\displaystyle{ x_2.}\)

Ja stwierdzasm, że \(\displaystyle{ C_1=C_2}\). Gdyby bowiem byłoby \(\displaystyle{ C_1 \neq C_2}\) (nie wiem na ile to uzasdnienie będzie formalne, ale lepszy rydz niż nic) . To ponieważ \(\displaystyle{ f(x_1)= f(x_2)}\), \(\displaystyle{ x_1\in C_1}\) ,\(\displaystyle{ x_2\in C_2}\), a \(\displaystyle{ C_1, C_2\in \mathcal{R}_1 }\), który to rozkład składa się z dokładnie \(\displaystyle{ i}\) zbiorów, to z konstrukcji funkcji f otrymujemy, że jej zbiór wartości ma co najwyzej \(\displaystyle{ (i-1)}\) elementów, a \(\displaystyle{ f\in \mathbb{B}_i}\) więc ten zbiór wartości ma dokładnie \(\displaystyle{ i}\)-elementów- sprzeczność.

Wobec czego \(\displaystyle{ C_1=C_2}\), oznaczmy ten zbiór jako \(\displaystyle{ C}\), wtedy \(\displaystyle{ x_1,x_2\in C}\), gdzie \(\displaystyle{ C\in \mathcal{R}_1}\), a więc \(\displaystyle{ x_1\sim_2 x_2.}\)

A zatem \(\displaystyle{ \left( \sim _1\right) = \left( \sim _2\right).}\)

Mamy

\(\displaystyle{ \mathbb{B} _{f_1}= \left\{ \stackrel{ \rightarrow } {f ^{-1} } \Bigl| \ \ y\in f_P\right\}.}\)

Tymczasem:

\(\displaystyle{ \mathcal{R}_1= X _{/\sim _2} = X _{/\sim 1} = \left\{ \left[ x\right] _{\sim _1}\Bigl| \ x\in X \right\}= \left\{ \left\{ y\in X: y\sim _1 x\right\}\Bigl| \ x\in X \right\} = \left\{ \left\{ y\in X: f(y)=f(x) \right\}\Bigl| \ \ x\in X \right\} =\\=\left\{ \left\{ y\in X: \ f(y)=z\right\} \Bigl| z\in f_P\right\} = \left\{ \left\{ x\in X: \ f(x)=y\right\}\Bigl| \ y\in f_P\right\} = \left\{ \stackrel { \rightarrow } {f ^{-1} } \left\{ y\right\} \Bigl| \ y\in f_P\right\} = \mathbb{B} _{f_1} , }\)

czyli \(\displaystyle{ \mathcal{R}_1= \mathbb{B} _{f_1}.}\)

W symetryczny sposób uzasdniamy, że \(\displaystyle{ \mathcal {R}_2= \mathbb{B} _{f_2}.}\)

Łącząc te dwa fakty (ponieważ \(\displaystyle{ f_1= f_2}\), a więc \(\displaystyle{ \mathbb{B} _{f_1} = \mathbb{B} _{f_2}}\) ) więc otrzymujemy, że \(\displaystyle{ \mathcal {R}_1= \mathcal{R}_2}\)- co daje sprzeczność.

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


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

Niech \(\displaystyle{ f\in \mathbb{B}_i}\). Wtedy \(\displaystyle{ f\in\mathbb{B}}\) i \(\displaystyle{ \left| f_P\right| =i}\). Wtedy \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest słabo rosnąca. Wtedy \(\displaystyle{ f_P\subset Y}\), i \(\displaystyle{ 0<\left| f_P\right| =i \le n}\), a więc \(\displaystyle{ f_P\in \mathbb{S}_i.}\)

Rozważmy rodzinę przeciwobrazów:

\(\displaystyle{ \mathbb{B}_f=\left\{ \stackrel { \rightarrow } {f ^{-1} } \left\{ y\right\} \Bigl| \ y\in f_P\right\} ,}\)

taka rodzina tworzy, na mocy pierwszego z lematów, ta rodzina jest rozkładem zbioru \(\displaystyle{ X}\) na przedziały, a zatem \(\displaystyle{ \mathbb{B}_f \in \mathbb{A}}\), i \(\displaystyle{ \left| \mathbb{B}_f\right| = \left| f_P\right|= i}\), a więc \(\displaystyle{ \mathbb{B}_f \in \mathbb{A}_i}\), i wtedy dla pary (dla dowolnych dwóch elementów możemy zawsze utworzyć parę uporządkowaną tych dwóch elementów): \(\displaystyle{ \left( f_P, \mathbb{B}_f\right)}\) , taka para jest elementem zbioru \(\displaystyle{ \mathbb{S}_i \times \mathbb{A}_i}\), czyli dziedziny funkcji \(\displaystyle{ \alpha}\); a zatem funkcja \(\displaystyle{ \alpha}\) zwraca na tej parze \(\displaystyle{ }\)e pewną funkcję \(\displaystyle{ g}\), tzn. mamy:

\(\displaystyle{ \alpha \left( \left( f_P, \mathbb{B}_f\right) \right) =g\in\mathbb{B}_i}\),

wtedy \(\displaystyle{ g\in\mathbb{B}}\) i \(\displaystyle{ \left| g_P\right|=i }\). Wtedy \(\displaystyle{ g:X \rightarrow Y}\) i funkcja \(\displaystyle{ g}\) jest słabo rosnąca. Również \(\displaystyle{ f:X \rightarrow Y}\). Wykazemy, że \(\displaystyle{ f=g}\). W tym celu weźmy dowolny element \(\displaystyle{ x\in X}\), i pokażmy, że \(\displaystyle{ f(x)= g(x).}\) Oznaczmy \(\displaystyle{ f_P=\left\{ y _{k_1}, y _{k_2},\ldots, y _{k_i} \right\}}\) , gdzie \(\displaystyle{ k_j \in \left\{ 1,2,\ldots, m\right\} }\), i gdzie \(\displaystyle{ k_1<k_2<\ldots <k_i}\). Przypuścy, że \(\displaystyle{ f_x= y _{k_j}=a}\). Wtedy \(\displaystyle{ x\in \stackrel { \rightarrow }{ f ^{-1} } \left\{ a\right\} \in \mathbb{B}_f.}\) Wykazemy, że dla każdego \(\displaystyle{ l \in \left\{ 1,2,\ldots, i \right\} }\), mamy: \(\displaystyle{ \stackrel { \rightarrow } {f ^{-1} } \left\{ y_{k_l}\right\} =B_l.}\)

INDUKCYJNY DOWÓD TEGO FAKTU::    

Wykażmy, że \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\} =B_1}\). Zbiór \(\displaystyle{ B_1}\) jest elementem najmniejszym rozkładu \(\displaystyle{ \mathbb{B}_f= \left\{ B_1, B_2,\ldots, B_i \right\} }\). wykazemy, że również zbiór \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\}}\) jest elementem najmniejszym rozkładu \(\displaystyle{ \mathbb{B}_f}\). Niech \(\displaystyle{ B' \in \mathbb{B}_f}\). Jeśli \(\displaystyle{ B'= \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\}}\) , to \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\}\sqsubseteq B'.}\) W przeciwnym przypadku , weźmy \(\displaystyle{ c\in \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_1}\right\} }\), i niech \(\displaystyle{ b\in B'}\), i pokazemy, że \(\displaystyle{ c<b}\). Ponieważ \(\displaystyle{ B'\in \mathbb{B_f},}\) to \(\displaystyle{ B' =\stackrel{ \rightarrow }{f ^{-1} } \left\{ y'\right\}}\) , gdzie \(\displaystyle{ y'\in f_P.}\)
Łatwo nierówność \(\displaystyle{ c \ge b}\), doprowadzić dowodem nie wprost do sprzeczności, gdyż funkcja \(\displaystyle{ f}\) jest słabo rosnąca.A zatem \(\displaystyle{ c<b,}\) i otrzymujemy, że zbiór \(\displaystyle{ \stackrel { \rightarrow } {f ^{-1} } \left\{ y _{k_i} \right\}}\) poprzedza zbiór \(\displaystyle{ B'}\), i \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\}\sqsubseteq B' }\). A zatem zbiór \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\} }\) jest elementem najmniejszym rozkładu \(\displaystyle{ \mathbb{B}_f }\). Ponieważ zbiór \(\displaystyle{ B_1}\) również jest elemntem najmniejszym rozkładu \(\displaystyle{ \mathbb{B}_f}\) a element najmniejszy zbioruu uporządkowanego zawsze jest wyznaczony jednoznacznie, więc \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_1} \right\} =B_1}\), co dowodzi podstawy indukcji.

Dalej stosujemy zasadę indukcji ograniczonej. Przypuśćmy, że dla \(\displaystyle{ 1 \le l<i}\), i dla każdego \(\displaystyle{ p \le l}\) mamy naszą równość: \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{p} } \right\} = B _{ p},}\) i wykazujemy ją dla \(\displaystyle{ (l+1)}\) tzn. wykazemy, że \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{l+1} } \right\} = B _{ (l+1)}.}\)

Ponieważ \(\displaystyle{ y _{k _{(l+1)} }\in f_P}\), to \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left\{ y _{k _{l+1} } \right\} \in\mathbb{B}_f= \left\{ B_1, B_2, \ldots, B-i\right\} }\), a więc \(\displaystyle{ \stackrel { \rightarrow }{f ^{-1} } \left\{ y _{k _{l+1} } \right\}=B_p}\). Jeśli \(\displaystyle{ p=l+1}\), to \(\displaystyle{ B_P= B _{\left( l+1\right) }}\) i dowód jest zakonczony. Pozostaje przyjąć, że \(\displaystyle{ p \neq l+1}\) i doprowadzić ten przypadek do sprzeczności.

Wtedy \(\displaystyle{ p<l+1}\) lub \(\displaystyle{ l+1<p.}\)

Jeśli \(\displaystyle{ l+1>p}\), to zbiór \(\displaystyle{ B_p}\) poprzedza zbiór \(\displaystyle{ B _{l+1} }\). Z załozenia indujkcyjnego otrzymujemy \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_p} \right\} =B_p =\stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{l+1} } \right\} }\). Jeśli \(\displaystyle{ y _{k_p} \neq y _{k_{l+1}} }\), to zbiór \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{p} } \right\} }\) jest zbiorem rozłącznym ze zbiorem \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_{l+1}} \right\} =B_p\in \mathbb{B}_f}\) , a \(\displaystyle{ \mathbb{B}_f}\) jest rozkładem, więc zbiór \(\displaystyle{ B_p}\) musi być niepusty, a zatem ponieważ zbiory \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_p} \right\}}\) oraz \(\displaystyle{ \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_{l+1}} \right\}}\)}\) są rozłączne i niepuste, a zatem rózne, więc otrzymujemy sprzeczność.
Wobec czego \(\displaystyle{ y _{k_p} = y _{k _{l+1} } }\), a więc \(\displaystyle{ k_p=k_{l+1}}\) i dalej \(\displaystyle{ p=l +1}\) -sprzeczność.

Pozostał do rozwazenia drugi przypadek, gdy \(\displaystyle{ l+1<p}\), wtedy zbior \(\displaystyle{ B _{l+1}}\) poprzedza zbior \(\displaystyle{ B_P}\) i zbiór \(\displaystyle{ B_l}\) poprzedza zbiór \(\displaystyle{ B_p}\). Niech \(\displaystyle{ x'\in B_l \neq \left\{ \right\}}\). Niech \(\displaystyle{ x'' \in B_p \neq \left\{ \right\} .}\) Wtedy, poniewaz \(\displaystyle{ B_p= \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{l(+1)} } \right\}}\), wiec\(\displaystyle{ f(x'') = y _{k _{l+1} }}\). Poniewaz \(\displaystyle{ x'\in B_l}\) i \(\displaystyle{ x''\in B_p}\) , a zbiór \(\displaystyle{ B_l}\) \(\displaystyle{ }\)poprzedza zbiór \(\displaystyle{ B_p}\), więc \(\displaystyle{ x'<x''.}\) Ponieważ funkcja \(\displaystyle{ f}\) jest słabo rosnąca, to \(\displaystyle{ y _{k _{(l+1)} } =f(x'') \ge f \left( x'\right) }\). Zbiory B_l, B_p\(\displaystyle{ }\) jako rózne zbiory rozkładu są zbiorami rozłącznymi.

I mamy \(\displaystyle{ y _{k _{l+1} } \neq f _{x'}}\), gdyby bowiem te dwie wartości byly równe, to \(\displaystyle{ x'\in \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_{(l+1)} } \right\} = B_p}\), a [ latex]x''\in B_p[/latex] i \(\displaystyle{ x'\in B_l \cap B_p}\), a zbiory \(\displaystyle{ B_l}\) i \(\displaystyle{ B_p}\) są rozłączne- sprzeczność. Wobec czego \(\displaystyle{ f\left( x''\right) \neq f\left( x'\right) .}\)

A zatem \(\displaystyle{ f\left( x'\right) <f\left( x''\right) = y _{k _{l+1} } .}\)

Oznaczmy \(\displaystyle{ f\left( x'\right)= y _{k_{l} ^{'} } }\) , gdzie \(\displaystyle{ k ^{'} _{l} \in \left\{ 1,2,\ldots, m\right\}.}\)

wtedy \(\displaystyle{ k _{l} ^{' } < k _{l+1}}\) łatwo to nie wprost udowodnić sprawdzajac dwa przypadki (równość i silną nierówność ), wobec czego \(\displaystyle{ k _{l} ^{'} <k _{l+1}}\) , a więc \(\displaystyle{ l''<l+1}\), a więc \(\displaystyle{ l' \le l}\), więc \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{l} } \right\} =B_l}\), na mocy załozenia indukcyjnego. Wtedy \(\displaystyle{ x'\in B_l= \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k _{l} } \right\} }\) , a więc \(\displaystyle{ f(x')=y _{k_l}}\) a ponieważ mamy \(\displaystyle{ f(x' )= y _{k_{l}^{'} } = y _{k_l}}\), to \(\displaystyle{ k _{l} ^{'}= k_l}\) i dalej \(\displaystyle{ l'=l. }\)

Niech \(\displaystyle{ x''' \in B_{l+1}}\), wtedy zbiór \(\displaystyle{ B_l }\) poprzedza zbiór \(\displaystyle{ B _{l+1}}\), więc ponieważ \(\displaystyle{ x'\in B_l}\), a zatem \(\displaystyle{ x'< x'''.}\) Ponieważ funkcja \(\displaystyle{ f}\) jest słabo rosnąca, wiec \(\displaystyle{ f\left( x'''\right) \ge f(x').}\) Podobnire ponieważ zbiór \(\displaystyle{ B _{l+1}}\) poprzedza zbiór \(\displaystyle{ B_p}\) , więc w podobny sposób uzasadniamy, że \(\displaystyle{ f\left( x''\right) \ge f\left( x'''\right). }\) Czyli \(\displaystyle{ y _{k_l} = y _{k _{l} ^{'} } = f\left( x'\right) \le f\left( x'''\right) \le f\left( x''\right) = y _{k _{l+1} }.}\)

Zauważmy, że \(\displaystyle{ f\left( x'\right) \neq f\left( x'''\right)}\), gdyż, w przeciwnym razie: \(\displaystyle{ f\left( x'''\right) = y _{k_l} = f(x')}\) , a zatem \(\displaystyle{ x'''\in \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_l} \right\} =B_l}\), a \(\displaystyle{ x'''\in B _{l+1}}\) , a zatem \(\displaystyle{ x'''\in B_l \cap B _{l+1}}\) , a zbiory \(\displaystyle{ B_l}\) i \(\displaystyle{ B _{l+1}}\) są rozłączne-sprzeczność.

W podobny sposób uzasdniamy, że \(\displaystyle{ f\left( x'''\right) \neq f\left( x''\right).}\)

W związku z czym:

\(\displaystyle{ y _{k_l} = f(x') < f\left( x'''\right) < f\left( x''\right) = y _{k _{\left( l+1\right) } } }\) , gdzie \(\displaystyle{ x''' \in X}\), co daje sprzeczność, bo to oznacza, że pomiędzy \(\displaystyle{ l}\)-warością ze zbioru \(\displaystyle{ f_P}\) a następmną jest wartośc pośrednia, a tak być nie moze, bo wtedy ten zbiór warości \(\displaystyle{ f_P}\) mialby co najmniej \(\displaystyle{ \left( i+1\right)}\) elementów , a on ma tylko \(\displaystyle{ i}\) elementów- sprzeczność. Wobec czego \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_{l+1}} \right\} = B _{l+1}}\), i na mocy zasady indukcji ograniczonej: \(\displaystyle{ \stackrel{ \rightarrow }{f ^{-1} } \left\{ y _{k_l} \right\} =B_l}\), dla każdego \(\displaystyle{ l \in \left\{ 1,2,\ldots, i\right\}.\square}\)

A zatem ponieważ \(\displaystyle{ f(x)=a= y_{k_j}= a}\) na mocy faktu udowodnionego powyżej \(\displaystyle{ \stackrel { \rightarrow } {f ^{-1} } \left\{ y_{k_j}\right\} =B_j.}\), więc \(\displaystyle{ x\in\stackrel { \rightarrow } {f ^{-1} } \left\{ a\right\} =\stackrel { \rightarrow } {f ^{-1} } \left\{ y_{k_j}\right\} = B_j \in \mathbb{B}_f}\), więc \(\displaystyle{ x\in B_j}\), więc zgodnie z definicją funkcji g otrzymujemy: \(\displaystyle{ g(x)= y _{k_j} =a= f(x)}\), i z dowolności wyboru \(\displaystyle{ x\in X}\) otrzymujemy, że \(\displaystyle{ g=f.}\)

A zatem \(\displaystyle{ \alpha \left( \left( f_p,\mathbb{B}_f\right) \right)= g=f,}\)

a więc funkcja \(\displaystyle{ f}\) jest wartością funkcji \(\displaystyle{ \alpha .}\)

Z dowolności wyboru takiej funkcji otrzymujemy, że funkcja \(\displaystyle{ \alpha}\) jest 'na'.

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

Poniewaz dla \(\displaystyle{ i\in \left\{ 2,3, \ldots, min(n,m)\right\} }\) mamy:

\(\displaystyle{ \left| \mathbb{S}_i\right| = {m \choose i} }\), która to wartośc jest liczbą naturalną, i

\(\displaystyle{ \left| \mathbb{A} _i\right| = {n -1\choose i-1}}\) , która to wartośc jest liczbą naturalną, a więc są to dwa zbiory skończone, więc moc ich iloczynu kartezjańskiego wynosi: \(\displaystyle{ {m \choose i} \cdot {n-1 \choose i-1} .}\)

Zauważmy, że dla \(\displaystyle{ i \neq j}\) zbiory \(\displaystyle{ \mathbb{B}_i}\) oraz \(\displaystyle{ \mathbb{B}_j}\) są rozłaczne, bo zbiór wartości funkcji nie może mieć jednocześnie dokładnie \(\displaystyle{ i }\) elementów oraz mieć dokładnie \(\displaystyle{ j }\) elementów.

I mamy:

\(\displaystyle{ \left| \mathbb{B}\right| =\left| \bigcup_{i=1}^{min\left( n,m\right) } \mathbb{B}_i\right| = \left| \mathbb{B}_1\right| +\left| \mathbb{B}_2\right| +\left| \mathbb{B}_3\right| +\ldots+ \left| \mathbb{B} _{min \left( n,m\right) } \right| = \left| \mathbb{B}_1\right| + \sum_{i=2}^{min (n,m)} \left| \mathbb{B}_i\right| = \sum_{i=2}^{min \left( n,m\right) } \left[ {m \choose i} {n-1 \choose i-1} \right] +m=}\)

a to, na mocy tego co wykazał Janusz Tracz , TUTAJ, jest równe:

\(\displaystyle{ ={n+m-1 \choose m-1} -m+m= {n+m-1 \choose m-1} }\), dla \(\displaystyle{ n \neq 0, m \neq 0}\),

a dla \(\displaystyle{ n=0}\), \(\displaystyle{ \left| \mathbb{B}\right|= 1}\) (funkcja pusta),

a \(\displaystyle{ {m-1\choose m-1}= 1}\), czyli dla \(\displaystyle{ n=0}\) również wzór zachodzi\(\displaystyle{ . \square}\)


Rozważmy jeszcze dwa zbiory \(\displaystyle{ X,Y\subset \RR}\), dwa zbiory skończone, przy czym zbiór \(\displaystyle{ Y}\) jest zbiorem niepustym. Załózmy, że zbiór \(\displaystyle{ X}\) ma \(\displaystyle{ n}\)-elemntów, a zbiór \(\displaystyle{ Y}\) ma \(\displaystyle{ m}\)-elemntów, i ponumerujmy te zbiory \(\displaystyle{ X=\left\{ x_1,x_2,\ldots, x_n\right\}}\) oraz \(\displaystyle{ Y=\left\{ y_1, y_2, \ldots, y_m\right\} }\). Rozwazmy rodzinę funkcji słabo malejących, daną jako:

\(\displaystyle{ \mathbb{A}=\left\{ f:X \rightarrow Y\Bigl| \ \ f \hbox{ jest słabo malejąca}\right\} ,}\)

i pytamy o moc rodziny \(\displaystyle{ \mathbb{A}.}\)

Wykazemy, że takich funkcji słabo malejących jest tyle samo co odpowiednuich funkcji słabo rosnących.

DOWÓD TEGO FAKTU:

Niech:

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

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

W tym celu definiujemy funkcję

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

jesli \(\displaystyle{ f\in \mathbb{B}}\), wtedy \(\displaystyle{ f:X \rightarrow Y}\) i funkcja \(\displaystyle{ f}\) jest słabo rosnąca, to definiujemy \(\displaystyle{ \alpha \left( f\right) =f'}\), gdzie funkcja \(\displaystyle{ f':X \rightarrow Y}\) jest określona w taki sposób, że

jeśli \(\displaystyle{ fx)= y _{k}}\), gdzie \(\displaystyle{ k \in \left\{ 1,2,\ldots, m \right\}}\) , to \(\displaystyle{ f'(x)=y _{m-k+1}}\), gdzie numer \(\displaystyle{ \left( m-k+1\right) \in \left\{ 1,2,\ldots, m\right\}}\) , i \(\displaystyle{ f' (x)\in Y}\) i funkcja \(\displaystyle{ f':X \rightarrow Y}\) jest dobrze określona. (Jest to funkcja o 'przeciwnych' wartościach).

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

DOWÓD TEGO FAKTU::    

Niech \(\displaystyle{ x' , x''\in X}\), będą takie, że \(\displaystyle{ x'<x'' }\). Pokazemy, że: \(\displaystyle{ f'\left( x''\right) \le f'(x').}\) Jeśli \(\displaystyle{ f\left( x'\right)= y_k}\), gdzie \(\displaystyle{ k \in \left\{ 1,2,\ldots,m\right\}}\), a \(\displaystyle{ f\left( x''\right) =y_j,}\) ponieważ funkcja \(\displaystyle{ f}\) jest słabo rosnąca, a \(\displaystyle{ x'<x'',}\) to \(\displaystyle{ f\left( x''\right) \ge f(x')}\), czyli \(\displaystyle{ y_j \ge y_k}\), a stąd \(\displaystyle{ j \ge k}\). A zatem \(\displaystyle{ m-k+1 \ge m-j+1}\), a stąd \(\displaystyle{ y _{m-k+1} \ge y _{m-j+1};}\) ponieważ \(\displaystyle{ f(x')= y_k}\), to \(\displaystyle{ f''\left( x'\right)= y _{m-k+1}}\) , a poniewaz \(\displaystyle{ f\left( x''\right) =y_j}\), to podobnie \(\displaystyle{ f'\left( x''\right) = y _{m-j+1} \le y _{m-k+1}= f'\left( x'\right)}\), czyli \(\displaystyle{ f' \left( x''\right) \le f'\left( x'\right) ,}\) i funkcja \(\displaystyle{ f'}\) jest słabo malejąca.

A zatem \(\displaystyle{ f' \in \mathbb{A}}\), i funkcja:

\(\displaystyle{ \alpha :\mathbb{B} \rightarrow \mathbb{A}, }\)

jest dobrze określona.

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

Wykażemy, że funkcja \(\displaystyle{ \alpha}\) jest róznowartościowa.
W tym celu weźmy dwie różne funkcje \(\displaystyle{ f,g\in\mathbb{B}}\) i pokażmy, że również przypisane im funkcję \(\displaystyle{ f'}\) i \(\displaystyle{ g'}\) są również różne. Mamy \(\displaystyle{ f,g:X \rightarrow Y}\) i te funkcje są różne, więc dla pewnego \(\displaystyle{ x\in X}\), mamy:\(\displaystyle{ f\left( x\right) \neq g\left( x\right) }\). Ponieważ \(\displaystyle{ f(x)\in Y}\), to \(\displaystyle{ f(x)= y_k}\), gdzie \(\displaystyle{ k \in \left\{ 1,2,\ldots, m\right\}}\) , i podobnie \(\displaystyle{ g(x)= y _{j} }\), dla pewnego \(\displaystyle{ j}\). Wtedy \(\displaystyle{ y_k \neq y_j}\), a więc również \(\displaystyle{ k \neq j}\), więc łatwo dowodem nie wprost udowodnić, że również \(\displaystyle{ (m-k+1) \neq (m-j+1)}\), i ponieważ ponumerowaliśmy zbiór \(\displaystyle{ Y}\) (a zatem tych numerów jest tylko \(\displaystyle{ m}\) , czyli tyle ile elementów zbioru \(\displaystyle{ Y}\), więc nie może być na różnych numerach nie może być określona ta sama wartość, gdyż wtedy zbiór \(\displaystyle{ Y}\) mialby co najwyzej \(\displaystyle{ (m-1)}\) elementów, a on ma \(\displaystyle{ m}\)-elemenntów- sprzeczność ), wobec czego:

\(\displaystyle{ f'(x)= y _{m-k+1} \neq y _{m-j+1} = g'(x),}\)

a więc \(\displaystyle{ f'(x) \neq g'(x)}\), gdzie \(\displaystyle{ x\in X}\), a więc \(\displaystyle{ f' \neq g' }\),

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

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

Niech \(\displaystyle{ f\in\mathbb{A}}\) . Wtedy \(\displaystyle{ f:X \rightarrow Y}\), i funkcja \(\displaystyle{ f}\) jest słabo malejąca.

Definiujemy funkcję \(\displaystyle{ g:X \rightarrow Y}\) podobnie jak przedtem.

Jeśli \(\displaystyle{ f(x)= y _{k}}\), gdzie \(\displaystyle{ k\in \left\{ 1,2,\ldots, m\right\} }\), to definiujemy \(\displaystyle{ g(x)=y _{m-k+1}}\), gdzie łatwo zauważyć, że numer \(\displaystyle{ \left( m-k+1\right) \in \left\{ 1,2,\ldots,m\right\} }\), a więc \(\displaystyle{ g(x) \in Y}\), i funkcja \(\displaystyle{ g:X \rightarrow Y}\) jest dobrze określona.

Ponieważ funkcja \(\displaystyle{ f}\) jest słabo malejąca, to podobnie jak powyzej możemy udowodnić, że funkcja \(\displaystyle{ g}\) jest słabo rosnąca. A więc \(\displaystyle{ g\in\mathbb{B}}\), i wtedy funkcja \(\displaystyle{ \alpha}\) zwraca na tej funkcji pewną funkcję \(\displaystyle{ g'}\), tzn. mamy:

\(\displaystyle{ \alpha \left( g\right) = g'\in\mathbb{A} .}\) Wtedy \(\displaystyle{ g':X \rightarrow Y.}\) Wykazemy, że \(\displaystyle{ f=g'.}\) Imamy \(\displaystyle{ f:X \rightarrow Y}\), więc aby pokazać, że te funkcję są równe, to weźmy \(\displaystyle{ x\in X}\), i pokazmy, że funkcje na tym argumencie przyjmują te same wartości.

Mamy \(\displaystyle{ f(x)\in Y}\), a więc jesli \(\displaystyle{ f(x)= y_k}\), dla pewnego \(\displaystyle{ k \in \left\{ 1,2,\ldots,m\right\}}\), to:

\(\displaystyle{ g(x)= y _{m-k+1}}\) i dalej:

\(\displaystyle{ g'(x)=y _{m-\left( m-k+1\right)+1 } = y_k= f(x)}\) ,

a więc, z dowolności wyboru \(\displaystyle{ x\in X}\) otrzymujemy \(\displaystyle{ f=g'.}\) A zatem

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

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

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

A zatem \(\displaystyle{ \left| \mathbb{A}\right|= \left| \mathbb{B}\right| = {n +m-1\choose m-1}}\) , dla \(\displaystyle{ m \neq 0. \square}\)

[Jakub Gurak]

Wczoraj udowodniłem, że jeśli \(\displaystyle{ X}\) jest skończonym zbiorem \(\displaystyle{ n}\)-elementowym, a \(\displaystyle{ Y}\) jest skończonym zbiorem \(\displaystyle{ m}\)-elementowym, to zbiór wszystkich funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) wynosi dokładnie \(\displaystyle{ \left( m+1\right) ^{n}}\). Zastanawia mnie teraz, czy te funkcję częściowe nie odpowiadają pewnym funkcjom ze zbioru \(\displaystyle{ \left\{ 1,2, \ldots, n\right\}}\) w pewien zbiór \(\displaystyle{ \left( m+1\right)}\)-elementowy- ja to lubię nietypową matematykę. Przedwczoraj udowodniłem też, że jeśli mamy dowolny podzbiór płaszczyzny \(\displaystyle{ A}\) zawirerający pewien prostokąt otwarty, czyli chodzi o pozbiór plaszczyzny zawierający iloczyn kartezjański pewnych dwóch niepustych przedziałów otwartych , to zbiór \(\displaystyle{ A}\) jest mocy continuum. Ostatnio udowodnłem też, że jeśli w zbiorze mamy dwie rozłączne relacje przeciwprzechodnie, to ich suma nie musi być relacją przeciwprzechodnią. Przedstawię teraz dowody tych ciekawych faktów.


Rozważmy dwa zbiory skończone \(\displaystyle{ X,Y}\). Załóżmy, że zbiór \(\displaystyle{ X}\) ma \(\displaystyle{ n}\)-elementów, a zbiór \(\displaystyle{ Y}\) ma \(\displaystyle{ m}\)-elementów. Ponumerujmy więc te zbiory: tzn. niech \(\displaystyle{ X=\left\{ x_1,x_2, \ldots, x_n\right\}}\); i niech \(\displaystyle{ Y= \left\{ y_1, y_2,\ldots, y_m\right\}}\) . Rozważmy rodzinę wszystkich funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\), tzn. rozważmy rodzinę \(\displaystyle{ \mathbb{B}}\), daną jako:

\(\displaystyle{ \mathbb{B} =\left\{ f\subset X \times Y\Bigl| \ \ f \hbox{ jest funkcją częściową }\right\} .}\)

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

Wykażemy, że: \(\displaystyle{ \left| \mathbb{B}\right| = \left( m+1\right) ^{n}.}\)

DOWÓD TEGO FAKTU:

Dla dowolnego ustalonego \(\displaystyle{ k=1,2,\ldots, n}\), podzielmy rodzinę \(\displaystyle{ \mathbb{B}}\) na podrodziny \(\displaystyle{ \mathbb{B}_k}\), dane jako:

\(\displaystyle{ \mathbb{B}_k=\left\{ f\in\mathbb{B}: \ \ \left| f_L\right|=k \right\} ,}\)

złożone z tych funkcji częściowych, których dziedziny mają dokładnie \(\displaystyle{ k}\)-elementów.

Niech \(\displaystyle{ \mathbb{A}_k}\) będzie rodziną wszystkich \(\displaystyle{ k}\)-elementowych podzbiorów zbioru \(\displaystyle{ X}\), tzn. niech:

\(\displaystyle{ \mathbb{A}_k=\left\{ A\subset X: \ \ \left| A\right|=k \right\}.}\)

Wtedy ponieważ \(\displaystyle{ \left| X\right| =n}\), więc \(\displaystyle{ \left| \mathbb{A}_k\right| = {n \choose k} .
}\)

Wykażemy, że: \(\displaystyle{ \mathbb{B}_k\sim \left( \mathbb{A}_k \times Y ^{\left\{ 1,2,\ldots, k\right\} }\right) .}\)

W tym celu definiujemy funkcję \(\displaystyle{ \alpha :\left( \mathbb{A}_k \times Y^{\left\{ 1,2,\ldots, k\right\} }\right) \rightarrow \mathbb{B}_k}\), w następujący sposób:

Jeśli \(\displaystyle{ A\in \mathbb{A}_k}\) i \(\displaystyle{ f:\left\{ 1,2,\ldots, k\right\} \rightarrow Y}\), wtedy \(\displaystyle{ A\subset X}\) i \(\displaystyle{ \left| A\right| =k}\), następnie porządkujemy zbiór \(\displaystyle{ A}\), tzn. niech \(\displaystyle{ A= \left\{ x _{l_1} , x _{l_2},\ldots, x _{l_k} \right\} }\), gdzie \(\displaystyle{ l_i \in \left\{ 1,2,\ldots, n\right\} ,}\) i gdzie \(\displaystyle{ l_1<l_2<\ldots <l_k}\), i definiujemy funkcję \(\displaystyle{ f':A \rightarrow Y}\), poniższym wzorem:

\(\displaystyle{ f'\left( x _{l_i} \right) = f\left( i\right) \in Y}\),

tzn. \(\displaystyle{ i}\)-temu elementowi zbioru \(\displaystyle{ A}\) przypisujemy \(\displaystyle{ i}\)-ą wartość funkcji \(\displaystyle{ f.}\)

Wtedy \(\displaystyle{ A\subset X}\) , a więc, łatwo się przekonać, że \(\displaystyle{ f'}\) jest funkcją częściową z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\). A zatem \(\displaystyle{ f'\in \mathbb{B}}\), i \(\displaystyle{ \left| f ^{'}_{L} \right| = \left| A\right| =k}\), a więc \(\displaystyle{ f' \in \mathbb{B}_k}\), i funkcja \(\displaystyle{ \alpha \left( :\mathbb{A}_k \times Y ^{\left\{ 1,2,\ldots, k\right\} }\right) \rightarrow \mathbb{B}_k}\) jest dobrze określona.

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

Wykażemy, że \(\displaystyle{ \alpha}\) jest funkcją różnowartościową . W tym celu weźmy dwie różne pary: \(\displaystyle{ \left( A_1, f_1\right) ; \left( A_2,f_2\right) \in\left( \mathbb{A}_k \times Y ^{\left\{ 1,2,\ldots, k\right\} }\right) .}\) Wtedy \(\displaystyle{ A_1, A_2\in \mathbb{A}_k}\) ; i \(\displaystyle{ f_1, f_2:\left\{ 1,2,\ldots, k\right\} \rightarrow Y}\). Rozważmy teraz dwa przypadki:

Jeśli \(\displaystyle{ A_1 \neq A_2}\), to dla przypisanych , przez funkcję \(\displaystyle{ \alpha,}\) funkcji, oznaczonych odpowiednio jako \(\displaystyle{ f_1 ^{'}}\) i \(\displaystyle{ f_2 ^{'}}\), mamy: \(\displaystyle{ \left( f_1 ^{'}\right) _L =A_1 \neq A_2= \left( f_2 ^{'} \right) _L}\), a więc ponieważ funkcje równe muszą mieć równe dziedziny, więc \(\displaystyle{ f_1 ^{'} \neq f_2 ^{'} . }\)

A jeśli \(\displaystyle{ A_1=A_2}\), to oznaczmy ten zbiór jako \(\displaystyle{ A.}\) Wtedy ponieważ dwie wybrane pary są różne, więc musi być \(\displaystyle{ f_1 \neq f_2}\). Ponieważ \(\displaystyle{ f_1,f_2: \left\{ 1,2,\ldots, k\right\} \rightarrow Y}\), czyli te dwie funkcje mają tą samą dziedzinę i przeciwdziedzinę i są różne, więc dla pewnego \(\displaystyle{ i \in \left\{ 1,2,\ldots, k\right\} }\), mamy: \(\displaystyle{ f_1\left( i\right) \neq f_2 \left( i\right)}\) . Wtedy \(\displaystyle{ f_1 ^{'} :A \rightarrow Y}\) i \(\displaystyle{ f_2 ^{'}: A \rightarrow Y}\), i wtedy \(\displaystyle{ f_1 ^{'} \left( x _{l_i} \right)= f_1\left( i\right) \neq f_2\left( i\right) =f_2^{'} \left( x _{l_i}\right) }\), a zatem \(\displaystyle{ f_1 ^{'} \neq f_2 ^{'} .}\)

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

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

Niech \(\displaystyle{ g\in\mathbb{B} _{k} }\). Wtedy \(\displaystyle{ g\in \mathbb{B} }\) i \(\displaystyle{ \left| g_L\right|=k}\). Wtedy \(\displaystyle{ g:g_L \rightarrow Y.}\) Mamy też \(\displaystyle{ g_L\subset X}\) i \(\displaystyle{ \left| g_L\right| =k}\), uporządkujmy zatem ten zbiór, tzn. niech: \(\displaystyle{ g_L= \left\{ x _{l_1}, x _{l_2},\ldots, x _{l_k} \right\}}\) , gdzie \(\displaystyle{ l_i \in \left\{ 1,2,\ldots, n\right\}, }\) i \(\displaystyle{ l_1<l_2<\ldots <l_k. }\)

Definiujemy funkcję \(\displaystyle{ f: \left\{ 1,2,\ldots, k \right\} \rightarrow Y}\), poniższym wzorem:

\(\displaystyle{ f\left( i\right) = g\left( x_{ l_i} \right) \in Y.}\)

wtedy \(\displaystyle{ x _{l_i} \in g_L}\) , a więc funkcja \(\displaystyle{ f: \left\{ 1,2,\ldots, k\right\} \rightarrow Y}\) jest dobrze określona, i mamy \(\displaystyle{ A:=g_L \subset X}\), i \(\displaystyle{ \left| A\right| = \left| g_L\right| =k}\), a zatem \(\displaystyle{ A\in \mathbb{A}_k}\). Możemy zatem wyliczyć wartość funkcji \(\displaystyle{ \alpha}\) na tej parze \(\displaystyle{ \left( A,f\right)}\) , tzn. niech \(\displaystyle{ \alpha \left( \left( A,f\right) \right) = f'. }\)

Pokażemy, że \(\displaystyle{ f'=g}\). Mamy \(\displaystyle{ f':A \rightarrow Y}\) i \(\displaystyle{ g:g_L=A \rightarrow Y}\); więc aby pokazać, że te funkcję są równe, to weźmy \(\displaystyle{ a\in A}\), i pokażmy, że funkcję \(\displaystyle{ f'}\) i \(\displaystyle{ g}\) przyjmują na tym elemencie tą samą wartość. Ponieważ \(\displaystyle{ a\in A=\left\{ x _{l_1}, x _{l_2} ,\ldots, x _{l_k} \right\}}\) , to przyjmijmy, że \(\displaystyle{ a= x _{l_i}}\), gdzie \(\displaystyle{ i\in \left\{ 1,2,\ldots, k\right\} }\). Wtedy :

\(\displaystyle{ f'(a)=f'\left( x _{l_i} \right) = f(i) = g\left( x _ {l_i} \right) =g(a)}\),

czyli \(\displaystyle{ f''(a)= g(a)}\), i ( z dowolności wyboru elementu \(\displaystyle{ a\in A}\)) otrzymujemy, że \(\displaystyle{ f'=g.}\)

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

A zatem \(\displaystyle{ \left( \mathbb{A}_k \times Y ^{\left\{ 1,2,\ldots, k\right\} }\right) \sim \mathbb{B}_k.}\)

Ponieważ obydwie składowe tego iloczynu kartezjańskiego są zbiorami skończonymi, to: \(\displaystyle{ \left| \mathbb{B}_k \right| = {n \choose k} \cdot \cdot m ^{k}.}\) Zauważmy, że \(\displaystyle{ \mathbb{B}= \bigcup_{k=0}^{n} \mathbb{B}_k}\) (gdzie, zbiór \(\displaystyle{ \mathbb{B}_0,}\) oznacza, nasze funkcje częściowe o pustej lewej dziedzinie ) , i zbiory \(\displaystyle{ \mathbb{B}_k}\) są rozłączne, a zatem:

\(\displaystyle{ \left| \mathbb{B}\right| = \left| \mathbb{B}_0\right| + \left| \mathbb{B}_1\right| +\ldots + \left| \mathbb{B}_n\right| = 1 \cdot 1+ \sum_{k=1}^{n} \left| \mathbb{B}_k \right|= 1+ \sum_{k=1}^{n} \left( {n \choose k} \cdot m ^{k} \right) = \sum_{k=0}^{n} \left( {n \choose k} \cdot m ^{k} \right) = \left( 1+m\right) ^{n}= \left( m+1\right) ^{n}}\), dla \(\displaystyle{ m \neq 0.}\)
\(\displaystyle{ }\)
A dla \(\displaystyle{ m=0}\), mamy tylko funkcje pustą ze zbioru pustego w siebie (bo nie może istnieć funkcja na zbiorze niepustym o wartościach w zbiorze pustym, bo musiałaby przyjąć wartość na pewnym argumencie - sprzeczność ), czyli nasz zbiór jest jednoelementowy, a \(\displaystyle{ \left( 0+1\right) ^{n} = 1^n=1}\), czyli dla \(\displaystyle{ m=0}\) również wzór zachodzi\(\displaystyle{ . \square}\)

Ciekawe jest teraz, czy te funkcje częsciowe nie odpowiadają pewnym funkcjom z pewnego zbioru \(\displaystyle{ n}\)-elementowego w pewien zbiór \(\displaystyle{ \left( m+1\right) }\)-elementowy, będzie można nad tym pomyśleć.


Wykażemy jeszcze, zgodnie z zapowiedzią , że jeśli mamy podzbiór płaszczyzny \(\displaystyle{ A\subset \RR^{2}}\), zawierajacy pewien prostokąt otwarty, tzn. chodzi o podzbiór płaszczyzny zawierający iloczyn kartezjański pewnych dwóch przedziałów otwartych \(\displaystyle{ \left( a,b\right) }\); oraz \(\displaystyle{ \left( c,d\right),}\) gdzie \(\displaystyle{ a<b}\) i \(\displaystyle{ c<d}\), to zbiór \(\displaystyle{ A}\) jest mocy continuum. Pokażemy nawet więcej.

Tzn. pokażemy, że:

LEMAT 1. Jeśli mamy podzbiór płaszczyzny \(\displaystyle{ A\subset \RR^2}\), zawierający pewien zbiór postaci \(\displaystyle{ \left( a,b\right) \times \left\{ y\right\} }\), gdize \(\displaystyle{ a,b\in \RR, a<b}\), i gdzie \(\displaystyle{ y\in \RR,}\) to zbiór \(\displaystyle{ A}\) jest mocy continuum.

Nim to udowodnimy, przypomnijmy, prosty fakt, że jeśli mamy dowolny zbiór\(\displaystyle{ X}\), oraz dowolny element \(\displaystyle{ a}\) (element, być może, nawet spoza tego zbioru), to mamy równoliczność zbiorów: \(\displaystyle{ X\sim X \times \left\{ a\right\}}\), oraz jeśli mamy zbiór \(\displaystyle{ X,}\) oraz dowolny element \(\displaystyle{ b}\), to mamy równoliczność zbiorów (ale nie wiem, czy tego ostatniego faktu szczegółowo nie udowadniałem) , to mamy równoliczność zbiorów: \(\displaystyle{ X\sim \left\{ b\right\} \times X}\) -są to proste fakty. Ale, te fakty, mają one ciekawą ilustracje (w przypadku, gdy \(\displaystyle{ a\in X}\) i \(\displaystyle{ b\in X}\)), oto ciekawe ilustracje tych faktów, przy pomocy kwadratu kartezjańskiego:

Na rysunku bowiem widać ( na pierwszym może trochę niewyraźnie , że każda prosta pozioma jest równoliczna z pierwszą osią, na drugim rusunku widać już wyraźnie, że każda prosta pionowa jest równoliczna z drugą osią, która jest równa pierwszej osi ).

Przejdźmy do zapowiedzianego dowodu.

DOWÓD TEGO FAKTU:

Ponieważ \(\displaystyle{ A\supset \left( a,b\right) \times \left\{ y\right\}}\) , to \(\displaystyle{ \left|A\right| \ge \left| \left( a,b\right) \times \left\{ y\right\} \right| =\left| \left( a,b\right)\right| }\) i ponieważ \(\displaystyle{ a<b}\), to taki przedział otwarty mam moc continuum. A zatem: \(\displaystyle{ \left| A\right| \ge \left| \RR\right| }\). Ale \(\displaystyle{ A\subset \RR^2}\), a zatem \(\displaystyle{ \left| A\right| \le \left| \RR^2\right| = \left| \RR\right|. }\) Na mocy twierdzenia Cantora-Bernsteina zbiór \(\displaystyle{ A}\) jest zbiorem mocy continuum\(\displaystyle{ .\square}\)

Można też udowodnić, że jeśli \(\displaystyle{ A}\) jest podzbiorem płaszczyzny zawireającym pewien zbiór postaci \(\displaystyle{ \left\{ x\right\} \times \left( a,b\right)}\) , gdzie \(\displaystyle{ x\in\RR}\), a \(\displaystyle{ a,b\in\RR}\) i \(\displaystyle{ a<b}\), to zbiór \(\displaystyle{ A}\) jest mocy continuum.

DOWÓD TEGO FAKTU, NIE ANALOGICZNY:    

Ponieważ \(\displaystyle{ A\subset \RR \times \RR}\), to zbiór \(\displaystyle{ A}\) jest relacją w zbiorze \(\displaystyle{ \RR}\). Wtedy, ponieważ relacja odwrotna do danej jest z nią równoliczna (jest to prosty fakt) , więc \(\displaystyle{ A ^{-1}\sim A}\). Zauważmy, że \(\displaystyle{ \left\{ x\right\}\subset \RR}\) i \(\displaystyle{ \left( a,b\right) \subset \RR}\), a zatem iloczyn kartezjański tych dwóch zbiorów jest podzbiorem zbioru \(\displaystyle{ \RR \times \RR=\RR ^{2}.}\) Zatem zbiór \(\displaystyle{ \left\{ x\right\} \times \left( a,b\right) }\) jest relacją w zbiorze liczb rzeczywistych. Ponieważ \(\displaystyle{ A\supset \left\{ x\right\} \times \left( a,b\right) }\), to \(\displaystyle{ A ^{-1}\supset \left( \left\{ x\right\} \times \left( a,b\right) \right) ^{-1} \stackrel {\left( B \times C\right) ^{-1}= C \times B } {=} \left( a,b\right) \times \left\{ x\right\} .}\) Ponieważ \(\displaystyle{ A\subset \RR \times \RR}\), to \(\displaystyle{ A ^{-1}\subset \RR \times \RR= \RR ^{2}.}\) I mamy \(\displaystyle{ A ^{-1} \supset \left( a,b\right) \times \left\{ x\right\}}\), gdzie \(\displaystyle{ a<b}\), możemy zatem zastosować udowodniony powyżej fakt , i otrzymać, że \(\displaystyle{ A ^{-1} \sim \RR. }\) Ponieważ \(\displaystyle{ A\sim A ^{-1}}\), to z przechodniości równoliczności otrzymujemy, że: \(\displaystyle{ A\sim \RR.\square}\)

Możemy zatem łatwo udowodnić nasz fakt, jako szczególny przypadek pierwszego z tych dwóch faktów :

Tzn. jeśli \(\displaystyle{ A\subset \RR^2}\), i \(\displaystyle{ A\supset \left( a,b\right) \times \left( c,d\right)}\) , gdzie \(\displaystyle{ a<b}\); \(\displaystyle{ c<d}\), to zbiór \(\displaystyle{ A}\) ma moc continuum.

DOWÓD TEGO FAKTU:

Ponieważ \(\displaystyle{ c<d}\), to przedział otwarty \(\displaystyle{ \left( c,d\right)}\) jest niepusty (aby to uzasadnić, możemy na przykład użyć faktu mówiącego, że pomiędzy dwoma liczbami rzeczywistymi jest liczba wymierna). Istnieje więc liczba rzeczywista \(\displaystyle{ y\in \left( c,d\right) }\), wtedy \(\displaystyle{ \left\{ y\right\} \subset \left( c,d\right)}\) , a zatem \(\displaystyle{ A\supset \left( a,b\right) \times \left( c,d\right) \supset \left( a,b\right) \times \left\{ y\right\} }\), czyli \(\displaystyle{ A\supset \left( a,b\right) \times \left\{ y\right\}}\) . Ponieważ \(\displaystyle{ A\subset \RR^2}\), a \(\displaystyle{ a<b}\), więc możemy zastosować fakt udowodniony powyżej, i otrzymać, że zbiór \(\displaystyle{ A}\) jest mocy continuum\(\displaystyle{ .\square}\)


Wykazemy jeszcze, zgodnie z zapowiedzią, że jesli w danym zbiorze mamy dwie rozłączne relacje przeciwprzechodnie, to ich suma nie musi być relacją przeciwprzechodnią.

Przypomnę może jeszcze, że jeśli mamy zbiór \(\displaystyle{ X,}\) oraz relację \(\displaystyle{ R}\) w zbiorze \(\displaystyle{ X}\), to ta relacja jest przeciwprzechodnia, gdy spełniona jest implikacja:

\(\displaystyle{ \left( a,b\right) \in R \wedge \left( b,c\right) \in R \Longrightarrow \left( a,c\right) \not\in R}\),

czyli relacja zachodząc miedzy elementem pierwszym a drugim i zachodząc między elementem drugim a trzecim nie zachodzi nigdy między elementem pierwszym a trzecim.

Przejdźmy do dowodu naszego faktu.

DOWÓD TEGO FAKTU:

Jako kontrprzykład, rozwazmy zbiór:

\(\displaystyle{ X=\left\{ 0,1,2\right\}}\) , a jako relacje rozważmy \(\displaystyle{ R= \left\{ \left( 0,1\right) ; \left( 1,2\right) \right\} }\) oraz niech \(\displaystyle{ S=\left\{ \left( 0,2\right) \right\}.}\)

Wtedy relacja \(\displaystyle{ S}\) jest przeciwprzechodnia (w tym przypadku założeń impilkacji nie da sie spełnić, a więc cała implikacja jest prawdziwa ), a więc jest to relacja przeciwprzechodnia, i relacja \(\displaystyle{ R}\) jest przeciworzechodnia (mamy: \(\displaystyle{ \left( 0,1\right) \in R}\) i \(\displaystyle{ \left( 1,2\right) \in R}\), lecz \(\displaystyle{ \left( 0,2\right) \notin R}\) ), a \(\displaystyle{ R \cup S= \left\{ \left( 0,1\right) ; \left( 1,2\right) ; \left( 0,2\right) \right\}}\) , czyli \(\displaystyle{ \left( 0,1\right) \in R \cup S}\); \(\displaystyle{ \left( 1,2\right) \in R \cup S}\) oraz \(\displaystyle{ \left( 0,2 \right) \in R \cup S}\) , a więc relacja \(\displaystyle{ R \cup S}\) nie jest przeciwprzechodnia, gdzie relacje \(\displaystyle{ R,S}\) są rozłączne\(\displaystyle{ .\square}\)

[Dasio11]

Wczoraj udowodniłem, że jeśli \(\displaystyle{ X}\) jest skończonym zbiorem \(\displaystyle{ n}\)-elementowym, a \(\displaystyle{ Y}\) jest skończonym zbiorem \(\displaystyle{ m}\)-elementowym, to zbiór wszystkich funkcji częściowych z \(\displaystyle{ X}\) do \(\displaystyle{ Y}\) wynosi dokładnie \(\displaystyle{ \left( m+1\right) ^{n}}\). Zastanawia mnie teraz, czy te funkcję częściowe nie odpowiadają pewnym funkcjom ze zbioru \(\displaystyle{ \left\{ 1,2, \ldots, n\right\}}\) w pewien zbiór \(\displaystyle{ \left( m+1\right)}\)-elementowy

Oczywiście, że odpowiadają - aby zdefiniować dowolną funkcję częściową z \(\displaystyle{ X}\) w \(\displaystyle{ Y}\), należy dla każdego \(\displaystyle{ x \in X}\) wybrać jedną z \(\displaystyle{ m+1}\) możliwości: albo pewną wartość \(\displaystyle{ f(x) \in Y}\), albo brak wartości, co oznacza że \(\displaystyle{ x \notin D_f}\).

Jeśli wolisz formalnie (choć jak dla mnie to mniej przejrzyste): bijekcją jest odwzorowanie ze zbioru \(\displaystyle{ (Y \cup \{ \bot \})^X}\) w zbiór funkcji częściowych z \(\displaystyle{ X}\) w \(\displaystyle{ Y}\), które funkcji \(\displaystyle{ g \in (Y \cup \{ \bot \})^X}\) przypisuje funkcję częściową \(\displaystyle{ g \restriction g^{-1}[Y]}\).

[Jan Kraszewski]

Przedwczoraj udowodniłem też, że jeśli mamy dowolny podzbiór płaszczyzny \(\displaystyle{ A}\) zawirerający pewien prostokąt otwarty, czyli chodzi o pozbiór plaszczyzny zawierający iloczyn kartezjański pewnych dwóch niepustych przedziałów otwartych , to zbiór \(\displaystyle{ A}\) jest mocy continuum.

Ale wiesz, że dowolny podzbiór płaszczyzny, zawierający podzbiór mocy continuum jest mocy continuum? A dowód tego, że prostokąt jest mocy continnum jest półlinijkowy - jest produktem dwóch zbiorów mocy continuum.

Na Wstępie do matematyki między innymi po to uczy się pewnych narzędzi, żeby potem pewne fakty były prostymi wnioskami, które nie wymagają długich (i niezbyt potrzebnych) rozumowań.

JK

[Jakub Gurak]

Ale wiesz, że dowolny podzbiór płaszczyzny, zawierający podzbiór mocy continuum jest mocy continuum?

A to ciekawe... Ale nawet chyba wiem jak to uzasadnić- twierdzeniem Cantora-Bernsteina ( i na mocy faktu, że cała płaszczyzna jest mocy continuum ).

A dowód tego, że prostokąt jest mocy continnum jest półlinijkowy - jest produktem dwóch zbiorów mocy continuum.

A tu się zachwiałem, spróbuję to uzasadnić, proszę o sprawdzenie.

Niech zbiory \(\displaystyle{ A,B\subset \RR,}\) będą takie, że \(\displaystyle{ A,B \sim \RR.}\) Wtedy \(\displaystyle{ A \times B\sim \RR \times \RR\sim \RR }\), a więc \(\displaystyle{ A \times B\sim \RR}\), dobrze

Na Wstępie do matematyki między innymi po to uczy się pewnych narzędzi, żeby potem pewne fakty były prostymi wnioskami, które nie wymagają długich (i niezbyt potrzebnych) rozumowań.

To ja teraz też nie udowadniam znanych mi faktów, ale jeśli chodzi o całą resztę, to co innego... Ale szczerze powiedziawszy, to powyższy post Dasia 11 mnie zszokował- ja tu się mozole, a On ( jak zwykle) przedstawia genialny pomysł ( na który móglbym sam nie wpaść) w jednej linijce. Dasio11- jak to robisz

A ja tak nie potrafię; ja wcale nie jestem miłośnikiem formalizacji- proszę zauważyć, że spójników logicznych i kwantyfikatorów używam bardzo rzadko, nie lubię ich używać. Ja, lubię tylko dogłębnie poznawać matematykę, i, gdzie potrzeba ścisłości- staram się o wszystko zadbać, żeby napisać w miarę dokładne rozwiązanie danego problemu, ja inaczej chyba nie potrafię. Dasio 11 jest zadziwiający.

Dasio 11, jak to robisz