Twierdzenie 6.1. [o definiowaniu przez indukcję]
Niech \( A \) i \( B \) będą zbiorami, a \( f: A \rightarrow B \) i \( g:B\times \mathbb{N}\times A \rightarrow B \) funkcjami. Istnieje unikalna funkcja \( h:\mathbb{N}\times A \rightarrow B \) taka, że:
\( h(0, a) = f(a), \mbox{ dla każdego }a \in A, \)
\( h(n', a) = g(h(n, a), n, a), \mbox{ dla każdego }a \in A \mbox{ i }n \in \mathbb{N}. \)
Dowód
Dowód istnienia funkcji \( h \) będzie się opierał na analizie elementów następującego zbioru:
\( H = \{e\,:\, \exists m\; m\in\mathbb{N} \land e:m'\times A \rightarrow B \land \mbox{(*)} \}, \)
gdzie
\( e(0, a) = f(a), \mbox{ dla każdego }a \in A, \)
\( e(g(n, a), n, a), \mbox{ dla każdego }a \in A \mbox{ i }n \in m \quad \mbox{(*)} \)
Zbiór \( H \) jest to zbiór funkcji, które częściowo rozwiązują nasz problem -- funkcje ze zbioru \( H \) działają dla liczb naturalnych mniejszych niż pewne, ustalone \( m \). Funkcja \( h \), której istnienia dowodzimy, powinna działać dla wszystkich liczb naturalnych.
W pierwszej części dowiedziemy, że zbiór \( H \) jest niepusty i, co więcej, zawiera przynajmniej jedną funkcję \( e:m'\times A \rightarrow B \) dla każdej liczby naturalnej \( m \). Dowód jest indukcyjny -- zdefiniujmy zbiór \( P \) jako zbiór tych liczb, dla których istnieją odpowiednie funkcje w \( H \):
\( P = \{m\in\mathbb{N}\,:\, \exists e\; e:m'\times A \rightarrow B \land e\in H\}. \)
Dowiedziemy indukcyjnie, że \( P=\mathbb{N} \):
zdefiniowana jako:
\( e'(n, a) = \begin{cases} e(n, a), & \mbox{jeśli } n \in m', \\ g(e(n, a), n, a), & \mbox{jeśli} n = m', \end{cases} \)
przeprowadza \( m''\times A \) w \( B \) i należy do \( H \), gwarantując, że \( m'\in P \).
Na podstawie twierdzenia o indukcji istnieje funkcja \( e:m'\times A \rightarrow B \) należąca do \( H \), dla każdego \( m\in\mathbb{N} \).
Kolejną rzeczą jako wykażemy jest to, że dowolne funkcje \( e\in H \) i \( e'\in H \) dla tych samych argumentów zwracają takie same wyniki (oczywiście zakładając, że argumenty należą do przecięcia dziedzin tych funkcji). Nasz dowód przebiega niewprost. Załóżmy że funkcje \( e,e'\in H \) są takie, że istnieje \( n\in\mathbb{N} \) i \( a\in A \) spełniające \( e(n,a)\neq e'(n,a) \). Zastosujmy Twierdzenie 5.2. do zbioru tych wszystkich \( n \), dla których istnieje \( a\in A \) spełniające \( e(n,a)\neq e'(n,a) \) (na mocy naszego założenia zbiór ten jest niepusty). Otrzymujemy najmniejszą liczbę naturalną \( n \) taką, że \( e(n,a)\neq e'(n,a) \). Liczba \( n \) nie może być równa \( 0 \), bo wtedy \( e(0,a) = f(a) = e'(0,a) \), więc, na mocy Faktu 4.2. \( n=k' \), dla pewnego \( k \). Ponieważ \( k < n \), więc \( e(k,a)=e'(k,a) \) i otrzymujemy sprzeczność dzięki:
\( e(n,a) = e(k',a)=g(e(k,a),k,a) = g(e'(k,a),k,a) = e'(k',a) = e'(n,a). \)
Dowód twierdzenia kończymy, definiując \( h = \bigcup H \). Na mocy wcześniejszego faktu \( h \) jest funkcją, a na mocy faktu, który dowodziliśmy indukcyjnie dziedziną \( h \) jest zbiór liczb naturalnych. Warunki stawiane \( h \) są spełnione w sposób oczywisty dzięki definicji zbioru \( H \).
Aby wykazać unikalność funkcji \( h \) załóżmy, że istnieje funkcja \( h'\neq h \) spełniająca tezę twierdzenia. Wnioskujemy, że istnieje \( n\in\mathbb{N} \) i \( a\in A \) takie, że \( h(n,a)\neq h'(n,a) \). Wtedy jednak \( h' \) zawężone do \( n' \) jest elementem zbioru \( H \), co stoi w sprzeczności z faktem wykazanym o \( H \).