Definição Recursiva

Uma definição recursiva de uma função define valores das funções para algumas entradas em termos dos valores da mesma função para outras entradas. Por exemplo, a função fatorial n! é definida pelas regras

0! = 1.
(n+1)! = (n+1)·n!.

Esta definição é valida porque, para todo n, a recursão sempre vai alcançar o caso base de 0. Assim, a definição é bem-fundada. A definição pode também ser vista como um procedimento que descreve como construir a função n!, a partir de n = 0 e prosseguindo em diante com n = 1, n = 2, n = 3 etc..

Uma definição indutiva de um conjunto descreve os elementos de um conjunto em termos de outros elementos no conjunto. Por exemplo, uma definição do conjunto ${\displaystyle \mathbb {N} }$ dos números naturais é:

1. 0 pertence a ${\displaystyle \mathbb {N} }$.
2. Se um elemento n pertence a ${\displaystyle \mathbb {N} }$ então n+1 pertence a ${\displaystyle \mathbb {N} }$.
3. ${\displaystyle \mathbb {N} }$ é o menor conjunto que satisfaz (1) e (2).

Há vários conjuntos que satisfazem (1) e (2) - por exemplo, o conjunto {0, 0.649, 1, 1.649, 2, 2.649, 3, 3.649, ...} satisfaz a definição. No entanto, a condição (3) especifica o conjunto dos números naturais, removendo os conjuntos com números externos.

Propriedades de funções e conjuntos definidos recursivamente muitas vezes podem ser provadas por um princípio de indução que segue a definição recursiva. Por exemplo, a definição dos números naturais aqui apresentada implica o princípio da indução matemática para os números naturais: se o número natural 0 possui uma propriedade, e n+1 tem a propriedade sempre que n também a possui, então a propriedade é inerente a todos os números naturais (Aczel 1978:742).

A maioria das definições recursivas possuem três fundamentos: um caso base, uma cláusula indutiva, e uma cláusula de exclusão.

A diferença entre uma definição circular e uma definição recursiva é que uma definição recursiva deve ter sempre os casos base que satisfazem a definição sem serem definidos em função de si mesmos. Em contraste, uma definição circular pode ter nenhum caso base, e definir o valor de uma função em termos de um valor em si, ao invés de outros valores da própria função.

Princípio da definição recursiva

Sejam dados a função ${\displaystyle f:X\to X}$  e um elemento ${\displaystyle a\in X}$ . Então, existe uma única sequência infinita ${\displaystyle (x_{n})_{n\in \mathbb {N} ^{*}}\subset X}$  tal que ${\displaystyle x_{1}=a}$  e ${\displaystyle x_{i+1}=f(x_{i})}$  para cada ${\displaystyle i\in \mathbb {N} ^{*}=\mathbb {N} -\{0\}}$ .

Demonstração

