Rozwinięcia ułamkowe w systemach pozycyjnych a zbiory mocy continuum

W tym wpisie postaram się omówić wykorzystanie rozwinięć dwójkowych liczb z przedziału [0,1] w popularnych dowodach: nieprzeliczalności przedziałów metodą przekątniową Cantora, a także dowodzie, że zbiór potęgowy zbioru liczb naturalnych jest mocy continuum. Wykorzystamy dowiedzione w poprzednich wpisach fakty, że każda liczba z [0,1] ma rozwinięcie w systemie dwójkowym (dwójkowy wystarczy spokojnie do naszych celów, ale możemy użyć każdego innego), a do tego tych rozwinięć są co najwyżej dwa (nawet wiemy, które liczby mają dwa a które jedno rozwinięcie). Zacznijmy od metody przekątniowej Cantora.

Metoda przekątniowa Cantora.

Będziemy chcieli wykazać, że przedział [0,1] jest nieprzeliczalny. Przypuśćmy więc, że jednak jest przeliczalny. Wtedy wszystkie liczby z przedziału [0,1] da się ustawić w różnowartościowy ciąg. Ponieważ na każdą liczbę przypadają co najwyżej dwa rozwinięcia w systemie dwójkowym (albo dowolnym o podstawie L), zbiór wszystkich rozwinięć liczb z przedziału [0,1] też się da ustawić w różnowartościowy ciąg. Na podobnej zasadzie jak ustawia się w ciąg liczby całkowite (rozwinięć będzie nie mniej niż liczb naturalnych a nie więcej niż całkowitych), bądź korzystając z faktu, że przeliczalna suma niepustych zbiorów skończonych jest zbiorem przeliczalnym.

Mamy więc nasz różnowartościowy ciąg ciągów \{a_n\}_{n=1}^\infty=\{\{c_k^n\}_{k=1}^\infty\}_{n=1}^\infty, bo pamiętamy, że rozwinięcia zdefiniowaliśmy jako ciągi cyfr, które występują po przecinku. Bardziej obrazowo, to mamy po prostu te cyfry po przecinku wylistowane wszystkie po kolei

c_1^1c_2^1c_3^1c_4^1\dots

c_1^2c_2^2c_3^2c_4^2\dots

c_1^3c_2^3c_3^3c_4^3\dots

c_1^4c_2^4c_3^4c_4^4\dots

\vdots

W metodzie przekątniowej interesuje nas tylko, jak sama nazwa wskazuje, przekątna dlatego uprościmy zapis mając na uwadze, że w miejscu X jest po prostu jakaś cyfra, a c_n jest n-tą cyfrą w n-tym ciągu

c_1XXXX\dots

Xc_2XXX\dots

XXc_3XX\dots

XXXc_4X\dots

\vdots

Ponieważ rozwinięcia te są w systemie dwójkowym (dowolnym o podstawie L), to mamy do dyspozycji (przynajmniej) dwie cyfry, zatem konstruujemy ciąg \{d_n\}_{n=1}^\infty, który na n-tym miejscu przyjmuje inną cyfrę niż c_n. Otrzymujemy w ten sposób pewien ciąg cyfr. Zauważmy, że różni się przynajmniej n-tym elementem od n-tego ciągu, co daje sprzeczność z tym, że w naszym ciągu ciągów miał występować każdy ciąg cyfr. W związku z tym otrzymujemy, że przedział [0,1] jest nieprzeliczalny.

Alternatywny sposób

Moglibyśmy też poprowadzić inaczej rozumowanie. Jeśli przedstawimy wszystkie liczby z przedziału [0,1] przy pomocy rozwinięć w systemie pozycyjnym przy podstawie L\geq 3 wybierając np. rozwinięcie skończone – jeśli tylko liczba takie posiada, wtedy ponownie zakładając nie wprost, że przedział [0,1] jest nieprzeliczalny otrzymamy ciąg liczb

0,c_1^1c_2^1c_3^1c_4^1\dots

0,c_1^2c_2^2c_3^2c_4^2\dots

0,c_1^3c_2^3c_3^3c_4^3\dots

0,c_1^4c_2^4c_3^4c_4^4\dots

\vdots

i podobnie jak przedtem konstruujemy rozwinięcie, a więc liczbę

0,d_1d_2d_3\dots

taką, że d_n\neq c^n_n, ale uważając, aby nasz ciąg nie był złożony od pewnego miejsca ciągle z cyfr L-1, gdyż wtedy ta liczba i tak nie należałaby do powyższego ciągu z definicji, więc nie otrzymalibyśmy sprzeczności. Ponieważ mamy do wyboru przynajmniej dwie cyfry, gdyż L \geq 3, to możemy skonstruować taki ciąg. Otrzymamy więc sprzeczność.

Zbiór potęgowy zbioru liczb naturalnych.

Teraz zajmiemy się zbiorem podzbiorów liczb naturalnych. Z twierdzenia Cantora wiadomo, że jest nieprzeliczalny, ale już nie wiadomo czy jego moc przypadkiem nie jest np. gdzieś pomiędzy mocami zbiorów liczb naturalnych i liczb rzeczywistych albo czy nie jest większa niż zbioru liczb rzeczywistych. Jednak moc \mathcal{P}(\mathbb{N}) jest dokładnie continuum. Jedną z metod dowodzenia tego faktu są właśnie rozwinięcia dwójkowe. Przejdźmy zatem do dowodu.

