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

Uma prova por indução transfinita requer o (único) passo seguinte:

1. 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:

1. k é um elemento mínimo, ou seja, não há elemento menor que k
2. k tem um predecessor direto, ou seja, o conjunto de elementos que são menores que k tem um elemento maior
3. 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

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:

1. f(k), para k um elemento mínimo
2. 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)
3. f(k) para k limite, usando todos seus antecessores: f(k) = h(f, y₁, y₂, ...), para todos y_i < k.

Por exemplo, o Universo de von Neumann é uma classe de conjuntos V_λ definidos por recursão transfinita.

Referências

1. 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
2. Hausdorff: Grundzüge der Mengenlehre, 1914, S. 112f [ler on-line]