Autor Tema: Dudas en relación con los teoremas de incompletitud

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

29 Agosto, 2013, 06:12 pm
Leído 6409 veces

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Se me hace extraño no haber reparado en este pequeño detalle a estas alturas de la película, pero....

 Es cierto que la sentencia de Gödel en una teoría aritmética recursiva cualquiera \( T \) afirma (en al menos la interpretación natural si es PA1, y quizás en muchas interpretaciones para teorías más complejas), entre otras cosas, la consistencia de la propia teoría \( T \). Pero muchas veces se usa el argumento recíproco en las demostraciones, ( doy por hecho es lícito hacerlo, pero no veo que eso salga inmediato de los teoremas de incompletitud), es decir, que cualquier sentencia expresada en lenguaje formal de primer orden que afirme la consistencia de la teoría\(  T  \)(en alguna interpretación de la teoría), es realmente indemostrable (si \( T \) es consistente


29 Agosto, 2013, 06:26 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En realidad no es "que afirme", sino que equivalga en \( T \) o, al menos, que implique en \( T \) la consistencia de \( T \), porque la consistencia de \( T \) es equivalente en \( T \) a la sentencia de Gödel \( G \), luego si en \( T \) se puede demostrar que una sentencia \( S \) implica la consistencia de \( T \), entonces en \( T \) se puede demostrar \( S\rightarrow G \), luego si se pudiera demostrar \( S \), también se podría demostrar \( G \).

29 Agosto, 2013, 07:41 pm
Respuesta #2

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Citar
la consistencia de\(  T  \)es equivalente en \( T  \)a la sentencia de Gödel \( G \)

Si consideramos obviamente la sentencia de Gödel original \( G \) tal como el la formuló, evidentemente es única, pero lo cierto es que si codificamos las fórmulas de otra forma distinta a como lo hizo Gödel (cosa que se puede hacer, ¿ no?), nos va a aparecer otra sentencia "de Gödel" diferente que también expresa la consistencia de\(  T \). ¿ Qué tiene de especial su codificación para poder asegurar que G afirma únicamente la consistencia de \( T \), y nada más?

Yo pensaba (quizás erróneamente) que en un lenguaje  de primer orden efectivamente hay sentencias que hablan de la consistencia de la teoría (desde luego, descubrir eso es una auténtica genialidad de Gödel), pero que todas ellas necesariamente afirman algo más.
Yo pensaba que lo que ocurre es que los lenguajes de primer orden no permiten una fórmula que únicamente afirme dicha consitencia, y de ahí que quepa la posibilidad de que no sean demostrables con la lógica de primer orden, no por una "insuficiencia" en la potencia de dicha lógica, cuyas propiedades metalógicas me convencen totalmente que cualquier razonamiento se puede formalizar en ella, sino porque demostrar la consistencia implica demostrar algo adicional en cualquier sentencia de primer orden, y es eso lo que no es demostrable.

29 Agosto, 2013, 08:15 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Citar
la consistencia de\(  T  \)es equivalente en \( T  \)a la sentencia de Gödel \( G \)

Si consideramos obviamente la sentencia de Gödel original \( G \) tal como el la formuló, evidentemente es única, pero lo cierto es que si codificamos las fórmulas de otra forma distinta a como lo hizo Gödel (cosa que se puede hacer, ¿ no?), nos va a aparecer otra sentencia "de Gödel" diferente que también expresa la consistencia de T.

Es razonable llamar sentencia de Gödel a cualquier sentencia que implique su propia indemostrabilidad.

¿ Qué tiene de especial su codificación para poder asegurar que G afirma únicamente la consistencia de T, y nada más?

No hay nada de especial en la codificación. Una sentencia de Gödel cualquiera equivale a su propia indemostrabilidad en T, luego implica la consistencia de T porque una teoría en la que haya una sentencia no demostrable es consistente.

Recíprocamente, la consistencia de T implica G porque eso es lo que dice el primer teorema de incompletitud de Gödel (que si T es consistente entonces G no es demostrable) y el segundo dice que esa implicación es formalizable en T.

Yo pensaba (quizás erróneamente) que en un lenguaje  de primer orden efectivamente hay sentencias que hablan de la consistencia de la teoría (desde luego, descubrir eso es una auténtica genialidad de Gödel), pero que todas ellas necesariamente afirman algo más.

Bueno, en el lenguaje de AP puedes considerar una sentencia que diga "AP es consistente, y ZFC también", y así afirma sin duda algo más que la consistencia de AP, pero también tienes la sentencia "AP es consistente" que afirma la consistencia de AP y nada más.

Entre otras cosas porque evidentemente si una teoría \( T  \)es consistente, hay un modelo en el que sus axiomas son verdaderos, y en ese modelo la afirmación\(  "T es consistente" \) es trivial y verdadera,

No exactamente. Hay modelos en los que "T es consistente" es verdadera y modelos en los que "T es consistente" es falsa. Por que T + "T no es consistente" es una teoría consistente, luego tiene modelos (que en particular son modelos de T) en los que "T es consistente" es falsa.

luego es demostrable como axioma, 

No sé qué significa eso de "es demostrable como axioma".

y sin embargo no es demostrable usando lógica de primer orden (por el segundo teorema de incompletitud)

Pues eso. No es demostrable (en T). No sé en qué sentido dices que sí que lo es. Quizás te refieras a que puedes tomarla como axioma, y entonces "T es consistente" es demostrable en la teoría T + "T es consistente".

Yo pensaba que lo que ocurre es que los lenguajes de primer orden no permiten una fórmula que únicamente afirme dicha consitencia,

No. En toda teoría aritmética T puedes definir una sentencia cuya interpretación natural es ni más ni menos que la consistencia de T.

y de ahí que quepa la posibilidad de que no sean demostrables con la lógica de primer orden, no por una "insuficiencia" en la potencia de dicha lógica, cuyas propiedades metalógicas me convencen totalmente que cualquier razonamiento se puede formalizar en ella, sino porque demostrar la consistencia implica demostrar algo adicional en cualquier sentencia de primer orden, y es eso lo que no es demostrable.

En efecto, no existe ninguna insuficiencia en la lógica de primer orden. Si la consistencia de T no es demostrable a partir de los axiomas de T es porque existen modelos de los axiomas de T en los que la afirmación "T es consistente" es falsa, luego no puede ser una consecuencia lógica de los axiomas de T.

29 Agosto, 2013, 08:33 pm
Respuesta #4

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Citar
No. En toda teoría aritmética T puedes definir una sentencia cuya interpretación natural es ni más ni menos que la consistencia de T.

Pero entonces sólo hay una sentencia de Gödel en cada teoría. Pero hay muchas fórmulas diferentes que afirman la consistencia de T. La sentencia de Gödel de T, la de T+ no consis T, la de T+no consis T+ no consis (T+no consis T), todas ellas afirman la consistencia de T, y desde luego no pueden ser equivalentes. Entonces, ¿hay una digamos "original" que sólo afirma la consistencia de T?

Aparte que en  PA1 sólo hay una interpretación natural (salvo isomorfismo), ¿ no? Pero en otras teorías, ¿ no hay distintas interpretaciones naturales, por ejemplo, en ZFC hay infinidad de modelos estándar (si es que hay uno), no tengo claro que haya uno que tenga más derecho a llamarse natural que otros

29 Agosto, 2013, 08:56 pm
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pero entonces sólo hay una sentencia de Gödel en cada teoría.

Si entiendes que dos sentencias equivalentes son la misma sentencia, sí. ¿Consideras que "5 es un primo mayor que 2" y "5 es un primo impar" son la misma sentencia?

Pero hay muchas fórmulas diferentes que afirman la consistencia de T. La sentencia de Gödel de T, la de T+ no consis T,

No. La segunda no afirma la consistencia de T, sino la no consistencia de T

la de T+no consis T+ no consis (T+no consis T), todas ellas afirman la consistencia de T,

No, al contrario, la niegan.

y desde luego no pueden ser equivalentes. Entonces, ¿hay una digamos "original" que sólo afirma la consistencia de T?

Depende de si cuentas las fórmulas equivalentes como una sola.

Aparte que en  PA1 sólo hay una interpretación natural (salvo isomorfismo), ¿ no?

Sí.

Pero en otras teorías, ¿ no hay distintas interpretaciones naturales, por ejemplo, en ZFC hay infinidad de modelos estándar (si es que hay uno), no tengo claro que haya uno que tenga más derecho a llamarse natural que otros

No creo que exista tal derecho. Pero en cualquier caso, todas las sentencias aritméticas tienen una interpretación natural, precisamente en el modelo natural de AP. La sentencia de Gödel de ZFC no sólo puede definirse en ZFC, sino también en AP y tiene una interpretación en el modelo natural de AP.

29 Agosto, 2013, 09:58 pm
Respuesta #6

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Citar
¿Consideras que "5 es un primo mayor que 2" y "5 es un primo impar" son la misma sentencia?

Bueno, la misma no, en el sentido que formalizada su cadena de signos es distinta, pero sí son equivalentes, porque el único primo par es el 2, luego al decir que es un primo impar estás diciendo que es necesariamente mayor que 2. Y por otra parte, también tenemos el recíproco: si es mayor que 2, que sea primo implica necesariamente que es impar. Es decir, que en general, "n es un primo mayor que 2" y "n es un primo impar" son equivalentes, para todo n. Es falsa para 2 y 1 y verdadera para todos los números primos que no sean el 2.

Citar
la de T+no consis T+ no consis (T+no consis T), todas ellas afirman la consistencia de T,

No, al contrario, la niegan.

Pues es cierto, no había reparado en ello . Lo que pasa es que en la interpretación natural T+ no consis T,  y la secuencia recurrente de teorías que se forman así son falsas en el modelo natural de T, claro.

 Entonces todas las sentencias de una teoría aritmética de primer orden T que afirman la consistencia de la teoría, son equivalentes, ¿no? Incluso aunque partamos de codificaciones de Gödel distintas para las fórmulas

. Pues estaba yo totalmente confundido. Claro, entonces si tiene sentido darles un nombre simbólico genérico como se suele hacer consis T.

29 Agosto, 2013, 10:07 pm
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Entonces todas las sentencias de una teoría aritmética de primer orden T que afirman la consistencia de la teoría, son equivalentes, ¿no? Incluso aunque partamos de codificaciones de Gödel distintas para las fórmulas. Pues estaba yo totalmente confundido. Claro, entonces si tiene sentido darles un nombre simbólico genérico como se suele hacer consis T.

consis T es la fórmula que afirma que no existe ningún número natural que sea el número de Gödel de la demostración de una contradicción en T. Si consideras dos codificaciones razonables, las sentencias correspondientes a cada una de ellas son equivalentes en T.