Definiowanie przez indukcje z parametrem

[Jakub Gurak]

Zawsze miałem z tym problem (bo wyjaśniania, że dodatkowa zmienna jest parametrem niewiele wyjaśnia). Ale teraz powoli staje się to jasne. Myślę, że znam to dobrze w kontekście dodawania i mnożenia liczb naturalnych. Teraz mnie naszło aby się w ogólności nad tym zastanowić.

Przede wszystkim tak- na czym polega takie definiowanie. Chcemy dla dowolnego \(\displaystyle{ n\in\NN}\) , dla dowolnego \(\displaystyle{ a \in A}\) zdefiniować jeden element \(\displaystyle{ f\left( n,a\right)}\)( i tak dla dowolnego \(\displaystyle{ n \in \NN,}\) i dowolnego \(\displaystyle{ a \in A}\)), tak Definiujemy więc dla dowolnego \(\displaystyle{ a \in A}\) element \(\displaystyle{ f\left( 0,a\right)}\). Mamy zatem zdefiniowane \(\displaystyle{ f\left( 0,a\right)}\) dla dowolnego \(\displaystyle{ a \in A.}\) Teraz dla dowolnego ustalonego \(\displaystyle{ a \in A}\) definiujemy \(\displaystyle{ f\left( 1,a\right)}\) na podstawie wartości \(\displaystyle{ f\left( 0,a\right),}\) tak? Mamy zatem zdefiniowane \(\displaystyle{ f\left( m,a\right),}\) dla wszystkich \(\displaystyle{ m=0,1, a\in A.}\). Teraz dla dowolnego ustalonego \(\displaystyle{ a \in A}\) definiujemy element \(\displaystyle{ f\left( 2,a\right),}\) na podstawie wartości \(\displaystyle{ f\left( 1,a\right);f\left( 0,a\right),}\) i tak dla dowolnego \(\displaystyle{ a \in A.}\) Dalej, w kroku \(\displaystyle{ n}\) zakładamy domyślnie, że zdefiniowana jest taka funkcja dla wszystkich \(\displaystyle{ m<n}\) oraz \(\displaystyle{ a \in A,}\) i dla dowolnego ustalonego \(\displaystyle{ a\in A}\) definiujemy element \(\displaystyle{ f\left( n,a\right)}\) na podstawie wartości \(\displaystyle{ f\left( 0,a\right);f\left( 1,a\right);\ldots;f\left( n-1,a\right),}\) i tak dla dowolnego \(\displaystyle{ a \in A}\). Stąd otrzymujemy funkcję na \(\displaystyle{ \NN \times A,}\) o to chodzi

Niech \(\displaystyle{ A=\RR, x \in A.}\)

\(\displaystyle{ \begin{cases} x ^{0}=1 \\ x ^{n+1}=x ^{n} \cdot x. \end{cases}}\) To dobry przykład Prosiłbym o jeszcze jeden, gdzie \(\displaystyle{ A \neq \NN.}\)

[matmatmm]

Też się nad tym kiedyś zastanawiałem, chociaż trochę w innym kontekście. Pokażę jak to według mnie wygląda ze strony formalnej, ale na przykładzie twierdzenia o definiowaniu przez indukcję w wersji, w której zależność jest tylko od poprzedniego wyrazu (nie tak jak u ciebie od wszystkich poprzednich).

Zerknijmy na twierdzenie o definiowaniu przez indukcję w klasycznej wersji bez parametru:

Twierdzenie. Niech \(\displaystyle{ X}\) będzie zbiorem, \(\displaystyle{ x_0\in X}\) oraz niech \(\displaystyle{ \Phi:\NN\times X\rightarrow X}\) będzie funkcją. Wówczas istnieje dokładnie jedna funkcja \(\displaystyle{ F:\NN\rightarrow X}\) taka, że
\(\displaystyle{ F(0)=x_0}\)
\(\displaystyle{ F(n+1)=\Phi(n,F(n))}\) dla każdego \(\displaystyle{ n\in\NN}\).

Powiedzmy, że chcemy teraz zdefiniować "coś z parametrem", tak jak w twoim przykładzie:

\(\displaystyle{ \begin{cases} x ^{0}=1 \\ x ^{n+1}=x ^{n} \cdot x. \end{cases}}\)

