Jednoznaczność rozwinięć

Jak pokazaliśmy poprzednio, każda liczba z przedziału [0,1] ma swoje rozwinięcie (nieskończone) w systemie liczbowym o dowolnej podstawie L>1.  W tym odcinku zamierzam opisać problem jednoznaczności takich rozwinięć. Innymi słowy będziemy badać zależności między takimi ciągami cyfr \{c_n\}_{n=1}^\infty, \{d_n\}_{n=1}^\infty, że

\displaystyle \sum_{n=1}^\infty \frac{c_n}{L^n}=\sum_{n=1}^\infty \frac{d_n}{L^n}.

Najpierw udowodnimy przydatny lemat.

Lemat.

Jedynym rozwiązaniem równania

x_0+x_1L + \dots + x_NL^N=0

spośród całkowitych -L<x_i<L jest x_0=0, x_1=0, \dots x_N=0.

Dowód.

Dowód przeprowadzimy indukcyjnie ze względu na ilość niewiadomych.

Dla N=0 mamy wprost x_0=0. Załóżmy, że teza spełniona jest, gdy mamy N+1 niewiadomych i rozważmy równanie dla N+2 niewiadomych

x_0+x_1L + \dots +x_NL^N + x_{N+1}L^{N+1}=0.

Stąd po przeniesieniu

x_1L + \dots +x_NL^N + x_{N+1}L^{N+1}=-x_0.

Zauważmy, że dla x_i całkowitych lewa strona jest całkowita a dodatkowo podzielna przez L. Stąd dostajemy, że L|x_0, ale -L<x_0<L, więc jedyna możliwość to x_0=0.

Zatem nasze równanie przyjmuje postać

x_1L + \dots +x_NL^N + x_{N+1}L^{N+1}=0.

i teraz wracając do poprzedniej postaci przez podzielenie obustronne przez L otrzymujemy równanie z N+1 niewiadomymi

x_1 + x_2L\dots +x_NL^{N-1} + x_{N+1}L^{N}=0.

którego rozwiązaniem z założenia indukcyjnego jest x_i=0 dla i=1, 2, \dots N+1. Zatem lemat mamy dowiedziony i możemy zająć się teraz badaniem rozwinięć.

Powiedzmy, że mamy daną dowolną liczbę x \in [0,1], którą można przedstawić przy pomocy rozwinięć \{c_n\}_{n=1}^\infty, \{d_n\}_{n=1}^\infty.

Własność 1.

Jeśli dla pewnej liczby  po przecinku rozwinięcia \{c_n\}_{n=1}^\infty, \{d_n\}_{n=1}^\infty są równe to są również takie same dla wszystkich wcześniejszych cyfr. Czyli mówiąc po polsku, jeśli istnieje n_0 takie, że c_{n_0}=d_{n_0}, to \forall k \leq n_0: \thinspace c_k=d_k.

Dowód.

Jeśli n_0=1, to nie ma już żadnych wcześniejszych wyrazów i nie ma czego dowodzić, zakładamy więc n_0>1.

Wiemy, że \displaystyle \sum_{n=1}^\infty \frac{c_n}{L^n}=x=\sum_{n=1}^\infty \frac{d_n}{L^n}. Stąd

\displaystyle \sum_{n=1}^\infty \frac{c_n-d_n}{L^n}=0

W powyższym szeregu wyraz n_0 jest równy 0, ponieważ c_{n_0}=d_{n_0}. Dzięki temu możemy zapisać, że

\displaystyle \sum_{n=1}^{n_0-1} \frac{c_n-d_n}{L^n}+\sum_{n=n_0+1}^\infty \frac{c_n-d_n}{L^n}=0

A po przeniesieniu i obustronnym przemnożeniu przez L^{n_0-1} otrzymujemy, że

\displaystyle \sum_{n=1}^{n_0-1} \frac{c_n-d_n}{L^{n-(n_0-1)}}=-\sum_{n=n_0+1}^\infty \frac{c_n-d_n}{L^{n-(n_0-1)}}

Zamieńmy wskaźnik sumowania w szeregu po prawej stronie równania tak, aby pozbyć się n-(n_0-1), czyli zastępujemy go przez k=n-(n_0-1). Skoro sumowanie zaczynaliśmy od n=n_0+1, to sumowanie po k zaczniemy od k=n_0+1-n_0+1=2. Mamy więc następujący szereg

