Twierdzenie Cantora

[freeze2]

Hej!

Mógłby mi ktoś wytłumaczyć jakoś łopatologicznie dowód twierdzenia
Cantora o tym, że nie ma zbioru zawierającego swój zbiór potęgowy?

pozdrawiam,
freeze

[Jan Kraszewski]

Na czym mialaby polegac oczekiwana lopatologicznosc?
Twierdzenie Cantora stanowi, ze zaden zbior nie jest rownoliczny ze swoim zbiorem potegowym, czyli, ze nie moze byc pomiedzy nimi bijekcji. Dowod jest nie wprost. Zakladamy, ze istnieje bijekcja \(\displaystyle{ f:A\to P(A)}\).
Niech \(\displaystyle{ B=\{x\in A:x\not\in f(x)\}}\). Ten zapis ma sens, bo \(\displaystyle{ f(x)}\) jest elementem \(\displaystyle{ P(A)}\), czyli \(\displaystyle{ f(x)\subseteq A}\), czyli biorac element x zbioru A mozemy pytac, czy nalezy on do \(\displaystyle{ f(x)}\). Zbior B, jak latwo zauwazyc z jego definicji tez jest podzbiorem zbioru A, zatem \(\displaystyle{ B\in P(A)}\). Ale funkcja f jest w szczegolnosci "na", czyli istnieje element a zbioru A, taki, ze \(\displaystyle{ f(a)=B}\). Mozna teraz zapytac, czy \(\displaystyle{ a\in B}\). Z definicji zbiory B mamy \(\displaystyle{ a\in B\iff a\not\in f(a)}\). Ale \(\displaystyle{ f(a)=B}\), czyli \(\displaystyle{ a\in B\iff a\not\in B}\). Takie stwierdzenie jest dosc ewidentnie sprzeczne, zatem nasze zalozenie o istnieniu bijekcji musialo byc falszywe, co konczy dowod.

Bardziej lopatologicznie (przez siec) chyba nie potrafie...
JK

[darek77]

Użytkownik Jan Kraszewski w zasadzie wszystko już dobrze wytłumaczył, ale ja postanowiłem zabawić się w skrajną łopatologię.