Zwróćmy uwagę na samym początku, że „przepuszczając” dowolny podzbiór A zbioru \mathbb{N} przez funkcję wskaźnikową (tj. \chi_A(n)=1 gdy n \in A oraz \chi_A(n)=0 gdy n\notin A określoną dla wszystkich n naturalnych) wygeneruje ona nieskończone ciągi złożone z zer i jedynek. Chodzi dokładnie o ciągi o wyrazach c_n=\chi_A(n). Tak naprawdę między ciągami zero-jedynkowymi a podzbiorami liczb naturalnych mamy odpowiedniość 1:1. Wiemy, że każdy pozdbiór generuje nam ciąg zero-jedynkowy. Mamy zatem poprawie określoną fukcję

T: 2^\mathbb{N} \ni A \mapsto \{\chi_A(n)\}_{n=0}^\infty \in \{0,1\}^\mathbb{N}

między zbiorem potęgowym liczb naturalnych, a zbiorem ciągów zero-jedynkowych.

Jeśli teraz weźmiemy dowolny ciąg zero-jedynkowy \{ c_n \}_{n=0}^\infty, to dla podzbioru liczb naturalnych (nie szkodzi, gdy jest pusty)

A=\{n\in \mathbb{N}: c_n=1 \}

mamy

T(A)=\{ c_n \}_{n=0}^\infty

więc T jest funkcją „na”.

Dodatkowo gdyby dla pewnych podzbiorów liczb naturalnych zachodziło

T(A)=T(B)

to dla każdego naturalnego n

\chi_A(n)=\chi_B(n)

zatem

n \in A \Leftrightarrow n \in B

czyli T jest różnowartościowa.

Możemy więc zamiast mocy zbioru potęgowego badać moc zbioru rozwinięć dwójkowych. Wiemy dzięki metodzie przekątniowej, że nie jest przeliczalny, będziemy chcieli teraz pokazać, że jest dokładnie mocy continuum. Nie mamy  prostej odpowiedniości 1:1 pomiędzy \{0,1\}^\mathbb{N} a przedziałem [0,1], gdyż jak wiemy niektóre liczby posiadają dwa rozwinięcia. Jest ich zatem „za dużo” jak na przedział [0,1], ale tylko pozornie. Będziemy musieli zatem coś zrobić z powtarzającymi liczbami. Przerzucimy je do przedziału [1,2]. Określimy teraz funkcję F: \{0,1\}^\mathbb{N} \mapsto [0,2]
następującym wzorem: bierzemy dowolny ciąg zero-jedynkowy \{ c_n \}_{n=0}^\infty i teraz

  1. Gdy \{ c_n \}_{n=0}^\infty od pewnego momentu przyjmuje same zera (ułamki skończone) a także gdy przyjmuje wyłącznie jedynki (rozwinięcie liczby jeden), to definiujemy \displaystyle F(\{ c_n \}_{n=0}^\infty):=\sum_{n=0}^\infty \frac{c_n}{2^{n+1}}.
  2. Gdy \{ c_n \}_{n=0}^\infty od pewnego k>0 przyjmuje same jedynki, to definiujemy \displaystyle F(\{ c_n \}_{n=0}^\infty):=1+ \sum_{n=1}^\infty \frac{c_n}{2^{n+1}}.
  3. W pozostałych przypadkach (jedynki i zera przeplatają się w nieskończoność) definiujemy tak samo jak w punkcie pierwszym \displaystyle F(\{ c_n \}_{n=0}^\infty):=\sum_{n=0}^\infty \frac{c_n}{2^{n+1}}.

Zgodnie z tym, co wiemy z poprzednich wpisów punkty 1. i 3. zapełnią cały przedział [0,1] bez powtarzania żadnej liczby, a punkt 2. przerzuci powtarzające się liczby do przedziału [1,2]. Otrzymujemy zatem, że funkcja F wyznacza nam odpowiedniość 1:1 między zbiorem \{0,1\}^\mathbb{N}) a pewnym zbiorem X=T(\{0,1\}^\mathbb{N}), który zawarty jest w przedziale [0,2], a który jednocześnie zawiera przedział [0,1]. Stąd moc X jest nie mniejsza niż przedziału [0,1], a jednocześnie nie większa niż przedziału [0,2], ale dowolne dwa przedziały są równoliczne, a więc zbiór ciągów zero-jedynkowych jest mocy continuum.
Powyższe rozumowanie możemy podsumować w ten sposób, że ciągów zero-jedynkowych jest tyle, co liczb w przedziale [0,1] i jeszcze pewien ciąg (gdyż skończonych ułamków jest przeliczalnie wiele).

Alternatywny sposób

W zasadzie skoro i tak korzystam z antysymetryczności nierówności dla mocy, można pokazać to prościej. Zainspirował mnie dowód równoliczności \mathbb{R} z \mathcal{P} (\mathbb{N}) forum matematyka.pl autorstwa PFloyd. Wiemy, że funkcja przypisująca liczbom z przedziału [0,1] rozwinięcia, np. te, które są nieskończone jest różnowartościowa. Stąd mamy pierwszą nierówność dla mocy \# \mathcal{P} (\mathbb{N}) \geq \# [0,1]. Teraz zaś przypisując ciągom zero-jedynkowym \{ c_n \}_{n=0}^\infty liczby w sposób następujący

\displaystyle G(\{ c_n \}_{n=0}^\infty):=\sum_{n=0}^\infty \frac{c_n}{3^{n+1}}

otrzymamy ponownie funkcję różnowartościową, gdyż w systemie trójkowym, aby dwa rozwinięcia reprezentowały tę samą liczbę, jedno z nich musi od pewnego momentu stale przyjmować cyfrę 2. Stąd dostajemy drugą nierówność \# \mathcal{P} (\mathbb{N}) \leq \# [0,1]. Przy okazji łącznie ze wspomnianym dowodem z matematyka.pl dostajemy bez użycia funkcji tangens, że \# \mathbb{R} = \# [0,1].