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

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

18 Abril, 2011, 07:23 pm
Leído 37402 veces

Raúl Aparicio Bustillo

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 3,113
  • Karma: +0/-3
  • Sexo: Masculino
Una teoría que no es consistente ( es decir, hay alguna contradicción en ella, se puede demostrar una cosa y su contraria), no puede tener un modelo, pues en el modelo de una sentencia cualquiera a, o bien a, o bien no a , han de ser verdaderas. Pero, ¿puede haber una teoría consistente sin modelos?

Por otra parte, cuando se trabaja sintácticamente no se puede hablar de verdad o falsedad, sino de consistencia o no consistencia de unos axiomas dados, cada simbolo del sistema no tenemos porque presuponerle un significado, ahora bien, el significado  de las conectivas lógicas si que deber darse, es decir, ┌ singifica no, = significa ),\longrightarrow{}significa implica,etc .... ¿es así?

Por otra parte, en la axiomatica de Peano, el unico relator es la igualdad, y queda claro cuando una formula atómica es verdadera. Lo es cuando lo que aparece a cada lado del signo igual es igual, valga la redundancia,y la verdad del resto de formulas se hace interpretando las conectivas combinadas con las formulas elementales. No obstante, en teoría de conjuntos, por ejemplo, hay otro tipo de formulas atómicas ,a \in{b}, ¿qué definición de verdad se maneja en estos casos?

Saludos

18 Abril, 2011, 08:33 pm
Respuesta #1

Óscar Matzerath

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

Una teoría que no es consistente ( es decir, hay alguna contradicción en ella, se puede demostrar una cosa y su contraria), no puede tener un modelo, pues en el modelo de una sentencia cualquiera a, o bien a, o bien no a , han de ser verdaderas. Pero, ¿puede haber una teoría consistente sin modelos?

No, aunque no es nada trivial de probar. El resultado es que una teoría es consistente si y sólo si tiene un modelo. De hecho el resultado de que toda teoría consistente tiene un modelo es esencialmente lo mismo que el teorema de completitud para la lógica de primer orden: supongamos que toda teoría consistente tiene un modelo, y veamos que si \( \Gamma \models \varphi \) entonces \( \Gamma \vdash \varphi \) (para algún cálculo adecuado). Por reducción al absurdo, si \( \Gamma \models \varphi \) pero \( \Gamma \not\vdash \varphi \), entonces \( \Gamma \cup \{ \neg \varphi \} \) es consistente, luego tiene un modelo M. Pero entonces \( M \models \Gamma \) y \( M \models \neg \varphi \), luego \( M \not\models \varphi \). Contradicción con \( \Gamma \models \varphi \) (todo modelo de \( \Gamma \) es también modelo de \( \varphi \)).

Citar
Por otra parte, cuando se trabaja sintácticamente no se puede hablar de verdad o falsedad, sino de consistencia o no consistencia de unos axiomas dados, cada simbolo del sistema no tenemos porque presuponerle un significado, ahora bien, el significado  de las conectivas lógicas si que deber darse, es decir, ┌ singifica no, = significa ),\longrightarrow{}significa implica,etc .... ¿es así?

No, el símbolo de las conectivas lógicas tampoco se da a nivel sintáctico, se da cuando defines la semántica (aunque obviamente todo lo que se hace sintácticamente se hace pensando en el sentido que va a tener después, pero en principio ningún símbolo tiene significado si trabajas a nivel sintáctico).

Citar
Por otra parte, en la axiomatica de Peano, el unico relator es la igualdad, y queda claro cuando una formula atómica es verdadera. Lo es cuando lo que aparece a cada lado del signo igual es igual, valga la redundancia,y la verdad del resto de formulas se hace interpretando las conectivas combinadas con las formulas elementales. No obstante, en teoría de conjuntos, por ejemplo, hay otro tipo de formulas atómicas ,a \in{b}, ¿qué definición de verdad se maneja en estos casos?

Lo de la verdad en un modelo arbitrario de la aritmética de Peano no es tan sencillo. Lo que dices de la igualdad es verdad, pero los términos que aparecen a los lados de la igualdad pueden contener símbolos como el 0, la suma + o la multiplicación ·, y cuando das un modelo M tienes que dar (además del dominio de M, que se suele designar igualmente por M si no hay confusión) una interpretación de cada uno de esos símbolos (es decir, un elemento \( 0^M \) del dominio de M al que designará el 0, y funciones \( +^M:M \times M \longrightarrow M \) y \( \cdot^M:M \times M \longrightarrow M \)), para poder interpretar los términos en que aparezcan el 0, el símbolo de suma y el símbolo de multiplicación.

