===== Recursão =====

<WRAP tip>
Para esta lista é melhor você estar familiarizado em como formalizar o conceito de funções. Veja isso nessa [[lista:funcoes|lista]].
</WRAP>

<WRAP tip>
A primeira parte desta lista serve mais como motivação e para dar uma intuição no que vem a seguir.
</WRAP>

**~~#~~** Seja $g: \omega \times \omega \to \omega$ uma função. Seja $k_0 \in \omega$. Vamos provar que existe $f: \omega \to \omega$ de forma que $f(0) = k_0$ e $f(n + 1) = g(f(n), n + 1)$.

**~~#.#~~** Considere $\mathcal F = \{h \subset \omega \times \omega: h$ é uma função de domínio $\{0, ..., n\}$ para algum $n \in \omega$, $h(0) = k_0$ e $h(a + 1) = g(h(a), a + 1)$ para todo $a = 0,..., n - 1\}$. Mostre que $\mathcal F$ é não vazio.

**~~#.#~~** Sejam $h, h' \in \mathcal F$. Seja $a \in dom(h) \cap dom(h')$. Mostre que $h(a) = h'(a)$. <wrap tip>[[dica:pegaoMin|Dica]]</wrap> 


**~~#.#~~** Mostre que para todo $n \in \omega$ existe $h \in \mathcal F$ tal que $n \in dom(h)$. 

**~~#.#~~** Mostre que $f = \bigcup \mathcal F$ é a função desejada.

**~~#~~** Use o exercício anterior para justificar a existência da função fatorial.

**~~#~~** Seja $A$ um conjunto bem ordenado e seja $B$ um conjunto qualquer. Considere $g: \wp(B) \times A \to B$. Mostre que existe $f: A \to B$ tal que $f(a) = g(\{f(b): b < a\}, a)$. 

<WRAP info>
Dizemos que uma fórmula $\varphi$ é do {{entry>tipo função}} se, para todo conjunto $a$ existe um único conjunto $b$ que satisfaça $\varphi(a, b)$. 
</WRAP>

<WRAP tip>
Pense numa fórmula do tipo função como sendo uma "função" cujo domínio é todos os conjuntos. Muitos lugares inclusive adotam a notação $b = \varphi(a)$ no lugar da descrita acima, para ressaltar este aspecto.
</WRAP>

**~~#~~**