Twierdzenie Hessenberga

[Dasio11]

Z injekcji \(\displaystyle{ g_L \to g_L}\) i \(\displaystyle{ X \setminus g_L \to g_L}\) robisz injekcję \(\displaystyle{ (X \setminus g_L) \cup g_L \to \{ 0, 1 \} \times g_L}\) a potem następne injekcje \(\displaystyle{ \{ 0, 1 \} \times g_L \to g_L \times g_L \to g_L}\).

[Jakub Gurak]

Czyli otrzymujemy funkcję różnowartościową z \(\displaystyle{ (X \setminus g_L) \cup g_L \to g _{L}}\), czyli funkcję różnowartościową z \(\displaystyle{ X}\) w \(\displaystyle{ g_{L}}\), a więc \(\displaystyle{ \left| X\right| \le \left| g_{L} \right|}\), a \(\displaystyle{ \left| X\right|>\left| g_{L} \right|}\) , i otrzymujemy sprzeczność na podstawie twierdzenia Cantora-Bernsteina.

Dobrze

[Dasio11]

Tak.

[Jakub Gurak]

Plan jest mniej więcej taki: znaleźć zbiory parami rozłączne \(\displaystyle{ T_1,T_2,T_3 \subseteq X\setminus g_L}\) takie, że \(\displaystyle{ T_1\sim T_2\sim T_3\sim g_L}\)

Obawiam się, że to ( i to nadal ) nie jest oczywiste

