Maciej1 napisał(a): Zapewne chodziło autorowi o "zapis pozycyjny".Raczej nie, bo nie każdy zapis pozycyjny zadziała, tylko binarny.
Maciej1 napisał(a): "Dowód z metody diagonalnej" zawiera inny, istotny błąd logiczny, o którym ja piszę,No to muszę sobie teraz poszukać...
Maciej1 napisał(a): nie wiadomo czy liczba r różni się od f(x) ponieważ algorytm nie rozważa całego zbioru nieskończonego (wszystkich cyfr liczby r), rozważa dowolny n-ty, ale nie rozważa n+1-szegoA po co?
Hint: jaki jest warunek identyczności dwóch nieskończonych ciągów?
Albo inaczej: mamy dwa nieskończone ciągi, a_n i b_n. Wiemy, że dla pewnego k, a_k ≠ b_k. Czy wobec tego te ciągi mogą być identyczne?
EDIT: Uświadomiłem sobie, że argument powyżej nie jest wystarczający, bo reprezentacja (czy to dziesiętna, czy binarna) danej liczby nie jest jednoznaczna. Ciągi cyfr 1,0000... i 0,999.... różnią się, ale reprezentują tę samą liczbę. Hmm... pełen dowód może być nieco bardziej skomplikowany.
EDIT2: Ups, chyba na podstawie powyższego wymyśliłem funkcję, która wykrzacza dowód
Niech f(1) = 0,1 (w zapisie binarnym, czyli 0,5 dziesiętnie), a dla n>1, niech f(n) ma 0 na n-tym miejscu po przecinku. Wówczas tak skonstruowana liczba r to 0,011111111... = 0,1 - czyli f(1). Ups.
Nie znaczy to jeszcze, że f jest bijekcją, ale podważa wnioskowanie, że tak skonstruowana liczba r nie ma prawa należeć do przeciwdziedziny f.
EDIT3: Dla porządku zacytuję jeszcze wzmiankowany dowód:
zefciu napisał(a):Załóżmy, że istnieje pewna funkcja [latex]f(x)[/latex], której dziedziną jest ℕ, a przeciwdziedziną przedział zbioru ℝ (0, 1). Załóżmy, że funkcja ta jest bijekcją, tzn. jest funkcją różnowartościową, a jej funkcja odwrotna również jest różnowartościowa.
Rozważmy liczbę r, której n-ta cyfra po przecinku w rozwinięciu dziesiętnym binarnym jest 0 jeśli n-ta cyfra f(n) jest 1 lub 1, jeśli n-ta cyfra f(n) jest 0.
Liczba r różni się przynajmniej jedną cyfrą od każdej cyfry przeciwdziedziny f(x). Nie należy zatem do tej przeciwdziedziny. Jednocześnie r należy do przedziału (0,1) zbioru liczb rzeczywistych.
Ergo – istnieje taka liczba, która należy do zbioru (0, 1), a nie jest przeciwdziedziną funkcji f(x). Ergo – f(x) nie jest bijekcją. Absurd. Ergo – funkcja, której istnienie założyliśmy nie może istnieć.
EDIT4: Co prawda bezpośrednie mapowanie jako zbiór rozwinięć binarnych nie działa, ale dowód wyżej dowodzi nieprzeliczalności ciągów zerojedynkowych. Ciągi zerojedynkowe natomiast mogą być interpretowane jako rozwinięcia dziesiętne liczb (więc wspomnienie o liczbach dziesiętnych w oryginalnym dowodzie nie było błędne, ale było skrótem myślowym), i tutaj już nie będzie niejednoznaczności. Wobec powyższego, ponieważ takie liczby są pewnym podzbiorem odcinka (0,1), sam ten odcinek również musi być nieprzeliczalny. Uff, jednak działa (Musiałem wspomóc się https://en.wikipedia.org/wiki/Cantor%27s...l_argument)
"Tylko dwie rzeczy są nieskończone - Wszechświat i ludzka głupota. Co do Wszechświata nie jestem pewien" - Albert Einstein