\displaystyle \sum_{k=2}^\infty \frac{a_k}{L^k},

gdzie a_k=c_{n-(n_0-1)}-d_{n-(n_0-1)}, co ma znaczenie o tyle, że wartości a_k są liczbami całkowitymi wahającymi się od -(L-1) do L-1, bo c_n i d_n przyjmują wartości całkowite od 0 do L-1. Ponieważ sumujemy od dwójki, to suma takiego szeregu będzie należała do przedziału (-1,1), bo zawsze zabraknie nam \frac{L-1}{L} do 1 lub \frac{-(L-1)}{L} do -1.  Oszacowaliśmy prawą stronę równości, przyjrzyjmy się więc teraz lewej stronie, żeby zobaczyć co z tego dla niej wynika.

\displaystyle \sum_{n=1}^{n_0-1} \frac{c_n-d_n}{L^{n-(n_0-1)}}.

Przenosząc L do licznika otrzymujemy

\displaystyle \sum_{n=1}^{n_0-1} (c_n-d_n)L^{(n_0-1)-n}.

Ponieważ sumujemy po n, które wynoszą co najwyżej n_0-1, więc przy L wystąpią nieujemne potęgi. Dodatkowo różnice c_n-d_n są całkowite.  Stąd cała lewa strona jest całkowita, a ponieważ oszacowaliśmy, że należy do przedziału (-1,1), to musi być równa zero.

\displaystyle \sum_{n=1}^{n_0-1} (c_n-d_n)L^{(n_0-1)-n}=0.

Zauważmy, że jest to równanie o postaci z Lematu, gdzie rolę x_k pełnią c_k-d_k. Zatem na mocy Lematu otrzymujemy, że c_n-d_n=0 dla dowolnego n\leq n_0 -1. Dostaliśmy więc, że c_n=d_n dla wszystkich n \leq n_0, co było do wykazania.

Wniosek.

Dwa różne rozwinięcie tej samej liczby albo są wszędzie różnie, albo są równe do pewnego momentu a potem cały czas różne.

Przyjrzymy się teraz w jaki sposób mogą się różnić dwa różne rozwinięcia tej samej liczby.

Własność 2.

Dla dwóch różnych rozwinięć \{c_n\}_{n=1}^\infty oraz \{d_n\}_{n=1}^\infty tej samej liczby x, pierwsze cyfry, które się różnią, różnią się o 1.

Wizualnie wygląda to tak:

x=c_1c_2c_3\dots c_{N-1} (d_N+1) c_{N+1} c_{N+2} \dots

x=c_1c_2c_3 \dots c_{N-1} \quad d_N \quad d_{N+1} d_{N+2} \dots

rozwinięcia te są równe do N-1 cyfry, potem różnią się o 1. Następne cyfry układają się wg schematu, który przedstawia kolejna własność.

Własność 3.

Gdy N-ta cyfra w rozwinięciu \{c_n\}_{n=1}^\infty jest większa o jeden od N-tej cyfry rozwinięcia \{d_n\}_{n=1}^\infty tej samej liczby x, to wszystkie cyfry począwszy od N+1 rozwinięcia \{c_n\}_{n=1}^\infty są zerami, a w rozwinięciu \{d_n\}_{n=1}^\infty występują od N+1 wyłącznie cyfry L-1.

Wizualnie (uwzględniając poprzednie własności):

x=c_1c_2c_3\dots c_{N-1} (c+1) 0 0 0 \dots

x=c_1c_2c_3 \dots c_{N-1} \quad c \quad (L-1) (L-1) (L-1) \dots

Udowodnimy zbiorczo obie własności.

Dowód.

Przyjmijmy oznaczenie jak powyżej, tzn. niech N będzie numerem pierwszej cyfry po przecinku, dla której c_n różni się od d_n. Zatem na podstawie Własności 1 c_n=d_n dla n<N (o ile takowe istnieją). Wiedząc, że c_N\neq d_N, możemy przyjąć na przykład, że c_N>d_N. Korzystając, że rozwinięcia te prowadzą to tej samej liczby mamy oczywiście, że

\displaystyle \sum_{n=1}^\infty \frac{d_n-c_n}{L^n}=0.

Ale na podstawie wcześniejszych uwag pierwsze N-1 wyrazów się kasuje (o ile istnieją). Stąd (w każdym przypadku)

\displaystyle \sum_{n=N}^\infty \frac{d_n-c_n}{L^n}=0.

Wyłączmy z sumy pierwszy wyraz, tzn. dla n=N, i  przenieśmy na drugą stronę. Otrzymujemy:

\displaystyle \sum_{n=N+1}^\infty \frac{d_n-c_n}{L^n}=\frac{c_N-d_N}{L^N}.

Po przemnożeniu przez L^N mamy:

\displaystyle \sum_{n=N+1}^\infty \frac{d_n-c_n}{L^{n-N}}=c_N-d_N.

Zamieńmy znowu wskaźnik sumowania dla szeregu po lewej stronie równości poprzez przyjęcie k=n-N.  Ponieważ sumowaliśmy od n=N+1, to sumowanie po k zaczniemy od k=N+1-N=1. Otrzymamy zatem, podobnie jak poprzednio szereg postaci

\displaystyle \sum_{k=1}^\infty \frac{a_k}{L^k},

gdzie wartości a_k wahają się od -(L-1) do L-1.

Widać stąd, że nie może być c_N-d_N>1, bo szereg po lewej stronie równości w najlepszym wypadku będzie równy 1 (tzn. gdy każde a_k będzie wynosiło L-1).

Ponieważ c_N-d_N\leq1 a jednocześnie wiedząc, że te cyfry się różnią, jedyną możliwości jest, aby c_N-d_N=1. Dowiedliśmy w ten sposób Własność 2. Jednocześnie kontynuując rozważania w tym momencie otrzymamy Własność 3. W tej sytuacji bowiem, jedyną możliwością doboru pozostałych cyfr jest, aby d_n-c_n=L-1 dla n>N (mamy tu rozwinięcie jedynki, które jest jednoznaczne), co implikuje, że musi być d_n=L-1 a c_n=0.

Podsumowanie.

Poprzednio pokazaliśmy, że każda liczba z przedziału [0,1] ma rozwinięcie w systemie o podstawie L. Teraz wiemy też, że albo są one jednoznaczne, albo liczba ma dokładnie dwa rozwinięcia. W tej drugiej sytuacji, tzn. gdy  mamy  \{c_n\}_{n=1}^\infty, \{d_n\}_{n=1}^\infty dwa różne rozwinięcia liczby x z przedziału [0,1] wiemy, że są do pewnego momentu takie same (no chyba, że różnią się już przy pierwszej cyfrze), następnie pierwsza różna cyfra np. w \{c_n\}_{n=1}^\infty jest mniejsza o jeden od cyfry w \{d_n\}_{n=1}^\infty, wtedy pozostałe cyfry w \{c_n\}_{n=1}^\infty muszą być równe L-1, a pozostałe w cyfry w \{d_n\}_{n=1}^\infty wynoszą 0.

Zatem słuszny był przykład z poprzedniego wpisu, że 0,5=0,4999\dots (w systemie dziesiątkowym oczywiście). Dodatkowo wiemy teraz także, że inaczej nie da się rozwinąć tej liczby. Ogólnie, jedynymi liczbami, które posiadają drugie rozwinięcie są liczby, które od pewnego momentu mają po przecinku same zera (lub same dziewiątki w systemie dziesiątkowym bądź odpowiadające im L-1 w dowolnym systemie). W szczególności są to liczby wymierne i jest ich nieskończenie wiele, stąd jest ich przeliczalnie wiele.

W następnym wpisie wykorzystamy te rozwinięcia w praktyce, tzn. w teorii, głównie mnogości. ;) Pojawi się metoda przekątniowa Cantora oraz moc zbioru potęgowego liczb naturalnych. Zapraszam!

Advertisements

2 uwagi do wpisu “Jednoznaczność rozwinięć

  1. Pingback: Systemy pozycyjne i algorytm wyznaczania cyfr | roznematematyka

  2. Pingback: Rozwinięcia dwójkowe a zbiory mocy continuum | roznematematyka

Skomentuj

Wprowadź swoje dane lub kliknij jedną z tych ikon, aby się zalogować:

Logo WordPress.com

Komentujesz korzystając z konta WordPress.com. Log Out / Zmień )

Zdjęcie z Twittera

Komentujesz korzystając z konta Twitter. Log Out / Zmień )

Facebook photo

Komentujesz korzystając z konta Facebook. Log Out / Zmień )

Google+ photo

Komentujesz korzystając z konta Google+. Log Out / Zmień )

Connecting to %s