Mamy więc dodatkowy zbiór \(\displaystyle{ A}\) i chcemy zdefiniować funkcję \(\displaystyle{ f:\NN\times A\rightarrow A}\). Cała ta zabawa w definiowanie to tak naprawdę dowodzenie istnienia i jednoznaczności tej funkcji. Zrobię to na twoim przykładzie funkcji potęgowej, chociaż można sformułować odpowiednie twierdzenie o definiowaniu z parametrem. Udowodnijmy więc najpierw, że

(*)Dla każdego \(\displaystyle{ a\in A=\RR}\) istnieje dokładnie jedna funkcja \(\displaystyle{ F:\NN\rightarrow \RR}\) taka, że

\(\displaystyle{ F(0)=1}\)
\(\displaystyle{ F(n+1)=F(n)\cdot a}\) dla każdego \(\displaystyle{ n\in\NN}\).

No więc jak to dowodzimy? Ustalamy \(\displaystyle{ a\in\RR}\), a potem stosujemy twierdzenie o definiowaniu przez indukcję w wersji bez parametru. Czyli musimy po prostu wskazać funkcję \(\displaystyle{ \Phi}\) (zależną od \(\displaystyle{ a}\)) i oczywiście pierwszy wyraz (w tym przypadku równy \(\displaystyle{ 1}\) chociaż w ogólności może zależeć od \(\displaystyle{ a}\)). W tym miejscu nie ma co wchodzić zbytnio w szczegóły ATM, jak dowodzi się, że takowe \(\displaystyle{ \Phi}\) istnieje.

Z chwilą, gdy udowodniliśmy (*) nic nie stoi na przeszkodzie, żeby tę jedyną funkcję \(\displaystyle{ F}\) zależną od \(\displaystyle{ a}\) oznaczyć sobie \(\displaystyle{ F_a}\), a dalej stosując aksjomat zastępowania (być może wyróżnianie też by wystarczyło) otrzymujemy funkcję \(\displaystyle{ a\mapsto F_a}\) i puentujemy wzorem \(\displaystyle{ f(n,a):=F_a(n)}\).

[Jakub Gurak]

Dobra, dobra, na formalne twierdzenie od razu się nie porywam. Najpierw chcę zrozumieć o co w tym chodzi. Nie uzyskałem odpowiedzi:

Przede wszystkim tak- na czym polega takie definiowanie. Chcemy dla dowolnego \(\displaystyle{ n\in\NN}\) , dla dowolnego \(\displaystyle{ a \in A}\) zdefiniować jeden element \(\displaystyle{ f\left( n,a\right)}\)( i tak dla dowolnego \(\displaystyle{ n \in \NN,}\) i dowolnego \(\displaystyle{ a \in A}\)), tak Definiujemy więc dla dowolnego \(\displaystyle{ a \in A}\) element \(\displaystyle{ f\left( 0,a\right)}\). Mamy zatem zdefiniowane \(\displaystyle{ f\left( 0,a\right)}\) dla dowolnego \(\displaystyle{ a \in A.}\) Teraz dla dowolnego ustalonego \(\displaystyle{ a \in A}\) definiujemy \(\displaystyle{ f\left( 1,a\right)}\) na podstawie wartości \(\displaystyle{ f\left( 0,a\right),}\) tak? Mamy zatem zdefiniowane \(\displaystyle{ f\left( m,a\right),}\) dla wszystkich \(\displaystyle{ m=0,1, a\in A.}\). Teraz dla dowolnego ustalonego \(\displaystyle{ a \in A}\) definiujemy element \(\displaystyle{ f\left( 2,a\right),}\) na podstawie wartości \(\displaystyle{ f\left( 1,a\right);f\left( 0,a\right),}\) i tak dla dowolnego \(\displaystyle{ a \in A.}\) Dalej, w kroku \(\displaystyle{ n}\) zakładamy domyślnie, że zdefiniowana jest taka funkcja dla wszystkich \(\displaystyle{ m<n}\) oraz \(\displaystyle{ a \in A,}\) i dla dowolnego ustalonego \(\displaystyle{ a\in A}\) definiujemy element \(\displaystyle{ f\left( n,a\right)}\) na podstawie wartości \(\displaystyle{ f\left( 0,a\right);f\left( 1,a\right);\ldots;f\left( n-1,a\right),}\) i tak dla dowolnego \(\displaystyle{ a \in A}\). Stąd otrzymujemy funkcję na \(\displaystyle{ \NN \times A,}\) o to chodzi

Proszę o odpowiedź.

[matmatmm]

Zgrubsza tak. O to chodzi.