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

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

04 Octubre, 2011, 10:43 pm
Respuesta #50

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
El teorema de Henkin respecto de la construcción de un modelo a partir de cualquier teoría consistente de orden 1 no está en cuestión.

Además de eso, según creo entender, Henkin extiende la teoría de Peano para que sea completa, pero lo hace sólo para el caso trivial en que todas las verdades del modelo han sido incorporadas al lenguaje de PA como axiomas.

No, eso no es así. El teorema de Henkin afirma que cualquier conjunto consistente de axiomas de un lenguaje formal de primer orden tiene un modelo, y para probarlo empieza demostrando que dicho conjunto puede extenderse a un conjunto completo de sentencias (esencialmente por el procedimiento que te puse como ejemplo) sin hacer referencia a que sean verdaderas en ningún modelo y, según creía yo entender, era precisamente esto lo que tú cuestionabas, que tuviera sentido decir que existe un conjunto así cuando no sabemos precisar cuáles son sus elementos en la práctica. Una vez tiene este conjunto consistente y completo de axiomas, construye un modelo en el que todas ellas son verdaderas. (En realidad hay un tecnicismo de por medio que estoy omitiendo, y es que hay que añadir también una familia de constantes para que todo objeto cuya existencia pueda ser demostrada a partir de la extensión completa sea nombrado por una constante.)

Para el caso trivial en que consideras las sentencias verdaderas en el modelo natural de PA no necesitas el teorema de Henkin, sino que ya tienes el modelo de partida.

Mi cuestionamiento, aparte de la trivialidad, es que me parece un abuso de lenguaje decir que "extiendo" el poder demostrativo de una teoría si para demostrar una sentencia debo incorporarla como axioma.

Pero es que nadie ha dicho eso. A ver si me explico:

Gödel demostró su teorema de incompletitud para sistemas aritméticos recursivos y \( \omega \)-consistentes, donde esto último es una condición técnica un tanto molesta, pero luego Rosser dio una demostración alternativa, algo más compleja, que eliminaba la hipótesis de \( \omega \)-consistencia y la sustituía por la mera consistencia.

A la vista de esto, alguna mente inquieta podría preguntarse: ¿y no podríamos eliminar también la hipótesis de recursividad y probar que todo sistema aritmético consistente es incompleto? Si alguien se plantea esto, podría pasarse horas y horas buscando una demostración más sofisticada aún del teorema de Gödel que no se apoyara en la recursividad de los axiomas.

Ahora bien, podemos demostrar que tal intento sería inútil, porque podemos extender los axiomas de PA a un conjunto completo de axiomas, bien como te expliqué yo, bien como explicó Oscar. Y entonces es cuando tú dices: ¡vaya bobada de sistema axiomático en el que no podemos saber qué es un axioma y qué no lo es!, lo cual es cierto, pero yo te contesto: ciertamente, ese sistema axiomático no sirve para trabajar con él, pero, al fin y al cabo, es un sistema aritmético consistente y completo, lo cual aporta una consecuencia útil y práctica: a saber, que la mente inquieta obstinada en encontrar una demostración refinada del teorema de Gödel que no use la recursividad como hipótesis está perdiendo el tiempo, pues tal demostración no puede existir, porque ese ejemplo tonto e inútil de sistema deductivo formal completo prueba que es imposible llenar un papel con algo que sea una demostración rigurosa del teorema de Gödel sin la hipótesis de recursividad, y esto no es evidente en absoluto.

De este modo, ese sistema aritmético tonto y estafador cumple una misión muy útil y nada trivial. Puedes burlarte de él todo lo que quieras como sistema deductivo, pero lo único que hace falta es que admitas su existencia. Si admites que existe, entonces deduces de dicha existencia algo no trivial: que lo que podría en un principio parecer un proyecto prometedor (generalizar el teorema de Gödel eliminando la recursividad) en realidad es un imposible.

Disculpen si en el calor de la polémica hubo algo fuera de tono de mi parte, o de parte de otros inducidos por mis posteos.

