Autor Tema: Prueba del principio del máximo (modelos booleanos)

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

13 Enero, 2025, 02:56 pm
Leído 1055 veces

franma

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

Estoy leyendo la prueba del principio del máximo de mis apuntes (página 67), el enunciado es el siguiente:
Para cada fórmula \( \phi(x,\vec{w}) \) (con parámetros \( \vec{w} \)), existe \( u^*\in V^\mathbb{B} \) tal que:
\( [\![ \exists x\, \phi(x,\vec{w}) ]\!] = [\![ \phi(u^*,\vec{w}) ]\!] \)

Y la demostración es la siguiente:
Sea \( B_{\phi,\vec{w}} := \{[\![ \phi(u,\vec{w}) ]\!] : V^\mathbb{B} \} \subseteq \mathbb{B} \). Como \( B_{\phi,\vec{w}} \) es un conjunto, existe por Colección + AC un ordinal \( \alpha \) y una familia \( (u_\xi)_{\xi<\alpha} \subseteq V^\mathbb{B} \) tal que \( B_{\phi,\vec{w}} = \{[\![ \phi(u,\vec{w}) ]\!] : \xi <\alpha \} \)

Para todo \( \xi<\alpha \) definimos \( a_\xi := [\![ \phi(u_\xi,\vec{w}) ]\!] - \bigvee_{\eta <\xi} [\![ \phi(u_\eta,\vec{w}) ]\!] \) (por recursión sobre \( \xi \)) y notamos \( u^* := \sum_{\xi<\alpha} a_\xi \cdot u_\xi \)

Por construcción, la familia \( (a_\xi)_{\xi<\alpha} \) es una anticadena, luego por el lema de la mezcla tenemos que \( a_\xi \leq [\![ u^* = u_\xi ]\!] \) y además por definición de \( a_\xi \) tenemos \( a_\xi \leq [\![ \phi(u_\xi,\vec{w}) ]\!] \), luego:
\( a_\xi \leq [\![ u^* = u_\xi ]\!] \land [\![ \phi(u_\xi ,\vec{w}) ]\!] \leq [\![ \phi(u^*,\vec{w}) ]\!] \)

Por lo tanto:
\( \displaystyle [\![ \exists x\, \phi(x,\vec{w}) ]\!] = \bigvee_{\xi<\alpha} [\![ \phi(u_\xi ,\vec{w}) ]\!]\,{\color{red} = }\bigvee_{\xi<\alpha} a_\xi \leq [\![ \phi(u^*,\vec{w}) ]\!] \leq [\![ \exists x\, \phi(x,\vec{w}) ]\!] \)
de donde:
\( [\![ \phi(u^*,\vec{w}) ]\!] = [\![ \exists x\, \phi(x,\vec{w}) ]\!] \)
como queríamos probar.

Mis dudas son las cosas que marqué en rojo:
  • ¿No basta con usar solamente AC? ¿Para que precisamos Colección?
  • ¿Esta igualdad es evidente? No me esta saliendo justificarla

Espero que alguien me pueda ayudar.

Saludos,
Franco.

13 Enero, 2025, 10:05 pm
Respuesta #1

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Estoy leyendo la prueba del principio del máximo de mis apuntes (página 67), el enunciado es el siguiente:
Para cada fórmula \( \phi(x,\vec{w}) \) (con parámetros \( \vec{w} \)), existe \( u^*\in V^\mathbb{B} \) tal que:
\( [\![ \exists x\, \phi(x,\vec{w}) ]\!] = [\![ \phi(u^*,\vec{w}) ]\!] \)

Y la demostración es la siguiente:
Sea \( B_{\phi,\vec{w}} := \{[\![ \phi(u,\vec{w}) ]\!] : {\color{red} u\in }V^\mathbb{B} \} \subseteq \mathbb{B} \). Como \( B_{\phi,\vec{w}} \) es un conjunto, existe por Colección + AC un ordinal \( \alpha \) y una familia \( (u_\xi)_{\xi<\alpha} \subseteq V^\mathbb{B} \) tal que \( B_{\phi,\vec{w}} = \{[\![ \phi(u_{\color{red}\xi},\vec{w}) ]\!] : \xi <\alpha \} \)

Te faltaban ahí algunas cosas que he puesto en rojo. Para cada \( b\in B_{\phi, \vec w} \) existe un \( u\in V^{\mathbb B} \) tal que \( b = [\![\phi(u, \vec w)]\!] \). Usas Colección para tomar un conjunto \( U\subset V^{\mathbb B} \) tal que \( B_{\phi, \vec w} = \{ [\![\phi(u, \vec w)]\!]\mid u\in U\} \), y usas el axioma de elección para biyectar este conjunto \( U \) con un ordinal \( \alpha \).

Respecto de la igualdad por la que preguntas, es un hecho general sobre álgebras de Boole completas. Es más claro enunciarlo prescindiendo de la notación concreta de este contexto.

Si \( B \) es un álgebra de Boole completa y \( \{b_\xi\}_{\xi<\alpha} \) es una familia de elementos de \( B \) (en nuestro caso \( b_\xi = [\![\phi(u_\xi,\vec w)]\!] \)), definimos \( a_\xi = b_\xi\land (\bigvee\limits_{\eta<\xi} b_\eta)' \). Entonces \( \bigvee\limits_{\xi<\alpha}b_\xi = \bigvee\limits_{\xi<\alpha}a_\xi \).

Podemos probarlo por inducción sobre \( \alpha \).

Para \( \alpha = 0 \) se reduce a \( 0 = 0 \). Si vale para \( \alpha \), tenemos que

\( b_\alpha = (b_\alpha\land \bigvee\limits_{\eta<\alpha} b_\eta)\lor (b_\alpha\land (\bigvee\limits_{\eta<\alpha} b_\eta)')=(b_\alpha\land \bigvee\limits_{\eta<\alpha} b_\eta)\lor a_{\alpha} \).

Entonces, por hipótesis de inducción,

\( \bigvee\limits_{\eta<\alpha+1}b_\eta = \bigvee\limits_{\eta<\alpha}b_\eta\lor b_{\alpha}= \bigvee\limits_{\eta<\alpha}b_\eta\lor (b_\alpha\land \bigvee\limits_{\eta<\alpha} b_\eta)\lor a_\alpha=\bigvee\limits_{\eta<\alpha}b_\eta\lor a_\alpha=\bigvee\limits_{\eta<\alpha}a_\eta\lor a_\alpha=\bigvee\limits_{\eta<\alpha+1}a_\eta \).

Si \( \alpha \) es un ordinal límite y vale para \( \delta<\alpha \),

\( \bigvee\limits_{\eta<\alpha}b_\eta = \bigvee\limits_{\delta<\alpha}\bigvee\limits_{\eta<\delta}b_\eta=\bigvee\limits_{\delta<\alpha}\bigvee\limits_{\eta<\delta}a_\eta = \bigvee\limits_{\eta<\alpha}a_\eta \).

13 Enero, 2025, 10:49 pm
Respuesta #2

franma

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

Te faltaban ahí algunas cosas que he puesto en rojo. Para cada \( b\in B_{\phi, \vec w} \) existe un \( u\in V^{\mathbb B} \) tal que \( b = [\![\phi(u, \vec w)]\!] \).

Gracias.

Usas Colección para tomar un conjunto \( U\subset V^{\mathbb B} \) tal que \( B_{\phi, \vec w} = \{ [\![\phi(u, \vec w)]\!]\mid u\in U\} \), y usas el axioma de elección para biyectar este conjunto \( U \) con un ordinal \( \alpha \).

Perfecto, todo entendido.

Respecto de la igualdad por la que preguntas, es un hecho general sobre álgebras de Boole completas. Es más claro enunciarlo prescindiendo de la notación concreta de este contexto.

Si \( B \) es un álgebra de Boole completa y \( \{b_\xi\}_{\xi<\alpha} \) es una familia de elementos de \( B \) (en nuestro caso \( b_\xi = [\![\phi(u_\xi,\vec w)]\!] \)), definimos \( a_\xi = b_\xi\land (\bigvee\limits_{\eta<\xi} b_\eta)' \). Entonces \( \bigvee\limits_{\xi<\alpha}b_\xi = \bigvee\limits_{\xi<\alpha}a_\xi \).

Podemos probarlo por inducción sobre \( \alpha \).

Para \( \alpha = 0 \) se reduce a \( b_0 = a_0 \). Si vale para \( \alpha \), tenemos que

\( b_\alpha = (b_\alpha\land \bigvee\limits_{\eta<\alpha} b_\eta)\lor (b_\alpha\land (\bigvee\limits_{\eta<\alpha} b_\eta)')=(b_\alpha\land \bigvee\limits_{\eta<\alpha} b_\eta)\lor a_{\alpha} \).

Entonces, por hipótesis de inducción,

\( \bigvee\limits_{\eta<\alpha+1}b_\eta = \bigvee\limits_{\eta<\alpha}b_\eta\lor b_{\alpha}= \bigvee\limits_{\eta<\alpha}b_\eta\lor (b_\alpha\land \bigvee\limits_{\eta<\alpha} b_\eta)\lor a_\alpha=\bigvee\limits_{\eta<\alpha}b_\eta\lor a_\alpha=\bigvee\limits_{\eta<\alpha}a_\eta\lor a_\alpha=\bigvee\limits_{\eta<\alpha+1}a_\eta \).

Si \( \alpha \) es un ordinal límite y vale para \( \delta<\alpha \),

\( \bigvee\limits_{\eta<\alpha}b_\eta = \bigvee\limits_{\delta<\alpha}\bigvee\limits_{\eta<\delta}b_\eta=\bigvee\limits_{\delta<\alpha}\bigvee\limits_{\eta<\delta}a_\eta = \bigvee\limits_{\eta<\alpha}a_\eta \).

Excelente, muchas gracias. Por cierto, ¿el caso \( \alpha= 0 \) no se reduce a \( 0=0 \)?

Saludos,
Franco.

13 Enero, 2025, 11:00 pm
Respuesta #3

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Si \( B \) es un álgebra de Boole completa y \( \{b_\xi\}_{\xi<\alpha} \) es una familia de elementos de \( B \) (en nuestro caso \( b_\xi = [\![\phi(u_\xi,\vec w)]\!] \)), definimos \( a_\xi = b_\xi\land (\bigvee\limits_{\eta<\xi} b_\eta)' \). Entonces \( \bigvee\limits_{\xi<\alpha}b_\xi = \bigvee\limits_{\xi<\alpha}a_\xi \).

Perdón que me entrometa, pero al ver que están hablando sobre álgebras de Boole no pude dejar de recordar este hilo: Probar: Toda álgebra de Boole finita es isomorfa al conjunto de partes de átomos.

¿Tiene algo que ver lo que están discutiendo aquí con aquel teorema? ¿Se puede realizar una demostración como las que muestran para probar dicho resultado, o se necesita de más batería para atacarlo?

Gracias y saludos

14 Enero, 2025, 12:37 am
Respuesta #4

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Por cierto, ¿el caso \( \alpha= 0 \) no se reduce a \( 0=0 \)?

Sí. Es cierto.

14 Enero, 2025, 12:50 am
Respuesta #5

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Hola

Si \( B \) es un álgebra de Boole completa y \( \{b_\xi\}_{\xi<\alpha} \) es una familia de elementos de \( B \) (en nuestro caso \( b_\xi = [\![\phi(u_\xi,\vec w)]\!] \)), definimos \( a_\xi = b_\xi\land (\bigvee\limits_{\eta<\xi} b_\eta)' \). Entonces \( \bigvee\limits_{\xi<\alpha}b_\xi = \bigvee\limits_{\xi<\alpha}a_\xi \).

Perdón que me entrometa, pero al ver que están hablando sobre álgebras de Boole no pude dejar de recordar este hilo: Probar: Toda álgebra de Boole finita es isomorfa al conjunto de partes de átomos.

¿Tiene algo que ver lo que están discutiendo aquí con aquel teorema?

Este resultado vale para álgebras de Boole completas arbitrarias, no necesariamente finitas. En particular, ni siquiera tienen por qué tener átomos. De hecho, las que le sirven a franma no tienen átomos.

¿Se puede realizar una demostración como las que muestran para probar dicho resultado, o se necesita de más batería para atacarlo?

No sé si entiendo la pregunta. ¿Te refieres a probar el resultado sobre álgebras de Boole finitas usando el teorema que he probado yo en este hilo? En principio no veo ninguna relación.

14 Enero, 2025, 12:57 am
Respuesta #6

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola

Este resultado vale para álgebras de Boole completas arbitrarias, no necesariamente finitas. En particular, ni siquiera tienen por qué tener átomos. De hecho, las que le sirven a franma no tienen átomos.

Las álgebras de Boole finitas todas tienen átomos. Así que intuyo que hablas en general, para cualquier álgebra de Boole.

No sé si entiendo la pregunta. ¿Te refieres a probar el resultado sobre álgebras de Boole finitas usando el teorema que he probado yo en este hilo? En principio no veo ninguna relación.

A probarlo usando la teoría que franma ha estado preguntando en los últimos hilos. Igual no nos sirve, pero quería quitarme la duda.

Saludos

14 Enero, 2025, 01:03 am
Respuesta #7

Carlos Ivorra

  • Administrador
  • Mensajes: 11,956
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
    • Página web personal
Este resultado vale para álgebras de Boole completas arbitrarias, no necesariamente finitas. En particular, ni siquiera tienen por qué tener átomos. De hecho, las que le sirven a franma no tienen átomos.

Las álgebras de Boole finitas todas tienen átomos. Así que intuyo que hablas en general, para cualquier álgebra de Boole.

Eso digo. Que las álgebras de Boole con las que trabaja franma son infinitas y no atómicas. Este resultado:

Si \( B \) es un álgebra de Boole completa y \( \{b_\xi\}_{\xi<\alpha} \) es una familia de elementos de \( B \) (en nuestro caso \( b_\xi = [\![\phi(u_\xi,\vec w)]\!] \)), definimos \( a_\xi = b_\xi\land (\bigvee\limits_{\eta<\xi} b_\eta)' \). Entonces \( \bigvee\limits_{\xi<\alpha}b_\xi = \bigvee\limits_{\xi<\alpha}a_\xi \).

es válido para álgebras de Boole completas cualesquiera. Vale para álgebras finitas, pero también para las que interesan en este hilo, que son infinitas y no atómicas.

No sé si entiendo la pregunta. ¿Te refieres a probar el resultado sobre álgebras de Boole finitas usando el teorema que he probado yo en este hilo? En principio no veo ninguna relación.

A probarlo usando la teoría que franma ha estado preguntando en los últimos hilos. Igual no nos sirve, pero quería quitarme la duda.

No. Franma está preguntando cosas sobre forcing, que es una teoría que usa álgebras de Boole, y propiedades de las álgebras de Boole como la que he probado yo antes, pero no está hecha para demostrar propiedades de las álgebras de Boole.