Autor Tema: Definición de verdad en teoría de conjuntos

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

01 Junio, 2011, 08:07 pm
Respuesta #10

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Aquí la tienes Elius:

http://www.cs.nyu.edu/mailman/listinfo/fom/

Si en esa página pulsas en FOM Archives puedes acceder a los archivos de discusiones.

Por cierto, últimamente se han discutido hasta la saciedad en FOM los atrevidos juicios de Voevodski en esta conferencia en el Instituto de Estudios Avanzados de Princeton:

http://video.ias.edu/stream&ref=415

Es un tema que puede estar relacionado con este hilo. Voevodski expone su creencia en que la aritmética de Peano es inconsistente (por tanto, la teoría de conjuntos también): argumenta que Gödel (en su segundo teorema) estableció que su consistencia no puede probarse. Harvey Friedman ha remitido a FOM, con permiso de Voevodski, su correspondencia con él. De ella se deduce que Voevodski cree

1. que la consistencia de la aritmética de Peano no puede demostrarse dentro de la aritmética de Peano:

2. que lo que el segundo teorema de Gödel sugiere es que la aritmética de Peano es inconsistente

a pesar de que es trivial que si la aritmética de Peano no demuestra su propia consistencia es consistente porque si fuese inconsistente demostraría todas las fórmulas de su lenguaje.

Pero Voevodski no es un cualquiera: recibió en su día la medalla Fields y está hablando en el Instituto en el que trabajaron Einstein y Gödel, así que todo es muy extraño...

Un saludo

01 Junio, 2011, 11:03 pm
Respuesta #11

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias, LauLuna!

Pero Voevodski no es un cualquiera: recibió en su día la medalla Fields y está hablando en el Instituto en el que trabajaron Einstein y Gödel, así que todo es muy extraño...

Tal parece que estos temas de lógica con aire paradójico quiebran cabezas laureadas también. He leído que Zermelo estuvo dos años tratando de encontrar un error en la demostración de Gödel, y Wittgenstein llegó a decir que no tenía importancia, que las contradicciones no debían generar un temor supersticioso "propio de los matemáticos" (???)
Contemporáneamente, Gregory Chaitin dice haber encontrado una forma de los teoremas de incompletitud más profunda que la de Gödel...

Saludos!

02 Junio, 2011, 03:52 pm
Respuesta #12

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Quizá Chaitin tenga algo de razón en eso, Elius.

Los axiomas de un sistema formal axiomático (de primer orden) son la compresión (no comprensión) en una expresión finita de un conjunto infinito de fórmulas. Lo que ha estudiado Chaitin es que hay conjuntos infinitos de fórmulas que no son compresibles (es decir, que tienen complejidad algorítmica infinita); en concreto, lo es el conjunto de las fórmulas verdaderas del lenguaje de la aritmética; y de ahí se deduce la incompletitud de Gödel.

Chaitin ha buscado una raíz de la incompletitud que resulta intuitiva.

Un saludo.

02 Junio, 2011, 06:19 pm
Respuesta #13

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Quizá Chaitin tenga algo de razón en eso, Elius.
......
Chaitin ha buscado una raíz de la incompletitud que resulta intuitiva.
Es cierto, pero aquí:
http://www.ams.org/notices/200109/rev-panu.pdf
le hacen una crítica bastante dura, sin ignorar sus logros, pero poniendo en duda su importancia.

Saludos!

30 Septiembre, 2011, 04:14 pm
Respuesta #14

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Bueno, realmente lo que es de Henkin no es el teorema en sí, que está claro que se sigue fácilmente del de completitud de Gödel
Oscar, disculpa si pregunto algo obvio, pero puesto que el teorema de completitud de Gödel es válido para el cálculo de predicados, y no para cualquier teoría de orden 1, no entiendo cómo se sigue que toda teoría de orden 1 consistente tiene un modelo. A la explicación que esbozas la entiendo; pero, si no es mucho pedir, me gustaría saber cómo se relaciona eso de construir una estructura en base a la teoría, con la demostración de Gödel de que toda sentencia lógicamente verdadera es demostrable en el cálculo puro de predicados, y viceversa.

Gracias de antemano, Saludos


30 Septiembre, 2011, 08:48 pm
Respuesta #15

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

En realidad el teorema de completitud de Gödel sí sirve para cualquier teoría de primer orden, es decir, si \( \Sigma \) es cualquier conjunto de sentencias de primer orden y \( \varphi \) cualquier sentencia de primer orden, se tiene \( \Sigma \models \varphi \iff \Sigma \vdash \varphi \). Como caso particular en que \( \Sigma = \emptyset \) obtienes que el cálculo deductivo puro de primer orden es consistente y completo para el conjunto de sentencias lógicamente válidas, pero como ya digo es más general.

No sé si la demostración original de Gödel es para cualquier teoría o si es sólo para el cálculo puro (debería echarle un vistazo), pero en cualquier caso lo que hoy en día la gente suele entender por "teorema de completitud de la lógica de primer orden" es la versión más general que he puesto arriba.

De todas maneras, la demostración de Henkin que mencioné construye "explícitamente" un modelo para cualquier teoría dada \( \Sigma \), así que no hay problema en ver que toda teoría consistente tiene un modelo.

Saludos

