Autor Tema: Prueba del teorema de Löwenheim-Skolem descendente.

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

07 Enero, 2025, 07:12 am
Leído 649 veces

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Buenas a todos,

Tengo problemas entendiendo la prueba del siguiente enunciado:
(Lowenheim-Skolem descendente)(con \( \mathsf{AC} \))
Sea \( M \) un conjunto equipado con una relación binaria \( E\subseteq M^2 \). Para todo \( P\subseteq M \), existe \( Q\subseteq M \) tal que:
  • \( Q\subseteq P \) y \( |Q|\leq \max(|P|,\aleph_0) \)
  • Para toda fórmula \( f=f(\vec{{\tt{x}}}) \in Form \) con variables libres \( \vec{{\tt{x}}} \) se tiene que:
    \( (\forall a \in Q)[ (Q,E)\models f(\vec{a}) \Leftrightarrow (M,E) \models f(\vec{a})] \)

La prueba se encuentra en los siguientes apuntes, la prueba comienza en la página 14. La prueba comienza así:

Sea una función de elección \( h:\mathfrak{P}^*(M)\to M \).
Se define una sucesión \( (Q_k)_{k\in \omega} \) de subconjuntos de \( M \) a partir de \( Q_0 := P \). Y para todo \( k\in \omega \), se define \( Q_{k+1} \) como el subconjunto de todos los elementos de \( M \) de la forma
\( h(\{a\in M : (M,E) \models f(a,a_1,...,a_n) \}) \)
donde \( n\in \mathbb{N} \), \( f\in Form_{n+1} \) y \( a_1,...,a_n\in Q_k \) son tales que:
\( \{a\in M : (M,E) \models f(a,a_1,...,a_n) \}) \neq \emptyset \)

Lo que no termino de entender es la motivación para tomar los conjuntos \( Q_k \), ¿exactamente que son?
Tenemos que \( Q_0=P \), luego \( Q_1 \) son para cada fórmula con parámetros en \( P \) y una única variable libre elegimos un elemento que "la cumpla" (si es que lo hay) y ¿así sucesivamente?

Saludos,
Franco.

07 Enero, 2025, 10:51 am
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
La prueba del teorema se entiende mejor si se separa una parte del argumento en un resultado independiente que tiene interés en sí mismo. La propiedad 2 del enunciado se enuncia también diciendo que \( (Q; E) \) es una subestructura elemental de \( (M, E) \) y admite la caracterización siguiente:

Si \( Q\subset M \), entonces \( (Q, E) \) es una subestructura elemental de \( (M, E) \) si y sólo si para toda fórmula \( f(a, \vec a) \), se cumple que
\( \forall \vec a\in Q(\exists a\in M\, (M, E)\vDash f(a, \vec a)\rightarrow \exists a\in Q\,(M, E)\vDash f(a, \vec a)) \).

Lo interesante de esta caracterización es que, mientras la definición de subestructura elemental involucra \( (M, E)\vDash \) y \( (Q, E)\vDash \), en este enunciado sólo aparece \( (M, E)\vDash \).

La prueba de que esto implica que \( (Q, E) \) es una subestructura elemental está implícita en la demostración que te han dado. En la segunda diapositiva, cuando quieres probar que \( (Q, E) \) es una subestructura elemental por inducción sobre \( f \), todos los casos son triviales excepto cuando \( f(\vec x) = (\dot\exists x_0)\,f_0(x_0, \vec x) \),  y en ese caso una implicación también es trivial. La única implicación no trivial es también inmediata si suponemos que \( Q \) cumple la propiedad que acabo de enunciar.

Por lo tanto, para conseguir una subestructura elemental \( Q \), lo que hay que conseguir es que el conjunto \( Q \) tenga la propiedad de que, para toda fórmula \( f(a, \vec a) \) y todos los parámetros \( \vec a \) en \( Q \), si existe un \( a\in M \) que cumpla \( (M, E)\vDash f(a, \vec a) \), hay al menos un \( a \) que cumple eso y está en \( Q \).

