Definiowanie przez indukcję

Następujące twierdzenie pozwala nam zdefiniować dodawanie, mnożenie i wiele ważnych operacji na liczbach naturalnych. Twierdzenie to mówi, że jeśli wiemy, jak zdefiniować pewną operację dla zera oraz jak zdefiniować ją dla następnika danej liczby, to możemy zdefiniować ją równocześnie dla wszystkich liczb.

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}$ :

Niewątpliwie $0\in P$ ponieważ funkcja $e:\{0\}\times A \rightarrow B$ zdefiniowana jako $e(0,a)=f(a)$ jest elementem $H$ .
Załóżmy, że $m\in P$ . To oznacza, że istnieje funkcja $e:m'\times A \rightarrow B$ spełniająca (*). Funkcja $e'$

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$ .