Enquanto a existência de uma tal sequência é intuitiva, a unicidade pode ser demonstrada usando o princípio da indução. Com efeito, existe uma única sequência de um único termo que seja igual a ${\displaystyle a}$ . Suponhamos, agora, que para cada ${\displaystyle n\in \mathbb {N} ^{*}=\mathbb {N} -\{0\}}$ , exista uma única sequência finita ${\displaystyle (x_{1}^{(n)},~x_{2}^{(n)},~\ldots ,~x_{n}^{(n)})}$  tal que ${\displaystyle x_{1}^{(n)}=a}$  e ${\displaystyle x_{i+1}^{(n)}=f(x_{i}^{(n)})}$  para cada ${\displaystyle 1\leq i\leq n-1}$ . Pela hipótese de indução e por definição de função, temos que existe uma única sequência finita ${\displaystyle (x_{1}^{(n+1)},~x_{2}^{(n+1)},~\ldots ,~x_{n}^{(n+1)},~x_{n+1}^{(n+1)})}$  tal que ${\displaystyle x_{1}^{(n+1)}=a}$  e ${\displaystyle x_{i+1}^{(n+1)}=f(x_{i}^{(n+1)})}$  para cada ${\displaystyle 1\leq i\leq n}$ . Assim, pelo princípio da indução, concluímos que para todo ${\displaystyle n\in \mathbb {N} ^{*}}$ , existe uma única sequência finita com as propriedades mencionadas. Ponhamos, então, ${\displaystyle (x_{n})_{n}}$  sendo ${\displaystyle x_{n}=x_{n}^{(n)}}$  para cada ${\displaystyle n\in \mathbb {N} ^{*}}$ . A sequência ${\displaystyle (x_{n})_{n}}$  é única. Caso contrário, existiriam um número natural ${\displaystyle j\in \mathbb {N} ^{*}}$  e uma outra sequência ${\displaystyle (y_{n})_{n}}$ , com ${\displaystyle y_{1}=a}$  e ${\displaystyle y_{i+1}=f(y_{i})}$  para cada ${\displaystyle i\in \mathbb {N} ^{*}}$ , tal que ${\displaystyle y_{j}\neq x_{j}}$ . Mas, isto é um absurdo, pois, neste caso, não é única a sequência finita ${\displaystyle (x_{1}^{(j)},~x_{2}^{(j)},~\ldots ,~x_{j}^{(j)})}$  tal que ${\displaystyle x_{1}^{(j)}=a}$  e ${\displaystyle x_{i+1}^{(j)}=f(x_{i}^{(j)})}$  para cada ${\displaystyle 1\leq i\leq j-1}$ . Isto conclui a demonstração.

Generalização

O enunciado acima pode ser estendido da seguinte forma: sejam dados a função ${\displaystyle f:X^{m}\to X}$  e um elemento ${\displaystyle a\in X}$ . Então, existe uma única sequência ${\displaystyle (x_{n})_{n}\subset X}$  tal que ${\displaystyle x_{1}=a}$  e ${\displaystyle x_{i+1}=f(x_{1},~x_{2},~\ldots ,~x_{i})}$ . Desta forma, cada termo da sequência é definido como função de um ou mais termos anteriores.

Números primos

Os números primos podem ser definidos como constituídos por:

• 2, o menor número primo;
• Cada inteiro positivo que não é divisível por nenhum dos primos menores que ele.

O inteiro 2 é o nosso caso base; verificar a primalidade de qualquer inteiro maior x requer que nós conheçamos a primalidade de todos os inteiros entre x e 2, mas cada inteiro deste está mais próximo do nosso caso base 2 do que x.

Números pares não-negativos

Os números pares podem ser definidos como constituídos por:

• 0 pertence ao conjunto P de números pares não-negativos (caso base);
• Para qualquer elemento x do conjunto P, x+2 pertence a P (cláusula indutiva);
• Nenhum elemento pertence a P, a menos que o mesmo seja obtido a partir do caso base e cláusula indutiva (cláusula de exclusão).

Fórmulas bem formadas

Na Lógica de primeira ordem, as fórmulas bem formadas são as palavras sobre o alfabeto da sua linguagem que são de fato fórmulas válidas. Podemos definir recursivamente o conjunto das fórmulas bem formadas (FBF), como sendo o menor conjunto que satisfaz:

• Toda fórmula atômica pertence a FBF;
• Se φ pertence a FBF então ¬φ pertence a FBF;
• Se φ pertence a FBF e ψ pertence a FBF então (φ ∧ ψ) pertence a FBF;
• Se φ pertence a FBF e ψ pertence a FBF então (φ ${\displaystyle \vee }$  ψ) pertence a FBF;
• Se φ pertence a FBF e ψ pertence a FBF então (φ → ψ) pertence a FBF;
• Se φ pertence a FBF então ∀xφ pertence a FBF;
• Se φ pertence a FBF então ∃xφ pertence a FBF.

• Recursão
• Indução matemática

Fontes

• P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), ISBN 0-444-86388-5
• James L. Hein (2009), Discrete Structures, Logic, and Computability. ISBN 0-763-77206-2