|
==Indução e Recursão==
Se (''X'', ''R'') é uma relação binária bem-fundada e ''P''(''x'') é alguma propriedade dos elementos de ''X'', queremos mostrar que ''P''(''x'') servevale para todos os elementos de ''X'', então é suficiente mostrar que:
<br>
Considerando a propriedade ''P'' como sendo "olhos claros" e a relação <math>yRx</math> significando "''y'' é pai de ''x''".
<br>
<center>
Se ''x'' é um elemento de ''X'' e ''P''(''y'') é verdadeiro para todo ''y'' tal que ''y'' se relaciona com ''x'' (''<math>yRx''</math>), então ''P''(''x'') deve ser também verdadeiro.
</center>
Talvez o signficado considerado para a propriedade ''P'' e para a relação ''R'' não seja tão expressivo para este caso, pois se ''y'' for pai de ''x'', não necessariamente ''x'' terá olhos claros (como seu pai), mas há signifcado mais expressivo a ser considerado.
<br>
As relaçõesRelações bem-fundadas suportamdão suporte não apenas à indução, mas também a construções de objetos por recursão transitivatransfinita. Seja (''X'', ''R'') um conjuntouma relação bem-fundada conjuntista e ''F'' uma função o qualque determina um objeto ''F''(''x'', ''g'') para cada <math>x \in X</math> e cada função parcial ''g'' em ''X''. Então existe uma única função ''G'' tal que para cada <math>x \in X</math>, ▼
▲As relações bem-fundadas suportam também construções de objetos por recursão transitiva. Seja (''X'', ''R'') um conjunto relação bem-fundada e ''F'' uma função o qual determina um objeto ''F''(''x'', ''g'') para cada <math>x \in X</math> e cada função parcial ''g'' em ''X''. Então existe uma única função ''G'' tal que para cada <math>x \in X</math>,
<br>
<br>
</center>
<br>
Isto é, se nós queremos construir uma função '''G''' em '''X''', nós podemos definir ''G''(''x)'') usando os valores de ''G''(''y)'') paratais y'''R'''xque <math>yRx</math>. Como um exemplo, consideremos a relação bem-fundada ('''N''','''S'''), onde '''N''' é o conjunto de todos os [[números naturais]] e '''S''' é o gráfico da função sucessor ''x->x+1''. Então, auma indução emsobre '''S''' é a usual [[indução]] matemática e a recursão em '''S''' dar-nos primitivas de recursão. Se nós considerar-mos a relação de ordem ('''N''',<), obtemos a indução completa e o curso de valores da recursão. A declaração de que ('''N''',<) é bem-fundada é também conhecido como [[princípio da boa ordenação]].
<br>
Existem outros casos especiais de indução bem-fundada. Quando a relação bem-fundada é ordenação naordenada numa classe de todos os [[números ordinais]] a técnica é chamada de [[indução transfinita.]]; Quandoquando o conjunto bem-fundado de estrutura de dados recursivamente definida, a técnica é chamada de [[indução estrutural]] (método de demonstração em que a proposição vale para todas as estruturas minimais, e que se valer para as subestruturas de uma determinada estrutura S, então deverá valer para S também.). Quando a relação bem-fundada é um elemento de um conjunto numa na classe universal, a técnica é conhecida como ∈ - [[indução]].
==Operações sobre conjuntos==
| 