Definiowanie przez indukcję

[Jakub Gurak]

Ciąg Fibonacciego jest zdefiniowany następująco:

\(\displaystyle{ \begin{cases} a_0=1, \\ a_1=1,\\ a_n=a_{n-1}+a_{n-2}, \hbox{ dla } n\ge 2 \end{cases} }\)

Czyli \(\displaystyle{ a_2=a_1+a_0=2, a_3=a_2+a_1=3,a_4=a_3+a_2=5, a_5=8,a_6=13,\ldots}\)

Zauważmy, że formalnie nie jest to ciąg, tylko inna funkcja, gdyż jej dziedziną nie jest zbiór liczb naturalnych. Funkcja ta działa trochę inaczej:

\(\displaystyle{ 0 \rightarrow 1,\\
1 \rightarrow 1,\\
\left( 1,1\right) \rightarrow 1+1=2,\\
\left( 2,1\right) \rightarrow 2+1=3,\\
\left( 3,2\right) \rightarrow 3+2=5,\\
\ldots}\)

A więc dziedziną tej funkcji nie są wszystkie kolejne liczby naturalne, tylko najpierw co prawda \(\displaystyle{ 0,1}\), a potem pary \(\displaystyle{ \left( 1,1\right) ;\left( 2,1\right); \left( 3,2\right) ;\ldots }\)

I właśnie twierdzenie o definiowaniu przez indukcję mówi, że taki sposób definiowania jest poprawny, gdyż wyznacza dokładnie jeden ciąg, taki, że

\(\displaystyle{ 0 \rightarrow 1,\\
1 \rightarrow 1,\\
2 \rightarrow 1+1=2,\\
3 \rightarrow 2+1=3,\\
4 \rightarrow 3+2=5,\\
\ldots
}\)
Czyli to czego chcemy.

W ogólności chodzi o to, że jeśli określimy sposób konstrukcji wartości ciągu podając jego wyraz zerowy (lub pierwsze dwa tak jak tu, ewentualnie pierwsze trzy, itd.- ), a w dalszych krokach jeśli określimy sposób konstrukcji wartości ciągu na argumencie \(\displaystyle{ n}\) na podstawie wartości tego ciągu określonych na liczbach naturalnych \(\displaystyle{ m<n}\), (czyli na podstawie kroków poprzednich), oraz na podstawie wartości \(\displaystyle{ n}\), to taki sposób definiowania jest poprawny gdyż wyznaczymy dokładnie jeden ciąg nieskończony, który idzie zgodnie z naszym konstruowaniem.

Ciekawy jest też szkic dowodu tego faktu. Aby udowodnić istnienie poszukiwanego ciągu nieskończonego, rozważa się rodzinę \(\displaystyle{ H}\), ciągów skończonych , które idą zgodnie z naszym konstruowaniem, a na koniec bierzemy \(\displaystyle{ \bigcup H}\) jako ciąg nieskończony( co wykazujemy). Myślę, że to ciekawe.

Ten sposób definiowania pozwala nie tylko zdefiniować ciąg Fibonacciego, nie tylko wszystkie inne tym sposobem ciągi liczb naturalnych, ale ma wiele innych zastosowań, np. jest bardzo pomocne w udowodnieniu, że jeżeli zbiór \(\displaystyle{ M}\) jest nieskończonym podzbiorem \(\displaystyle{ \NN}\), to zbiór \(\displaystyle{ M}\) jest równoliczny z \(\displaystyle{ \NN. }\)

[matmatmm]

Zauważmy, że formalnie nie jest to ciąg, tylko inna funkcja, gdyż jej dziedziną nie jest zbiór liczb naturalnych. Funkcja ta działa trochę inaczej:

Wypada mi się z tym nie zgodzić, bo \(\displaystyle{ (a_n)}\) to oczywiście ciąg.

Inna kwestia, że jeśli uzasadniamy istnienie (i jednoznaczność) takiego ciągu powołując się na wspomniane przez ciebie twierdzenie o definiowaniu przez indukcję, to musimy przedstawić pewną funkcję \(\displaystyle{ \xi:\mathcal{S}\rightarrow \NN}\), gdzie \(\displaystyle{ \mathcal{S}}\) jest rodziną ciągów skończonych o wyrazach w \(\displaystyle{ \NN}\). Właśnie to \(\displaystyle{ \xi}\) musimy wskazać, a nie funkcję, którą opisałeś tutaj:

Funkcja ta działa trochę inaczej:

\(\displaystyle{ 0 \rightarrow 1,\\
1 \rightarrow 1,\\
\left( 1,1\right) \rightarrow 1+1=2,\\
\left( 2,1\right) \rightarrow 2+1=3,\\
\left( 3,2\right) \rightarrow 3+2=5,\\
\ldots}\)

A więc dziedziną tej funkcji nie są wszystkie kolejne liczby naturalne, tylko najpierw co prawda \(\displaystyle{ 0,1}\), a potem pary \(\displaystyle{ \left( 1,1\right) ;\left( 2,1\right); \left( 3,2\right) ;\ldots }\)

[Jakub Gurak]

Formalnie rzeczywiście musimy określić funkcję na odpowiednim większym zborze- ale sposób w jaki to zrobimy jest zupełnie nieistotny, jak napisał Jan Kraszewski możemy to zrobić jakkolwiek, nie wpływa to nijak na otrzymany ciąg, ale prawda- formalnie musimy funkcję przedłużyć do całej rozwazanej dziedziny.

[Jakub Gurak]

Ten sposób definiowania pozwala nie tylko zdefiniować ciąg Fibonacciego, nie tylko wszystkie inne tym sposobem ciągi liczb naturalnych, ale ma wiele innych zastosowań, np. jest bardzo pomocne w udowodnieniu, że jeżeli zbiór \(\displaystyle{ M}\) jest nieskończonym podzbiorem \(\displaystyle{ \NN}\), to zbiór \(\displaystyle{ M}\) jest równoliczny z \(\displaystyle{ \NN. }\)

Aby to krotko uzasadnić,to:

Niech \(\displaystyle{ M}\) będzie nieskończonym podzbiorem zbioru \(\displaystyle{ \NN}\). Zbiór \(\displaystyle{ M}\) bedąc nieskończony jest oczywiście niepusty, i jest podzbiorem zbioru liczb naturalnych, zatem, na podstawie zasady minimum ma liczbę najmniejszą \(\displaystyle{ m_0}\). Niech zatem \(\displaystyle{ f_0=m_0}\) ( definiujemy ciąg elementów \(\displaystyle{ M}\)) . Niech \(\displaystyle{ f_1}\) będzie najmniejszym elementem \(\displaystyle{ M}\), który jest silnie większy od \(\displaystyle{ f_0 }\) (liczba taka istnieje, bo zbiór \(\displaystyle{ M}\) jest nieskończony, a więc ma więcej niż jeden element). Dalej: przypuśćmy, że zdefiniowaliśmy elementy: \(\displaystyle{ f_0,f_1,\ldots,f_n}\), elementy zbioru \(\displaystyle{ M}\), niech teraz \(\displaystyle{ f_{n+1}}\) będzie najmniejszym elementem \(\displaystyle{ M}\) który jest silnie większy od \(\displaystyle{ f_n}\) (element taki istnieje, bo zbiór \(\displaystyle{ M}\) jest nieskończony). Zdefiniowaliśmy zatem element \(\displaystyle{ f_{n+1}}\) zbioru \(\displaystyle{ M}\). Korzystając z twierdzenia o definiowaniu przez indukcję otrzymujemy ciąg \(\displaystyle{ f:\NN \rightarrow M}\).

Ciąg taki jest silnie rosnący, a zatem różnowartościowy. Ciąg taki jest 'na' zbiór \(\displaystyle{ M}\), gdyż jeśli \(\displaystyle{ m\in M}\), to \(\displaystyle{ m\in\NN}\), i wtedy \(\displaystyle{ m\in\stackrel { \rightarrow }{f}\left( m'=\left\{ 0,1,\ldots,m\right\} \right).}\) Ponieważ \(\displaystyle{ \stackrel { \rightarrow }{f}\left( m'=\left\{ 0,1,\ldots,m\right\} \right) \subset \stackrel { \rightarrow }{f}\left( \NN\right)=f_P}\), to \(\displaystyle{ m\in f_P. \square}\)

Również definiowanie indukcyjne jest pomocne aby uzasadnić, że każda liczba rzeczywista \(\displaystyle{ x,}\) taka, ze \(\displaystyle{ 0 \le x< 1}\) ma nieskończone rozwinięcie dwójkowe. Więc chodzi o taki ciąg \(\displaystyle{ a:\NN \rightarrow \left\{ 0,1\right\}}\) zapiszmy go \(\displaystyle{ a_0,a_1,\ldots}\), że ciąg liczb wymiernych (ciąg przybliżeń dolnych liczby \(\displaystyle{ x}\))

\(\displaystyle{ 0,a_0; 0,a_0a_1; 0,a_0a_1a_2;\ldots }\)

(w systemie dwójkowym) zbiega do liczby rzeczywistej \(\displaystyle{ x}\) (ja bym to wyraził, że supremum (w zbiorze liczb rzeczywistych) zbioru wyrazów(wartości) tego ciągu przybliżeń liczby \(\displaystyle{ x}\), to supremum jest równe tej liczbie rzeczywistej \(\displaystyle{ x}\)).

Szkic konstrukcji:

Ciąg \(\displaystyle{ a:\NN \rightarrow \left\{ 0,1\right\}}\) definiujemy indukcyjnie:

Jeśli \(\displaystyle{ 0\le x< \frac{1}{2}}\), to definiujemy \(\displaystyle{ a_0=0}\), w przeciwnym przypadku tzn. \(\displaystyle{ \frac{1}{2} \le x<1}\), to definiujemy \(\displaystyle{ a_0=1.}\)

Zauważmy, że podzieliliśmy przedział \(\displaystyle{ \left[ 0,1\right)}\), na dwa podprzedziały \(\displaystyle{ \left[ 0, \frac{1}{2} \right)}\) oraz \(\displaystyle{ \left[ \frac{1}{2} ,1\right)}\) tego samego typu. Na dalszych etapach przedział w którym jesteśmy aktualnie dzielimy na dwie równe części, i przypisujemy \(\displaystyle{ 0}\) gdy liczba znajduje się w lewej połówce przedziału, a piszemy \(\displaystyle{ 1}\) gdy liczba znajduje się w prawej połówce przedziału( lub gdy jest dokładnie na środku). Tak wygląda konstrukcja. Twierdzenie o definiowaniu przez indukcje daje nam szukany ciag \(\displaystyle{ a:\NN \rightarrow \left\{ 0,1\right\} . }\)