Spróbuję to uzasadnić. Ponieważ \(\displaystyle{ g_{L}}\) jest zbiorem nieskończonym, a \(\displaystyle{ \left| X \setminus g_{L} \right|>\left| g_{L} \right|,}\) więc \(\displaystyle{ X \setminus g_{L}:=C}\) jest zbiorem nieprzeliczalnym. W takim razie możemy odnaleźć w nim nieskończony zbiór przeliczalny \(\displaystyle{ A _{0} \subset C.}\) Ponieważ zbiory nieprzeliczalne są odporne na ujmowanie zbiorów co najwyżej przeliczalnych (prezentowałem dowód: tu, to \(\displaystyle{ C \setminus A_{0}\sim C.}\)

Ale niestety \(\displaystyle{ C}\) nie jest równoliczny z \(\displaystyle{ g _{L}}\), więc zachodzi pytanie: Panie Janie Kraszewski , czy konieczne jest aby te poszukiwane trzy zbiory były dokładnie równoliczne z \(\displaystyle{ g _{L}}\), nie mogą być silnie większe Bo w tym momencie ją mogę zdefiniować zbiory: \(\displaystyle{ C\sim A _{1}:=C \setminus A _{0}}\) Możemy znowu odnaleźć w takim zbiorze nieskończony zbiór przeliczalny \(\displaystyle{ B _{1} \subset A_{1}}\), zdefiniować \(\displaystyle{ A _{2}:= A_{1} \setminus B _{1}}\), zbiór równoliczny z \(\displaystyle{ C}\), i jeszcze raz podobnie. Jan Kraszewski, czy to się uda dalej , czy może nie w ten sposób.

[Dasio11]

Wprawdzie nie jestem Janem Kraszewskim, ale i tak odpowiem.

czy konieczne jest aby te poszukiwane trzy zbiory były dokładnie równoliczne z \(\displaystyle{ g _{L}}\), nie mogą być silnie większe

Jest konieczne, między innymi dlatego, że na tym etapie nie uda Ci się wybrać większych.

Powinieneś zrobić to samo, ale nie odejmując trzykrotnie zbiór przeliczalny od zbioru nieprzeliczalnego, tylko odejmując zbiór równoliczny z \(\displaystyle{ g_L}\) od zbioru mocy większej niż \(\displaystyle{ |g_L|}\). Możesz też od razu zauważyć, że \(\displaystyle{ | \{ 0, 1, 2 \} \times g_L | \le |g_L \times g_L| = |g_L| \le |X \setminus g_L|}\), co od razu daje trzy rozłączne podzbiory \(\displaystyle{ X \setminus g_L}\) równoliczne z \(\displaystyle{ g_L}\).

[Jakub Gurak]

Chodzi o zbiory: \(\displaystyle{ \left\{ 0\right\} \times g_{L},\left\{ 1\right\} \times g_{L}, \hbox{ i } \left\{ 2\right\} \times g _{L}}\)?

[Dasio11]

Tak, a ściślej - ich obrazy przez injekcję \(\displaystyle{ \{ 0, 1, 2 \} \times g_L \to X \setminus g_L}\).

[Jakub Gurak]

Obrazy zbiorów rozłącznych są rozłączne przez funkcję różnowartościową ?A jeśli tak, to dlaczego

[Dasio11]

Tak. Może sam spróbujesz to udowodnić, to nie jest trudne...

Albo może Cię przekonać argument nieformalny, że funkcja różnowartościowa jest bijekcją na obraz, a bijekcja to teoriomnogościowy izomorfizm, czyli zachowuje wszystkie teoriomnogościowe własności, takie jak rozłączność, zawieranie...

[Jakub Gurak]

Dobrze, spróbuję to udowodnić. Niech \(\displaystyle{ f:X \rightarrow Y}\) będzie różnowartościowa. Niech zbiory \(\displaystyle{ A,B \subset X}\) będą rozłączne. Pokazujemy, że obrazy \(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A\right),\stackrel{ \rightarrow }{f}\left( B\right)}\) są rozłączne, czyli nie mają wspólnych elementów. Gdyby miały wspólny element \(\displaystyle{ y \in\stackrel{ \rightarrow }{f}\left( A\right)}\) i \(\displaystyle{ y \in \stackrel{ \rightarrow }{f}\left( B\right)}\), to wtedy \(\displaystyle{ y=f\left( x _{1} \right)}\), przy \(\displaystyle{ x _{1} \in A}\), oraz \(\displaystyle{ y= f\left( x_{2}\right)}\) przy \(\displaystyle{ x _{2} \in B}\), zatem \(\displaystyle{ y=f\left( x _{1} \right)=f\left( x _{2} \right)}\), a ponieważ \(\displaystyle{ f}\) jest różnowartościowa, to \(\displaystyle{ x_{1}= x_{2}.}\) Oznaczmy tą wartość jako \(\displaystyle{ x}\). Ponieważ\(\displaystyle{ x=x _{1} \in A}\), \(\displaystyle{ x=x _{2} \in B}\), to \(\displaystyle{ x\in A \cap B}\), czyli zbiory \(\displaystyle{ A,B}\) mają wspólny element, a są z założenia rozłączne- sprzeczność.

Chyba dobrze?

Też przeczytałem, że dla funkcji różnowartościowej \(\displaystyle{ f:X \rightarrow Y}\), i zbiorów \(\displaystyle{ A,B \subset X}\), mamy \(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A \cap B\right)=\stackrel{ \rightarrow }{f}\left( A\right) \cap \stackrel{ \rightarrow }{f}\left( B\right)}\). Z tego ponoć ma wynikać, że właśnie obrazy zbiorów rozłącznych są rozłączne. Ale w ogóle tego nie uzasadniali, chętnie bym to zobaczył jeszcze. Dlatego też spytałem o to, dlaczego to zachodzi, byłem ciekawy.

[Dasio11]

Chyba dobrze?

Dobrze.

Też przeczytałem, że dla funkcji różnowartościowej \(\displaystyle{ f:X \rightarrow Y}\), i zbiorów \(\displaystyle{ A,B \subset X}\), mamy \(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A \cap B\right)=\stackrel{ \rightarrow }{f}\left( A\right) \cap \stackrel{ \rightarrow }{f}\left( B\right)}\). Z tego ponoć ma wynikać, że właśnie obrazy zbiorów rozłącznych są rozłączne.

Zgadza się. Zawieranie w jedną stronę zachodzi bez założenia różnowartościowości i sam udowodniłeś je tutaj.