No veo que esto sea necesario, pero si alguien puede pensar que algo dicho por mí estaba fuera de tono, pido disculpas. Sólo he tratado de describir lo más clara y gráficamente un punto de vista (el mío) sin ánimo de censurar a nadie y, recíprocamente, no soy capaz de detectar nada en tus mensajes que pudiera interpretarse como ofensivo o qué se yo.

05 Octubre, 2011, 12:51 am
Respuesta #51

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
La demostración del teorema de completitud de Gödel pasa por la construcción de un modelo de una teoría axiomática dada bajo la única hipótesis de su consistencia. Por lo tanto, Lelius, si no te crees que tenga sentido hablar de un conjunto completo de sentencias que extienda a unos axiomas dados por el hecho de que no puedas saber qué sentencias están en él y cuáles no, entonces no puedes creerte el teorema de completitud.

No, esto no es así. El teorema de que todo conjunto LP1-consistente de fórmulas de primer orden tiene un modelo sigue siendo válido en un contexto constructivista: que todo conjunto recursivo (o recursivamente enumerable) LP1-consistente de fórmulas de primer orden tiene un modelo se deduce del teorema anterior trivialmente es la lectura constructivista del teorema.

A partir de ahí, la demostración de completitud de LP1 es fácil e inobjetable desde el punto de vista constructivista. Repito la que di unos mensajes atrás.

Asumimos que todo conjunto de sentencias de primer orden LP1-consistente tiene un modelo, donde LP1 es la lógica de predicados de primer orden. Sea V una verdad lógica cualquiera de primer orden. Por definición de verdad lógica, {¬V} no tiene modelos; entonces es LP1-inconsistente, es decir, LP1 deduce una contradicción 'p&¬p' a partir de {¬V}; entonces, por el teorema de deducción, LP1 demuestra '¬V -> p&¬p'; luego LP1 demuestra V por reducción al absurdo y doble negación.

No hay nada objetable desde un punto de vista constructivista (o intuicionista) en esta demostración.

Un saludo.

05 Octubre, 2011, 12:57 am
Respuesta #52

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No, esto no es así. El teorema de que todo conjunto LP1-consistente de fórmulas de primer orden tiene un modelo sigue siendo válido en un contexto constructivista: que todo conjunto recursivo (o recursivamente enumerable) LP1-consistente de fórmulas de primer orden tiene un modelo se deduce del teorema anterior trivialmente.

Disculpa, pero no acabo de entender lo que dices: ¿Cómo se demuestra (constructivamente) que todo conjunto recursivo (o recursivamente numerable) y consistente de fórmulas de la lógica de primer orden tiene un modelo? No sé a qué teorema anterior te refieres. Ciertamente, a partir de ahí el resto no da problemas, pero ¿cómo se demuestra eso?

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

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Sigo sin entender la rectificación que has hecho:

Tenemos el teorema que afirma que todo conjunto consistente (recursivo o no, pero supongamos que es recursivo) de sentencias de un lenguaje de primer orden tiene un modelo. El problema es que emplees la construcción que emplees para llegar a ello, no podrás tener un criterio para saber qué afirmaciones son verdaderas en dicho modelo. Esto no es ya por las características de la construcción que he esbozado (que es la típica de Henkin), sino por el teorema de Tarski de indefinibilidad de la verdad: si la demostración fuera "constructiva" hasta el punto de que pudiera existir una forma de saber qué afirmaciones son verdaderas y cuáles son falsas en dicho modelo, el conjunto de las afirmaciones verdaderas sería recursivo, pero, simplemente con que fuera recursivamente numerable, sería ya bastante para que fuera aritmético, es decir, expresable en el lenguaje de la aritmética, y entonces podríamos construir una afirmación que sea verdadera si y sólo si es falsa, y tendríamos una contradicción.

Si hay realmente una versión constructiva de ese teorema, hay algo que se me escapa. Por eso te agradecería más detalles al respecto.

05 Octubre, 2011, 01:25 am
Respuesta #54

LauLuna

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

tienes razón: en mi anterior mensaje he pasado eso por alto, y es lo fundamental.

Pero parece que esa demostración existe: http://lara.epfl.ch/w/lugano:program

Aunque no conozco el detalle de ella.

A propósito, pregunto: ¿es constructiva la prueba de Gödel de 1930? Si no ¿en que punto deja de serlo?

En cuanto a la prueba de Henkin, parece que no es constructiva. Pero, dado un conjunto recursivamente enumerable de sentencias de primer orden ¿no habrá una manera recursiva de construir el conjunto saturado y máximamente consistente que necesitamos para construir para él el modelo de Henkin?

Conjeturo que sí. Dejadme pensarlo.

Un saludo.

05 Octubre, 2011, 01:49 am
Respuesta #55

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Ojo que aquí hablo sin conocer en profundidad el asunto, pero tengo entendido que la prueba original de Gödel consiste en definir un árbol de sentencias y usar una variante del teorema de König, que le permite asegurar que dicho árbol tiene una rama infinita, y esa rama le da el modelo que busca, pero sin poder determinar cuál es esa rama concretamente.

De hecho, el propio Gödel razonó que no podía existir una prueba constructiva del teorema, y la razón es la que te he dicho antes: si pudieras construir recursivamente el conjunto saturado y máximamente consistente de sentencias, éstas acaban siendo las afirmaciones verdaderas del modelo que construyes, pero el conjunto de afirmaciones verdaderas en un modelo de una teoría aritmética no puede ser recursivo, ni recursivamente numerable, ni complementario de un conjunto recursivamente numerable, pues todos estos conjuntos son aritméticos, y entonces el argumento del teorema de Tarski permite construir una sentencia aritmética que afirma su propia falsedad, y esto lleva a una contradicción. En otras palabras, si se pudiera hacer lo que pretendes, se podría formalizar la paradoja del mentiroso, pasando de ser una paradoja informal sin importancia teórica o práctica (en el sentido de que no afecta para nada a la lógica formal) a una contradicción en toda regla.

He encontrado en internet varios artículos sobre la demostración que indicas (busca constructive proof of godel completeness theorem en google y no tardarás en encontrarlos). No lo he visto con detalle, pero se trata de una prueba para la lógica intuicionista, no para la lógica clásica. La verdad es que todo lo que acabo de leer brevemente es muy escurridizo, pero necesariamente hay "gato encerrado", es decir, es imposible que prueben una versión realmente equivalente al teorema de Henkin. De hecho, en un artículo dicen que la misma técnica permite dar una prueba constructiva de la existencia de ultrafiltros, lo cual ya es el colmo, porque la existencia de ultrafiltros depende esencialmente del axioma de elección (aunque no es equivalente a él, sino un poco más débil).

05 Octubre, 2011, 01:39 pm
Respuesta #56

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Yo, y no por convicción, porque aunque no estoy de acuerdo (o mejor dicho, creo que la ciencia necesita un continuo alef1 para describir el espacio (físico), no sólo el espacio-tiempo relativista curvo que se concibe actualmente sino ya en la tal como se concebía en época de Newton) es cierto que los conceptos de la  Matemática existen independientes de lo que ocurre en el mundo real (podríamos construir, los ultrafinitistas lo hacen, una Matemática sin infinitos), ahora bien, si para describir la realidad los infinitos son necesarios, no es que el ultrafinitismo tenga que por que ser erroneo, pero no es una Matemática adecuada para hablar de Física o de cualquier otra ciencia natural. Otro tanto parecido le ocurre a las escuelas constructivistas.

Ahora bien, el constructivismo nos dejó una lógica intuicionista, que dicho en pocas palabras, es una lógica clasica a la que le quitamos el  tercero excluido.

Yo sinceramente, creo que es la lógica más adecuada en el mundo real, y que fijar una descripción impropia en un modelo no es más que un invento ad hoc para poder seguir usando la lógica aristotélica y crear un principio de tercero excluido donde no lo hay. Si fuera un matemático experto quizás trabajara en una logica intuicionista , pero no me resulta obvio ver que teoremas se pueden deducir sin admitir el tercero excluido, y por eso trabajo con los estandars de la lógica clásica como hace la mayoría