En teoría de conjuntos es muy parecido, sólo que aquí no tienes constantes ni símbolos de función (como +, ·). En cambio, tienes un símbolo de relación binario, \( \in \). Así que dar un modelo de la teoría de conjuntos M, es dar un dominio M y una interpretación para el símbolo \( \in \), que es un subconjunto de MxM, \( \in^M \subset M \times M \). Entonces una fórmula del tipo \( x \in y \) es verdadera en el modelo M bajo una asignación de variables s (recuerda que \( s:Var \longrightarrow M \), donde Var es el conjunto de variables, y es necesaria además del modelo para la verdad de formulas con variables libres, ya que la asignación s te dice qué elemento de M va a designar la variable libre), si \( (s(x),s(y)) \in \in^M \), es decir si el par \( (s(x),s(y)) \) está relacionado por la relación \( \in^M \).

Saludos

19 Abril, 2011, 10:11 pm
Respuesta #2

LauLuna

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

El resultado de que todo conjunto consistente de fórmulas tiene un modelo vale para los lenguajes de PRIMER orden, no en general. Óscar se refiere a los lenguajes de primer orden.

Las conectivas proposicionales suelen tener un valor constante a través de las interpretaciones, un valor determinado por sus tablas de verdad. Es lo usual cada vez que interpretamos un lenguaje formal pero naturalmente son posibles tratamientos puramente sintácticos de los lenguajes formales en los que ni siquiera estas constantes lógicas se dan como interpretadas; por ejemplo, cuando demostramos algo sobre los teoremas de un sistema o las fórmulas de un lenguaje por inducción sobre el número de signos en una fórmula. Creo que a esto último es a lo que Óscar se refiere.

La verdad -bajo la interpretación estándar- de los enunciados aritméticos que no contienen cuantificadores es decidible. El problema empieza con los cuantificadores. Aún así es posible definir recursivamente la verdad aritmética pero, naturalmente, no en el lenguaje de la aritmética.

Un saludo.


21 Abril, 2011, 12:08 am
Respuesta #3

Óscar Matzerath

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

Totalmente de acuerdo con las puntualizaciones de LauLuna.

Sobre la primera, es una puntualización importante. Estoy tan acostumbrado a trabajar con la lógica clásica de primer orden por defecto que cuando digo "lógica" sin especificar me refiero a ella. En efecto, en general el resultado es falso, por ejemplo en lógica clásica de segundo orden con la semántica usual y un cálculo adecuado, existen teorías que son consistentes pero sin embargo no tienen modelos.

Saludos

27 Mayo, 2011, 11:04 pm
Respuesta #4

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
... supongamos que toda teoría consistente tiene un modelo, y veamos que si \( \Gamma \models \varphi \) entonces \( \Gamma \vdash \varphi \) (para algún cálculo adecuado). Por reducción al absurdo, si \( \Gamma \models \varphi \) pero \( \Gamma \not\vdash \varphi \), entonces \( \Gamma \cup \{ \neg \varphi \} \) es consistente, luego tiene un modelo M. Pero entonces \( M \models \Gamma \) y \( M \models \neg \varphi \), luego \( M \not\models \varphi \). Contradicción con \( \Gamma \models \varphi \) (todo modelo de \( \Gamma \) es también modelo de \( \varphi \)).
Disculpa Oscar, pero ¿no es una petición de principio suponer lo que hay que demostrar?
Además, me parece que lo que demuestras es que toda sentencia lógicamente válida (verdadera para todas las interpretaciones) es demostrable en orden 1, pero no que una teoría consistente no puede carecer de modelo.

Saludos!

27 Mayo, 2011, 11:48 pm
Respuesta #5

Óscar Matzerath

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

Disculpa Oscar, pero ¿no es una petición de principio suponer lo que hay que demostrar?
Además, me parece que lo que demuestras es que toda sentencia lógicamente válida (verdadera para todas las interpretaciones) es demostrable en orden 1, pero no que una teoría consistente no puede carecer de modelo.

