Indução transfinita: diferenças entre revisões
Conteúdo apagado Conteúdo adicionado
m Bot: Adicionando: cs, de, es, fi, fr, he, hu, it, ko, pl, ru, zh |
Recursão transfinita |
||
Linha 1:
Em [[matemática]], e em especial na [[teoria dos conjuntos]], a '''indução transfinita''' é uma técnica matemática rigorosa que permite provar propriedades para todos [[número ordinal|números ordinais]] (ou, de forma mais geral, para qualquer conjunto (ou classe) [[
Analogamente a definições recursivas (por exemplo, o [[fatorial]], definido como ''0! = 1'' e, recursivamente, como ''(n+1)! = (n+1) n!''), existe a '''recursão transfinita''', que consiste em definir uma "função" cujo argumento pertence a uma classe bem ordenada.
=== Indução Transfinita ===▼
Uma prova por indução transfinita requer o (único) passo seguinte:
Linha 14 ⟶ 16:
A rigor, não é necessário provar a base na indução transfinita, porque este é um caso especial vazio da proposição de que se ''P'' é verdadeiro para todo ''n'' < ''k'', então ''P'' é verdadeiro para ''k''. Isto é precisamente verdadeiro, porque não há valores para ''n'' < ''k'' que poderiam servir como contra-exemplos.
== Recursão transfinita ==
A '''recursão transfinita''' é uma forma de definir objetos a partir dos ordinais, de um conjunto bem ordenado ou mesmo de uma classe bem ordenada.
A forma genérica é definir ''f(x)'' como uma função de todos (ou alguns) ''f(y)'' para todos ''y < x''. Assim como a indução transfinita, costuma-se, por motivos práticos, quebrar a definição em três passos:
# ''f(k)'', para ''k'' um elemento mínimo
# ''f(k)'' para ''k'' sucessor, definido como ''f(k) = g(f, k-1)'' (em que, por um abuso de notação, ''k-1'' representa o antecessor de ''k'')
# ''f(k)'' para ''k'' limite, usando todos seus antecessores: ''f(k) = h(f, y<sub>1</sub>, y<sub>2</sub>, ...)'', para todos ''y<sub>i</sub> < k''.
Por exemplo, o [[Universo de von Neumann]] é uma classe de conjuntos ''V<sub>λ</sub>'' definidos por recursão transfinita.
[[Categoria:Teoria dos conjuntos]]
| |||