Y la forma de conseguirlo es ésta:

Tenemos un candidato \( Q_0 \) a subestructura elemental, pero no tiene por qué serlo, ya que puede haber fórmulas \( f \) y parámetros \( \vec a\in Q_0 \) para los que exista un \( a\in M \) que cumpla \( (M, E)\vDash f(a, \vec a) \) y ninguno de dichos \( a \) esté en \( Q_0 \).

Entonces definimos \( Q_1 \) como el conjunto que resulta de añadirle a \( Q_0 \) un \( a \) que "arregle" el problema para cada fórmula \( f \) y cada conjunto de parámetros \( \vec a \) en \( Q_0 \).

Pero \( Q_1 \) no tiene por qué servir, ya que cumple la caracterización de subestructura elemental para cada fórmula y cada conjunto \( \vec a \) de parámetros en \( Q_0 \), pero necesitamos que se cumpla para cada conjunto de parámetros en \( Q_1 \).

Por eso repetimos el proceso y formamos un \( Q_2 \) que incluya un \( a\in M \) que sea necesario para que se cumpla la caracterización para cada fórmula y cada conjunto de parámetros en \( Q_1 \), pero otra vez tenemos el problema de que necesitamos que la caracterización se cumpla para parámetros en \( Q_2 \), lo que nos lleva a definir la sucesión \( \{Q_k\}_{k\in \omega} \). Aparentemente tenemos la batalla perdida, porque a cada nuevo paso nos aparecen más elementos que debemos considerar como parámetros posibles, pero el infinito juega a nuestro favor, ya que si consideramos la unión \( Q \) de todos los \( Q_k \), esa unión sí que cumple lo requerido, ya que cualquier conjunto de parámetros \( \vec a \) en \( Q \) está en un \( Q_k \), luego los "a" necesarios para cualquier fórmula con dichos parámetros ya están incluidos en \( Q_{k+1} \) y, por lo tanto en \( Q \).

Esa es la idea subyacente a la prueba. Los \( Q_k \) son intentos parciales de "cerrar" \( Q_0 \) ante posibles contraejemplos a la caracterización de las subestructuras elementales.

08 Enero, 2025, 04:01 am
Respuesta #2

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Hola Carlos :),

La prueba del teorema se entiende mejor si se separa una parte del argumento en un resultado independiente que tiene interés en sí mismo. La propiedad 2 del enunciado se enuncia también diciendo que \( (Q; E) \) es una subestructura elemental de \( (M, E) \) y admite la caracterización siguiente:

Si \( Q\subset M \), entonces \( (Q, E) \) es una subestructura elemental de \( (M, E) \) si y sólo si para toda fórmula \( f(a, \vec a) \), se cumple que
\( \forall \vec a\in Q(\exists a\in M\, (M, E)\vDash f(a, \vec a)\rightarrow \exists a\in Q\,(M, E)\vDash f(a, \vec a)) \).

Lo interesante de esta caracterización es que, mientras la definición de subestructura elemental involucra \( (M, E)\vDash \) y \( (Q, E)\vDash \), en este enunciado sólo aparece \( (M, E)\vDash \).

La prueba de que esto implica que \( (Q, E) \) es una subestructura elemental está implícita en la demostración que te han dado. En la segunda diapositiva, cuando quieres probar que \( (Q, E) \) es una subestructura elemental por inducción sobre \( f \), todos los casos son triviales excepto cuando \( f(\vec x) = (\dot\exists x_0)\,f_0(x_0, \vec x) \),  y en ese caso una implicación también es trivial. La única implicación no trivial es también inmediata si suponemos que \( Q \) cumple la propiedad que acabo de enunciar.

Entendido. La verdad que le tenía bastante "miedo" a este tipo de modelos usando fórmulas internas ya que me costaba entender el predicado \( (Q,E)\models \) pero trabajando en la prueba de esta demostración me di cuenta (tal vez tardé demasiado) en que es exactamente igual que como cuando uno define los modelos de Tarski y define cosas como:
\( \mathscr{M} \models \exists x\phi(x) \) sii \( \mathscr{M}\models \phi(a)  \) para algún \( a\in \mathscr{M} \)
Todas esas definiciones (o equivalencias) resultan ser idénticas en el caso de fórmulas internas, lo cual lo hace mucho más fácil de manejar.
Se que esto debe ser algo obvio :-[, pero tardé en darme cuenta y ahora creo que lo entiendo mucho más.

Y la forma de conseguirlo es ésta:

Tenemos un candidato \( Q_0 \) a subestructura elemental, pero no tiene por qué serlo, ya que puede haber fórmulas \( f \) y parámetros \( \vec a\in Q_0 \) para los que exista un \( a\in M \) que cumpla \( (M, E)\vDash f(a, \vec a) \) y ninguno de dichos \( a \) esté en \( Q_0 \).

Entonces definimos \( Q_1 \) como el conjunto que resulta de añadirle a \( Q_0 \) un \( a \) que "arregle" el problema para cada fórmula \( f \) y cada conjunto de parámetros \( \vec a \) en \( Q_0 \).

Pero \( Q_1 \) no tiene por qué servir, ya que cumple la caracterización de subestructura elemental para cada fórmula y cada conjunto \( \vec a \) de parámetros en \( Q_0 \), pero necesitamos que se cumpla para cada conjunto de parámetros en \( Q_1 \).

Por eso repetimos el proceso y formamos un \( Q_2 \) que incluya un \( a\in M \) que sea necesario para que se cumpla la caracterización para cada fórmula y cada conjunto de parámetros en \( Q_1 \), pero otra vez tenemos el problema de que necesitamos que la caracterización se cumpla para parámetros en \( Q_2 \), lo que nos lleva a definir la sucesión \( \{Q_k\}_{k\in \omega} \). Aparentemente tenemos la batalla perdida, porque a cada nuevo paso nos aparecen más elementos que debemos considerar como parámetros posibles, pero el infinito juega a nuestro favor, ya que si consideramos la unión \( Q \) de todos los \( Q_k \), esa unión sí que cumple lo requerido, ya que cualquier conjunto de parámetros \( \vec a \) en \( Q \) está en un \( Q_k \), luego los "a" necesarios para cualquier fórmula con dichos parámetros ya están incluidos en \( Q_{k+1} \) y, por lo tanto en \( Q \).

Esa es la idea subyacente a la prueba. Los \( Q_k \) son intentos parciales de "cerrar" \( Q_0 \) ante posibles contraejemplos a la caracterización de las subestructuras elementales.

Excelente. Con esto me queda mucho más clara la prueba.

Muchísimas gracias Carlos.

Saludos,
Franco.

08 Enero, 2025, 03:43 pm
Respuesta #3

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Por las dudas, lo que me refería con mi mensaje anterior es que si \( M \) es un conjunto y \( E\subseteq M^2 \) es una relación binaria entonces se tiene que:
\( \begin{align*}
    (M,E) \models a_1 \doteq a_2 &\Leftrightarrow a_1 = a_2 \\
    (M,E) \models a_1 \dot{\in} a_2 &\Leftrightarrow E(a_1,a_2) \\
    (M,E) \models \dot{\neg} f(\vec{a}) &\Leftrightarrow (M,E)\not\models f(\vec{a}) \\
    (M,E) \models f_1(\vec{a}) \dot{\lor} f_2(\vec{a}) &\Leftrightarrow ((M,E)\models f_1(\vec{a})) \lor ((M,E)\models f_2(\vec{a})) \\
    (M,E) \models f_1(\vec{a}) \dot\land f_2(\vec{a}) &\Leftrightarrow ((M,E)\models f_1(\vec{a})) \land ((M,E)\models f_2(\vec{a})) \\
    (M,E) \models f_1(\vec{a}) \dot\Rightarrow f_2(\vec{a}) &\Leftrightarrow ((M,E)\models f_1(\vec{a})) \Rightarrow ((M,E)\models f_2(\vec{a})) \\
    (M,E) \models (\dot\exists {\tt{x}}) f({\tt{x}}, \vec{a}) &\Leftrightarrow (\exists a\in M)\ (M,E)\models f(a,\vec{a}) \\
    (M,E) \models (\dot\forall {\tt{x}}) f({\tt{x}}, \vec{a}) &\Leftrightarrow (\forall a\in M)\ (M,E)\models f(a,\vec{a})
\end{align*} \)
Donde si \( f({\tt{x}}_1,...,{\tt{x}}_n)\in \text{Form} \) definimos
\( (M,E)\models f(a_1,...,a_n) :\equiv (\exists \rho\in M^{Var})(\rho({\tt{x}}_1)=a_1\land \cdots \land \rho({\tt{x}}_n)=a_n \land \rho \in \text{Val}_{(M,E)}(f)) \)

Se prueba muy fácilmente usando el resultado que dice que si dos valuaciones coinciden en las variables libres de una fórmula entonces una pertenece a \( \text{Val}_{(M,E)}(f) \) si y sólo si la otra pertenece.

Una vez "entendí" esto, ya me resulta mucho más fácil trabajar con estos modelos.



Por cierto, me surgió una duda más de la prueba de Lowenheim-Skolem: la utilidad de probar que \( Q_k \subseteq Q_{k+1} \) es solo para obtener la cota de \( |Q| \), ¿no?. Ya que para ver que \( Q \) es una subestructura elemental basta con usar el resultado que enunciaste tu. Porque me preguntaba si realmente precisamos probar que \( Q_k \subseteq Q_{k+1} \). Ya que tenemos que \( |Q_k| \leq \max(|P|,\aleph_0) \) por inducción, luego:
\( \displaystyle |Q| = \left |{\bigcup_{n\in\omega} Q_k }\right | \leq \sum_{n\in \omega} |Q_k| \leq \sum_{n\in \omega} \max(|P|,\aleph_0) = \aleph_0 \cdot \max(|P|,\aleph_0) = \max(|P|,\aleph_0) \)
Ya que \( \max(|P|,\aleph_0)\geq \aleph_0 \). ¿Esto esta bien?

Agrego: Perdón, esto me pasa por escribir cosas sin antes pensar todos los detalles de la prueba. El hecho que \( \{Q_k\} \) sea creciente se usa para probar que \( (Q,E) \) esta en las hipótesis de tu lema, ya que cuando tomamos parámetros \( \vec{a}\in Q \) al ser la unión creciente existe algún \( k \) tal que \( \vec{a}\in Q_k \)

Saludos,
Franco.

08 Enero, 2025, 08:47 pm
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Agrego: Perdón, esto me pasa por escribir cosas sin antes pensar todos los detalles de la prueba. El hecho que \( \{Q_k\} \) sea creciente se usa para probar que \( (Q,E) \) esta en las hipótesis de tu lema, ya que cuando tomamos parámetros \( \vec{a}\in Q \) al ser la unión creciente existe algún \( k \) tal que \( \vec{a}\in Q_k \)

Sí, eso es.

08 Enero, 2025, 09:13 pm
Respuesta #5

franma

  • $$\Large \color{#5b61b3}\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 1,655
  • País: uy
  • Karma: +2/-0
  • Sexo: Masculino
Agrego: Perdón, esto me pasa por escribir cosas sin antes pensar todos los detalles de la prueba. El hecho que \( \{Q_k\} \) sea creciente se usa para probar que \( (Q,E) \) esta en las hipótesis de tu lema, ya que cuando tomamos parámetros \( \vec{a}\in Q \) al ser la unión creciente existe algún \( k \) tal que \( \vec{a}\in Q_k \)

Sí, eso es.

Perfecto, muchas gracias.