Teoremas da incompletude de Gödel

Introdução

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.

Formalizando a Aritmética

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.

Aritmética de Peano

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.

Fatos aritméticos básicos

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.

Impredicatividade e recursão

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.

Recursão nos naturais

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.

Recursão de funções predicativas

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.

Codificação de sequências de números

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.

Função beta de Gödel

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.

Teorema Chinês dos restos e a função beta

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.

Metateoremas na aritmética de Peano

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.

Teorema da representação

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.

Representação da Aritmética

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.

'Prova da prova' na Aritmética

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".

Bibliografia Recomenda

  1. Tópicos em Lógica de Primeira Ordem - Rodrigo Freire


  1. Mathematical logic - Joseph R. Shoenfield


  1. A mathematical introduction to logic - Herbert Enderton


  1. Godel's Incompleteness Theorems - Raymond M. Smullyan