Definição recursiva

Na lógica matemática e em ciência da computação, uma definição recursiva (ou definição indutiva) é usada para definir um objeto em termos de si próprio (Aczel 1977).

Quatro fases na construção de um Floco de neve de Koch. Como em muitos outros fractais, os estágios são obtidos através de uma 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 $\mathbb {N}$ dos números naturais é:

1. 0 pertence a $\mathbb {N}$.
2. Se um elemento n pertence a $\mathbb {N}$ então n+1 pertence a $\mathbb {N}$.
3. $\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).

Forma de definições recursivas

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 $f:X\to X$ e um elemento $a\in X$. Então, existe uma única sequência infinita $(x_{n})_{n\in \mathbb {N} ^{*}}\subset X$ tal que $x_{1}=a$ e $x_{i+1}=f(x_{i})$ para cada $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 $a$. Suponhamos, agora, que para cada $n\in \mathbb {N} ^{*}=\mathbb {N} -\{0\}$, exista uma única sequência finita $(x_{1}^{(n)},~x_{2}^{(n)},~\ldots ,~x_{n}^{(n)})$ tal que $x_{1}^{(n)}=a$ e $x_{i+1}^{(n)}=f(x_{i}^{(n)})$ para cada $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 $(x_{1}^{(n+1)},~x_{2}^{(n+1)},~\ldots ,~x_{n}^{(n+1)},~x_{n+1}^{(n+1)})$ tal que $x_{1}^{(n+1)}=a$ e $x_{i+1}^{(n+1)}=f(x_{i}^{(n+1)})$ para cada $1\leq i\leq n$. Assim, pelo princípio da indução, concluímos que para todo $n\in \mathbb {N} ^{*}$, existe uma única sequência finita com as propriedades mencionadas. Ponhamos, então, $(x_{n})_{n}$ sendo $x_{n}=x_{n}^{(n)}$ para cada $n\in \mathbb {N} ^{*}$. A sequência $(x_{n})_{n}$ é única. Caso contrário, existiriam um número natural $j\in \mathbb {N} ^{*}$ e uma outra sequência $(y_{n})_{n}$, com $y_{1}=a$ e $y_{i+1}=f(y_{i})$ para cada $i\in \mathbb {N} ^{*}$, tal que $y_{j}\neq x_{j}$. Mas, isto é um absurdo, pois, neste caso, não é única a sequência finita $(x_{1}^{(j)},~x_{2}^{(j)},~\ldots ,~x_{j}^{(j)})$ tal que $x_{1}^{(j)}=a$ e $x_{i+1}^{(j)}=f(x_{i}^{(j)})$ para cada $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 $f:X^{m}\to X$ e um elemento $a\in X$. Então, existe uma única sequência $(x_{n})_{n}\subset X$ tal que $x_{1}=a$ e $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.

Exemplos de definições recursivas

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 (φ $\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.

Ver também

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

Referências

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