W drugą jest podobnie, jak zrobiłeś wyżej: ustalmy dowolny element \(\displaystyle{ y \in f[A] \cap f}\). Wtedy istnieje takie \(\displaystyle{ a \in A}\), że \(\displaystyle{ y = f(a)}\), oraz takie \(\displaystyle{ b \in B}\), że \(\displaystyle{ y = f(b)}\). Wówczas \(\displaystyle{ f(a) = f(b)}\), więc z różnowartościowości dostajemy \(\displaystyle{ a = b}\). Stąd \(\displaystyle{ a \in A \cap B}\) oraz \(\displaystyle{ f(a) = y}\), co oznacza, że \(\displaystyle{ y \in f[A \cap B]}\).


Można też argumentować jak poprzednio, że injekcja jest izomorfizmem na obraz, więc zachowuje także działania teoriomnogościowe - sumę, przekrój, dopełnienie, itd.

[Jakub Gurak]

Zgadza się. Zawieranie w jedną stronę zachodzi bez założenia różnowartościowości i sam udowodniłeś je tutaj.

W drugą jest podobnie, jak zrobiłeś wyżej: ustalmy dowolny element \(\displaystyle{ y \in f[A] \cap f}\). Wtedy istnieje takie \(\displaystyle{ a \in A}\), że \(\displaystyle{ y = f(a)}\), oraz takie \(\displaystyle{ b \in B}\), że \(\displaystyle{ y = f(b)}\). Wówczas \(\displaystyle{ f(a) = f(b)}\), więc z różnowartościowości dostajemy \(\displaystyle{ a = b}\). Stąd \(\displaystyle{ a \in A \cap B}\) oraz \(\displaystyle{ f(a) = y}\), co oznacza, że \(\displaystyle{ y \in f[A \cap B]}\).

Nie o ten dowód mi chodziło... To jest klasyczny fakt, żebym miał się tu rozwodzić nad takim, bez przesady...

Chodziło mi jak z równości \(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A \cap B\right)=\stackrel{ \rightarrow }{f}\left( A\right) \cap \stackrel{ \rightarrow }{f}\left( B\right)}\) (dla funkcji różnowartościowej) ma wynikać, że wtedy obrazy zbiorów rozłącznych są zawsze rozłączne.

Przejdźmy dalej:

potem zdefiniować bijekcje:

\(\displaystyle{ f_1:T_1\to (T_1\cup T_2\cup T_3)\times g_L,\\ f_2:T_2\to g_L\times(T_1\cup T_2\cup T_3), \\f_3: T_3\to (T_1\cup T_2\cup T_3)\times (T_1\cup T_2\cup T_3),}\)
korzystając wyłącznie z tego, że funkcja \(\displaystyle{ g}\) zapewnia nam istnienie bijekcji pomiędzy \(\displaystyle{ g_L}\) i \(\displaystyle{ g_L\times g_L}\) (co oczywiście łatwo przenosi się na dowolne zbiory równoliczne z \(\displaystyle{ g_L}\)).

To już wydaje mi się bardzo proste
Dla przykładu udowodnię, że \(\displaystyle{ T _{3}\sim \left( T_{1}\cup T_{2}\cup T_{3} \right)\times \left( T_{1}\cup T_{2}\cup T_{3} \right)}\).

Mamy \(\displaystyle{ T _{3}\sim g_{L}\sim g _{L} \times g_{L}}\), ponieważ \(\displaystyle{ \left( T_{1}\cup T_{2}\cup T_{3} \right)\sim g _{L}}\) (suma zbiorów równolicznych z \(\displaystyle{ g_{L}}\) jest równoliczna z \(\displaystyle{ g_{L}}\) ), więc \(\displaystyle{ \left( T_{1}\cup T_{2}\cup T_{3} \right)\sim g _{L}}\) a zatem \(\displaystyle{ g _{L} \times g_{L}\sim \left( T_{1}\cup T_{2}\cup T_{3} \right)\times \left( T_{1}\cup T_{2}\cup T_{3} \right),}\) i w efekcie \(\displaystyle{ T _{3}\sim \left( T_{1}\cup T_{2}\cup T_{3} \right)\times \left( T_{1}\cup T_{2}\cup T_{3} \right)}\).