Więc zacznijmy od dowodu , wedle którego żaden zbiór nie może być ze swoim [url=http://pl.wikipedia.org/wiki/Zbi%C3%B3r_pot%C4%99gowy]zbiorem potęgowym[/url] a zatem dla dowolnego zbioru \(\displaystyle{ A}\) nie istnieje [url=http://pl.wikipedia.org/wiki/Funkcja_wzajemnie_jednoznaczna]bijekcja[/url] \(\displaystyle{ h\colon A \to 2^A}\).

Dowód:
Jeżeli \(\displaystyle{ A}\) jest zbiorem pustym Twierdzenia Cantora oczywiście zachodzi (liczebność przeciwdziedziny nie może dominować nad liczebnością dziedziny funkcji , jeśli mamy do czynienia z bijekcją), przyjmijmy zatem w dalszej części dowodu , że \(\displaystyle{ A}\) zawiera co najmniej jeden element. Rozważmy dowolną funkcję \(\displaystyle{ f\colon A \to 2^A}\) czyli taką, której wartością może być zbiór pusty lub dowolny inny podzbiór zbioru \(\displaystyle{ A}\). Zdefiniujmy zbiór \(\displaystyle{ B}\) zawierający tylko takie elementy \(\displaystyle{ x\in A}\) że \(\displaystyle{ x\not\in f(x)}\). Zatem \(\displaystyle{ B\subseteq A}\) i w rezultacie \(\displaystyle{ B\in 2^A}\). Zauważmy ,że dla dowolnego elementu \(\displaystyle{ m\in A}\) zachodzi:
\(\displaystyle{ m\in f(m) \Rightarrow m\in f(m) \wedge m \not\in B \Rightarrow f(m) \neq B}\)
lub:
\(\displaystyle{ m \not\in f(m) \Rightarrow m\not\in f(m) \wedge m \in B \Rightarrow f(m) \neq B}\)
Oznacza to ,że ze względu na istnienie zbioru \(\displaystyle{ B}\), \(\displaystyle{ f}\) nie może okazać się [url=http://pl.wikipedia.org/wiki/Funkcja_%22na%22]suriekcją[/url] a już tym bardziej bijekcją, co też należało wykazać.

Warto tutaj zauważyć ,że gdy tylko \(\displaystyle{ A}\) jest zbiorem niepustym zawsze można skonstruować funkcję różnowartościową \(\displaystyle{ f\colon A \to 2^A}\) , zwracającą chociażby różne zbiory jednoelementowe. Zgodnie z twierdzeniem Cantora \(\displaystyle{ f}\) nigdy nie zwróci \(\displaystyle{ B}\), czyli nigdy nie wyczerpie wszystkich możliwych wartości przeciwdziedziny, oznacza to ,że również w przypadku zbiorów nieskończenie wielkich można przyjmować ,że chociażby przez wzgląd na \(\displaystyle{ B}\) liczebność \(\displaystyle{ 2^A}\) dominuje nad liczebnością \(\displaystyle{ A}\). Oczywiście gdy \(\displaystyle{ A}\) to zbiór pusty wówczas okoliczność dotycząca dominacji liczebności również zachodzi. Zatem nie jest możliwe skonstruowanie zbioru \(\displaystyle{ X}\) takiego ,że \(\displaystyle{ 2^X\subseteq X}\), co określane jest jako [url=http://pl.wikipedia.org/wiki/Paradoks_zbioru_wszystkich_zbior%C3%B3w]paradoks nie istnienia zbioru wszystkich zbiorów[/url]. Twierdzenie Cantora jako takie , można wykorzystać do udowodnienia [url=http://pl.wikipedia.org/wiki/Zbi%C3%B3r_przeliczalny]nieprzeliczalności[/url] [url=http://pl.wikipedia.org/wiki/Zbi%C3%B3r_Cantora]zbioru Cantora[/url], którego prosty schemat konstruowania (postać standardowa) można znaleźć chociażby [url=http://www.youtube.com/watch?v=MdNg6f0e1Ys]tutaj[/url]. Nieprzeliczalność zbioru Cantora determinuje nieprzeliczalność zbioru liczb rzeczywistych i w pewnym stopniu burzy klasyczne podejście do zbioru , jako czegoś, co składa się z elementów , które zawsze idzie w pełni ponumerować liczbami naturalnymi.

[Mania]

Odświeżam stary wątek. Otóż mam problem z "uwierzeniem" w twierdzenie Cantora z tego względu:
Z twierdzenia Cantora wynika, że zbiór l. naturalnych nie jest równoliczny ze zbiorem l.rzeczywistych, ponieważ tworzymy jakiś zbiór \(\displaystyle{ X=\{a\in A: a\notin f(a)\}}\) i z tego biorą się potem sprzeczności. Czaję. Ale czy samo tworzenie takiej sprzeczności nie jest nieuprawnione? Przecież tak samo moglibyśmy na tej podstawie stwierdzić, że zbiór l. nat. nie jest równoliczny ze zb. l. całkowitych, a jest bo da się wykazać taką biejkcję. Jednak w przypadku l. nat i l. cał. tak samo moglibyśmy utworzyć taki zbiór \(\displaystyle{ X}\) i przerzucić, element \(\displaystyle{ a}\) do zbioru do którego nie należy. Gdzie tu różnica?

[Dasio11]

Spróbuj, to zobaczymy.

[Mania]

Spróbuj co?

[a4karo]

Cantor łopatologicznie idzie tak:

przypuśćmy, że udało się ustalić odpowiedniość 1-1 między zbiorem i wszystkimi jego podzbiorami.

Nazwijmy podzbiory zespołami. Oznacza to, że każdy zespół ma swojego szefa i każdy szefuje jednemu zespołowi.

Szefowie mogą być dwojakiego rodzaju: albo szef jest członkiem zespołu, któremu szefuje - wtedy nazwiemy go liderem, albo do tego zespołu nie należy - takich będziemy nazywać kierownikami.

Przyjrzyjmy się teraz zespołowi złożonemu z wszystkich kierowników. Ten zespół ma oczywiście szefa, a ten szef jest albo liderem, albo kierownikiem.
Gdyby był liderem, to należałby do zespołu, którym kieruje, a więc byłby kierownikiem. A to jest niemożliwe. Zatem jest kierownikiem, ale to też jest niemożliwe, bo wtedy mielibyśmy kierownika poza zespołem wszystkich kierowników.

Ta sprzeczność dowodzi, że przypisanie, które założyliśmy na początku nie jest możliwe.

[Dasio11]

Spróbuj co?

No spróbuj przeprowadzić dowód, o którym piszesz, że "można go zrobić tak samo". Bez tego trudno zrozumieć, co masz na myśli, bo sytuacja z liczbami całkowitymi nie jest w żaden sposób analogiczna do sytuacji z podzbiorami.

[Jakub Gurak]

Teraz widzę, że idea dowodu twierdzenia Cantora jest rozumowaniem przekątniowym. Teraz bardzo prosto i łopatologicznie to widzę, i muszę się tym podzielić. Przedstawię ideę dowodu, że \(\displaystyle{ \NN\not\sim P\left( \NN\right).}\)

Przypuszczam, że każdy podzbiór \(\displaystyle{ \NN}\) ma swój numer naturalny. Popatrzmy na tablicę \(\displaystyle{ \NN \times \NN}\) (w celach jedynie poglądowych). Powiedzmy, że jeśli mamy podzbiór \(\displaystyle{ A\subset \NN}\), to (w pewnym wierszu) tej tablicy, na kolejnych liczbach naturalnych, zamiast nich piszemy \(\displaystyle{ 0}\), gdy \(\displaystyle{ n\notin A}\), a piszemy \(\displaystyle{ 1,}\) gdy \(\displaystyle{ n \in A}\). I teraz popatrzmy na przekątną w tej tablicy nieskończonej, i na przekątnej zamieniamy \(\displaystyle{ 0}\) na \(\displaystyle{ 1}\), a \(\displaystyle{ 1}\) na \(\displaystyle{ 0}\), i te wartości wpisujemy w nowym wierszu, tworząc nowy podzbiór, nazwijmy go \(\displaystyle{ S}\)( w polu \(\displaystyle{ n}\), \(\displaystyle{ 0}\) oznacza że \(\displaystyle{ n\notin S}\), a \(\displaystyle{ 1}\) oznacza że \(\displaystyle{ n\in S}\)). Jest to istotnie nowy zbiór, gdyż z konstrukcji przekątniowej wynika, że w dowolnym polu \(\displaystyle{ n}\), gdy było \(\displaystyle{ 1}\) na przekątnej , to u nas było \(\displaystyle{ 0}\), a więc jedynki są rozmieszczone inaczej, a więc są to zbiory różne, a gdy było \(\displaystyle{ 0}\) na przekątnej, to u nas było \(\displaystyle{ 1}\), a więc również są to zbiory różne. Zatem (z dowolności \(\displaystyle{ n}\)) ten zbiór \(\displaystyle{ S}\), reprezentowany jako wiersz, nie pojawia się w naszej tablicy nieskończonej, sprzeczność. Zatem nie może być to funkcja 'na'.

Szkoda tylko, że dochodzę do tego po wielu latach doświadczenia z teoria mnogości. Widzę, że czasem tak jest, że (być może pod wpływem formalizacji) zostaje zapomniana idea rozumowania, i można mieć kłopoty z przyswojenie sobie dowodu. Tak jak tutaj, została tylko nazwa, dowód przekątniowy. Nikt(żaden student) nie ma pojęcia co ta nazwa ma do rzeczy

[Jakub Gurak]

Wczoraj i dzisiaj męczyłem głowę, aby dobrze zrozumieć dlaczego liczb rzeczywistych jest istotnie mniej niż podzbiorów zbioru liczb rzeczywistych.
Spróbuję zilustrować ten fakt metodą przekątniową, tzn. fakt mówiący, że \(\displaystyle{ \left| \RR\right|<\left| P(\RR)\right|. }\)


Oczywiście \(\displaystyle{ \left| \RR\right| \le P\left( \RR\right)}\), bo możemy rozważyć funkcję przypisującą liczbie rzeczywistej \(\displaystyle{ x}\) przypisujemy jej zbiór \(\displaystyle{ \left\{ x\right\} \subset \RR}\), i dla \(\displaystyle{ x_1 \neq x_2}\) mamy \(\displaystyle{ \left\{ x_1\right\} \neq \left\{ x_2\right\}}\) , a zatem jest to funkcja różnowartościowa, a zatem \(\displaystyle{ \left| \RR\right| \le P\left( \RR\right) }\).

Albo inaczej: mamy ogólny, prosty i ciekawy fakt, mówiący, że dowolny zbiór \(\displaystyle{ X}\) jest równoliczny z rodziną wszystkich jego podzbiorów jednoelementowych, czyli: \(\displaystyle{ X\sim \left\{ \left\{ x\right\}\Bigl| \ \ x \in X\right\} }\), a zatem \(\displaystyle{ \RR\sim \left\{ \left\{ x\right\} \Bigl| \ \ x \in \RR\right\} \subset P(\RR)}\), a zatem \(\displaystyle{ \left| \RR \right| \le \left| P(\RR)\right|. }\)

Pozostaje pokazać, że \(\displaystyle{ \RR\not\sim P(\RR).}\)

Przypuśćmy nie wprost, że \(\displaystyle{ \RR\sim P(\RR). }\)

Istnieje wtedy bijekcja \(\displaystyle{ f: \RR \rightarrow P(\RR). }\)
Spróbuje zilustrować przykład podzbioru zbioru liczb rzeczywistych, który nie będzie wartością tej funkcji.

Mamy rodzinę zbiorów \(\displaystyle{ \left( A_x\right) _{x \in \RR}}\) (i tu wreszcie jest sensowna w użyciu rodzina indeksowana, to ma wreszcie sens, a nie używać rodziny indeksowanej tylko po to, żeby wzory ładnie wyglądały ) , która jest zbiorem wartości tej funkcji, i każdy podzbiór zbioru liczb rzeczywistych tu się pojawia.

Skonstruujemy zbiór różny od tych wszystkich zbiorów \(\displaystyle{ A_x}\).

Mamy \(\displaystyle{ A_x \subset \RR}\).

Zamiast patrzeć na taki podzbiór, jako na zwykły podzbiór, popatrzmy na niego jak na funkcję ze zbioru liczb rzeczywistych w \(\displaystyle{ \left\{ 0,1\right\}}\) , która elementom tego podzbioru przypisuje \(\displaystyle{ 1}\), a pozostałym liczbom przypisuje \(\displaystyle{ 0}\), tzn. funkcja:

\(\displaystyle{ f_x:\RR \rightarrow \left\{ 0,1\right\} , }\)

jest określona w taki sposób, że:

\(\displaystyle{ f_x\left( a\right) = \begin{cases} 1, \hbox{ gdy } a \in A_x;\\ 0,\hbox{ gdy } a\not \in A_x.\end{cases} }\)

Oto ilustracja tego faktu:

\(\displaystyle{ \\}\)

\(\displaystyle{ \\}\)
I za poszukiwany zbiór, nazwijmy go \(\displaystyle{ B}\), bierzemy zbiór wszystkich zer leżących na przekątnej (a właściwie nie zer, tylko ich rzutów na oś \(\displaystyle{ x}\), tzn. argumentów, dla których jest osiągane \(\displaystyle{ 0}\) na przekątnej dla kolejnych funkcji ).

Wtedy \(\displaystyle{ B \neq A_x}\), dla każdego \(\displaystyle{ x \in \RR}\), bo jest to zbiór zer, a dla dowolnej ustalonej funkcji \(\displaystyle{ f_x}\), wtedy \(\displaystyle{ 0}\) oznacza, że dana liczba nie należy do zbioru \(\displaystyle{ A_x}\), a zatem \(\displaystyle{ B \neq A_x}\), i to dla każdego \(\displaystyle{ x \in \RR}\); ale \(\displaystyle{ B \subset \RR}\), a zatem \(\displaystyle{ B \in P(\RR)}\), a zatem funkcja \(\displaystyle{ f}\) nie jest 'na' -sprzeczność. \(\displaystyle{ \square}\)

W podobny sposób, przy pomocy kwadratu kartezjańskiego, możemy zilustrować, że w ogólnym przypadku : \(\displaystyle{ X\not\sim P(X)}\).
(I tak- taka matematyka mnie rozwija najbardziej , nawet nie jest to dla mnie łatwe, trzeba będzie teraz zająć się czymś lżejszym) .