szukanie zaawansowane
 [ Posty: 10 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 6 lut 2018, o 07:12 
Użytkownik

Posty: 388
Lokalizacja: Rzeszów
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 g:A \rightarrow  B jest bijekcją, oraz C \subset B, to C\sim \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right).

Ilustracja:
Obrazek

Szkic dowodu:

Definiujemy bijekcję h: \  \stackrel{ \rightarrow }{g^{-1}} \left( C \right) \rightarrow C, jako: h\left( x\right) =g\left( x\right).

Funkcja h jest dobrze zdefiniowana, bo jeśli x\in h_{L}=  \stackrel{ \rightarrow }{g^{-1}} \left( C \right), to h\left( x\right) =g\left( x\right) \in C.

Ponieważ, g jest bijekcją, czyli jest różnowartościowa i 'na', to bardzo łatwo pokazać, że h jest różnowartościowa, i, nieco trudniej, że h jest 'na' C, a więc jest bijekcją między \stackrel{ \rightarrow }{g^{-1}} \left( C \right) a C, czyli C \sim \  \ \stackrel{ \rightarrow }{g^{-1}} \left( C \right). \square

LEMAT 2. Jeśli g: A \rightarrow  B jest bijekcją, oraz mamy zbiory B_{1}, B_{2} \subset B, takie, że B_{1} \sim B_{2}, to wtedy \ \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 g oraz zbiór B_{1} spełniają założenia LEMATU 1, więc B_{1} \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right). Stosując LEMAT 1 jeszcze raz, tym razem do zbioru B_{2}, otrzymujemy, że B_{2} \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right). Mamy również założenie, że B_{1} \sim B_{2}. Z przechodniości równoliczności otrzymujemy, że \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{1} \right) \sim \ \stackrel{ \rightarrow }{g^{-1}} \left( B_{2} \right).\square

Łatwo teraz będzie udowodnić :lol: , ż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 X. Ponieważ jest nieskończony, to X \times \left\{ 0,1\right\} jest równoliczny z X. Istnieje więc bijekcja f:  X\rightarrow X \times \left\{ 0,1\right\}. Mając ją, rozważmy zbiory: \ \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 X \times \left\{ 0\right\} oraz X \times \left\{ 1\right\}. Zbiory te sumują się do X, gdyż:

\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 X. Pozostaje pokazać, że są równoliczne.

Niewątpliwie X\sim X \times \left\{ 0\right\}, oraz X\sim X \times  \left\{ 1\right\}. Zbiory 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ę f, czyli \ \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.\square :D

Podział na 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 X) równolicznych podzbiorów. :lol: :lol: Dowód jest analogiczny, ale to już nie dziś.
Góra
Mężczyzna Online
PostNapisane: 6 lut 2018, o 07:24 
Użytkownik

Posty: 15343
Lokalizacja: Bydgoszcz
I mówisz, że taką pracę napisałeś?
429421.htm#p5531616
Góra
Mężczyzna Offline
PostNapisane: 6 lut 2018, o 14:21 
Administrator

Posty: 22891
Lokalizacja: Wrocław
a4karo napisał(a):
I mówisz, że taką pracę napisałeś?

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...

Proponowałem mu kiedyś, żeby poczytał coś innego niż ważniak, ale chyba na razie trzyma się swojej drogi.

JK
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2018, o 07:04 
Użytkownik

Posty: 388
Lokalizacja: Rzeszów
a4karo napisał(a):
I mówisz, że taką pracę napisałeś?
Tak, ale to zajmuję (łącznie z tym co już przedstawiłem) jedynie dwie i pół kartki.

Niech X \neq \left\{ \right\} będzie niepustym zbiorem, a \left\{ \right\} \neq M \subset X jego niepustym podzbiorem. Ilorazem X/M zbioru X przez podzbiór M, to \mathbb{A}\in P\left( P\left( X\right) \right) rodzina podzbiorów X, taka że:

1. \mathbb{A} jest rozkładem zbioru X.
2. \mathbb{A}\sim M.
3. A,B\in \mathbb{A} \Longrightarrow A\sim B.

Przykład: Niech X=\NN. M=\NN.
Rodzina zbiorów \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 \NN na nieskończoną ilość zbiorów równolicznych ( zbiory dwuelementowe są równoliczne). A więc jest to iloraz \NN przez M=\NN.

I teraz główne twierdzenie:

Jeśli X jest dowolnym zbiorem nieskończonym, a M jego dowolnym niepustym podzbiorem, to istnieje iloraz X/M.

DOWÓD (NIETRUDNY):

Jeśli M jest jednoelementowy, czyli M=\left\{ a\right\} , to \left\{ X\right\} jest poszukiwanym ilorazem. Jest to rozkład zbioru X (niewłaściwy),\left\{ X\right\}\sim M=\left\{ a\right\}, i spełniony jest punkt 3 poprzez X\sim X. A więc jest to poszukiwany iloraz.
Jeśli M jest dwuelementowy, to wykazałem to wcześniej. Jeśli M jest n-elementowy, to łatwo to zrobić indukcyjnie- zobacz tu: https://www.matematyka.pl/429421.htm
Pozostają zbiory M nieskończone. Jeśli M jest równoliczny z X, to \mathbb{A}=\left\{ \left\{ x\right\} \Bigl| \ x\in X \right\} jest poszukiwanym ilorazem. Jest to niewątpliwie rozkład zbioru X, \mathbb{A}\sim X\sim M, a więc \mathbb{A}\sim  M, oraz każde dwa zbiory rodziny \mathbb{A} są równoliczne ( jako jednoelementowe).
Pozostają zbiory M nieskończone, nierównoliczne z X. Wtedy:

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 X jest nieskończony. W takim razie z tw. Cantora-Bernsteina X \times M\sim X. Niech więc f będzie bijekcją między X a X \times M.
Rozważmy rodzinę podzbiorów X:

\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 X, gdyż:

\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 X. \mathbb{A}\sim M, bo wystarczy przyporządkować: 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 \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 \mathbb{A} jest ilorazem zbioru X przez podzbiór M, co kończy dowód.\square :D :lol: 8-)

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. :lol: :D

Na koniec chciałem podziękować użytkownikowi a4karo za pomysł. Bez tego sprawa mogłaby by wyglądać znacznie ciężej...
Góra
Mężczyzna Online
PostNapisane: 10 lut 2018, o 10:24 
Użytkownik

Posty: 15343
Lokalizacja: Bydgoszcz
Brrrr, jakbyś to zrobił w prosty sposób, to pewnie dałoby się to przeczytać.

To teraz udowodnij, dla każdej liczby kardynalnej \mathfrak{n} zbiór o mocy \mathfrak{m} \geq\mathfrak{n} da się podzielić na zbiory o mocy \mathfrak{n}
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2018, o 10:56 
Moderator
Avatar użytkownika

Posty: 7835
Lokalizacja: Wrocław
Jakub Gurak napisał(a):
Ilorazem X/M zbioru X przez podzbiór M, to \mathbb{A}\in P\left( P\left( X\right) \right) rodzina podzbiorów X, taka że:

1. \mathbb{A} jest rozkładem zbioru X.
2. \mathbb{A}\sim M.
3. A,B\in \mathbb{A} \Longrightarrow A\sim B.
Oznaczenie X/M jest bardzo mylące, bo sugeruje, że iloraz ma jakiś związek ze zbiorem M, a tymczasem z definicji widać, że ważna jest tylko moc M. Dlatego lepiej byłoby to oznaczyć X/\kappa, gdzie 0 < \kappa \le |X|. Inna sprawa, że dla \kappa = |X| ten zapis mógłby oznaczać zarówno podział X na \kappa zbiorów jednoelementowych, jak i podział na \kappa zbiorów mocy \kappa - czy te podziały powinny więc mieścić się pod jednym symbolem?


Jakub Gurak napisał(a):
Pozostają zbiory M nieskończone, nierównoliczne z X. Wtedy:
Następujący po tym cytacie dowód działa nie tylko dla zbioru M nieskończonego, nierównolicznego z 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.
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2018, o 13:42 
Administrator

Posty: 22891
Lokalizacja: Wrocław
Powiem tak - jak dla mnie jedyny trudniejszy fakt w tym rozumowaniu to ten, który został tylko zacytowany, czyli że dla nieskończonego zbioru X mamy X\sim X\times X. Reszta jest wnioskiem z tego faktu.

JK
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2018, o 14:34 
Użytkownik

Posty: 388
Lokalizacja: Rzeszów
Definicja rzeczywiście nie wyznacza w sposób jednoznaczny tego ilorazu, co mnie nie zaskakuje. Natomiast w sprawie oznaczenia 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. :?
Dasio11 napisał(a):
Następujący po tym cytacie dowód działa nie tylko dla zbioru M nieskończonego, nierównolicznego z 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.
Też mi się wydawało, że niepotrzebnie rozpatruje przypadki (ale podzbiory 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...
a4karo napisał(a):
To teraz udowodnij, dla każdej liczby kardynalnej \mathfrak{n} zbiór o mocy \mathfrak{m} \geq\mathfrak{n} da się podzielić na zbiory o mocy \mathfrak{n}
Tego Ci nie udowodnię, bo obawiam się, że to nieprawda- zbiór o mocy 3 \ge 2 nie da się podzielić na zbiory o mocy 2.
Góra
Mężczyzna Offline
PostNapisane: 10 lut 2018, o 14:51 
Administrator

Posty: 22891
Lokalizacja: Wrocław
Jakub Gurak napisał(a):
a4karo napisał(a):
To teraz udowodnij, dla każdej liczby kardynalnej \mathfrak{n} zbiór o mocy \mathfrak{m} \geq\mathfrak{n} da się podzielić na zbiory o mocy \mathfrak{n}
Tego Ci nie udowodnię, bo obawiam się, że to nieprawda- zbiór o mocy 3 \ge 2 nie da się podzielić na zbiory o mocy 2.

Idę o zakład, że jak a4karo używał gotyku, to miał na myśli nieskończone liczby kardynalne.

JK
Góra
Mężczyzna Online
PostNapisane: 10 lut 2018, o 15:00 
Użytkownik

Posty: 15343
Lokalizacja: Bydgoszcz
Wystarczy że ten większy jest nieskończony
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 10 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 Co to jest zbiór parami rozłącznych kół?  zdzichukowalski  2
 Czy te zbiory są równoliczne?  Giks  1
 zbiór skierowany i łańcuch  Pasjonatka91  1
 Wyznacz zbiór - zadanie 16  Sidu  11
 Znajdź zbiór - zadanie 3  boratsahgdyiev1  1
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl