Dwa dowody jednego twierdzenia

Zbiór wszystkich liczb rzeczywistych $|R$ nie jest równoliczny ze zbiorem wszystkich liczb naturalnych $N:$

Przypomnijmy: zbiory $|A$ i $B$ są równoliczne, gdy istnieje funkcja różnowartościowa z $A$ na $B$ (lub - równoważnie - z $B$ na $)A.$

Twierdzenie. Zbiór wszystkich liczb rzeczywistych $|R$ nie jest równoliczny ze zbiorem wszystkich liczb naturalnych $N.$

Dowód przekątniowy

Gwoli jednoznaczności przyjmijmy, że każdą niezerową liczbę z przedziału $|[0, 1]$ reprezentujemy przez jej rozwinięcie dziesiętne, w którym jest nieskończenie wiele cyfr niezerowych (a więc, na przykład, 1/4 jest reprezentowana przez $0,24(9),$ a nie $|0,25$ ). Wówczas każda liczba rzeczywista z przedziału $|[0,1]$ ma dokładnie jedną reprezentację dziesiętną. Niech $| f N [0,1]$ będzie dowolną funkcją z $N$ w przedział domknięty $|[0, 1],$ czyli ciągiem o wyrazach rzeczywistych należących do tego przedziału, i niech $| f(k) = 0,ak1ak2ak3...,$ gdzie $|akm$ oznacza $m |$ -tą cyfrę po przecinku liczby $f (k).$ Niech dalej

bk = 4, gdy akk ≠4 oraz bk = 5, gdy akk = 4.

Wówczas liczba $b = 0,bb b ... 1 2 3$ należy do przedziału $[0,1]$ i nie jest wyrazem ciągu $f.$ Rzeczywiście: $|b≠ f (1),$ bo $b1 ≠a11,$ podobnie $|b≠ f(2),$ bo $b2 ≠ a22$ i tak dalej. Ogólniej, dla każdej liczby naturalnej $|k,bk≠ akk,$ co oznacza, że $|b ≠ f (k).$

Wobec dowolności wyboru funkcji $f$ możemy stwierdzić, że nie istnieje funkcja z $N$ w $|[0,1],$ której zbiór wartości wyczerpywałby przedział $|[0, 1]$ ; tym bardziej nie istnieje funkcja z $N$ na całe $R.$

Dowód analityczny

Jak poprzednio, niech $f N [0,1]$ będzie dowolną funkcją z $|N$ w przedział domknięty $[0,1],$ czyli ciągiem o wyrazach rzeczywistych należących do tego przedziału.

Niech $f (k) = ck$ dla $k ∈N.$ Podzielmy przedział $[0,1]$ na trzy domknięte podprzedziały o długości 1/3 każdy i niech $[a ,b ] 0 0$ będzie takim z nich, do którego nie należy $c0.$ Tak więc $1 |[a0,b0] ⊂ [0, 1],b0 −a0 = 3$ oraz $|c0 /∈ [a0,b0].$ Załóżmy, że dla $k ∈ N$ zdefiniowaliśmy już przedział $|[ak, bk]$ tak, że $[ak,bk] ⊂ [0,1],bk − ak = 31k 1$ oraz $ck /∈ [ak,bk].$ Wówczas dzielimy przedział $|[a ,b ] k k$ na trzy domknięte podprzedziały równej długości i definiujemy $|[ak+1,bk+1]$ jako ten podprzedział, do którego nie należy $|ck+1.$ Mamy wtedy:

--1- [ak+1,bk+1]⊂ [ak,bk], bk+1− ak+1 = 3k+2 oraz ck+1 /∈ [ak+1,bk+1].

W ten sposób na mocy indukcji otrzymujemy taki ciąg przedziałów $|[a ,b ], n n$ że dla każdej liczby naturalnej $n$

[an+1,bn+1]⊂ [an,bn] ⊂[0,1], bn − an =--1- oraz cn /∈ [an,bn]. 3n+1

Ciąg $|(an)$ jest niemalejący i ograniczony z góry przez 1, ciąg $(bn)$ jest nierosnący i ograniczony z dołu przez 0, zatem oba te ciągi są zbieżne i mają wspólną granicę, gdyż ciąg $(bn − an)$ dąży do 0; nazwijmy ją $|c.$ Ponadto dla każdej liczby naturalnej $n, c∈ [a ,b ], n n$ podczas gdy $|cn /∈ [an, bn].$ Wniosek: $|c≠ cn$ dla każdego $n.$

Tak więc nie istnieje funkcja z $N$ w $[0,1],$ której zbiór wartości wyczerpywałby przedział $[0,1]$ ; tym bardziej nie istnieje funkcja z $|N$ na całe $|R.$