Mamy zatem trzy pary zbiorów równolicznych, więc ustalmy wspomniane wcześniej trzy bijekcję \(\displaystyle{ f_{1}, f_{2},f_{3}}\) pomiędzy powyższymi zbiorami.

Wtedy funkcja \(\displaystyle{ h=g_L\cup f_1\cup f_2\cup f_3}\) zapewnia nam żądaną sprzeczność z maksymalnością \(\displaystyle{ g}\).

Należy pokazać, że funkcja \(\displaystyle{ f=g\cup f_1\cup f_2\cup f_3}\), najpierw, że \(\displaystyle{ f}\) należy do rodziny funkcji \(\displaystyle{ \mathbb{X}}\). Taka funkcja jest bijekcją, jako suma bijekcji określonych na rozłącznych zbiorach, i mających rozłączne zbiory wartości. Przeprowadza \(\displaystyle{ g_{L} \cup T _{1} \cup T_{2} \cup T_{3}}\) w (dodajemy dziedziny i zbiory wartości (a więc w ostatnim przeciwdziedziny)), czyli jest o wartościach w :

\(\displaystyle{ \left( g_{L} \times g_{L}\right) \cup \left[ (T_1\cup T_2\cup T_3)\times g_L\right] \cup \left[ g_L\times(T_1\cup T_2\cup T_3)\right] \cup \left[ (T_1\cup T_2\cup T_3)\times (T_1\cup T_2\cup T_3)\right]= \ = \left( g_{L} \cup T _{1} \cup T_{2} \cup T_{3}\right) \times \left( g_{L} \cup T _{1} \cup T_{2} \cup T_{3}\right)}\) - Stosujemy rozdzielność mnożenia kartezjańskiego względem sumy zbiorów. Stąd już łatwo otrzymujemy \(\displaystyle{ f\in\mathbb{X},}\) i \(\displaystyle{ f\supsetneq g.}\) \(\displaystyle{ \square}\)

Skoro zakończyłem problem, to ja na deser spróbuję udowodnić (bo tego jeszcze chyba nie robiłem, a jest to przydatny fakt), że suma bijekcji \(\displaystyle{ f _{1} : X_{1} \rightarrow Y _{1}}\) \(\displaystyle{ f _{2} : X_{2} \rightarrow Y _{2}}\), gdzie zbiory \(\displaystyle{ X_{1},X_{2}}\) są rozłączne oraz zbiory \(\displaystyle{ Y_{1},Y_{2}}\) są rozłączne, taka suma \(\displaystyle{ f= f_{1} \cup f_{2}}\) jest bijekcją z \(\displaystyle{ X= X _{1} \cup X_{2}}\) w \(\displaystyle{ Y= Y _{1} \cup Y_{2}.}\)

Ponieważ \(\displaystyle{ f_{1} \subset X_{1} \times Y _{1} \subset \left( X _{1} \cup X_{2}\right) \times Y_{1} \subset \left( X _{1} \cup X_{2}\right) \times \left( Y_{1} \cup Y_{2}\right) = X\times Y.}\) Zatem \(\displaystyle{ f_{1} \subset X\times Y.}\) Podobnie możemy uzasadnić, że \(\displaystyle{ f_{2} \subset X_{2} \times Y _{2} \subset X \times Y,}\) Zatem również \(\displaystyle{ f= f_{1} \cup f_{2} \subset X \times Y}\).

