Zrobił się z tego podtemat w śmietniku, ale sam temat jest ciekawy, więc stwierdziłem, że stworzę właściwy wątek o tej kwestii.
@Maciej nie lubi dowodu Cantora na nierównoliczność zbiorów liczb naturalnych i rzeczywistych - ale to nic. Można tę nierównoliczność udowodnić inaczej.
Przypomnijmy: zbiory A i B są równoliczne jeśli istnieje bijekcja między tymi zbiorami. Bijekcja natomiast jest to funkcja, która każdemu elementowi zbioru A przyporządkowuje inny element zbioru B, i każdy element zbioru B jest przyporządkowany do jakiegoś elementu zbioru A. Innymi słowy, zbiory są równoliczne, jeśli ich elementy możemy "połączyć w pary". W jakie pary, to nieistotne - ważne, że da się połączyć w jakieś pary.
Na przykład, zbiory {1, 2} i {3, 4} możemy połączyć w pary: np. (1,3) i (2,4). Albo (1,4) i (2,3). Nieistotne. Bijekcja istnieje, więc zbiory są równoliczne.
Ale zbiorów {1, 2} i {3, 4, 5} połączyć w pary się nie da. Nieważne jakie liczby ze zbioru {3, 4, 5} przyporządkujemy liczbom 1 i 2, zawsze jakaś zostanie "luzem". Bijekcja nie istnieje, zbiory nie są równoliczne.
Dla zbiorów nieskończonych też to działa. Na przykład, zbiory liczb naturalnych i całkowitych są równoliczne. "Ale jak to", można spytać, "przecież liczby naturalne są zawarte w liczbach całkowitych, więc jak każdej liczbie naturalnej przyporządkujemy jej odpowiednik w liczbach całkowitych, to zostaną wszystkie liczby ujemne?". Tak - w takim przypadku zostaną, więc takie przyporządkowanie nie jest bijekcją. Ale pytanie brzmi czy bijekcja istnieje, a nie czy każde przyporządkowanie jest bijekcją. A bijekcja istnieje, na przykład taka:
Każdej liczbie naturalnej n przyporządkowujemy: jeśli n jest parzyste, liczbę n/2, a jeśli jest nieparzyste, liczbę -(n+1)/2. Czyli wygląda to jakoś tak:
0 → 0
1 → -1
2 → 1
3 → -2
4 → 2
...
Każdej liczbie naturalnej jest przyporządkowana jakaś liczba całkowita, i nie ma dwóch którym byłaby przyporządkowana ta sama. I na odwrót, każda liczba całkowita jest przyporządkowana jakiejś liczbie naturalnej. Weźmy liczbę całkowitą z. Jeśli jest to liczba ujemna, jest ona przyporządkowana liczbie naturalnej -2z - 1. Jeśli jest dodatnia, jest przyporządkowana liczbie 2z. Wszystko się zgadza. Bijekcja istnieje. Zbiory są równoliczne.
Podobnie można udowodnić również równoliczność zbiorów liczb naturalnych i liczb wymiernych. A co z liczbami rzeczywistymi?
Cantor udowodnił, że dla liczb naturalnych i liczb rzeczywistych nie da się stworzyć bijekcji. Zatem, choć oba te zbiory liczb są nieskończone, nie są one tak samo nieskończone. Jego dowód jest dość znany i można go sobie wygooglać. Tutaj przedstawię inny dowód, na który nie da się przenieść zastrzeżeń Macieja odnośnie dowodu Cantora.
Zacznijmy od definicji: zbiorem potęgowym zbioru X, oznaczanym 2^X albo P(X), nazywamy zbiór wszystkich podzbiorów zbioru X.
Czyli na przykład: jeśli X = {1, 2}, to zbiór P(X) = { ∅, {1}, {2}, {1, 2} }. Każdy możliwy podzbiór X jest elementem zbioru P(X).
Co więcej, dla zbiorów skończonych zachodzi fakt, że jeśli zbiór X ma n elementów, to zbiór P(X) ma 2^n elementów (stąd też częsta notacja 2^X). Czemu? Dość łatwo to zobaczyć: każdy podzbiór X możemy zdefiniować przyporządkowując elementom X 1 jeśli należą do tego podzbioru i 0 jeśli nie należą. Ponieważ dla każdego elementu mamy dwie możliwości, ogólnie możemy podzbiór zdefiniować na 2^n możliwości.
Ze zbiorami nieskończonymi jest nieco trudniej, bo nie ma za bardzo czegoś takiego jak 2^nieskończoność. Ale istnieje ciekawe twierdzenie:
Żaden zbiór X nie jest równoliczny ze swoim zbiorem potęgowym P(X).
(Nawiasem mówiąc, to twierdzenie jest znane jako... twierdzenie Cantora.)
Jak to udowodnić? Najłatwiej nie wprost.
Załóżmy, że zbiory X i P(X) są równoliczne. To znaczy, że istnieje jakaś bijekcja ze zbioru X w zbiór P(X). Nazwijmy tę bijekcję f. To oznacza, że każdemu elementowi x zbioru X przyporządkowany jest obiekt f(x), który jest zbiorem - i do tego podzbiorem zbioru X.
Możemy zatem sensownie spytać, czy jakiś element x zbioru X jest również elementem f(x)? Czasem odpowiedź będzie "tak", czasem "nie". Zdefiniujmy zatem zbiór A:
A = { x ∈ X: x ∉ f(x) }
Jest to zbiór tych i tylko tych elementów zbioru X, które nie należą do podzbiorów X przyporządkowanych im przez bijekcję f.
Ale właśnie - f miało być bijekcją, a zbiór A zawiera wyłącznie elementy zbioru X, więc jest jakimś podzbiorem X. Czyli musi istnieć jakiś element zbioru X - nazwijmy go a - któremu f przyporządkowuje zbiór A:
f(a) = A
To teraz pytanie - czy a należy do zbioru A?
Jeśli należy - to należy do podzbioru, który przyporządkowuje mu funkcja f, czyli zgodnie z definicją zbioru A, nie należy do zbioru A.
A jeśli nie należy, to z definicji zbioru A, należy do zbioru A.
Czyli jeśli a należy do zbioru A, to do niego nie należy, a jeśli do niego nie należy, to do niego należy.
Sprzeczność. I ta sprzeczność wynika z tego, że założyliśmy istnienie bijekcji f. Czyli taka bijekcja istnieć nie może. Zbiory X i P(X) nie są równoliczne. ∎
Fajnie, ale co to ma do tematu?
- Nie zakładaliśmy nic o zbiorze X. Dowód działa tak samo dla zbiorów skończonych, jak i nieskończonych. Czyli na dzień dobry, zbiór liczb naturalnych nie jest równoliczny ze zbiorem podzbiorów liczb naturalnych. Już mamy dwa nieskończone zbiory, które nie są równoliczne. Co na to @Maciej ?
- Zbiór
P(N) jest równoliczny ze zbiorem liczb rzeczywistych. Przykładową konstrukcję bijekcji między podzbiorami liczb naturalnych a liczbami rzeczywistymi można znaleźć tutaj: https://math.stackexchange.com/questions/1645130/explicit-bijection-between-mathbbr-and-mathcalp-mathbbn
W związku z powyższym, mamy alternatywny dowód, że zbiór liczb naturalnych nie jest równoliczny ze zbiorem liczb rzeczywistych.
No to teraz powodzenia, @Maciej . Szukaj dziury w całym.