30 Septiembre, 2011, 08:58 pm
Respuesta #16

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Elius,

a ver si te sirven estas demostraciones apresuradas.

Supón que LP1 (lógica de predicados de primer orden) demuestra todas las verdades lógicas; de ahí se sigue que, dado un conjunto C de fórmulas de primer orden, LP1 deduce a partir de C todas las consecuencias lógicas de C; en efecto, si phi es consecuencia de C, hay (por el teorema de compactidad) su subconjunto finito F de C, tal que phi es consecuencia de F; entonces el condicional formado así:

f1 & f2 & f3 & ... fn -> phi

donde las efes son los elementos de F, es una verdad lógica que LP1 demuestra; luego LP1 demuestra phi a partir de F por modus ponens; por tanto, también lo demuestra a partir de C. QED.

Contando con esa completitud, supón ahora que un conjunto C de fórmulas de primer orden es consistente de acuerdo con LP1; entonces de C no es consecuencia ninguna contradicción (si lo fuera, LP1 la deduciría de C y C sería inconsistente según LP1); entonces todas las fórmulas de C pueden ser verdaderas a la vez, es decir, C tiene un modelo (aquí dejo algún paso a tu buen entender). QED.

A la inversa, supón que todo conjunto consistente según LP1 tiene un modelo. Sea V una verdad lógica; por definición de verdad lógica, {¬V} no tiene un modelo; entonces es inconsistente según LP1; entonces LP1 deduce una contradicción 'p&¬p' de {¬V}; por el teorema de deducción, LP1 demuestra '¬V -> p&¬p'; luego por reducción al absurdo y doble negación, LP1 demuestra V. QED.

Óscar,

uso el teorema de compactidad para pasar de la completitud con respecto a la validez lógica a la completitud con respecto a la consecuencia lógica. La implicación inversa es la que tú demuestras.

Un saludo.

30 Septiembre, 2011, 09:15 pm
Respuesta #17

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Sí, con compacidad es sencillo pasar del caso particular para pasar de la completitud para \( \Sigma = \emptyset \) al caso para un \( \Sigma \) cualquiera. El único "problema" (que en realidad no es tal, por supuesto) es que usualmente cuando se presenta la lógica se demuestra el teorema de compacidad a partir del teorema de completitud (en la versión general), ya que las demostraciones del cálculo son por definición finitas y por tanto sólo pueden involucrar un número finito de premisas de \( \Sigma \).

Por suerte hay formas de obtener el teorema de compacidad sin usar para nada el teorema de completitud, y sin hacer referencia a ningñun cálculo, sino de forma totalmente semántica. La demostración típica por este camino (pero que creo que hoy en día poca gente hace, porque requiere introducir un poco de "arsenal pesado") es mediante ultraproductos y el teorema de Los. Aprovecho para preguntar si alguien conoce otras demostraciones del teorema de compacidad que no sean vía el teorema de completitud ni vía ultraproductos, ya que el teorema de compacidad es para mí el teorema más útil de la lógica de primer orden y nunca está de más conocer nuevas demostraciones.

Saludos

30 Septiembre, 2011, 11:26 pm
Respuesta #18

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Muchas gracias, LauLuna y Óscar; voy a leer los posteos con detenimiento.
Me permito adelantar una perplejidad, tal vez fruto del apresuramiento: si la completitud vale para las teorías de orden 1 en general, ¿cómo es que hay algunas incompletas, como la aritmética de Peano? ¿O es que hay que distinguir entre completitudes, semántica y sintáctica?

Saludos!

01 Octubre, 2011, 12:05 am
Respuesta #19

Óscar Matzerath

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 567
  • Karma: +0/-0
  • Sexo: Masculino
Hola,

Eso es porque (desafortunadamente tal vez) se usa la palabra "completitud" para dos cosas distintas: una es un cálculo completo respecto a una semántica, que es lo que hemos estado discutiendo, y otra muy distinta es el hecho de que una teoría sea completa. Una teoría (que no es más que un conjunto de sentencias, aunque hay que ir con ojo si miras por ahí porque hay gente que define teoría como conjunto de sentencias cerrado bajo consecuencia lógica) es completa si para toda sentencia de primer orden \(  \varphi \) en el lenguaje de la teoría o bien \( T \vdash \varphi \) o bien \( T \vdash \neg \varphi \) (podemos imponer también en la definición que T sea consistente, pues una teoría inconsistente es trivialmente "completa", ya que prueba todas las sentencias).

Aún así, hay que andar con ojo con los temas de incompletitud porque se prestan a muchos malentendidos. Toda teoría se puede extender a una teoría completa. En particular, PA puede extenderse a una teoría completa de primer orden. Lo que el teorema de Gödel dice es que ninguna de esas extensiones va a ser recursivamente axiomatizable (es decir, no vas a poder dar una lista de axiomas tal que exista un algoritmo para decidir si una fórmula dada es un axioma de tu teoría o no, dicho grosso modo). Así pues, sí que existen teorías que extienden a PA, ZFC o cualquier otra teoría y que son completas, pero ninguna de estas va a resultar útil en la práctica (pensando en dar demostraciones mediante un cálculo) pues ni siquiera podemos identificar una demostración correcta en tal teoría (ya que no tenemos manera de saber cuáles son sus axiomas).

Saludos