Ponieważ \(\displaystyle{ X_{1} \cap X_{2}= \emptyset}\) wnioskujemy, że \(\displaystyle{ f}\) jest funkcją.
Pokażemy, że jest 'na' \(\displaystyle{ Y=Y_1 \cup Y_2.}\) Niech \(\displaystyle{ y\in Y}\). Jeśli \(\displaystyle{ y\in Y_1}\), to ponieważ \(\displaystyle{ f _{1} : X_{1} \rightarrow Y _{1}}\) jest bijekcją, a więc jest 'na' \(\displaystyle{ Y_1}\), to \(\displaystyle{ y=f_1\left( x\right)}\), gdzie \(\displaystyle{ x\in X_{1},}\) lub inaczej mówiąc \(\displaystyle{ \left( x,y\right) \in f_1}\), a więc tymbardziej \(\displaystyle{ \left( x,y\right) \in f= f_{1} \cup f_{2}}\), inaczej mówiąc \(\displaystyle{ y=f\left( x\right)}\), czyli \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ f}\). W przeciwnym przypadku \(\displaystyle{ y\in Y_2}\) analogicznie uzasadniamy, że \(\displaystyle{ y}\) jest wartością funkcji \(\displaystyle{ f}\). Zatem \(\displaystyle{ f}\) jest 'na'.

Pokażemy, że \(\displaystyle{ f}\) jest różnowartościowa. Weźmy dowolne różne argumenty \(\displaystyle{ x _{1},x _{2}\in X=X _{1} \cup X_{2}.}\) Jeśli \(\displaystyle{ x _{1},x _{2}\in X _{1}}\), ponieważ\(\displaystyle{ f _{1} : X_{1} \rightarrow Y _{1}}\) jest różnowartościowa, to \(\displaystyle{ f _{1}\left( x _{1}\right)=:y_{1} \neq y_{2} :=f _{1}\left( x _{2}\right)}\), równoważnie \(\displaystyle{ \left( x _{1}, y_{1} \right) \in f _{1}}\) i \(\displaystyle{ \left( x _{2}, y_{2} \right) \in f _{1}}\). Ponieważ \(\displaystyle{ f _{1} \subset f}\), to pary \(\displaystyle{ \left( x _{1}, y_{1} \right) \in f}\) i \(\displaystyle{ \left( x _{2}, y_{2} \right) \in f}\), czyli \(\displaystyle{ f\left( x _{1}\right) =y_{1} \neq y_{2}=f\left( x _{2}\right).}\)
Jeśli \(\displaystyle{ x _{1},x _{2}\in X _{2}}\), rozumujemy analogicznie.
Jeśli \(\displaystyle{ x _{1}\in X _{1},x _{2}\in X _{2}}\), wtedy oczywiście \(\displaystyle{ f _{1}\left( x _{1}\right)=:y_{1} \in Y_{1}}\) oraz \(\displaystyle{ f _{2}\left( x _{2}\right)=:y_{2} \in Y_{2}}\). Ponieważ zbiory \(\displaystyle{ Y_{1}, Y_{2}}\) są rozłączne, to wartości \(\displaystyle{ y_{1},y_{2}}\) są różne. Mamy \(\displaystyle{ \left( x _{1}, y_{1} \right) \in f _{1}}\) i \(\displaystyle{ \left( x _{2}, y_{2} \right) \in f _{2}}\), ponieważ \(\displaystyle{ f= f_{1} \cup f _{2}}\), to obie pary należą do funkcji \(\displaystyle{ f}\), czyli \(\displaystyle{ \left( x _{1}, y_{1} \right) \in f}\) i \(\displaystyle{ \left( x _{2}, y_{2} \right) \in f}\), inaczej mówiąc \(\displaystyle{ f\left( x _{1}\right) =y_{1} \neq y_{2}=f\left( x _{2}\right).}\)
Jeśli \(\displaystyle{ x _{1}\in X _{2},x _{2}\in X _{1},}\) to rozumujemy analogicznie. Zatem \(\displaystyle{ f}\) jest różnowartościowa. Zatem \(\displaystyle{ f}\) jest bijekcją.\(\displaystyle{ \square}\)

[Dasio11]

