Każdy zbiór nieskończony podzielić na równoliczne podzbiory.
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Każdy zbiór nieskończony podzielić na równoliczne podzbiory.
Temat wywodzi się z problemu:
Czy każdy zbiór nieskończony można podzielić na dwa równoliczne podzbiory
To intuicyjne twierdzenie ma nieco inny dowód niż podpowiada intuicja, ale już nie taki trudny. Moja praca jest uogólnieniem tego zadania.
Będziemy potrzebowali dwóch prostych lematów.
LEMAT 1. Jeśli \(\displaystyle{ g:A \rightarrow B}\) jest bijekcją, oraz \(\displaystyle{ C \subset B}\), to \(\displaystyle{ C\sim \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right)}\).
Ilustracja:
Szkic dowodu:
Definiujemy bijekcję \(\displaystyle{ h: \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right) \rightarrow C}\), jako: \(\displaystyle{ h\left( x\right) =g\left( x\right).}\)
Funkcja \(\displaystyle{ h}\) jest dobrze zdefiniowana, bo jeśli \(\displaystyle{ x\in h_{L}= \stackrel{ \rightarrow }{g^{-1}} \left( C \right)}\), to \(\displaystyle{ h\left( x\right) =g\left( x\right) \in C}\).
Ponieważ, \(\displaystyle{ g}\) jest bijekcją, czyli jest różnowartościowa i 'na', to bardzo łatwo pokazać, że \(\displaystyle{ h}\) jest różnowartościowa, i, nieco trudniej, że \(\displaystyle{ h}\) jest 'na' \(\displaystyle{ C}\), a więc jest bijekcją między \(\displaystyle{ \stackrel{ \rightarrow }{g^{-1}} \left( C \right)}\) a \(\displaystyle{ C}\), czyli \(\displaystyle{ C \sim \ \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right). \square}\)
LEMAT 2. Jeśli \(\displaystyle{ g: A \rightarrow B}\) jest bijekcją, oraz mamy zbiory \(\displaystyle{ B_{1}, B_{2} \subset B}\), takie, że \(\displaystyle{ B_{1} \sim B_{2}}\), to wtedy \(\displaystyle{ \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right) \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right)}\).
Dowód:
Dowód jest natychmiastowym wnioskiem z LEMATU 1. Funkcja \(\displaystyle{ g}\) oraz zbiór \(\displaystyle{ B_{1}}\) spełniają założenia LEMATU 1, więc \(\displaystyle{ B_{1} \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right)}\). Stosując LEMAT 1 jeszcze raz, tym razem do zbioru \(\displaystyle{ B_{2}}\), otrzymujemy, że \(\displaystyle{ B_{2} \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right)}\). Mamy również założenie, że \(\displaystyle{ B_{1} \sim B_{2}}\). Z przechodniości równoliczności otrzymujemy, że \(\displaystyle{ \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right) \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right).\square}\)
Łatwo teraz będzie udowodnić , że każdy zbiór nieskończony można podzielić na dwa równoliczne podzbiory.
Oto dowód:
Rozpoczynając dowód, ustalmy dowolny zbiór nieskończony \(\displaystyle{ X}\). Ponieważ jest nieskończony, to \(\displaystyle{ X \times \left\{ 0,1\right\}}\) jest równoliczny z \(\displaystyle{ X}\). Istnieje więc bijekcja \(\displaystyle{ f: X\rightarrow X \times \left\{ 0,1\right\}}\). Mając ją, rozważmy zbiory: \(\displaystyle{ \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 0\right\} \right) \hbox{ oraz } \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 1\right\} \right).}\)
Zbiory te są rozłączne, jako przeciwobrazy zbiorów rozłącznych \(\displaystyle{ X \times \left\{ 0\right\}}\) oraz \(\displaystyle{ X \times \left\{ 1\right\}.}\) Zbiory te sumują się do \(\displaystyle{ X}\), gdyż:
\(\displaystyle{ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 0\right\} \right) \cup \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 1\right\} \right)=\stackrel{ \rightarrow }{f^{-1}} \Bigl( \left( X \times \left\{ 0\right\}\right) \cup \left( X \times \left\{ 1\right\}\right) \Bigr)=\stackrel{ \rightarrow }{f^{-1}}\left( X \times \left\{ 0,1\right\} \right)=X.}\) Aj ten Latex
A więc zbiory te tworzą rozkład zbioru \(\displaystyle{ X}\). Pozostaje pokazać, że są równoliczne.
Niewątpliwie \(\displaystyle{ X\sim X \times \left\{ 0\right\}}\), oraz \(\displaystyle{ X\sim X \times \left\{ 1\right\}}\). Zbiory \(\displaystyle{ X \times \left\{ 0\right\}, X \times \left\{ 1\right\}}\) są równoliczne, więc na mocy LEMATU 2 odpowiadające im przeciwobrazy poprzez bijekcję \(\displaystyle{ f}\), czyli \(\displaystyle{ \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 0\right\} \right) \hbox{ i } \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 1\right\} \right)}\) są równoliczne, co kończy dowód.\(\displaystyle{ \square}\)
Podział na \(\displaystyle{ n}\) zbiorów równolicznych łatwo zrobić indukcyjnie. Zdefiniowałem pojęcie które jest uogólnieniem tego rozkładu zbioru na ilość nieskończoną, i to udowodniłem, tzn. że każdy zbiór nieskończony można podzielić na dowolną ilość ( ograniczoną przez wielkość zbioru nieskończonego \(\displaystyle{ X}\)) równolicznych podzbiorów. :lol: Dowód jest analogiczny, ale to już nie dziś.
Czy każdy zbiór nieskończony można podzielić na dwa równoliczne podzbiory
To intuicyjne twierdzenie ma nieco inny dowód niż podpowiada intuicja, ale już nie taki trudny. Moja praca jest uogólnieniem tego zadania.
Będziemy potrzebowali dwóch prostych lematów.
LEMAT 1. Jeśli \(\displaystyle{ g:A \rightarrow B}\) jest bijekcją, oraz \(\displaystyle{ C \subset B}\), to \(\displaystyle{ C\sim \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right)}\).
Ilustracja:
Szkic dowodu:
Definiujemy bijekcję \(\displaystyle{ h: \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right) \rightarrow C}\), jako: \(\displaystyle{ h\left( x\right) =g\left( x\right).}\)
Funkcja \(\displaystyle{ h}\) jest dobrze zdefiniowana, bo jeśli \(\displaystyle{ x\in h_{L}= \stackrel{ \rightarrow }{g^{-1}} \left( C \right)}\), to \(\displaystyle{ h\left( x\right) =g\left( x\right) \in C}\).
Ponieważ, \(\displaystyle{ g}\) jest bijekcją, czyli jest różnowartościowa i 'na', to bardzo łatwo pokazać, że \(\displaystyle{ h}\) jest różnowartościowa, i, nieco trudniej, że \(\displaystyle{ h}\) jest 'na' \(\displaystyle{ C}\), a więc jest bijekcją między \(\displaystyle{ \stackrel{ \rightarrow }{g^{-1}} \left( C \right)}\) a \(\displaystyle{ C}\), czyli \(\displaystyle{ C \sim \ \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right). \square}\)
LEMAT 2. Jeśli \(\displaystyle{ g: A \rightarrow B}\) jest bijekcją, oraz mamy zbiory \(\displaystyle{ B_{1}, B_{2} \subset B}\), takie, że \(\displaystyle{ B_{1} \sim B_{2}}\), to wtedy \(\displaystyle{ \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right) \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right)}\).
Dowód:
Dowód jest natychmiastowym wnioskiem z LEMATU 1. Funkcja \(\displaystyle{ g}\) oraz zbiór \(\displaystyle{ B_{1}}\) spełniają założenia LEMATU 1, więc \(\displaystyle{ B_{1} \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right)}\). Stosując LEMAT 1 jeszcze raz, tym razem do zbioru \(\displaystyle{ B_{2}}\), otrzymujemy, że \(\displaystyle{ B_{2} \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right)}\). Mamy również założenie, że \(\displaystyle{ B_{1} \sim B_{2}}\). Z przechodniości równoliczności otrzymujemy, że \(\displaystyle{ \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right) \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right).\square}\)
Łatwo teraz będzie udowodnić , że każdy zbiór nieskończony można podzielić na dwa równoliczne podzbiory.
Oto dowód:
Rozpoczynając dowód, ustalmy dowolny zbiór nieskończony \(\displaystyle{ X}\). Ponieważ jest nieskończony, to \(\displaystyle{ X \times \left\{ 0,1\right\}}\) jest równoliczny z \(\displaystyle{ X}\). Istnieje więc bijekcja \(\displaystyle{ f: X\rightarrow X \times \left\{ 0,1\right\}}\). Mając ją, rozważmy zbiory: \(\displaystyle{ \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 0\right\} \right) \hbox{ oraz } \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 1\right\} \right).}\)
Zbiory te są rozłączne, jako przeciwobrazy zbiorów rozłącznych \(\displaystyle{ X \times \left\{ 0\right\}}\) oraz \(\displaystyle{ X \times \left\{ 1\right\}.}\) Zbiory te sumują się do \(\displaystyle{ X}\), gdyż:
\(\displaystyle{ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 0\right\} \right) \cup \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 1\right\} \right)=\stackrel{ \rightarrow }{f^{-1}} \Bigl( \left( X \times \left\{ 0\right\}\right) \cup \left( X \times \left\{ 1\right\}\right) \Bigr)=\stackrel{ \rightarrow }{f^{-1}}\left( X \times \left\{ 0,1\right\} \right)=X.}\) Aj ten Latex
A więc zbiory te tworzą rozkład zbioru \(\displaystyle{ X}\). Pozostaje pokazać, że są równoliczne.
Niewątpliwie \(\displaystyle{ X\sim X \times \left\{ 0\right\}}\), oraz \(\displaystyle{ X\sim X \times \left\{ 1\right\}}\). Zbiory \(\displaystyle{ X \times \left\{ 0\right\}, X \times \left\{ 1\right\}}\) są równoliczne, więc na mocy LEMATU 2 odpowiadające im przeciwobrazy poprzez bijekcję \(\displaystyle{ f}\), czyli \(\displaystyle{ \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 0\right\} \right) \hbox{ i } \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ 1\right\} \right)}\) są równoliczne, co kończy dowód.\(\displaystyle{ \square}\)
Podział na \(\displaystyle{ n}\) zbiorów równolicznych łatwo zrobić indukcyjnie. Zdefiniowałem pojęcie które jest uogólnieniem tego rozkładu zbioru na ilość nieskończoną, i to udowodniłem, tzn. że każdy zbiór nieskończony można podzielić na dowolną ilość ( ograniczoną przez wielkość zbioru nieskończonego \(\displaystyle{ X}\)) równolicznych podzbiorów. :lol: Dowód jest analogiczny, ale to już nie dziś.
-
- Administrator
- Posty: 34276
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Każdy zbiór nieskończony podzielić na równoliczne podzbi
Jakub Gurak lubi samodzielnie odkrywać matematykę (ew. przy pomocy ważniaka), stąd te drobiazgowe dowody (z dużą liczbą przymiotników), wymyślanie rzeczy znanych itp. Widocznie uznał Twój post za dalece niewystarczający szkic dowodu...a4karo pisze:I mówisz, że taką pracę napisałeś?
Proponowałem mu kiedyś, żeby poczytał coś innego niż ważniak, ale chyba na razie trzyma się swojej drogi.
JK
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Każdy zbiór nieskończony podzielić na równoliczne podzbiory.
Tak, ale to zajmuję (łącznie z tym co już przedstawiłem) jedynie dwie i pół kartki.a4karo pisze:I mówisz, że taką pracę napisałeś?
Niech \(\displaystyle{ X \neq \left\{ \right\}}\) będzie niepustym zbiorem, a \(\displaystyle{ \left\{ \right\} \neq M \subset X}\) jego niepustym podzbiorem. Ilorazem \(\displaystyle{ X/M}\) zbioru \(\displaystyle{ X}\) przez podzbiór \(\displaystyle{ M}\), to \(\displaystyle{ \mathbb{A}\in P\left( P\left( X\right) \right)}\) rodzina podzbiorów \(\displaystyle{ X}\), taka że:
1. \(\displaystyle{ \mathbb{A}}\) jest rozkładem zbioru \(\displaystyle{ X.}\)
2. \(\displaystyle{ \mathbb{A}\sim M.}\)
3. \(\displaystyle{ A,B\in \mathbb{A} \Longrightarrow A\sim B.}\)
Przykład: Niech \(\displaystyle{ X=\NN}\). \(\displaystyle{ M=\NN}\).
Rodzina zbiorów \(\displaystyle{ \left\{ \left\{ 0,1\right\},\left\{ 2,3\right\},\left\{ 4,5\right\},\ldots \right\}=\left\{ \left\{ 2n, 2n+1\right\} \Bigl| \ n\in \NN\right\}}\) jest niewątpliwie rozkładem \(\displaystyle{ \NN}\) na nieskończoną ilość zbiorów równolicznych ( zbiory dwuelementowe są równoliczne). A więc jest to iloraz \(\displaystyle{ \NN}\) przez \(\displaystyle{ M=\NN}\).
I teraz główne twierdzenie:
Jeśli \(\displaystyle{ X}\) jest dowolnym zbiorem nieskończonym, a \(\displaystyle{ M}\) jego dowolnym niepustym podzbiorem, to istnieje iloraz \(\displaystyle{ X/M}\).
DOWÓD (NIETRUDNY):
Jeśli \(\displaystyle{ M}\) jest jednoelementowy, czyli \(\displaystyle{ M=\left\{ a\right\}}\) , to \(\displaystyle{ \left\{ X\right\}}\) jest poszukiwanym ilorazem. Jest to rozkład zbioru \(\displaystyle{ X}\) (niewłaściwy),\(\displaystyle{ \left\{ X\right\}\sim M=\left\{ a\right\}}\), i spełniony jest punkt 3 poprzez \(\displaystyle{ X\sim X}\). A więc jest to poszukiwany iloraz.
Jeśli \(\displaystyle{ M}\) jest dwuelementowy, to wykazałem to wcześniej. Jeśli \(\displaystyle{ M}\) jest \(\displaystyle{ n}\)-elementowy, to łatwo to zrobić indukcyjnie- zobacz tu: https://www.matematyka.pl/429421.htm
Pozostają zbiory \(\displaystyle{ M}\) nieskończone. Jeśli \(\displaystyle{ M}\) jest równoliczny z \(\displaystyle{ X}\), to \(\displaystyle{ \mathbb{A}=\left\{ \left\{ x\right\} \Bigl| \ x\in X \right\}}\) jest poszukiwanym ilorazem. Jest to niewątpliwie rozkład zbioru \(\displaystyle{ X}\), \(\displaystyle{ \mathbb{A}\sim X\sim M}\), a więc \(\displaystyle{ \mathbb{A}\sim M}\), oraz każde dwa zbiory rodziny \(\displaystyle{ \mathbb{A}}\) są równoliczne ( jako jednoelementowe).
Pozostają zbiory \(\displaystyle{ M}\) nieskończone, nierównoliczne z \(\displaystyle{ X}\). Wtedy:
\(\displaystyle{ X \le \left| X \times M\right| \le \left| X \times X\right| =\left| X\right|}\) . Ostatnia równość mocy wynika stąd, że zbiór \(\displaystyle{ X}\) jest nieskończony. W takim razie z tw. Cantora-Bernsteina \(\displaystyle{ X \times M\sim X}\). Niech więc \(\displaystyle{ f}\) będzie bijekcją między \(\displaystyle{ X}\) a \(\displaystyle{ X \times M}\).
Rozważmy rodzinę podzbiorów \(\displaystyle{ X}\):
\(\displaystyle{ \mathbb{A}=\left\{ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ m\right\} \right) \Bigl| \ m\in M\right\} =\left\{ Y \subset X\Bigl| \ \bigvee\limits_{m\in M} \ \ Y=\stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ m\right\} \right)\right\}}\).
Łatwo pokazać, że zbiory w tej rodzinie są rozłączne. Zbiory te sumują się do \(\displaystyle{ X}\), gdyż:
\(\displaystyle{ \bigcup_{m\in M} \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ m\right\} \right)= \stackrel{ \rightarrow }{f^{-1}} \left( \bigcup_{m\in M} X \times \left\{ m\right\} \right) =\stackrel{ \rightarrow }{f^{-1}} \left( X \times M\right) =X.}\)
A więc zbiory te tworzą rozkład zbioru \(\displaystyle{ X}\). \(\displaystyle{ \mathbb{A}\sim M}\), bo wystarczy przyporządkować: \(\displaystyle{ m\in M \stackrel {h}{ \rightarrow } \ \ \stackrel{ \rightarrow }{f^{-1}} \left( X \times \left\{ m\right\} \right).}\) Łatwo pokazać, że jest to bijekcja,. a więc \(\displaystyle{ \mathbb{A}\sim M}\). Każde dwa różne zbiory tej rodziny są równoliczne- wynika to w analogiczny sposób jak dla rozkładu na dwa zbiory z LEMATU 2.
W ten oto prosty sposób spełnione są wszystkie wymagania stawiane w definicji ilorazu zbioru przez zbiór, a więc \(\displaystyle{ \mathbb{A}}\) jest ilorazem zbioru \(\displaystyle{ X}\) przez podzbiór \(\displaystyle{ M}\), co kończy dowód.\(\displaystyle{ \square}\)
Dodajmy, że zbiory skończone na ogół takich własności nie mają- aby móc zbiór skończony niepusty podzielić na każdą ilość mniejszą lub równą ilości elementów w zbiorze (podzielić na zbiory równoliczne). Np. zbiór trójelementowy nie da się podzielić na dwa zbiory równoliczne. Natomiast zbiory nieskończone takie własności już mają, w myśl udowodnionego twierdzenia.
Na koniec chciałem podziękować użytkownikowi a4karo za pomysł. Bez tego sprawa mogłaby by wyglądać znacznie ciężej...
-
- Użytkownik
- Posty: 22209
- Rejestracja: 15 maja 2011, o 20:55
- Płeć: Mężczyzna
- Lokalizacja: Bydgoszcz
- Podziękował: 38 razy
- Pomógł: 3755 razy
Re: Każdy zbiór nieskończony podzielić na równoliczne podzbi
Brrrr, jakbyś to zrobił w prosty sposób, to pewnie dałoby się to przeczytać.
To teraz udowodnij, dla każdej liczby kardynalnej \(\displaystyle{ \mathfrak{n}}\) zbiór o mocy \(\displaystyle{ \mathfrak{m} \geq\mathfrak{n}}\) da się podzielić na zbiory o mocy \(\displaystyle{ \mathfrak{n}}\)
To teraz udowodnij, dla każdej liczby kardynalnej \(\displaystyle{ \mathfrak{n}}\) zbiór o mocy \(\displaystyle{ \mathfrak{m} \geq\mathfrak{n}}\) da się podzielić na zbiory o mocy \(\displaystyle{ \mathfrak{n}}\)
- Dasio11
- Moderator
- Posty: 10225
- Rejestracja: 21 kwie 2009, o 19:04
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 40 razy
- Pomógł: 2362 razy
Każdy zbiór nieskończony podzielić na równoliczne podzbiory.
Oznaczenie \(\displaystyle{ X/M}\) jest bardzo mylące, bo sugeruje, że iloraz ma jakiś związek ze zbiorem \(\displaystyle{ M,}\) a tymczasem z definicji widać, że ważna jest tylko moc \(\displaystyle{ M.}\) Dlatego lepiej byłoby to oznaczyć \(\displaystyle{ X/\kappa,}\) gdzie \(\displaystyle{ 0 < \kappa \le |X|.}\) Inna sprawa, że dla \(\displaystyle{ \kappa = |X|}\) ten zapis mógłby oznaczać zarówno podział \(\displaystyle{ X}\) na \(\displaystyle{ \kappa}\) zbiorów jednoelementowych, jak i podział na \(\displaystyle{ \kappa}\) zbiorów mocy \(\displaystyle{ \kappa}\) - czy te podziały powinny więc mieścić się pod jednym symbolem?Jakub Gurak pisze:Ilorazem \(\displaystyle{ X/M}\) zbioru \(\displaystyle{ X}\) przez podzbiór \(\displaystyle{ M}\), to \(\displaystyle{ \mathbb{A}\in P\left( P\left( X\right) \right)}\) rodzina podzbiorów \(\displaystyle{ X}\), taka że:
1. \(\displaystyle{ \mathbb{A}}\) jest rozkładem zbioru \(\displaystyle{ X.}\)
2. \(\displaystyle{ \mathbb{A}\sim M.}\)
3. \(\displaystyle{ A,B\in \mathbb{A} \Longrightarrow A\sim B.}\)
Następujący po tym cytacie dowód działa nie tylko dla zbioru \(\displaystyle{ M}\) nieskończonego, nierównolicznego z \(\displaystyle{ X,}\) ale po prostu dla każdego, który spełnia założenia Twojego stwierdzenia. Dlatego dowód mógłby zacząć się w tym miejscu.Jakub Gurak pisze:Pozostają zbiory \(\displaystyle{ M}\) nieskończone, nierównoliczne z \(\displaystyle{ X}\). Wtedy:
-
- Administrator
- Posty: 34276
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Każdy zbiór nieskończony podzielić na równoliczne podzbi
Powiem tak - jak dla mnie jedyny trudniejszy fakt w tym rozumowaniu to ten, który został tylko zacytowany, czyli że dla nieskończonego zbioru \(\displaystyle{ X}\) mamy \(\displaystyle{ X\sim X\times X}\). Reszta jest wnioskiem z tego faktu.
JK
JK
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Każdy zbiór nieskończony podzielić na równoliczne podzbi
Definicja rzeczywiście nie wyznacza w sposób jednoznaczny tego ilorazu, co mnie nie zaskakuje. Natomiast w sprawie oznaczenia \(\displaystyle{ X/M}\), to Dasio11 masz rację, zupełnie nie zwróciłem uwagi- różne obiekty nie można oznaczyć tym samym symbolem ( bo w danej sytuacji oczywiście ten sam symbol ma to samo znaczenie). Oznaczyłem sobie nieuważnie.
Też mi się wydawało, że niepotrzebnie rozpatruje przypadki (ale podzbiory \(\displaystyle{ M}\) powinny być co najmniej dwuelementowe, więc dla jednoelementowych bym sprawdził osobno) ale przeglądając dowód coś się zagubiłem, więc uznałem, że zrobię tak jak mam- rozpatrując przypadki. Wiem, niepotrzebnie...Dasio11 pisze:Następujący po tym cytacie dowód działa nie tylko dla zbioru \(\displaystyle{ M}\) nieskończonego, nierównolicznego z \(\displaystyle{ X}\), ale po prostu dla każdego, który spełnia założenia Twojego stwierdzenia. Dlatego dowód mógłby zacząć się w tym miejscu.
Tego Ci nie udowodnię, bo obawiam się, że to nieprawda- zbiór o mocy \(\displaystyle{ 3 \ge 2}\) nie da się podzielić na zbiory o mocy \(\displaystyle{ 2}\).a4karo pisze: To teraz udowodnij, dla każdej liczby kardynalnej \(\displaystyle{ \mathfrak{n}}\) zbiór o mocy \(\displaystyle{ \mathfrak{m} \geq\mathfrak{n}}\) da się podzielić na zbiory o mocy \(\displaystyle{ \mathfrak{n}}\)
-
- Administrator
- Posty: 34276
- Rejestracja: 20 mar 2006, o 21:54
- Płeć: Mężczyzna
- Lokalizacja: Wrocław
- Podziękował: 3 razy
- Pomógł: 5203 razy
Re: Każdy zbiór nieskończony podzielić na równoliczne podzbi
Idę o zakład, że jak a4karo używał gotyku, to miał na myśli nieskończone liczby kardynalne.Jakub Gurak pisze:Tego Ci nie udowodnię, bo obawiam się, że to nieprawda- zbiór o mocy \(\displaystyle{ 3 \ge 2}\) nie da się podzielić na zbiory o mocy \(\displaystyle{ 2}\).a4karo pisze:To teraz udowodnij, dla każdej liczby kardynalnej \(\displaystyle{ \mathfrak{n}}\) zbiór o mocy \(\displaystyle{ \mathfrak{m} \geq\mathfrak{n}}\) da się podzielić na zbiory o mocy \(\displaystyle{ \mathfrak{n}}\)
JK
-
- Użytkownik
- Posty: 1407
- Rejestracja: 20 lip 2012, o 21:19
- Płeć: Mężczyzna
- Lokalizacja: Rzeszów
- Podziękował: 66 razy
- Pomógł: 83 razy
Re: Każdy zbiór nieskończony podzielić na równoliczne podzbiory.
Udowodniłem pewien fakt wspomniany we "Wstępie do Teorii Mnogości i Topologii" Wacława Sierpińskiego, str. 78:
"Każdy zbiór co najmniej dwuelementowy jest sumą dwuelementowych rozłącznych podzbiorów, albo, taki zbiór, staję się taką sumą, takich podzbiorów dwuelementowych, po wyrzuceniu z niego pewnego jego jednego elementu".
(Zacytowałem tutaj ten fakt własnymi słowami, ale starałem się zachować identyczną treść).
Dla nieskończonych zbiorów \(\displaystyle{ X}\) pokazałem nawet więcej. Wykazałem, że:
Jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, to istnieje rodzina \(\displaystyle{ \mathbb{B}}\) podzbiorów zbioru \(\displaystyle{ X}\), podzbiorów dwuelementowych, rodzina zbiorów rozłącznych, taka, że: \(\displaystyle{ \bigcup\mathbb{B}=X.}\)
Dowód tego faktu wynika łatwo z tytułowego twierdzenia mówiącego, że każdy zbiór nieskończony można podzielić na dwa równoliczne podzbiory.
PROSTY DOWÓD TEGO FAKTU:
Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym.
Z twierdzenia Zermelo (równoważnego aksjomatowi wyboru), a dokładniej z tytułowego twierdzenia tego wątku wynika, ze istnieją dwa zbiory
\(\displaystyle{ X_1, X_2 \subset X}\), równoliczne, rozłączne, i takie, że w sumie dają cały zbiór \(\displaystyle{ X}\)- : \(\displaystyle{ X_1 \cup X_2=X.}\)
Ponieważ zbiory \(\displaystyle{ X_1}\) i \(\displaystyle{ X_2}\) są równoliczne, więc istnieje bijekcja \(\displaystyle{ f:X _{1} \rightarrow X_2.}\)
Rozważmy sumę:
\(\displaystyle{ \bigcup_{\left( x,y\right) \in f } \left\{ x,y\right\}.}\)
Jeśli \(\displaystyle{ \left( x,y\right) \in f}\), to \(\displaystyle{ x \in X_1 \subset X}\), i \(\displaystyle{ y \in X_2 \subset X}\), a więc \(\displaystyle{ \left\{ x,y\right\} \subset X, }\) i ponieważ zbiory \(\displaystyle{ X_1}\) i \(\displaystyle{ X_2}\) są rozłączne, to \(\displaystyle{ x \neq y}\), a więc zbiór \(\displaystyle{ \left\{ x,y\right\}}\) jest dwuelementowy, i rodzina \(\displaystyle{ \left\{ \left\{ x,y\right\}\Bigl| \ \left( x,y\right) \in f \right\}}\) jest rodziną dwuelementowych podzbiorów zbioru \(\displaystyle{ X}\). I jest to rodzina zbiorów rozłącznych, bo funkcja \(\displaystyle{ f}\) jest różnowartościowa.
I mamy:
\(\displaystyle{ \bigcup_{ \left( x,y\right) \in f } \left\{ x,y\right\} = \bigcup_{\left( x,y\right) \in f } \left( \left\{ x\right\} \cup \left\{ y\right\} \right)= \left( \bigcup_{\left( x,y\right) \in f } \left\{ x\right\} \right) \cup \left( \bigcup_{\left( x,y\right) \in f } \left\{ y\right\}\right) = f_L \cup f_P= }\)
i ponieważ funkcja \(\displaystyle{ f}\) jest funkcją 'na', więc to jest równe:
\(\displaystyle{ = X_1 \cup X_2= X.\square}\)
A jeśli zbiór \(\displaystyle{ X}\) jest skończony, co najmniej dwuelementowy, to jeśli jego moc jest liczbą parzystą, tzn. \(\displaystyle{ \left| X\right|= 2n}\), gdzie \(\displaystyle{ n \in \NN_+}\), to oznaczając jego elementy jako:
\(\displaystyle{ X= \left\{ x_1, x_2, x_3, x_4,\ldots, x _{2n-1}, x _{2n} \right\},}\)
mamy:
\(\displaystyle{ X= \bigcup_{m=1}^{n} \left\{ x _{2m-1} , x _{2m} \right\} .}\)
co należało pokazać.
A jeśli moc skończonego zbioru \(\displaystyle{ X}\) jest liczbą nieparzystą, tzn.\(\displaystyle{ \left| X\right| =2n+1}\), gdzie \(\displaystyle{ n \ge 1}\), to
\(\displaystyle{ \left| X\right| \ge 3}\), istnieje więc element \(\displaystyle{ x \in X \neq \left\{ \right\}}\). Wtedy \(\displaystyle{ \left| X \setminus \left\{ x\right\} \right|=2n}\), więc oznaczając jego elementy:
\(\displaystyle{ X \setminus \left\{ x\right\} = \left\{ x_1, x_2, x_3, x_4,\ldots, x _{2n-1}, x _{2n} \right\}}\) ,
to podobnie jak powyżej otrzymujemy:
\(\displaystyle{ X \setminus \left\{ x\right\}= \bigcup_{m=1}^{n} \left\{ x _{2m-1} , x _{2m} \right\} .\square}\)
Podział na \(\displaystyle{ n \in \NN}\) zbiorów, gdzie \(\displaystyle{ n \ge 3}\), uzyskujemy w ten sposób, że wpierw porządkujemy dobrze nieskończony zbiór \(\displaystyle{ X}\), i ustawiamy na kolejnych elementach zbioru \(\displaystyle{ X}\) przypisujemy im kolejno: \(\displaystyle{ \underbrace{1,2,3,\ldots, n}_{}, \underbrace{1,2,3,\ldots, n}_{},1,2,3\ldots,}\) podobnie jak w przypadku dla \(\displaystyle{ n=2. }\)
A jeśli zbiór \(\displaystyle{ M}\) jest nieskończony, to pomysł jest taki, aby zastosować twierdzenie Zermelo jeszcze raz, aby go dobrze uporządkować. I podobnie, na kolejnych elementach zbioru \(\displaystyle{ X}\) ustawiamy cyklicznie kolejne elementy zbioru \(\displaystyle{ M}\)- jednak powstaje tu pewna trudność, bo nie działało by to tutaj gdyby np. zbiór \(\displaystyle{ X}\) był typu \(\displaystyle{ \omega +2}\), i gdyby zbiór \(\displaystyle{ M}\) był typu \(\displaystyle{ \omega+1}\). Zrobimy to inaczej, rozważając dwa przypadki. Rozważmy więc dwa przypadki:
\(\displaystyle{ 1 ^{\circ}: M\sim X}\). Wtedy rodzina \(\displaystyle{ \left\{ \left\{ x\right\}\Bigl| \ x \in X \right\}}\) jest, jak łatwo sprawdzić, jest poszukiwanym ilorazem.
\(\displaystyle{ 2 ^{\circ}:}\) Pozostaje rozważyć przypadek, bo \(\displaystyle{ M \subset X}\), więc pozostaje rozważyć przypadek gdy moc zbioru \(\displaystyle{ M}\) jest silnie mniejsza od mocy zbioru \(\displaystyle{ X}\). Wtedy, ponieważ zbiór \(\displaystyle{ M}\) jest nieskończony, więc suma \(\displaystyle{ \left| M\right|}\) wielu zbiorów mocy \(\displaystyle{ \left| M\right|}\) jest równoliczna ze zbiorem \(\displaystyle{ M}\). I ustawiając na kolejnych elementach zbioru \(\displaystyle{ X}\) kolejne elementy zbioru \(\displaystyle{ M}\), gdy ich braknie znowu cyklicznie powtarzamy ten proces; ponieważ suma \(\displaystyle{ \left| M\right|}\) wielu zbiorów mocy \(\displaystyle{ \left| M\right|}\) jest mocy \(\displaystyle{ \left| M\right| <\left| X\right|}\), to takich cykli musimy ustawić więcej niż moc zbioru \(\displaystyle{ M}\), a więc musimy ustawić nieskończenie wiele takich cykli. Więc nawet gdyby ostatni cykl byłby zaburzony, (tzn. elementy nie byłyby rozdzielone po równo), to takie tworzone zbiory są nieskończone, bo ilość cykli (oj, ta nieskończoność, tu już mam problemy) jest nieskończona, chyba tak, a dodanie/wyrzucenie po jednym elemencie ze zbiorów nieskończonych niczego nie zmienia. I dla dowolnego ustalonego \(\displaystyle{ m \in M}\) bierzemy zbiór wszystkich elementów zbioru \(\displaystyle{ X}\), którym przypisaliśmy to \(\displaystyle{ m}\), bierzemy taki zbiór, jako zbiór rodziny, która ma być poszukiwanym ilorazem; i tak po \(\displaystyle{ m \in M}\) bierzemy takie zbiory. Oh,... na szczęście nie musimy tego robić, dzięki pomysłowi a4karo ...
Na koniec dodam taki prosty fakt, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem uporządkowanym, niekoniecznie liniowo, to zbiór wszystkich elementów maksymalnych w tym zbiorze uporządkowanym jest antyłańcuchem (chyba niekoniecznie maksymalnym); podobnie zbiór wszystkich elementów minimalnych w tym zbiorze uporządkowanym jest antyłańcuchem.
"Każdy zbiór co najmniej dwuelementowy jest sumą dwuelementowych rozłącznych podzbiorów, albo, taki zbiór, staję się taką sumą, takich podzbiorów dwuelementowych, po wyrzuceniu z niego pewnego jego jednego elementu".
(Zacytowałem tutaj ten fakt własnymi słowami, ale starałem się zachować identyczną treść).
Dla nieskończonych zbiorów \(\displaystyle{ X}\) pokazałem nawet więcej. Wykazałem, że:
Jeśli \(\displaystyle{ X}\) jest zbiorem nieskończonym, to istnieje rodzina \(\displaystyle{ \mathbb{B}}\) podzbiorów zbioru \(\displaystyle{ X}\), podzbiorów dwuelementowych, rodzina zbiorów rozłącznych, taka, że: \(\displaystyle{ \bigcup\mathbb{B}=X.}\)
Dowód tego faktu wynika łatwo z tytułowego twierdzenia mówiącego, że każdy zbiór nieskończony można podzielić na dwa równoliczne podzbiory.
PROSTY DOWÓD TEGO FAKTU:
Niech \(\displaystyle{ X}\) będzie zbiorem nieskończonym.
Z twierdzenia Zermelo (równoważnego aksjomatowi wyboru), a dokładniej z tytułowego twierdzenia tego wątku wynika, ze istnieją dwa zbiory
\(\displaystyle{ X_1, X_2 \subset X}\), równoliczne, rozłączne, i takie, że w sumie dają cały zbiór \(\displaystyle{ X}\)- : \(\displaystyle{ X_1 \cup X_2=X.}\)
Ponieważ zbiory \(\displaystyle{ X_1}\) i \(\displaystyle{ X_2}\) są równoliczne, więc istnieje bijekcja \(\displaystyle{ f:X _{1} \rightarrow X_2.}\)
Rozważmy sumę:
\(\displaystyle{ \bigcup_{\left( x,y\right) \in f } \left\{ x,y\right\}.}\)
Jeśli \(\displaystyle{ \left( x,y\right) \in f}\), to \(\displaystyle{ x \in X_1 \subset X}\), i \(\displaystyle{ y \in X_2 \subset X}\), a więc \(\displaystyle{ \left\{ x,y\right\} \subset X, }\) i ponieważ zbiory \(\displaystyle{ X_1}\) i \(\displaystyle{ X_2}\) są rozłączne, to \(\displaystyle{ x \neq y}\), a więc zbiór \(\displaystyle{ \left\{ x,y\right\}}\) jest dwuelementowy, i rodzina \(\displaystyle{ \left\{ \left\{ x,y\right\}\Bigl| \ \left( x,y\right) \in f \right\}}\) jest rodziną dwuelementowych podzbiorów zbioru \(\displaystyle{ X}\). I jest to rodzina zbiorów rozłącznych, bo funkcja \(\displaystyle{ f}\) jest różnowartościowa.
I mamy:
\(\displaystyle{ \bigcup_{ \left( x,y\right) \in f } \left\{ x,y\right\} = \bigcup_{\left( x,y\right) \in f } \left( \left\{ x\right\} \cup \left\{ y\right\} \right)= \left( \bigcup_{\left( x,y\right) \in f } \left\{ x\right\} \right) \cup \left( \bigcup_{\left( x,y\right) \in f } \left\{ y\right\}\right) = f_L \cup f_P= }\)
i ponieważ funkcja \(\displaystyle{ f}\) jest funkcją 'na', więc to jest równe:
\(\displaystyle{ = X_1 \cup X_2= X.\square}\)
A jeśli zbiór \(\displaystyle{ X}\) jest skończony, co najmniej dwuelementowy, to jeśli jego moc jest liczbą parzystą, tzn. \(\displaystyle{ \left| X\right|= 2n}\), gdzie \(\displaystyle{ n \in \NN_+}\), to oznaczając jego elementy jako:
\(\displaystyle{ X= \left\{ x_1, x_2, x_3, x_4,\ldots, x _{2n-1}, x _{2n} \right\},}\)
mamy:
\(\displaystyle{ X= \bigcup_{m=1}^{n} \left\{ x _{2m-1} , x _{2m} \right\} .}\)
co należało pokazać.
A jeśli moc skończonego zbioru \(\displaystyle{ X}\) jest liczbą nieparzystą, tzn.\(\displaystyle{ \left| X\right| =2n+1}\), gdzie \(\displaystyle{ n \ge 1}\), to
\(\displaystyle{ \left| X\right| \ge 3}\), istnieje więc element \(\displaystyle{ x \in X \neq \left\{ \right\}}\). Wtedy \(\displaystyle{ \left| X \setminus \left\{ x\right\} \right|=2n}\), więc oznaczając jego elementy:
\(\displaystyle{ X \setminus \left\{ x\right\} = \left\{ x_1, x_2, x_3, x_4,\ldots, x _{2n-1}, x _{2n} \right\}}\) ,
to podobnie jak powyżej otrzymujemy:
\(\displaystyle{ X \setminus \left\{ x\right\}= \bigcup_{m=1}^{n} \left\{ x _{2m-1} , x _{2m} \right\} .\square}\)
Jakub Gurak pisze: ↑6 lut 2018, o 06:12 Każdy zbiór nieskończony można podzielić na dowolną ilość ( ograniczoną przez wielkość zbioru nieskończonego \(\displaystyle{ X}\)
) równolicznych podzbiorów.
A mój pomysł był taki:Jakub Gurak pisze: ↑10 lut 2018, o 06:04 Na koniec chciałem podziękować użytkownikowi a4karo za pomysł. Bez tego sprawa mogłaby by wyglądać znacznie ciężej...
Podział na \(\displaystyle{ n \in \NN}\) zbiorów, gdzie \(\displaystyle{ n \ge 3}\), uzyskujemy w ten sposób, że wpierw porządkujemy dobrze nieskończony zbiór \(\displaystyle{ X}\), i ustawiamy na kolejnych elementach zbioru \(\displaystyle{ X}\) przypisujemy im kolejno: \(\displaystyle{ \underbrace{1,2,3,\ldots, n}_{}, \underbrace{1,2,3,\ldots, n}_{},1,2,3\ldots,}\) podobnie jak w przypadku dla \(\displaystyle{ n=2. }\)
A jeśli zbiór \(\displaystyle{ M}\) jest nieskończony, to pomysł jest taki, aby zastosować twierdzenie Zermelo jeszcze raz, aby go dobrze uporządkować. I podobnie, na kolejnych elementach zbioru \(\displaystyle{ X}\) ustawiamy cyklicznie kolejne elementy zbioru \(\displaystyle{ M}\)- jednak powstaje tu pewna trudność, bo nie działało by to tutaj gdyby np. zbiór \(\displaystyle{ X}\) był typu \(\displaystyle{ \omega +2}\), i gdyby zbiór \(\displaystyle{ M}\) był typu \(\displaystyle{ \omega+1}\). Zrobimy to inaczej, rozważając dwa przypadki. Rozważmy więc dwa przypadki:
\(\displaystyle{ 1 ^{\circ}: M\sim X}\). Wtedy rodzina \(\displaystyle{ \left\{ \left\{ x\right\}\Bigl| \ x \in X \right\}}\) jest, jak łatwo sprawdzić, jest poszukiwanym ilorazem.
\(\displaystyle{ 2 ^{\circ}:}\) Pozostaje rozważyć przypadek, bo \(\displaystyle{ M \subset X}\), więc pozostaje rozważyć przypadek gdy moc zbioru \(\displaystyle{ M}\) jest silnie mniejsza od mocy zbioru \(\displaystyle{ X}\). Wtedy, ponieważ zbiór \(\displaystyle{ M}\) jest nieskończony, więc suma \(\displaystyle{ \left| M\right|}\) wielu zbiorów mocy \(\displaystyle{ \left| M\right|}\) jest równoliczna ze zbiorem \(\displaystyle{ M}\). I ustawiając na kolejnych elementach zbioru \(\displaystyle{ X}\) kolejne elementy zbioru \(\displaystyle{ M}\), gdy ich braknie znowu cyklicznie powtarzamy ten proces; ponieważ suma \(\displaystyle{ \left| M\right|}\) wielu zbiorów mocy \(\displaystyle{ \left| M\right|}\) jest mocy \(\displaystyle{ \left| M\right| <\left| X\right|}\), to takich cykli musimy ustawić więcej niż moc zbioru \(\displaystyle{ M}\), a więc musimy ustawić nieskończenie wiele takich cykli. Więc nawet gdyby ostatni cykl byłby zaburzony, (tzn. elementy nie byłyby rozdzielone po równo), to takie tworzone zbiory są nieskończone, bo ilość cykli (oj, ta nieskończoność, tu już mam problemy) jest nieskończona, chyba tak, a dodanie/wyrzucenie po jednym elemencie ze zbiorów nieskończonych niczego nie zmienia. I dla dowolnego ustalonego \(\displaystyle{ m \in M}\) bierzemy zbiór wszystkich elementów zbioru \(\displaystyle{ X}\), którym przypisaliśmy to \(\displaystyle{ m}\), bierzemy taki zbiór, jako zbiór rodziny, która ma być poszukiwanym ilorazem; i tak po \(\displaystyle{ m \in M}\) bierzemy takie zbiory. Oh,... na szczęście nie musimy tego robić, dzięki pomysłowi a4karo ...
Na koniec dodam taki prosty fakt, że jeśli \(\displaystyle{ \left( X, \le\right) }\) jest zbiorem uporządkowanym, niekoniecznie liniowo, to zbiór wszystkich elementów maksymalnych w tym zbiorze uporządkowanym jest antyłańcuchem (chyba niekoniecznie maksymalnym); podobnie zbiór wszystkich elementów minimalnych w tym zbiorze uporządkowanym jest antyłańcuchem.