zbiór nieprzeliczalny

Algebra zbiorów. Relacje, funkcje, iloczyny kartezjańskie... Nieskończoność, liczby kardynalne... Aksjomatyka.
Awatar użytkownika
Chewbacca97
Użytkownik
Użytkownik
Posty: 462
Rejestracja: 9 lis 2013, o 22:09
Płeć: Mężczyzna
Podziękował: 33 razy
Pomógł: 120 razy

zbiór nieprzeliczalny

Post autor: Chewbacca97 » 25 paź 2017, o 01:37

Należy udowodnić, że \(\displaystyle{ X = \RR \cup \left\{ 5-2i\right\}}\) jest zbiorem nieprzeliczalnym.

W przypadku zbiorów przeliczalnych pokazywałem, że istnieje iniekcja z \(\displaystyle{ X}\) do zbioru liczb naturalnych. W tym przypadku prawdopodobnie należy pokazać, że taka iniekcja nie istnieje...

Jestem świadom, że jeżeli nieprzeliczalny zbiór \(\displaystyle{ A}\) jest podzbiorem zbioru \(\displaystyle{ B}\), to \(\displaystyle{ B}\) też jest zbiorem nieprzeliczalnym. W naszym przypadku: \(\displaystyle{ \RR \subseteq X}\) i z tej własności zbiorów nieprzeliczalnych zadanie jest (chyba) rozwiązane. Jednak chciałbym pokazać to, o czym wspomniałem wyżej i jakoś nie potrafię.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15212
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 161 razy
Pomógł: 5047 razy

Re: zbiór nieprzeliczalny

Post autor: Premislav » 25 paź 2017, o 02:23

https://pl.wikipedia.org/wiki/Metoda_przek%C4%85tniowa
no a \(\displaystyle{ [0,1] \subset \RR \cup \left\{ 5-2i\right\}}\)

a4karo
Użytkownik
Użytkownik
Posty: 19226
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3247 razy

Re: zbiór nieprzeliczalny

Post autor: a4karo » 25 paź 2017, o 05:00

Zawsze zastanawiałem się dlaczego nieprzeliczalnosci zbioru liczb rzeczywistych nie pokazuje się tak:
Przypuśćmy, że jest I pokryjmy \(\displaystyle{ n}\)-tą liczbę odcinkiem o długości \(\displaystyle{ 1/2^n}\).
W ten sposób całą prostą pokryjemy odcinkami o łącznej długości równej jeden.

Jan Kraszewski
Administrator
Administrator
Posty: 27305
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4597 razy

Re: zbiór nieprzeliczalny

Post autor: Jan Kraszewski » 25 paź 2017, o 07:26

Może dlatego, że Cantor wymyślił ten dowód w latach 70-tych XIX wieku, a miara Lebesgue'a to wymysł dwudziestowieczny...? :)

JK

a4karo
Użytkownik
Użytkownik
Posty: 19226
Rejestracja: 15 maja 2011, o 20:55
Płeć: Mężczyzna
Lokalizacja: Bydgoszcz
Podziękował: 6 razy
Pomógł: 3247 razy

Re: zbiór nieprzeliczalny

Post autor: a4karo » 25 paź 2017, o 08:09

Może? Ale przyznasz, że od tego argumentu do miary Lebesgue'a jeszcze całe lata świetlne.

Jan Kraszewski
Administrator
Administrator
Posty: 27305
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4597 razy

Re: zbiór nieprzeliczalny

Post autor: Jan Kraszewski » 25 paź 2017, o 09:57

Tak, ale to jednak jest argument miarowy.

Trzeba pamiętać, że wtedy to była terra incognita i te pojęcia dopiero powstawały. Przecież Cantor nie myślał o "nieprzeliczalności", tylko o wzajemnie jednoznacznej odpowiedniości zbiorów. Największym przełomem było to, że w ogóle dopuścił możliwość dwóch różnych nieskończoności.

JK

Awatar użytkownika
Chewbacca97
Użytkownik
Użytkownik
Posty: 462
Rejestracja: 9 lis 2013, o 22:09
Płeć: Mężczyzna
Podziękował: 33 razy
Pomógł: 120 razy

Re: zbiór nieprzeliczalny

Post autor: Chewbacca97 » 25 paź 2017, o 11:36

Premislav, czyli dzięki metodzie przekątniowej wiem, że moc zbioru liczb rzeczywistych jest większa od mocy zbioru liczb naturalnych. Nie mogę więc skonstruować takiej funkcji różnowartościowej z \(\displaystyle{ \RR}\) do \(\displaystyle{ \NN}\) bo zwyczajnie w dziedzinie jest więcej elementów, czyli w pewnym momencie do dwóch różnych elementów dziedziny będzie przypisany ten sam element przeciwdziedziny. Jednak u mnie: \(\displaystyle{ \left[ 0,1\right] \subset \RR \subseteq X}\) i cały czas korzystam z faktu, że zbiór liczb rzeczywistych jest podzbiorem \(\displaystyle{ X}\).

Chyba, że mogę powiedzieć, że dzięki metodzie przekątniowej wiem, iż moc zbioru \(\displaystyle{ \RR \cup \left\{ 5-2i\right\}}\) jest większa od mocy zbioru liczb naturalnych. Co jest w sumie logiczne, jeżeli liczb rzeczywistych jest więcej niż liczb naturalnych, to po dodaniu jeszcze jednego elementu do \(\displaystyle{ \RR}\), w dalszym ciągu jest ich więcej niż liczb naturalnych. A to skutkuje tym, że nie można skonstruować iniekcji do zbioru liczb naturalnych. I dzięki temu zbiór \(\displaystyle{ X}\) jest zbiorem nieprzeliczalnym?-- 25 paź 2017, o 18:10 --Dobra, po prostu nie widziałem większego związku między podzbiorem a szukaną przeze mnie iniekcją. Problem się rozwiązał. Swoją drogą, dzięki za metodę przekątniową.

matmatmm
Użytkownik
Użytkownik
Posty: 2012
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 77 razy
Pomógł: 292 razy

Re: zbiór nieprzeliczalny

Post autor: matmatmm » 25 paź 2017, o 20:42

Chewbacca97 pisze: (...)Co jest w sumie logiczne, jeżeli liczb rzeczywistych jest więcej niż liczb naturalnych, to po dodaniu jeszcze jednego elementu do \(\displaystyle{ \RR}\), w dalszym ciągu jest ich więcej niż liczb naturalnych (...)
To (intuicyjne) rozumowanie to nic innego jak fakt, że z \(\displaystyle{ |A|<|B| \wedge |B|\le |C|}\). wynika \(\displaystyle{ |A|<|C|}\). Polecam udowodnić tę własność (do dowodu przyda się twierdzenie Cantora-Bernsteina). W twoim przypadku \(\displaystyle{ A=\NN,B=\RR,C=\RR\cup\{5-2i\}}\).

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9432
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 2072 razy

Re: zbiór nieprzeliczalny

Post autor: Dasio11 » 25 paź 2017, o 21:05

matmatmm pisze:(do dowodu przyda się twierdzenie Cantora-Bernsteina)
E tam.

Awatar użytkownika
Premislav
Użytkownik
Użytkownik
Posty: 15212
Rejestracja: 17 sie 2012, o 13:12
Płeć: Mężczyzna
Lokalizacja: Warszawa
Podziękował: 161 razy
Pomógł: 5047 razy

Re: zbiór nieprzeliczalny

Post autor: Premislav » 25 paź 2017, o 21:16

Może to głupie pytanie, ale jak to łatwo uzasadnić bez twierdzenia Cantora-Bernsteina?
Jak dla mnie \(\displaystyle{ |A|<|B| \wedge |B|\le |C|}\) oznacza, że istnieje surjekcja z \(\displaystyle{ C}\) na \(\displaystyle{ B}\) i że nie istnieje surjekcja z \(\displaystyle{ A}\) na \(\displaystyle{ B}\).
Nie wprost: weźmy pewną konkretną surjekcję \(\displaystyle{ \phi: C\rightarrow B}\);
gdyby istniała surjekcja \(\displaystyle{ \varphi}\) z \(\displaystyle{ A}\) na \(\displaystyle{ C}\), to
\(\displaystyle{ \phi \circ \varphi: A\rightarrow B}\) byłaby surjekcją z \(\displaystyle{ A}\) na \(\displaystyle{ B}\), a to jest sprzeczność.
Zatem taka \(\displaystyle{ \varphi}\) nie może istnieć.
Ale po pierwsze za Chiny ludowe nie pamiętam, czy to się właśnie tak definiuje, a po drugie nie wiem, czy nie przemycam tu jakiejś nieoczywistej rzeczy. Jeszcze po trzecie: dowód nie wprost wydaje mi się tu na siłę, ale prawie wszystkie dowody w zadaniach zahaczających choćby o elementarną teorię mnogości robię nie wprost, bo inaczej mam wrażenie, że zakładam tezę. Może da się to tutaj ominąć (wygląda to piekielnie niezgrabnie)?

Awatar użytkownika
Dasio11
Moderator
Moderator
Posty: 9432
Rejestracja: 21 kwie 2009, o 19:04
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 37 razy
Pomógł: 2072 razy

Re: zbiór nieprzeliczalny

Post autor: Dasio11 » 25 paź 2017, o 22:26

Twój dowód jest przez kontrapozycję i jest OK. Mam pewne wątpliwości co do definicji (ja wolę taką, że \(\displaystyle{ |A| \leqslant |B|}\) jeśli istnieje injekcja \(\displaystyle{ A \to B}\), bo wtedy działa jak \(\displaystyle{ A}\) jest pusty - dla tej definicji dowód jest analogiczny).

Awatar użytkownika
Chewbacca97
Użytkownik
Użytkownik
Posty: 462
Rejestracja: 9 lis 2013, o 22:09
Płeć: Mężczyzna
Podziękował: 33 razy
Pomógł: 120 razy

Re: zbiór nieprzeliczalny

Post autor: Chewbacca97 » 25 paź 2017, o 22:38

Premislav i Dasio11, ja skorzystałem z lematu:
Jeżeli \(\displaystyle{ f:A \rightarrow B}\) jest iniekcją i \(\displaystyle{ B}\) jest zbiorem przeliczalnym, to \(\displaystyle{ A}\) też jest zbiorem przeliczalnym.

Założyłem, że \(\displaystyle{ X = \RR\cup\{5-2i\}}\) jest zbiorem przeliczalnym. Wtedy inkluzja \(\displaystyle{ f: \RR \rightarrow X}\) jest żądaną iniekcją. A to oznaczałoby, że \(\displaystyle{ \RR}\) jest zbiorem przeliczalnym. Sprzeczność, ponieważ \(\displaystyle{ \RR}\) jest zbiorem nieprzeliczalnym. Czyli \(\displaystyle{ X}\) jest zbiorem nieprzeliczalnym.

Wydaje mi się, że analogicznie do was dowód przeprowadziłem. Jest w porządku?

matmatmm
Użytkownik
Użytkownik
Posty: 2012
Rejestracja: 14 cze 2011, o 11:34
Płeć: Mężczyzna
Lokalizacja: Sosnowiec
Podziękował: 77 razy
Pomógł: 292 razy

Re: zbiór nieprzeliczalny

Post autor: matmatmm » 25 paź 2017, o 22:52

Chewbacca97, Twój lemat jest równoważny zdaniu:

Jeśli \(\displaystyle{ |A|\le|B|}\) i \(\displaystyle{ A}\) jest nieprzeliczalny (czyli \(\displaystyle{ |A|>|\NN|}\)), to \(\displaystyle{ B}\) jest nieprzeliczalny (czyli \(\displaystyle{ |B|>|\NN|}\))

I jest on wnioskiem z własności, którą przytoczyłem w poprzednim poście:
matmatmm pisze:z \(\displaystyle{ |A|<|B| \wedge |B|\le |C|}\). wynika \(\displaystyle{ |A|<|C|}\)

Jan Kraszewski
Administrator
Administrator
Posty: 27305
Rejestracja: 20 mar 2006, o 21:54
Płeć: Mężczyzna
Lokalizacja: Wrocław
Podziękował: 1 raz
Pomógł: 4597 razy

Re: zbiór nieprzeliczalny

Post autor: Jan Kraszewski » 25 paź 2017, o 22:56

Chewbacca97 pisze:Jest w porządku?
Poprawnie (poza tym, że nie zdefiniowałeś \(\displaystyle{ f}\)...), ale nie powiem, żebym był zachwycony takim polowaniem na komara z armatą, jakieś ogólne twierdzenia, żeby załatwić jeden element. Wolałbym wskazanie bijekcji pomiędzy \(\displaystyle{ \RR}\) i \(\displaystyle{ \RR\cup\{5-2i\}}\)...

JK

Awatar użytkownika
Chewbacca97
Użytkownik
Użytkownik
Posty: 462
Rejestracja: 9 lis 2013, o 22:09
Płeć: Mężczyzna
Podziękował: 33 razy
Pomógł: 120 razy

Re: zbiór nieprzeliczalny

Post autor: Chewbacca97 » 25 paź 2017, o 23:22

Jan Kraszewski, przez inkluzję rozumiem funkcję \(\displaystyle{ \iota : A \rightarrow B}\), \(\displaystyle{ \iota\left( x\right) =x}\) (inclusion mapping? nie jestem pewien, jakie jest prawidłowe tłumaczenie)

Zapewne wychodzą tutaj moje braki, ale czy gdyby istniała wspomniana bijekcja pomiędzy \(\displaystyle{ \RR}\) i \(\displaystyle{ \RR\cup\{5-2i\}}\), to nie oznaczałoby to, że te dwa zbiory są równoliczne? A przecież \(\displaystyle{ X}\) posiada ten jeden, nieszczęsny, dodatkowy element. Niestety nie rozumiem więc, co miał pan na myśli.

ODPOWIEDZ