Intento aclarar un poco mejor el concepto de modelo natural de la teoría de conjuntos, en especial para donald. Tengamos un conjunto definido por extensión C={a,b,d}, es indiferente que a, b y d sean otros conjuntos , urelementos, o incluso pares ordenados

Un modelo natural implica que a, b, d € C, es decir, que la enumeración de elementos de un conjunto nos dice ya que elementos pertenecen a ellos. Obviamente la definición por enumeración sólo es practica con conjuntos de cardina muy pequeño, sino hay que emplear la definición por compresión (restringida de algun modo) para evitar la paradoja de Russell y otras. En ese caso diriamos que e€C, si y solo sí hace verdadero un predicado asociado al conjunto C de tal manera que PsubC(x) <---> equivale a x€C, desde luego, aqui tambien a que  restringir de algun modo (dependiente de que teoría de conjuntos usemos) qué predicados son válidos para definir un conjunto. Y luego están los conjuntos que tienen elementos no definibles, por ejemplo , conjuntos no definibles, en los que no existe una manera sensata de definir a sus componentes, estos conjuntos en la práctica existen por el teorema de elección pero salvo para incluirlos a la hora de contar conjuntos no se me ocurre cómo trabajar con ellas (no quiero decir que no se pueda, sino que simplemente no conecto el método)

Mi pregunta es si trabajando en un modelo cualquiera, numerable incluso, por un lado , y luego restringiendonos a modelos naturales, toda afirmación ( en el modelo concreto, no en la teoría general vista sintácticamente) ha de ser verdadera o falsa en un modelo, aunque desde luego, determinadas formulas (precisamente las que no son sintácticamente decidibles) pueden ser verdaderas o falsas, dependiendo del modelo, pero mi duda es si ya fijado un modelo , la fórmula puede seguir sin ser verdadero o falso, o el imponer trabajar en un modelo, obliga a que toda fórmula de la teoría (entendida en ese modelo) sea verdadera o falsa

Saludos

05 Octubre, 2011, 08:32 pm
Respuesta #57

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
No, esto no es así. El teorema de que todo conjunto LP1-consistente de fórmulas de primer orden tiene un modelo sigue siendo válido en un contexto constructivista: que todo conjunto recursivo (o recursivamente enumerable) LP1-consistente de fórmulas de primer orden tiene un modelo se deduce del teorema anterior trivialmente.

Disculpa, pero no acabo de entender lo que dices: ¿Cómo se demuestra (constructivamente) que todo conjunto recursivo (o recursivamente numerable) y consistente de fórmulas de la lógica de primer orden tiene un modelo? No sé a qué teorema anterior te refieres. Ciertamente, a partir de ahí el resto no da problemas, pero ¿cómo se demuestra eso?

Gödel no intenta demostrar eso.

Hay muchos nombres diferentes, y muchos caminos, para un mismo propósito, y a la inversa, a veces se usa un mismo nombre para teoremas diferentes. Me parece que eso sucede con las contribuciones de Henkin.

Pero en el caso de Gödel, y su teorema de completitud del cálculo puro de orden 1 (LP1), está todo muy claro.

a) Plantea que toda fbf lógicamente válida es demostrable, y a la inversa. No parte del enunciado semántico, usa métodos semánticos para demostrarlo. Se limita al cálculo puro de predicados de orden 1.

b.1) La inversa es la parte más fácil, pues los axiomas son tautologías, y las reglas de inferencia conservan el carácter tautológico.

b.2) La directa no sería rechazada por el constructivismo, pues da un método genérico para construir una fórmula equivalente a cualquiera que sea satisfecha por cualquier modelo, y no usa tercero excluído.

Por lo que puedo inferir, las teorías específicas, con axiomas compuestos por predicados fijos, como PA, ZF, etc, quedan excluídas.

Una fuente muy buena para este teorema es

