Ferramentas do usuário
Recursão
Para esta lista é melhor você estar familiarizado em como formalizar o conceito de funções. Veja isso nessa lista.
A primeira parte desta lista serve mais como motivação e para dar uma intuição no que vem a seguir.
1 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)$.
1.1 Considere $\mathcal F = \{h \subset \omega \times \omega: h$ é uma função de domínio $\{0, \ldots, n\}$ para algum $n \in \omega$, $h(0) = k_0$ e $h(a + 1) = g(h(a), a + 1)$ para todo $a = 0,\ldots, n - 1\}$. Mostre que $\mathcal F$ é não vazio.
1.2 Sejam $h, h' \in \mathcal F$. Seja $a \in dom(h) \cap dom(h')$. Mostre que $h(a) = h'(a)$. Dica
1.3 Mostre que para todo $n \in \omega$ existe $h \in \mathcal F$ tal que $n \in dom(h)$.
1.4 Mostre que $f = \bigcup \mathcal F$ é a função desejada.
2 Use o exercício anterior para justificar a existência da função fatorial.
3 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)$.
Dizemos que uma fórmula $\varphi$ é do tipo função se, para todo conjunto $a$ existe um único conjunto $b$ que satisfaça $\varphi(a, b)$.
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.
4
Ferramentas da página
