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

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

06 Octubre, 2011, 01:11 am
Respuesta #60

LauLuna

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

mi sugerencia no era la de producir una prueba constructiva del teorema de completitud (que otros dicen haber encontrado y que, después de leer tu razonamiento, parece dudoso) sino una prueba constructiva de este otro enunciado aparentemente más débil:

todo conjunto constructivamente admisible y LP1-consistente de sentencias de primer orden tiene un modelo.

Esto es lo que sería el equivalente constructivista del teorema de completitud.

No he tenido mucho tiempo para pensar esto pero un primer intento de producir constructivamente un modelo estilo Henkin para conjuntos recursivos se me ha atrancado. A ver si en los próximos días puedo dedicar algún tiempo al asunto, que es interesante.

Un saludo.

06 Octubre, 2011, 09:29 am
Respuesta #61

Óscar Matzerath

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

Respecto al teorema de Henkin, conjuntos recursivos y constructivismo, puede ser interesante conocer unos cuantos resultados obtenidos en "reverse mathematics". Para quien no sepa de qué va esto, es una rama de la lógica matemática que busca identificar los sistemas más débiles en los que es posible demostrar un teorema matemático (y esto incluye desde resultados de lógica hasta resultados de álgebra o de análisis funcional). Más concretamente se trata con subsistemas de la aritmética de segundo orden, entendida como una lógica de primer orden two-sorted donde una "sort" son los números naturales y la otra subconjuntos de naturales, de manera que hay un cálculo deductivo para cada uno de estos subsistemas. Un \( \omega \)-modelo de uno de estos subsistemas es un modelo (two-sorted) donde el universo de la sort de números es \( \omega \), los naturales estándar y la interpretación de los símbolos aritméticos es la estándar, y donde el universo para la sort de subconjuntos puede ser cualquier cosa contenida en \( P(\omega) \) (pero no necesariamente tiene por qué ser todo \( P(\omega) \)).

El subsistema más débil que se considera es el llamado \( RCA_0 \) (por "recursive comprehension axiom" y el 0 viene de que la inducción está restringida a fórmulas \( \Sigma^0_1 \), es decir, fórmulas cuyos únicos cuantificadores no acotados son cuantificadores existenciales sobre números). Lo interestante de este subsistema es que tiene un \( \omega \)-modelo donde el universo de los subconjuntos es precisamente REC, el conjunto de todos los subconjuntos recursivos de \( \omega \). Este hecho y varios otros hacen que la gente "identifique" en cierta manera este subsistema con lo que se puede obtener en matemática constructivista, aunque hay que advertir que hay muchas diferencias (para empezar, aquí se usa lógica clásica, en particular vale el tercero excluido). En cualquier caso, lo que parece claro es que todo teorema de matemática constructivista es reproducible en este subsistema.

En \( RCA_0 \) es posible reproducir gran parte de la lógica matemática básica. En particular es posible probar el siguiente teorema, que es una versión débil del teorema de Henkin:

Sea \( X \subseteq Sent \) consistente y cerrado bajo consecuencia lógica. Entonces existe un modelo numerable M tal que \( M \models \sigma \) para toda \( \sigma \in X \).

Lo interesante es notar que no podemos prescindir del hecho de ser cerrado bajo consecuencia lógica, ya que tomando una teoría aritmética básica como Q, tenemos que toda teoría cerrada bajo consecuencia lógica que extiende a Q es no recursiva, luego en el \( \omega \)-modelo REC de \( RCA_0 \) vale "Q es consistente pero no tiene ningún modelo". Y por lo dicho antes, lo mismo debería valer en matemáticas constructivistas.

Saludos