Claro, es que lo que demuestro ahí es que el teorema de Henkin "Toda teoría consistente tiene un modelo" (en el contexto de la lógica de primer orden) implica de manera muy sencilla el teorema de completitud como tal, es decir "para cualquier conjunto de fórmulas \( \Gamma \) y cualquier fórmula \( \varphi \), si \( \Gamma \models \varphi \) entonces \( \Gamma \vsah \varphi \)".

Desde luego no pretendo demostrar que toda teoría consistente tiene un modelo. Eso es mucho más laborioso, aunque la idea no es demasiado complicada. Básicamente dada una teoría T consistente se toma una estructura M que tenga como dominio el conjunto de términos del lenguaje módulo la relación de equivalencia que identifica dos términos t, t' si \( T \vdash t=t' \), es decir, \( [t]=[t'] \iff T \vdash t=t'  \) , y se definen las interpretaciones de constantes y funciones de manera obvia por la acción en términos (\( c^M = [c], f^M([t_1],...,[t_n])=[ft_1...t_n] \)), y para relaciones, \( R^M ([t_1],...,[t_n]) \iff T \vdash Rt_1...t_n \). Para que esto funcione, previamente hay que extender T a una teoría T' consistente completa y que tenga testigos, esto es, para cada fórmula del tipo \( \exists x \varphi \) tal que \( T' \vdash \exists x \varphi \), hay un término t tal que \( T' \vdash \varphi \frac{t}{x} \). Se puede comprobar que partiendo de cualquier teoría T, la podemos extender a una teoría T' que cumpla esas condiciones, y que la estructura que hemos definido para T' está bien definida y es realmente un modelo de T'. Así pues, como T' extiende T, en particular hemos construido un modelo M de T.

Saludos

28 Mayo, 2011, 12:11 am
Respuesta #6

LauLuna

  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 546
  • País: es
  • Karma: +1/-0
  • Sexo: Masculino
Claro, es que lo que demuestro ahí es que el teorema de Henkin "Toda teoría consistente tiene un modelo" (en el contexto de la lógica de primer orden) implica de manera muy sencilla el teorema de completitud como tal, es decir "para cualquier conjunto de fórmulas \( \Gamma \) y cualquier fórmula \( \varphi \), si \( \Gamma \models \varphi \) entonces \( \Gamma \vsah \varphi \)".

Cuento como curiosidad que Martin Davis rechazó un mensaje mío al foro FOM porque yo atribuía a Henkin ese misno teorema que tú le atribuyes. Según Davis, el teorema de completitud de Gödel (1930) es una forma de ese teorema que enunciaría Henkin en 1949 y debe atribuírsele a Gödel.

Un saludo


28 Mayo, 2011, 12:24 am
Respuesta #7

Óscar Matzerath

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

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, aunque se le conoce por ese nombre y así aparece en varios libros prestigiosos de lógica matemática (sinceramente, me parece una tontería rechazar un artículo por algo así), sino la demostración del mismo que he esbozado, y que es el enfoque que se usa actualmente de manera casi universal para demostrar el teorema de completitud. La demostración original de Gödel de 1930 es bastante distinta a esta de Henkin, y no se suele explicar en clase (ni recuerdo haberla visto en ningún libro introductorio de lógica matemática).

Saludos

28 Mayo, 2011, 10:17 am
Respuesta #8

LauLuna

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

La demostración que encontró Henkin allá por 1949 es bastante más usada (por ser más fácil) que la original de Gödel; de ahí la tendencia a atribuir ese teorema de satisfacibilidad a Henkin.

Un saludo.

01 Junio, 2011, 06:06 pm
Respuesta #9

Elius

  • $$\Large \color{#5e8d56}\pi\,\pi\,\pi$$
  • Mensajes: 399
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
Cuento como curiosidad que Martin Davis rechazó un mensaje mío al foro FOM porque yo atribuía a Henkin ese misno teorema que tú le atribuyes. Según Davis, el teorema de completitud de Gödel (1930) es una forma de ese teorema que enunciaría Henkin en 1949 y debe atribuírsele a Gödel.
LauLuna, ¿cuál es la URL del foro FOM? Si es que la puedes dar...
Uno que parece bueno es http://mathoverflow.net (en inglés).

Saludos!