Indução transfinita
 |
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úmeros ordinais (ou, de forma mais geral, para qualquer conjunto (ou classe) bem ordenado) a partir de etapas finitas. É uma generalização da indução finita.
A indução transfinita foi feita, primeiro, por Georg Cantor em 1897[1], e foi formalizada em 1914 por Felix Hausdorff, no livro Grundzüge der Mengenlehre (Bases da Teoria dos Conjuntos) [2].
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[editar | editar código-fonte]
Uma prova por indução transfinita requer o (único) passo seguinte:
- Mostrar que se o enunciado vale para todo n < k, então o mesmo enunciado também vale para n = k.
Por razões práticas, as provas costumam ser feitas em três passos:
- k é um elemento mínimo, ou seja, não há elemento menor que k
- k tem um predecessor direto, ou seja, o conjunto de elementos que são menores que k tem um elemento maior
- k não tem um predecessor direto, ou seja, k é chamado de ordinal limite.
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.
Na teoria axiomática dos conjuntos [modelo ZFC], o Princípio da Indução Transfinita é equivalente ao Axioma da Escolha, pois o Princípio esta relacionado ao "Princípio dos Bem-ordenados, de Ernst Zermelo".
Recursão transfinita[editar | editar código-fonte]
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, y1, y2, ...), para todos yi < k.
Por exemplo, o Universo de von Neumann é uma classe de conjuntos Vλ definidos por recursão transfinita.
Referências
- ↑ transfinite Rekursion zur Definition der Potenz von Ordinalzahlen, in: Cantor: Beiträge zur Begründung der transifiniten Mengenlehre 2., in: Mathematische Annalen 49 (1897), §18, 231f
- ↑ Hausdorff: Grundzüge der Mengenlehre, 1914, S. 112f [ler on-line]
