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

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

03 Octubre, 2011, 06:09 pm
Respuesta #30

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
La sentencia indecidible de Gödel para PA, ¿tiene expresión en algún modelo? Pues se afirma que no sólo es una fórmula bien formada, sino también que es verdadera.

¿Qué quieres decir con "tiene expresión"? Se trata de una afirmación sobre números naturales que sólo involucra números, sumas, productos e igualdades. Puede interpretarse en todo modelo del lenguaje de la aritmética. Y es verdadera en la interpretación "natural", si admites que existen realmente unos objetos llamados "números naturales" que cumplen lo que cumplen y no cumplen lo que no cumplen, independientemente de cualquier axiomática que quieras fijar.
Pues entonces el teorema de Henkin afirma que debería ser demostrable... A eso me refiero.


03 Octubre, 2011, 06:21 pm
Respuesta #31

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
En el sentido de que hay afirmaciones que son consecuencia de los axiomas, en el sentido de que si los axiomas son verdaderos en un modelo tales afirmaciones también tienen que serlo y, a pesar de ello, dichas afirmaciones no pueden demostrarse a partir de dichos axiomas.
No entiendo cómo una afirmación puede ser "consecuencia de los axiomas" si no puede demostrarse a partir de ellos.

Toma por ejemplo la aritmética de segundo orden, donde el axioma de inducción es un único axioma en el que una variable de segundo orden recorre todos los subconjuntos de \( \mathbb{N} \). A dicho sistema se le puede aplicar el teorema de Gödel, que te da una sentencia G que no es demostrable ni refutable a partir de los axiomas. Ahora bien, la aritmética de segundo orden tiene un único modelo (salvo isomorfismo), luego la sentencia G tiene que ser verdadera o falsa en dicho modelo (de hecho es verdadera, pero si fuera falsa lo que voy a decir se aplicaría igualmente a su negación, con lo que no importa, así que aceptemos que es verdadera). Tenemos, pues, que todo sistema de objetos que cumpla los axiomas de la aritmética de segundo orden cumple necesariamente la sentencia G. En este sentido podemos decir que la sentencia G es consecuencia lógica de los axiomas: si los axiomas son verdaderos, G tiene que ser verdadera también, pero por el teorema de incompletitud no puedes obtener una demostración formal de G a partir de dichos axiomas.

03 Octubre, 2011, 06:26 pm
Respuesta #32

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Pues entonces el teorema de Henkin afirma que debería ser demostrable... A eso me refiero.

No. El teorema de Henkin dice que, dados unos aximas, si para todo modelo en el cual sean verdaderos, una determinada fórmula es verdadera también, entonces dicha fórmula se puede deducir formalmente a partir de los axiomas. (Y esto vale para la lógica de primer orden, pero no para la de segundo orden.)

Ahora bien, la fórmula de Gödel (para la aritmética de Peano) es verdadera en el modelo natural de la aritmética, pero, precisamente por el teorma de Henkin, como no es demostrable a partir de los axiomas de la aritmética, no puede ser verdadera en todo modelo, sino que, por el contrario, tiene que haber otro modelo de la aritmética en el cual sea falsa. Tales modelos son modelos no estándar, es decir, modelos en los que hay objetos que cumplen la definición de número natural, pero que no son ni el cero, ni el uno, ni el dos, ni el tres...

03 Octubre, 2011, 06:30 pm
Respuesta #33

Óscar Matzerath

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

donald ha explicado muy bien el tema de las posibles extensiones no recursivas de una teoría, y ha puesto un ejemplo típico que es enumerar todas las sentencias en el lenguaje de la teoría e ir añadiendo una a una de manera que la teoría se mantenga consistente en cada paso. Dejadme dar otra manera muy usual de obtener extensiones completas de una teoría, especialmente en campos como teoría de modelos. Sea T una teoría consistente cualquiera (en general, no completa) y sea M un modelo de T. Entonces, \( Th(M)= \{ \sigma \in L : M \models \sigma \} \), es decir, el conjunto de todas las sentencias que satisface M, es una teoría completa que extiende T, como se puede comprobar fácilmente (extiende T por ser M modelo de T, y es completa porque en una estructura y una sentencia cualquiera, o bien se satisface ella o bien su negación). En particular, \( Th(\mathbb{N}) \), el conjunto de sentencias de primer orden que satisfacen los naturales estándar (en un lenguaje que contenga la suma y el producto, digamos) es una teoría completa que extiende a PA, sin embargo es no recursiva (por el segundo teorema de completitud de Gödel). Fíjate que cuando axiomatizamos una teoría aritmética, lo que realmente nos gustaría sería que pudiéramos deducir todas las sentencias de \( Th(\mathbb{N}) \), sin embargo el teorema de Gödel nos dice que esto es imposible, es decir, que \( Th(\mathbb{N}) \) no es recursivamente axiomatizable.

Elius, el teorema de Henkin sólo construye un modelo de la teoría. Pero en general tienes muchos modelos de la misma teoría, y si la teoría es incompleta, esos modelos no tienen por qué ser elementalmente equivalentes, es decir, puede que haya sentencias verdaderas en unos y falsas en otras. Si aplicas la construcción de Henkin a PA obtendrás un modelo donde la sentencia de Gödel es o bien verdadera o bien falsa, pero siempre habrá modelos de PA donde sea verdadera y modelos de PA donde sea falsa. De hecho, una caracterización semántica de sentencia indecidible es la siguiente: dada una teoría T, \( \sigma \) es indecidible en T (en el sentido de que \( T \not\vdash \sigma \) y \( T \not\vdash \neg \sigma \) si y sólo si existen modelos M,M' de T tales que \( M \models \sigma \) y \( M' \not\models \sigma \).

Saludos

03 Octubre, 2011, 10:18 pm
Respuesta #34

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Así pues, un conjunto no recursivo de axiomas, será sin duda mucho menos práctico (nada en absoluto), pero no menos "comprensible" o más "paradójico" que un conjunto no recursivo de teoremas, y el conjunto de teoremas de cualquier teoría aritmética recursiva es no recursivo.
Bueno, tomar la totalidad de las verdades del modelo como el conjunto de axiomas de la teoría no es contradictorio, pero es una especie de "abuso de lenguaje". Es como que nos piden el mapa de una región, y nosotros los llevamos a recorrrer toda ella, y les decimos: "he aquí vuestro mapa". Una especie de koan.   :laugh:

Es bueno que a vosotros no os parezca raro ni paradójico, así nos lo explicáis a nosotros!


Saludos!



03 Octubre, 2011, 10:25 pm
Respuesta #35

LauLuna

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

el concepto de consecuencia lógica usual es semántico, no sintáctico: una fórmula phi es consecuencia lógica de un conjunto de fórmulas C syss phi es verdadera en todos los modelos de C (es decir, en todas las estructuras que hacen verdaderas a todas las fórmulas de C).

Todas las verdades de la aritmética de segundo orden son consecuencias lógicas de los axiomas de la aritmética de segundo orden; esos axiomas no tienen (en la semántica estándar) más modelo que los números naturales (o modelos isomorfos); sin embargo, no es posible añadir a esos axiomas un número finito de reglas de inferencia capaces de deducir de esos axiolmas todas sus consecuencias lógicas, es decir, todas las verdades de la aritmética de segundo orden, porque la lógica de segundo orden es incompleta respecto de la consecuencia lógica; es decir, la sintaxis no está aquí a la altura de la semántica, y eso hace que se cumpla el teorema de Gödel también en segundo orden.

En la semática estándar todos los modelos contienen todos los subconjuntos del dominio o universo de discurso. En la semántica de Henkin eso no es así (por decirlo así, no se toma como verdad lógica el axioma del conjunto potencia). La consecuencia es que en la semántica de Henkin hay más posibles modelos y, por tanto, menos verdades lógicas; eso hace a la lógica de segundo orden completa en esta semántica pero hace que los axiomas de segundo orden tengan más modelos que el de los números naturales. Básicamente, la semántica de Henkin convierte el caso de la aritmética de segundo orden en el caso de la aritmética de primer orden.

Para semánticas no estándar busca en la red artículos o apuntes de María Manzano (univ. de Salamanca). Si no los encuentras, tal vez pueda yo cargar aquí algunos que ella me hizo llegar hace un tiempo.

Un saludo.

03 Octubre, 2011, 10:42 pm
Respuesta #36

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Bueno, tomar la totalidad de las verdades del modelo como el conjunto de axiomas de la teoría no es contradictorio, pero es una especie de "abuso de lenguaje". Es como que nos piden el mapa de una región, y nosotros los llevamos a recorrrer toda ella, y les decimos: "he aquí vuestro mapa". Una especie de koan.   :laugh:

Es bueno que a vosotros no os parezca raro ni paradójico, así nos lo explicáis a nosotros!

¿Vosotros?, ¿nosotros?  ???

Pero fíjate que nadie está proponiendo usar como axiomas de ninguna teoría las sentencias verdaderas en un modelo. La cuestión es que si alguien pregunta si todo sistema aritmético consistente es incompleto, la respuesta es "no", pues si no supones que es recursivo te puedes encontrar contraejemplos como los que te hemos puesto. No esperarás que respondamos "sí" porque los ejemplos te parezcan raros. Lo que es, es y lo que no es, no es, eso es la lógica.

Por otra parte, no es necesario tomar todas las sentencias verdaderas. A partir del conjunto de todas ellas, puedes enumerarlas y empezar a eliminarlas una a una siempre que cada sentencia que eliminas se pueda deducir de las que te quedan. Así puedes llegar a un conjunto de axiomas "bastante más pequeño" y que igualmente es completo.

03 Octubre, 2011, 11:47 pm
Respuesta #37

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
La cuestión es que si alguien pregunta si todo sistema aritmético consistente es incompleto, la respuesta es "no", pues si no supones que es recursivo te puedes encontrar contraejemplos como los que te hemos puesto. No esperarás que respondamos "sí" porque los ejemplos te parezcan raros. Lo que es, es y lo que no es, no es, eso es la lógica.
¿No hay un problema lingüístico aquí? No es que parezca raro, o paradójico, o no solamente eso: el conjunto que se da como ejemplo no es factible, aún quitando la condición de recursividad. No puede siquiera comenzar a construírse. Entonces, es una elección de juego de lenguaje decir que todo sistema aritmético consistente es incompleto o decir que hay uno que es completo, pero sus axiomas no pueden ser explicitados (salvando el recurso a Berry, por supuesto!  ;D )

Saludos!

04 Octubre, 2011, 12:16 am
Respuesta #38

LauLuna

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

si supones que sólo existen los conjuntos que se pueden construir, te sitúas en una filosofía de las matemáticas muy diferente de la dominante: te alineas con alguna versión del constructivismo.

Ciertamente, hay puntos de vista constructivistas para los que no existen teorías completas de la aritmética: los conjuntos de sentencias aritméticas que son completos no son recursivamente enumerables, menos aun recursivos, por el teorema de Gödel. Entonces no existen según algunas posiciones constructivistas.

No se trata quizá de una diferencia lingüística la que os separa a donald y a ti sino de una diferencia filosófica.

Un saludo.

04 Octubre, 2011, 12:17 am
Respuesta #39

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿No hay un problema lingüístico aquí? No es que parezca raro, o paradójico, o no solamente eso: el conjunto que se da como ejemplo no es factible, aún quitando la condición de recursividad. No puede siquiera comenzar a construírse. Entonces, es una elección de juego de lenguaje decir que todo sistema aritmético consistente es incompleto o decir que hay uno que es completo, pero sus axiomas no pueden ser explicitados (salvando el recurso a Berry, por supuesto!  ;D )

Sigues confundiendo definir un conjunto con ser capaz de determinar cuáles son sus elementos. Vuelvo a preguntarte: ¿No es factible el conjunto de los números trascendentes porque no conozcamos ningún algoritmo para determinar si un número real arbitrario es o no trascendente?

Te he puesto antes el ejemplo del conjunto de los teoremas de una teoría aritmética recursiva y parece que aceptas su existencia, a pesar de que no existe ningún algoritmo para decidir si una sentencia dada es o no uno de sus elementos. Has dicho que ese vale porque puedes definir los teoremas como la sentencias deducibles a partir de los axiomas. Vale, yo también te he indicado cómo definir un conjunto completo de axiomas que no es conceptualmente más complicado que el que te permite definir el conjunto de los teoremas de una teoría aritmética recursiva. ¿Por qué aceptas que la segunda definición te define realmente un conjunto y en cambio te niegas a aceptar que la que yo te he dado tambén lo hace?

¿Por qué en el caso de los axiomas consideras imprescindible que se pueda decidir qué es un axioma y qué no lo es y en el caso de los teoremas no te importa que no pueda hacerse tal cosa? ¿Es una cuestión de lenguaje decir que existe el conjunto de los teoremas de una teoría aritmética o que no existe?