Teoremas da incompletude de Gödel

Essa é uma introdução ao teorema de Gödel. Falaremos brevemente sobre o projeto de fundamentação da matemática de Hilbert. Em seguida, usaremos alguns exemplos para entendermos o que significa dizer uma teoria matemática é incompleta.

Introduzimos a aritmética mostrando alguns exemplos de problemas aritméticos. Em seguida, mostramos alguns dos passos importantes para a formalização da aritmética como a notação de zero e sucessor. Por fim, demonstramos fatos elementares a partir de axiomas que definem a soma e o produto.

Introduzimos a aritmética de Peano. Exploraremos essa formalização a partir de um problema básico de aritmética, observando a necessidade de definir a operação de diferença e a relação de divisibilidade. Ao final, demonstramos o resultado de que 6 divide (n^3 - n) para todo n.

Demonstramos uma sequência de fatos aritméticos básicos. O objetivo é observar demonstrações na teoria formal da aritmética. Desse modo, esperamos evitar os formalismos mais a frente na série sem perder de vista que os argumentos podem ser formalizados.

Introduzimos o tema das definições impredicativas. Partimos de uma análise conceitual da ideia de definição e fazemos a análise do paradoxo do mentiroso que emerge de uma definição impredicativa. Por fim, mostramos que algumas definições impredicativas não geram paradoxos nas teorias de primeira ordem clássicas -- as definições recursivas.

Definimos a formalização da recursão nos naturais e discutimos brevemente a relação com a tese de Church-Turing. Mostramos também algumas dificuldades para conectar com a noção intuitiva de funções recursivas.

Demonstramos que algumas funções definidas de modo predicativo são recursivas. Começamos mostrando que a composição booleana de fórmulas recursivas é recursiva. Em seguida mostramos que as relações de igualdade e desigualdade são recursivas. Com isso, mostramos que a função que tem como resultado o menor divisor diferente de um é uma função recursiva. Por fim, provamos que, de modo similar, a função de segundo menor divisor diferente de um é recursiva.

Mostraremos uma primeira estratégia para a codificação de sequências de números. Definimos uma função de codificação e decodificação; em seguida mostramos como obter o número que representa a história de uma função intuitivamente recursiva. Por fim, apresentamos os limites da função gama definida e enfatizamos que será necessário definir uma função que evite o uso de funções que não sabemos ser ou não recursivas.

Introduzimos a função beta de Gödel. Trata-se de uma função recursiva que decodifica sequências de números naturais a partir de um número natural. Mostramos uma estratégia simples de como codificar e decodificar sequências de 2 elementos. Em seguida, usamos essas funções para reduzir a busca por uma função Beta à busca por uma função que usa dois números para codificar sequências de números.

Estudaremos o teorema Chinês dos restos e como usar esse antigo resultado para fazer a decodificação beta de sequências de números. Apresentaremos um caso particular para o teorema. Contudo, faremos de tal modo que seja possível observar o procedimento geral para obter as soluções.

Mostraremos como demonstrar metateoremas na aritmética. O caso que trabalharemos é o da regra comutativa para numerais e, para isso, mostraremos alguns resultados intermediários. Por fim, falaremos brevemente sobre o teorema da representação a ser demonstrado no vídeo seguinte.

Demonstraremos o teorema da representação, importante resultado para conectar as funções recursivas com representações na Aritmética de Peano. Demonstramos que as funções recursivas básicas são representáveis e que as regras para gerar funções recursivas preserva a representabilidade.

Neste vídeo, usaremos o teorema da representação e a codificação com as funções Beta para representar os axiomas das teorias recursivas.

Neste vídeo, usaremos o teorema da representação e a codificação com as funções Beta para representar o conceito de que um número representa a prova de uma sentença aritmética. Esse resultado mostra que existe um modo de representar a idéia de que "uma teoria prova que prova essa sentença".

Exploramos o significado do lema diagonal de Gödel e em seguida faremos a demonstração do lema usando as ferramentas desenvolvidas nos vídeos anteriores.

Neste vídeo, provamos o primeiro teorema da incompletude de Gödel reunindo as ideias de aritmetização, predicado de provabilidade e lema diagonal. 

Demonstramos o teorema de Gödel a partir da suposição de consistência de PA ao invés de omega consistência. Para isso, falaremos do truque de Rosser, que faz uma pequena modificação no predicado "é teorema" .

Mostramos como representar a consistência de teorias recursivamente axiomatizadas. Ao final, falamos da ideia geral para a demonstração do segundo teoria da incompletude de Gödel: a aritmética de Peano não prova a sua própria consistência.

Demonstramos o segundo teorema da incompletude de Gödel a partir das condições de provabilidade. O teorema afirma que, se a aritmética é consistente, então ela não prova a própria consistência.

Demonstraremos as condições de provabilidade para o segundo teorema da incompletude de Gödel: internalização de Modus Ponens e internalização de "prova da prova".

Discutiremos as consequências dos teoremas de Gödel, apresentando as suas versões mais gerais. Concluímos que a incompletude das teorias matemáticas não pode ser contornada por adições de axiomas e os sistemas axiomáticos que estendem a aritmética de Peano são todos incapazes de demonstrar a sua própria consistência.