06 Octubre, 2011, 04:05 pm
Respuesta #62

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
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.
¿Inmediato? Ese es el paso que cuesta tanto que la mayoría de las memorias de la demostración original omite. Implica el armado de un árbol de sentencias manteniendo la equivalencia, el método para la construcción de la rama infinita del lema de König que tú mencionabas ("In the proof, Gödel explicitly constructs the branch given by König's Lemma rather than citing it by name", www.plato.stanford.edu/entries/goedel/#ProComThe).
No sé si Gödel era constructivista, pero se acercó cuanto pudo al constructivismo, puesto que construyó explícitamente la sentencia indecidible de PA, no solamente demostró su existencia.

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.
¿Podrías mencionar algún teorema de completitud que incluya PA y ZF? El que mencionábamos días atrás como de Henkin, en realidad es el lema de Lindenbaum, y se refiere a una extensión que incluye como axiomas todas las sentencias no refutables, de modo que no es PA ni ZF, y ni siquiera son extensionalmente equivalentes, porque mientras PA no tiene como teorema las sentencias indecidibles, su extensión por Lindenbaum sí las tiene.

Saludos!


06 Octubre, 2011, 04:57 pm
Respuesta #63

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
...mi sugerencia no era la de producir una prueba constructiva del teorema de completitud (que otros dicen haber encontrado y que, después de leer tu razonamiento, parece dudoso)
Me pregunto si una prueba constructiva de completitud implicaría necesariamente la decidibilidad, pues, en ese caso sería imposible por Turing y Church. Pero podría ser constructiva en el sentido inverso del de Henkin: a partir de \( M \models \varphi \), establecer la existencia necesaria de una deducción en el lenguaje formal.

\( M \models \varphi \: \: \: \Longrightarrow{} \: \: \: L\vdash \varphi  \)

En el caso de las teorías específicas, supongamos que tomo ZF como modelo de PA. A partir de la deducción en ZF puedo construir una deducción en PA...

Saludos!


06 Octubre, 2011, 06:28 pm
Respuesta #64

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
En \( RCA_0 \) es posible reproducir gran parte de la lógica matemática básica. En particular es posible probar el siguiente teorema, que es una versión débil del teorema de Henkin:

Sea \( X \subseteq Sent \) consistente y cerrado bajo consecuencia lógica. Entonces existe un modelo numerable M tal que \( M \models \sigma \) para toda \( \sigma \in X \).

Lo interesante es notar que no podemos prescindir del hecho de ser cerrado bajo consecuencia lógica, ya que tomando una teoría aritmética básica como Q, tenemos que toda teoría cerrada bajo consecuencia lógica que extiende a Q es no recursiva, luego en el \( \omega \)-modelo REC de \( RCA_0 \) vale "Q es consistente pero no tiene ningún modelo". Y por lo dicho antes, lo mismo debería valer en matemáticas constructivistas.

Por favor, Óscar, aclárame esto. Q usa la lógica de primer orden, que es completa respecto de la consecuencia lógica. Por tanto, el conjunto de los teoremas de Q es cerrado respecto de la consecuencia lógica, y como es consistente, tiene un modelo según la versión débil del teorema de Henkin que es demostrable en RCA0. Pero dices que en el modelo REC de RCA0 vale que Q es consistente pero no tiene ningún modelo.

Por ora parte, parece claro que el teorema débil implica que todo conjunto consistente (cerrado o no bajo consecuencia lógica) tiene un modelo, ya que bastaría extender el conjunto no cerrado a otro cerrado, y el modelo de este último sería modelo del primero.

Gracias.

06 Octubre, 2011, 09:29 pm
Respuesta #65

Óscar Matzerath

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

Cuando antes he dicho Q me refería a un conjunto recursivo de axiomas para Q. En particular, como Q es finitamente axiomatizable podemos tomar un conjunto finito de axiomas, que es recursivo. Este conjunto obviamente no es cerrado bajo consecuencia lógica.

Por ora parte, parece claro que el teorema débil implica que todo conjunto consistente (cerrado o no bajo consecuencia lógica) tiene un modelo, ya que bastaría extender el conjunto no cerrado a otro cerrado, y el modelo de este último sería modelo del primero.

Aquí está la cuestión, que no es cierto que en \( RCA_0 \) todo conjunto (no cerrado bajo consecuencia lógica en general) se puede extender a un conjunto cerrado bajo consecuencia lógica. Por ejemplo, el conjunto finito de axiomas para Q del que hablaba antes es recursivo, sin embargo ningún conjunto consistente de sentencias cerrado bajo consecuencia lógica que contenga a los axiomas de Q es recursivo (aunque puede ser recursivamente enumerable) y por tanto no "existe" en el modelo REC (porque en ese modelo los únicos subconjuntos de naturales que "existen" son precisamente los recursivos).
En cambio, se puede ver que si A es un conjunto consistente de sentencias cerrado bajo consecuencia lógica existe un conjunto B que extiende a A, B es completo y además B es recursivo relativo a A (en particular si A era recursivo, B también lo será).

Otra cosa, quizás la más interesante que se saca de este análisis al estilo "reverse mathematics", es que el teorema de Henkin sin la restricción de ser cerrado bajo consecuencia lógica es equivalente al lema de König débil, y esta equivalencia es demostrable en \( RCA_0 \). Además, el lema de König débil no es demostrable en \( RCA_0 \), por tanto en \( RCA_0 \) no vale el teorema de Henkin sin restricciones (aunque como he dicho antes esto también se sigue del hecho de que REC es un modelo de \( RCA_0 \)). El lema de König débil dice que todo árbol \( T \subseteq 2^{< \omega} \) infinito tiene una rama infinita. La demostración de este lema no es constructiva. Bajo la interpretación que mencioné antes de \( RCA_0 \) como las matemáticas constructivas, esto se puede ver como que el lema débil de König es exactamente el resultado no constructivo que tienes que asumir para probar el teorema de Henkin sin restricciones.

Saludos

06 Octubre, 2011, 10:27 pm
Respuesta #66

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Hola

Mi pregunta es si trabajando en un modelo cualquiera toda afirmación ( en un modelo concreto, no en la teoría  en general vista sintácticamente) ha de ser verdadera o falsa en un modelo, aunque desde luego, determinadas fórmulas (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

06 Octubre, 2011, 10:46 pm
Respuesta #67

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
¿Podrías mencionar algún teorema de completitud que incluya PA y ZF? El que mencionábamos días atrás como de Henkin, en realidad es el lema de Lindenbaum, y se refiere a una extensión que incluye como axiomas todas las sentencias no refutables, de modo que no es PA ni ZF, y ni siquiera son extensionalmente equivalentes, porque mientras PA no tiene como teorema las sentencias indecidibles, su extensión por Lindenbaum sí las tiene.

No. El teorema de completitud de Gödel (que a veces se llama de Henkin, porque la demostración más habitual es suya) afirma que si \( A \) es un conjunto de axiomas en un lenguaje de primer orden y \( \phi \) es una fórmula tal que \( A\vDash \phi \), es decir, tal que es verdadera en todo modelo de \( A \), entonces \( A\vdash \phi \). He corregido la errata que me señaláis.

Esto vale para cualquier sistema axiomático, incluido PA o ZFC. No hace falta exigir que sea completo. De hecho, lo primero que se hace en la prueba de Henkin es demostrar que todo sistema consistente de axiomas puede extenderse a un sistema consistente y completo (y además ejemplificado, en el sentido de que, extendiendo el lenguaje con infinitas constantes, siempre que la extensión contiene una fórmula de tipo \( \exists x\alpha(x) \) (aquí había otra errata de LaTeX) contiene también a \( \alpha(c) \) para cierta constante \( c \).

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.
¿Inmediato? Ese es el paso que cuesta tanto que la mayoría de las memorias de la demostración original omite. Implica el armado de un árbol de sentencias manteniendo la equivalencia, el método para la construcción de la rama infinita del lema de König que tú mencionabas ("In the proof, Gödel explicitly constructs the branch given by König's Lemma rather than citing it by name", www.plato.stanford.edu/entries/goedel/#ProComThe).
No sé si Gödel era constructivista, pero se acercó cuanto pudo al constructivismo, puesto que construyó explícitamente la sentencia indecidible de PA, no solamente demostró su existencia.

A ver. Me he dado cuenta de que hay una pequeña metedura de pata en lo que dije, pero no tanto como indicas. No sé si habrá algún malentendido, pero cuando dices que toda fórmula lógicamente válida es demostrable quieres decir toda fórmula que es verdadera en todo modelo de su lenguaje formal. Si es así, la demostración inmediata en la que yo pensaba demuestra únicamente una versión débil del teorema de completitud, para el caso en que el conjunto \( A \) es finito.

En efecto, si suponemos que toda fórmula lógicamente válida es demostrable y \( \alpha_1,\ldots, \alpha_n\vDash \phi \), entonces \( \alpha_1\land \cdots \land \alpha_n\Rightarrow \phi \) es lógicamente válida, luego \( \vdash\alpha_1\land \cdots \land \alpha_n\Rightarrow \phi \), luego \( \alpha_1,\ldots, \alpha_n\vdash \phi \). (Más erratas)

En esto estaba pensando, pero no veo que de aquí se deduzca el caso para conjuntos infinitos de axiomas.

06 Octubre, 2011, 10:49 pm
Respuesta #68

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 toda afirmación ( en un modelo concreto, no en la teoría  en general vista sintácticamente) ha de ser verdadera o falsa en un modelo, aunque desde luego, determinadas fórmulas (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, o sigo sin entenderte o no me entiendes tú a mí, porque lo que entiendo que preguntas es lo que ya te respondí algo más arriba:

Porque si pasamos al plano semántico, y eso nos lleva a tu pregunta, la respuesta es simple: toda sentencia es verdadera o falsa en un modelo, simplemente porque "falsa" significa, por definición, no verdadera. Más aún, si \( \phi \) es una sentencia, o bien \( \phi \) es verdadera o bien \( \lnot \phi \) es verdadera (en un modelo prefijado \( M \)), porque, por definición, \( M\vdash \lnot \phi \) significa que no se cumple \( M\vDash \phi \), es decir, \( \lnot \phi \) es verdadera por definición si y sólo si \( \phi \) es falsa.

Naturalmente, todo esto vale para la lógica clásica, con semántica clásica y todo clásico.

06 Octubre, 2011, 10:52 pm
Respuesta #69

Óscar Matzerath

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

Sí, en todo modelo una sentencia es o bien verdadera o bien falsa. Pero como creo que estás interesado en modelos de teoría de conjuntos, hay un detalle sutil sobre esto que hay que tener en cuenta. Es un teorema de ZFC (aunque lo que voy a decir aplica a cualquier teoría de conjuntos donde puedas formalizar la lógica) que para todo modelo M \( M \models \sigma \) o \( M \models \neg\sigma \). Pero hay que ir con mucho cuidado, porque si bien \( ZFC \vdash M \models \sigma \vee M \models \neg\sigma \), es muy posible que suceda que \( ZFC \not\vdash M \models \sigma \) y \( ZFC \not\vdash M \models \neg \sigma \). Es decir, en todo modelo de ZFC una sentencia es o bien verdadera o bien falsa, pero es posible que ZFC no demuestre ninguna de las dos posibilidades.

Saludos