Autor Tema: Argumento diagonal

0 Usuarios y 1 Visitante están viendo este tema.

24 Junio, 2015, 03:50 pm
Leído 1488 veces

sargentopimienta

  • Visitante
¿Me podrían explicar el argumento de Cantor aplicado al teorema de Gödel y a la prueba de Turing?

21 Septiembre, 2015, 02:58 am
Respuesta #1

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 545
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
No se trata exactamente del mismo argumento diagonal en los tres casos sino de argumentos que guardan entre sí cierta analogía.

Te doy un ejemplo INFORMAL de un argumento diagonal que lleva a una versión del primer teorema de incompletitud de Gödel. Este argumento fue propuesto por Gödel mismo en su artículo de 1931.

Supón que S es un sistema formal que contiene la aritmética de Peano. Si suponemos que es correcto, podemos usar un argumento 'diagonal' para demostrar que es incompleto (que hay una verdad aritmética que no demuestra).

Existe una enumeración E de todos los predicados aritméticos expresables en el lenguaje de S (todo lenguaje de un sistema formal es enumerable). Gödel demostró que el siguiente es un predicado aritmético expresable en el lenguaje de S: el enésimo predicado de E aplicado al nº n da una fórmula que S no demuestra.

Por tanto, ese predicado tiene que estar en E. Supón que es el i-ésimo predicado en E. Entonces ese predicado aplicado al número i da una fórmula que dice que el i-ésimo predicado en E aplicado al nº i da una fórmula que S no demuestra. Es decir, esa fórmula dice de sí misma que es indemostrable en S. Y es verdadera porque, si fuese falsa, S la demostraría, con lo que demostraría una falsedad, y eso no puede ser ya que hemos supuesto que S es correcto. Por tanto, la sentencia es verdadera pero indemostrable en S, y S es incompleto.

Este argumento usa una enumeración para construir algo que se escapa del poder demostrativo de S (si S es correcto). En ese sentido se parece al argumento diagonal de Cantor.

Recuerda que el argumento que he dado es informal. Para un argumento 'diagonal' del teorema de Turing te remito a este vídeo: