Autor Tema: Modelos finitos y demás cosas confusas.

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

27 Noviembre, 2012, 08:19 am
Leído 2070 veces

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Buenas, buenas!
Tengo problemas para manejar interpretar y hacerme entender a mí mismo, el concepto de interpretación, tanto como para hacérseme demasiado complicado el desarrollo de los siguientes ejercicios, pos, son varios, pero supongo que con el consejo de algunos podré intentar solucionar los otros.

1. (a) Para cualquier wf \( \mathcal A \), demuestre que existe sólo un número finito de interpretaciones de \( \mathcal A \) en un dominio dado de cardinalidad finita \( k \). (creo haber hecho este bien, por inducción)
   (b) Para cualquier wf \( \mathcal A \), pruebe que existe un método efectivo para determinar si \( \mathcal A \) es verdadera para todas las interpretaciones con dominio de cadinalidad finita fija \( k \). (de este leí la respuesta, pero parecía probarlo para cierta interpretación de cardinalidad finita \( k \) y no para todos)
   (c) Una wf \( \mathcal A \) se le llama k-válida si es cierta para toda interpretación que tiene dominio de k elementos. Llamamos a \( \mathcal A \) precisamente k-válida si no es (k+1)-válida. Muestre que si \( \mathcal A \) es (k+1)-válida entonces \( \mathcal A \) es k-válida y dé un ejemplo de una wf que sea precisamente k-válida. (¿ein?)

Tengo problemas con esto, porque me entero que no es sólo falta de ideas para realizar el ejercicio, es también la sensación a no saber qué buscar, cuestión que se me reafirma con los dos siguientes ejercicios. Ambos, son ejercicios que están en el Mendelson y la definición de interpretación que allí dan se me hace un tanto confusa, y pues no se me ocurre demasiado qué hacer con ella ni para comprobar los ejercicios...

Me disculpo porque sean tantos ejercicios, pero son los que se me acumularon en un mismo tema, todos de seguido, entonces quedé un poco enfermo mirándolos uno a uno sin poder hacerles nada.

2. Muestre que la siguiente wf es verdadera para todo dominio finito y falso para algún domino infinito. (Y con este confirmé que no entendía mucho):
\( ((\forall x)(\forall y)(\forall z) [A_1^2(x,x)\wedge (A_1^2(x,y)\wedge A_1^2(y,z)\Rightarrow A_1^2(x,z))\wedge (A_1^2(x,y) \vee A_1^2(y,x))])\Rightarrow (\exists y)(\forall x)A_1^2(y,x) \)

3. Demuestre que no existe una teoría \( K \) cuyo modelos sea exactamente una interpretación con domino finito. (Este particularmente parece importante  ???)


Ya en este punto se ha desarrollado, el teorema de completitud de Gödel, varios teoremas sobre la cardinalidad de los modelos, el teorema fundamental del cálculo de predicados -qué nombre-. Aclaro que tanto las demostraciones como los teoremas mismos considero que los entiendo -tal vez no los interprete todavía de la manera más adecuada-. Cosa que debe sonar bastante contradictoria a que diga anteriormente que no lograba sacar información suficiente de la definición de interpretación que tenía, porque no la entendía. Al principio tampoco entendía en absoluto el concepto de satisfacción, sin embargo me era posible demostrar algunas consecuencias de la definición; esto obviamente es perder enfoque, pero supongo que en parte, por esto mismo, pregunto.

¡Muchas gracias por respuestas y sugerencias!  ::)
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

27 Noviembre, 2012, 03:06 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
1. (a) Para cualquier wf \( \mathcal A \), demuestre que existe sólo un número finito de interpretaciones de \( \mathcal A \) en un dominio dado de cardinalidad finita \( k \). (creo haber hecho este bien, por inducción)

No creo que haga falta ninguna inducción. La idea es que una fórmula tiene un número finito de signos lógicos, y sobre un conjunto finito sólo se puede definir un número finito de relaciones y funciones, por lo que sólo hay un número finito de formas de asignar un elemento del universo, una relación o una función a cada uno de los signos que aparecen en la fórmula.

   (b) Para cualquier wf \( \mathcal A \), pruebe que existe un método efectivo para determinar si \( \mathcal A \) es verdadera para todas las interpretaciones con dominio de cadinalidad finita fija \( k \). (de este leí la respuesta, pero parecía probarlo para cierta interpretación de cardinalidad finita \( k \) y no para todos)

Bueno, una forma a lo bruto es considerarlas todas una a una, puesto que sólo hay una cantidad finita. Supongo que se podrán encontrar algoritmos más finos, pero si la cuestión es si es posible, está claro.

   (c) Una wf \( \mathcal A \) se le llama k-válida si es cierta para toda interpretación que tiene dominio de k elementos. Llamamos a \( \mathcal A \) precisamente k-válida si no es (k+1)-válida. Muestre que si \( \mathcal A \) es (k+1)-válida entonces \( \mathcal A \) es k-válida y dé un ejemplo de una wf que sea precisamente k-válida. (¿ein?)

Éste tengo que pensarlo. Entiendo que consideras lenguajes sin igualador, pues si no la primera parte sería falsa y la segunda inmediata.

2. Muestre que la siguiente wf es verdadera para todo dominio finito y falso para algún domino infinito. (Y con este confirmé que no entendía mucho):
\( ((\forall x)(\forall y)(\forall z) [A_1^2(x,x)\wedge (A_1^2(x,y)\wedge A_1^2(y,z)\Rightarrow A_1^2(x,z))\wedge (A_1^2(x,y) \vee A_1^2(y,x))])\Rightarrow (\exists y)(\forall x)A_1^2(y,x) \)

Lo que dice esa fórmula es que si una relación es reflexiva, transitiva y conexa, entonces tiene un mínimo elemento. Eso es cierto en todo dominio finito, pero falso, por ejemplo, sobre el conjunto de los números naturales con la relación inversa de la usual.


3. Demuestre que no existe una teoría \( K \) cuyo modelos sea exactamente una interpretación con domino finito. (Este particularmente parece importante  ???)

¿Es correcta mi conjetura de que tus lenguajes formales no tienen igualador? Lo digo porque con igualador es relativamente simple, si no, tendría que pensarlo, pero prefiero no darle vueltas si resulta que al final sí que podemos usar el igualador.


Al principio tampoco entendía en absoluto el concepto de satisfacción, sin embargo me era posible demostrar algunas consecuencias de la definición; esto obviamente es perder enfoque, pero supongo que en parte, por esto mismo, pregunto.

No sé exactamente qué diferencia estableces entre interpretación y satisfacción. Sea como sea, las ideas de fondo son completamente naturales: se trata de asignar un objeto a cada constante, una relación a cada signo de relación y una función a cada signo de función, lo que a su vez te permite asociar un significada a cada fórmula del lenguaje en cuestión, de modo que cada fórmula significa lo que cualquiera que la lea entendería que significa sabiendo el significado que hay que dar a los signos básicos (constantes, relatores, etc.).

28 Noviembre, 2012, 06:07 pm
Respuesta #2

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
Antes de responder a la respuesta dada (¡Gracias!) hago un par de anotaciones:

La definición de interpretación dada por el Mendelson (aún me parece un suicidio cambiar al Enderton) es:

Una interpretación \( M \) consiste en un conjunto no vacío \( D \), llamado dominio de interpretación y una asignación para cada relator \( A_j^n \) de una relación de n-espacio \( (A_j^n)^M \) en \( D \) para cada funtor \( f_j^n \) una operación de n-espacios \( (f_j^n)^M \) en \( D \), y a cada constante individual \( a_i \) algún elemento fijo \( (a_i)^M \) de \( D \).

La cosa que yo escribí para dar una definición que consideré con el mismo significado, pero se me hizo "más en español", es la siguiente:

Una interpretación \( M \) lo es si cumple con las siguientes propiedades:
1. Tiene (?) un conjunto no vacío \( D \), llamado conjunto de interpretación.
2. Denotando a \( \mathfrak{A}^n \) al conjunto de todos los relatores de la forma \( A_j^n \). Entonces, existe una (única) función:
\( f:\mathfrak{A}^n\rightarrow P(D^n) \)
en \( M \).
3. Si \( \mathfrak{F}^n \) es el conjunto de todos los funtores de la forma \( f_j^n \). Entonces existe una (única) función  :
\( g:\mathfrak{F}^n\rightarrow \mathfrak{D}^n \)
en \( M \), donde \( \mathfrak{D}^n \) es el conjunto de todas las funciones \( t:D^n\rightarrow D \). .
4. Si \( \mathfrak{A}^n \) es el conjunto de todas las constantes existe una (única) función:
\( h:\mathfrak{A}^n\rightarrow D \)

en \( M \).

Y bien..., esta fue la definición que "arreglé" a partir de la definición del Mendelson de tal manera que se me hiciera más "digerible" o clara, si cabe. Pero obviamente, intenté decir lo mismo. Eeeem..., la palabra única aparece en rojo porque no sé si eso sea correcto decirlo, o sea que la función que asigna, debe ser sólo una.

Para definir satisfacción, también modificando, éste menos que la definición de interpretación, hice lo siguiente (sigo usando la misma notación dada arriba):

Sea \( \Sigma \) el conjunto de todas las sucesiones del dominio \( D \) de la interpretación (¿No es lo mismo que decir \( D^\mathbb N \)?). Sea, además, \( \mathfrak{T} \) el conjunto de todos los términos. Definimos la función \( s* \) de una sucesión \( s=(s_1,s_2,...) \) de \( \Sigma \), como la función
\( s*:\mathfrak T \rightarrow D \)
que tiene como regla:
\( s*(t)=\begin{Bmatrix} s_j & \mbox{ si }&\textsf{ t es }x_j\\h(a_j) & \mbox{si}&\textsf{ t es }a_i\\g(f_j^n)(s*(t_1),..., s*(t_n))& \mbox{ si }&\textsf{ t es }f_i^n(t_1,...,t_n)\end{matrix} \)

Y a partir de esto, se da la definición de satisfacción:

Se dice que \( s=(s_1, s_2,...) \) satisface \( \mathcal A \) si se puede mostrar que lo hace de las siguientes reglas:
1. \( \mathcal A \) es una fórmula atómica de forma \( A_j^n(t_1,...,t_n) \) y \( f(A_k^n) \) es el elemento que le corresponde de \( P(D^n) \) en la intepretación. La secuencia \( s \) satisface \( \mathcal A \) si y sólo si la n-upla \( <s*(t_1), s*(t_2),..., s*(t_n)> \) está en \( f(A_k^n) \).
2. \( \mathcal A \) es \( \neg\mathcal B \). \( s \) satiface \( \mathcal A \) si y sólo si \( s \) no satisface \( \mathcal B \).
3. \( \mathcal A \) es \( \mathcal B\rightarrow \mathcal C \). \( s \) satisface \( \mathcal A \) si y sólo si \( s \) no satisface \( \mathcal B \) o satisface \( \mathcal C \).
4. \( \mathcal A \) es \( \forall x_i \mathcal B \). \( s \) satisface \( \mathcal A \) si y sólo si toda secuencia que difiere de \( s \) en a los más la \( i \)-ésima posición satisface \( \mathcal B \)

Esta es la definición de satisfacción. Que sólo le cambie algo del modo en que lo decía el Mendelson en el primer numeral. El resto son exactamente los mismo (excepto que en español). Pos, tal vez esto se vea como algo demasiado innecesario, pero considero que me ha aclarado algunas cuestiones que con el modo en que las mostraba el Mendelson, sólo lograban confundirme.

Ahora sí, con respecto a lo que me respondió usted, Carlos Ivorra  :P:

   (b) Para cualquier wf \( \mathcal A \), pruebe que existe un método efectivo para determinar si \( \mathcal A \) es verdadera para todas las interpretaciones con dominio de cadinalidad finita fija \( k \). (de este leí la respuesta, pero parecía probarlo para cierta interpretación de cardinalidad finita \( k \) y no para todos)

Bueno, una forma a lo bruto es considerarlas todas una a una, puesto que sólo hay una cantidad finita. Supongo que se podrán encontrar algoritmos más finos, pero si la cuestión es si es posible, está claro.
¡Ooooooooooooooooooooooooooooooooooooooooh! Habiendo hecho lo anterior (esa traducción medianamente 'inútil) creo que he entendido esto. La 'forma' del conjunto está dado por la interpretación, pos las propiedades. Por eso los elementos del conjunto no son importantes siempre que tenga éste k elementos.

   (c) Una wf \( \mathcal A \) se le llama k-válida si es cierta para toda interpretación que tiene dominio de k elementos. Llamamos a \( \mathcal A \) precisamente k-válida si no es (k+1)-válida. Muestre que si \( \mathcal A \) es (k+1)-válida entonces \( \mathcal A \) es k-válida y dé un ejemplo de una wf que sea precisamente k-válida. (¿ein?)

Éste tengo que pensarlo. Entiendo que consideras lenguajes sin igualador, pues si no la primera parte sería falsa y la segunda inmediata.


En este momento todavía no he comenzado el capítulo con igualador, da la casualidad de que es el capítulo inmediatamente debajo de estos ejercicios. (Teorías con igualdad se llama el subcapítulo)

2. Muestre que la siguiente wf es verdadera para todo dominio finito y falso para algún domino infinito. (Y con este confirmé que no entendía mucho):
\( ((\forall x)(\forall y)(\forall z) [A_1^2(x,x)\wedge (A_1^2(x,y)\wedge A_1^2(y,z)\Rightarrow A_1^2(x,z))\wedge (A_1^2(x,y) \vee A_1^2(y,x))])\Rightarrow (\exists y)(\forall x)A_1^2(y,x) \)

Lo que dice esa fórmula es que si una relación es reflexiva, transitiva y conexa, entonces tiene un mínimo elemento. Eso es cierto en todo dominio finito, pero falso, por ejemplo, sobre el conjunto de los números naturales con la relación inversa de la usual.

Con esto que dijiste, ya puedo pensarlo, bueno, aunque ya diste un contraejemplo pero queda probarlo para todo finito. Aún me cuesta un poco interpretar que esos relatores están siendo si bien no definidos sí identificados con propiedades en ese tipo de wf. ¿Cuál es la relación inversa de la usual? ¿Cuál es la relación usual?

3. Demuestre que no existe una teoría \( K \) cuyo modelos sea exactamente una interpretación con domino finito. (Este particularmente parece importante  ???)

¿Es correcta mi conjetura de que tus lenguajes formales no tienen igualador? Lo digo porque con igualador es relativamente simple, si no, tendría que pensarlo, pero prefiero no darle vueltas si resulta que al final sí que podemos usar el igualador.
¡Es correcta!  ::)

Al principio tampoco entendía en absoluto el concepto de satisfacción, sin embargo me era posible demostrar algunas consecuencias de la definición; esto obviamente es perder enfoque, pero supongo que en parte, por esto mismo, pregunto.

No sé exactamente qué diferencia estableces entre interpretación y satisfacción. Sea como sea, las ideas de fondo son completamente naturales: se trata de asignar un objeto a cada constante, una relación a cada signo de relación y una función a cada signo de función, lo que a su vez te permite asociar un significada a cada fórmula del lenguaje en cuestión, de modo que cada fórmula significa lo que cualquiera que la lea entendería que significa sabiendo el significado que hay que dar a los signos básicos (constantes, relatores, etc.).

A saber en qué diferencio podría ayudar lo primero que publiqué.  :P

¡Gracias por las respuestas, la paciencia!
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.

28 Noviembre, 2012, 10:36 pm
Respuesta #3

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Y bien..., esta fue la definición que "arreglé" a partir de la definición del Mendelson de tal manera que se me hiciera más "digerible" o clara, si cabe. Pero obviamente, intenté decir lo mismo. Eeeem..., la palabra única aparece en rojo porque no sé si eso sea correcto decirlo, o sea que la función que asigna, debe ser sólo una.

Estás llamando interpretación a lo que más habitualmente se llama un modelo. Más que "existe una única función", lo que sucede es que el modelo (o interpretación) es un par \( (D,F) \), donde \( D \) es el dominio y \( F \) es una función que a cada relator y cada funtor le asigna la relación o función correspondiente.

¿Cuando defines "grupo" dirías que es un conjunto \( G \) tal que existe una única operación que cumple..." o más bien que es un par \( (G,*) \) donde..."?

En cuanto a la definición de satisfacción, la notación \( M\vDash \mathcal A[s] \) es bastante más habitual.

   (b) Para cualquier wf \( \mathcal A \), pruebe que existe un método efectivo para determinar si \( \mathcal A \) es verdadera para todas las interpretaciones con dominio de cadinalidad finita fija \( k \). (de este leí la respuesta, pero parecía probarlo para cierta interpretación de cardinalidad finita \( k \) y no para todos)

Bueno, una forma a lo bruto es considerarlas todas una a una, puesto que sólo hay una cantidad finita. Supongo que se podrán encontrar algoritmos más finos, pero si la cuestión es si es posible, está claro.
¡Ooooooooooooooooooooooooooooooooooooooooh! Habiendo hecho lo anterior (esa traducción medianamente 'inútil) creo que he entendido esto. La 'forma' del conjunto está dado por la interpretación, pos las propiedades. Por eso los elementos del conjunto no son importantes siempre que tenga éste k elementos.

Esto sería más natural si te hubieran hablado antes de isomorfismos de modelos, pero bueno. Luego dicen que la lógica es rara.

   (c) Una wf \( \mathcal A \) se le llama k-válida si es cierta para toda interpretación que tiene dominio de k elementos. Llamamos a \( \mathcal A \) precisamente k-válida si no es (k+1)-válida. Muestre que si \( \mathcal A \) es (k+1)-válida entonces \( \mathcal A \) es k-válida y dé un ejemplo de una wf que sea precisamente k-válida. (¿ein?)

Para la primera parte, se me ocurre lo siguiente:

Sea \( \mathcal A \) una fórmula k+1-válida y tomemos un modelo M con k elementos, \( a_1,\ldots, a_k \). Define como sigue un modelo \( M^* \) con k+1 elementos añadiendo un nuevo elemento \( a_{k+1} \) y extendiendo como sigue las relaciones y funciones del modelo dado: si \( R \) es una relación \( n \)-ádica asociada a un relator n-ádico del lenguaje, definimos \( R^*(x_1,\ldots, x_n) \), para \( x_1,\ldots, x_n \) en el universo de \( M^* \) si y sólo si se cumple la relación \( R \) cuando cambiamos cualquier \( x_i \) que sea \( a_{k+1} \) por \( a_k \).

Igualmente, si \( f \) es una función asociada a un funtor \( n \)-ádico, definimos \( f^*(x_1,\ldots, x_n) \) como la función \( f \) actuando sobre la \( n \)-tupla que resulta de sustituir cualquier \( x_i \) que sea \( a_{k+1} \) por \( a_k \).

De este modo, en el modelo \( M^* \) los objetos \( a_k \) y \( a_{k+1} \) son indistinguibles, tienen exactamente las mismas propiedades.

No he hecho las comprobaciones, pero diría que una inducción sobre la longitud de \( \mathcal A \) debería probar que, para toda \( s \) que tome valores en M, se cumple \( M\vDash \mathcal A[s] \) si y sólo si \( M^*\vDash \mathcal A[s] \). Por lo tanto, para la fórmula dada como \( M^*\vDash \mathcal A[s] \), también se cumple \( M\vDash \mathcal A[s] \), para todo modelo M.

Con esto que dijiste, ya puedo pensarlo, bueno, aunque ya diste un contraejemplo pero queda probarlo para todo finito. Aún me cuesta un poco interpretar que esos relatores están siendo si bien no definidos sí identificados con propiedades en ese tipo de wf. ¿Cuál es la relación inversa de la usual? ¿Cuál es la relación usual?

Hombre, la relación de orden usual en los números naturales es la que te enseñaron de pequeñito: primero el 0, luego el 1, luego el 2, etc. Y la inversa es la que tiene al 0 como máximo, y antes el 1, y antes el 2...

Que los conjuntos finitos cumplen esa propiedad no es un problema de lógica, sino de teoría de conjuntos: si tienes una relación reflexiva y transitiva y conexa en un conjunto finito, tiene que tener un mínimo elemento, pues si no lo tuviera, tomamos un \( a_0 \) en el conjunto, como no es mínimo, hay un \( a_1<a_0 \), como \( a_1 \) no es mínimo, hay un \( a_2<a_1 \), y así vemos que el conjunto tiene que ser infinito. (Nota: \( a<b \) significa \( a\leq b\land \lnot b\leq a \), que sin la propiedad antisimétrica (que no se puede enunciar sin igualador) no es lo mismo que \( a\leq b\land a\neq b \).)

3. Demuestre que no existe una teoría \( K \) cuyo modelos sea exactamente una interpretación con domino finito. (Este particularmente parece importante  ???)

Hombre, importante... trabajar sin igualador en estos contextos es una vez más trabajar con las manos atadas por capricho del profesor/autor del libro de turno. Dudo mucho que sea importante ningún resultado sobre teorías sin igualador cuando todas las teorías interesantes tienen igualador y lo natural es que lo tengan.

Creo que se podría demostrar con la misma técnica de antes: si la teoría es verdadera en todos los modelos finitos, en particular es verdadera en un modelo con un único elemento \( a \). A partir de este modelo, construye otro nuevo con dominio infinito en el que todos los elementos sean indistinguibles de \( a \). Los axiomas de la teoría serán también verdaderos en este modelo.

01 Diciembre, 2012, 02:47 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Un ejemplo de fórmula precisamente k-válida es ésta:

\( \exists x_1\cdots x_k(\exists x\,Rx\rightarrow (Rx_1\lor \cdots \lor Rx_k)) \).

07 Diciembre, 2012, 06:09 pm
Respuesta #5

yotas

  • Sé valiente, no voluble, no maleable.
  • $$\Large \color{#c88359}\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 725
  • Karma: +0/-0
  • Sexo: Masculino
  • Plop, plop.
¡Gracias por las respuestas, perdón por demorarme tanto en contestar!  ;D
Esto todavía no lo comprendo como quisiera. Por el momento iré a sufrir con el libro del A. G. Hamilton a ver qué pasa, pues ya salgo a vacaciones y ojalá el tiempo me sobre. Lo hago con la intención de que las dudas provocadas por Mendelson se puedan aclarar aunque sea un poco con ese libro. Pero es para estudiar el mismo tema.
Es que las demostraciones que se mostraron aquí las entiendo, pero no me siento en la capacidad de emularlas o peor que se me ocurra algo semejante.
 :)
Citar
Creo debes tener un problema en tu mente por el cual complicas las cosas y las afirmaciones más sencillas.

Sí, es un problema muy frecuente en este foro. Se llama saber matemáticas.