Chodziło mi jak z równości \(\displaystyle{ \stackrel{ \rightarrow }{f}\left( A \cap B\right)=\stackrel{ \rightarrow }{f}\left( A\right) \cap \stackrel{ \rightarrow }{f}\left( B\right)}\) (dla funkcji różnowartościowej) ma wynikać, że wtedy obrazy zbiorów rozłącznych są zawsze rozłączne.

No jeśli \(\displaystyle{ A \cap B = \varnothing}\), to \(\displaystyle{ f[A] \cap f = \ldots}\)

Twoja końcówka dowodu jest OK.

Cały fragment od otrzymania elementu maksymalnego z lematu Kuratowskego-Zorna można nieformalnie podsumować następująco: mamy maksymalny podzbiór \(\displaystyle{ Y \subseteq X}\) taki, że \(\displaystyle{ Y \sim Y \times Y}\). Jeśli \(\displaystyle{ Y \sim X}\), to OK. W przeciwnym razie w \(\displaystyle{ X \setminus Y}\) znajdujemy podzbiór równoliczny z \(\displaystyle{ Y}\). Skoro \(\displaystyle{ |Y| = |Y^2|}\), to brutalną arytmetyką otrzymujemy, że również \(\displaystyle{ |Y| = |3Y^2|}\), a więc \(\displaystyle{ |2Y| = |Y| + |Y| = |Y^2| + |3Y^2| = |4Y^2| = \left| (2Y)^2 \right|}\), a co więcej bijekcja świadcząca o tej równoliczności przedłuża oryginalną bijekcję \(\displaystyle{ Y \to Y \times Y}\), zatem "\(\displaystyle{ Y \subsetneq 2Y}\)" daje sprzeczność z maksymalnością \(\displaystyle{ Y}\).

[Jakub Gurak]

Przedstawię parę wniosków z tego twierdzenia.

Suma dwóch zbiorów rozłącznych gdzie przynajmniej jeden z nich jest nieskończony ma moc równą mocy większego (słabo) z tych dwóch zbiorów.

Podobnie moc iloczynu kartezjańskiej dwóch zbiorów, gdzie przynajmniej jeden z nich jest nieskończony, a mniejszy z nich (może być skończony ) ale gdy jest niepusty, to wtedy moc takiego iloczynu kartezjańskiego jest równa mocy większego (słabo) tych dwóch zbiorów.

(W języku liczb kardynalnych: suma dwóch liczb kardynalnych gdzie przynajmniej jedna z nich jest nieskończona jest równa większej z nich; podobnie iloczyn dwóch liczb kardynalnych gdzie przynajmniej jedna z nich jest nieskończona, a mniejsza z nich jest różna od 0 jest równy większej z nich).

Dowód:

Niech X, Y będą zbiorami rozłącznymi, tak że co najmniej jeden z nich jest nieskończony. Załóżmy. ze X jest niemniejszy (względem mocy) od Y. Wtedy X jest nieskończony (można udowadniać, że zbiór większy na moc od nieskończonego jest nieskończony ). Jeśli zbiór \(\displaystyle{ Y}\) jest pusty, to teza jest oczywista. Załóżmy więc, że \(\displaystyle{ Y \neq \left\{ \right\}.}\) Korzystamy z twierdzenia Cantora-Bernsteina:

Ponieważ \(\displaystyle{ X \subset X \cup Y,}\) więc \(\displaystyle{ \left| X \cup Y\right| \ge \left| X\right| .}\)

W drugą stronę:

\(\displaystyle{ \left| X \cup Y\right| =\left| X \times \left\{ 0\right\} \cup Y \times \left\{ 1\right\} \right| \le \left| X \times \left\{ 0\right\} \cup X \times \left\{ 1\right\} \right| =\left| X \times \left\{ 0,1\right\} \right| \le \left| X \times X\right| =\left| X\right|.}\)

Ostatnia równość mocy wynika z tego, że zbiór \(\displaystyle{ X}\) jest nieskończony i twierdzenia Hessenberga. A więc \(\displaystyle{ \left| X \cup Y\right| \le \left| X\right|}\), i na mocy twierdzenia Cantora-Bernsteina zbiór \(\displaystyle{ X \cup Y}\) jest równoliczny z \(\displaystyle{ X.}\)

