Indução transfinita

Origem: Wikipédia, a enciclopédia livre.
Ir para: navegação, pesquisa
NoFonti.svg
Este artigo ou se(c)ção cita uma ou mais fontes fiáveis e independentes, mas ela(s) não cobre(m) todo o texto.
Por favor, melhore este artigo providenciando mais fontes fiáveis e independentes e inserindo-as em notas de rodapé ou no corpo do texto, conforme o livro de estilo.
Encontre fontes: Googlenotícias, livros, acadêmicoYahoo!Bing. Veja como referenciar e citar as fontes.

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:

  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.

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:

  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, 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

  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]