Introducción a la metamatemática
Stephen Cole Kleene
Editorial Tecnos, Madrid, 1974 - 494 páginas

y en internet,

http://plato.stanford.edu/entries/goedel/#ProComThe

Saludos!



05 Octubre, 2011, 11:49 pm
Respuesta #58

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
No, esto no es así. El teorema de que todo conjunto LP1-consistente de fórmulas de primer orden tiene un modelo sigue siendo válido en un contexto constructivista: que todo conjunto recursivo (o recursivamente enumerable) LP1-consistente de fórmulas de primer orden tiene un modelo se deduce del teorema anterior trivialmente.

Disculpa, pero no acabo de entender lo que dices: ¿Cómo se demuestra (constructivamente) que todo conjunto recursivo (o recursivamente numerable) y consistente de fórmulas de la lógica de primer orden tiene un modelo? No sé a qué teorema anterior te refieres. Ciertamente, a partir de ahí el resto no da problemas, pero ¿cómo se demuestra eso?

Gödel no intenta demostrar eso.

Sí, eso parece que ya ha quedado claro. Como ya dije, no estoy familiarizado con la prueba original de Gödel.

a) Plantea que toda fbf lógicamente válida es demostrable, y a la inversa. No parte del enunciado semántico, usa métodos semánticos para demostrarlo. Se limita al cálculo puro de predicados de orden 1.

Hombre, "ser lógicamente válida" es un concepto semántico. Pasar de ahí al enunciado en términos de "consecuencia lógica" implica "ser deducible" ya es inmediato.

b.2) La directa no sería rechazada por el constructivismo, pues da un método genérico para construir una fórmula equivalente a cualquiera que sea satisfecha por cualquier modelo, y no usa tercero excluído.

Por lo que puedo inferir, las teorías específicas, con axiomas compuestos por predicados fijos, como PA, ZF, etc, quedan excluídas.

¿Sí? Ya digo que no sé qué demostró exactamente Gödel y no puedo afirmar nada, pero me resulta extraño, pues la "gracia" del teorema de completitud es que es aplicable a esas teorías.

05 Octubre, 2011, 11:56 pm
Respuesta #59

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Mi pregunta es si trabajando en un modelo cualquiera, numerable incluso, por un lado , y luego restringiendonos a modelos naturales, toda afirmación ( en el modelo concreto, no en la teoría general vista sintácticamente) ha de ser verdadera o falsa en un modelo, aunque desde luego, determinadas formulas (precisamente las que no son sintácticamente decidibles) pueden ser verdaderas o falsas, dependiendo del modelo, pero mi duda es si ya fijado un modelo , la fórmula puede seguir sin ser verdadero o falso, o el imponer trabajar en un modelo, obliga a que toda fórmula de la teoría (entendida en ese modelo) sea verdadera o falsa

Pues sigo sin estar seguro de entenderte. Voy a dar un palo de ciego a ver si lo que preguntas tiene que ver con esto:

Para no complicar el ejemplo con tecnicismos, voy a considerar la teoría ZFCI, que es ZFC más la existencia de un cardinal fuertemente inaccesible. Si alguien no sabe lo que es eso, no importa. Basta con saber que si \( \kappa \) es fuertemente inaccesible, entonces el conjunto \( M=V_\kappa \) formado por todos los conjuntos de rango menor que \( \kappa \) es un modelo natural de ZFC. Si alguien no sabe lo que significa esto, tampoco importa, lo que importa es que así tenemos un modelo natural de ZFC adecuado para lo que voy a decir.

Tomemos, por ejemplo, la hipótesis del continuo HC. Por definición de "verdad", podemos afirmar (demostrar en ZFCI) que o bien \( M\vDash HC \) o bien \( M\vDash \lnot HC \). Ahora bien, no podemos demostrar cuál de los dos casos se da, pues si se cumple HC, entonces se cumplirá \( M\vDash HC \), mientras que si no se cumple HC, entonces se cumplirá \( M\vDash \lnot HC \). ¿Tiene que ver con eso tu pregunta?