Druga część:

Niech X,Y będą zbiorami, tak że co najmniej jeden z nich jest nieskończony, i oba nie są puste. Załóżmy, że X jest większej lub równej mocy od Y. Wtedy X jest nieskończony, a więc na mocy twierdzenia Hessenberga \(\displaystyle{ \left| X \times X\right|=\left| X\right|.}\) Pokażemy, korzystając z twierdzenia Cantora-Bernsteina, że \(\displaystyle{ X \times Y\sim X.}\)

Oczywiście \(\displaystyle{ \left| X \times Y\right| \ge \left| X \times \left\{ 0\right\} \right| =\left| X\right|}\)(korzystając z niepustości Y). W drugą stronę:

Ponieważ \(\displaystyle{ \left| X\right| \ge \left| Y\right|,}\) więc \(\displaystyle{ \left| X \times Y\right| \le \left| X \times X\right|.}\) wystarczy ustalić funkcję różnowartościową \(\displaystyle{ f:Y \rightarrow X,}\) I aby pokazać że \(\displaystyle{ \left| X \times Y\right| \le \left| X \times X\right|}\) definiujemy funkcję \(\displaystyle{ g:X \times Y \rightarrow X \times X}\) jako:

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

Ponieważ f jest różnowartościową, to łatwo sprawdzić, że g również jest różnowartościowa, a więc \(\displaystyle{ \left| X \times Y\right| \le \left| X \times X\right| =\left| X\right|.}\)

Na mocy twierdzenia Cantora-Bernsteina zbiór \(\displaystyle{ X \times Y}\) jest równoliczny z \(\displaystyle{ X.\square}\)

Można też zobaczyć tu: Ilość funkcji z X do X

[Jakub Gurak]

Kolejny wniosek z twierdzenia Hessenberga (który dzisiaj udowodniłem):

Jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to rodzina jego wszystkich podzbiorów skończonych jest równoliczna ze zbiorem \(\displaystyle{ X}\).

Lemat 1: Jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, a zbiory \(\displaystyle{ X_0,X_1,X_2,\ldots}\) są równoliczne z \(\displaystyle{ X}\), to również suma \(\displaystyle{ \bigcup_{n\in\NN} X_n}\) jest równoliczna z \(\displaystyle{ X}\).

Wynika to z twierdzenia Hessenberga (i twierdzenia Cantora-Bernsteina).

Lemat 2. Ustalmy dowolne \(\displaystyle{ n}\) naturalne dodatnie. Niech zbiór \(\displaystyle{ X}\) będzie nieskończony. Wtedy zbiór wszystkich ciągów \(\displaystyle{ n}\)-elementowych o elementach z \(\displaystyle{ X}\) jest równoliczny z \(\displaystyle{ X}\).

SZKIC DOWODU:    

Stosujemy zasadę indukcji matematycznej ze względu na ilość elementów ciągu (długość ciągu).

Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym.

Jeśli \(\displaystyle{ n=1}\), to oczywiście zbiór jednoelementowych ciągów o elemencie z \(\displaystyle{ X}\) jest równoliczny z \(\displaystyle{ X}\).

Krok indukcyjny: Załóżmy, że zbiór wszystkich ciągów \(\displaystyle{ n}\)-elementowych (\(\displaystyle{ n \ge 1}\))o elementach z \(\displaystyle{ X}\) jest równoliczny z \(\displaystyle{ X}\). Pokażemy, że również zbiór wszystkich ciągów \(\displaystyle{ (n+1)}\)-elementowych jest równoliczny z \(\displaystyle{ X.}\) Łatwo zauważyć, że \(\displaystyle{ \left\{ \left( x_1,x_2,\ldots,x_n,x_n+1\right)\Bigl| \ x_i\in X \right\}\sim \left\{ \left( x_1,x_2,\ldots,x_n\right)\Bigl| \ \ x_i\in X \right\} \times X. }\) Ostatni zbiór na mocy założenia indukcyjnego jest równoliczny z \(\displaystyle{ X \times X}\), który to zbiór na mocy twierdzenia Hessenberga jest równoliczny z \(\displaystyle{ X}\). Otrzymujemy zatem, że zbiór ciągów \(\displaystyle{ (n+1)}\)elementowych jest równoliczny ze zbiorem \(\displaystyle{ X}\). Krok indukcyjny został dowiedziony.

Zasada indukcji matematycznej, pozwala (oraz inne proste chwyty) pozwala zakończyć dowód lematu.

Lemat 3. Jeśli zbiór \(\displaystyle{ X}\) jest nieskończony, to zbiór wszystkich skończonych ciągów z \(\displaystyle{ X}\) jest równoliczny z \(\displaystyle{ X}\) (prosty wniosek z lematu 1 i lematu 2).


Przechodzimy do dowodu głównego twierdzenia:

Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym. A \(\displaystyle{ B}\) zbiorem wszystkich skończonych ciągów z \(\displaystyle{ X}\), a \(\displaystyle{ C}\) rodziną wszystkich skończonych podzbiorów zbioru \(\displaystyle{ X}\). Rozważmy funkcję \(\displaystyle{ f:B \rightarrow C}\), która skończonemu ciągowi \(\displaystyle{ a}\) przypisuje zbiór jego wyrazów \(\displaystyle{ a_P}\). Wtedy \(\displaystyle{ a_P}\) jest zbiorem skończonym, a więc \(\displaystyle{ a_P \in C.}\) Pokażemy, że taka funkcja jest 'na'. Niech \(\displaystyle{ Y\in C}\), wtedy \(\displaystyle{ Y}\) jest skończonym podzbiorem zbioru \(\displaystyle{ X}\). Ponieważ \(\displaystyle{ Y}\) jest zbiorem skończonym, to \(\displaystyle{ Y}\) jest równoliczny z pewną liczbą naturalną von Neumanna \(\displaystyle{ n}\). Ponieważ zbiory \(\displaystyle{ n}\) i \(\displaystyle{ Y}\) są równoliczne, to istnieje bijekcja \(\displaystyle{ g:n \rightarrow Y}\), wtedy \(\displaystyle{ Y\subset X}\), skąd \(\displaystyle{ g:n \rightarrow X}\) jest ciągiem skończonym, i \(\displaystyle{ g_P=Y}\)- bo \(\displaystyle{ g}\) jest bijekcją z \(\displaystyle{ n}\) do \(\displaystyle{ Y}\). A zatem \(\displaystyle{ f(g)=g_P=Y}\), a więc zbiór \(\displaystyle{ Y}\) jest wartością funkcji \(\displaystyle{ f}\). Z dowolności wyboru takiego zbioru otrzymujemy, że \(\displaystyle{ f}\) jest 'na'. A zatem \(\displaystyle{ \left| C\right| \le \left| B\right|}\). Z lematu 3 mamy, że \(\displaystyle{ \left| B\right|=\left| X\right|.}\) A zatem \(\displaystyle{ \left| C\right| \le \left| X\right|}\). Mamy również \(\displaystyle{ \left| C\right| \ge \left| X\right|}\), gdyż \(\displaystyle{ C\supset \left\{ \left\{ x\right\}\Bigl| \ \ x\in X \right\}\sim X.}\) A zatem z twierdzenia Cantora-Bernsteina \(\displaystyle{ \left| C\right|=\left| X\right|. \square}\)

Bardzo ciekawym wnioskiem z twierdzenia Hessenberga jest twierdzenie mówiące, że każdy zbiór nieskończony \(\displaystyle{ X}\) może być podzielony na każdą ilość (ograniczoną) przez wielkość zbioru \(\displaystyle{ X}\) równolicznych podzbiorów( zbiory skończone takich własności na ogół nie mają), co zostało udowodnione tu: CIEKAWY PROBLEM