Autor Tema: Probar: Toda álgebra de Boole finita es isomorfa al conjunto de partes de átomos

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

15 Junio, 2020, 01:49 am
Leído 7314 veces

manooooh

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

Estoy tratando de probar que cualquier álgebra de Boole finita es isomorfa al conjunto de partes de sus átomos.

Definiciones previas
Definición 1.1 Un álgebra de Boole es una red distributiva y complementada.

Definición 1.2 Sea \( (B,\lor,\land) \). Diremos que \( B \) es un álgebra de Boole si y sólo si se cumple:

1) \( \lor \) y \( \land \) son operaciones cerradas en \( B \).

2) \( \lor \) y \( \land \) son conmutativas.

3) \( \lor \) y \( \land \) son distributivas entre sí.

4) \( \lor \) y \( \land \) tienen elementos neutros \( 0_B \) y \( 1_B \) respectivamente.

5) Todos los elementos de \( B \) tienen complementos.

Definición 2 Sea \( (A,\preceq) \) un conjunto ordenado con primer elemento \( p\in A \). Se dice que \( m\in A \) es átomo de \( A \) si para todo \( x\in A \), \( (x\preceq m\to x=m\lor x=p)\land m\neq p \).

Observación Los átomos son los elementos que "siguen inmediatamente" al primer elemento.

Definición 3 Sean \( (A,\lor,\land) \) y \( (B,\lor',\land') \) dos álgebras de Boole, con primeros elementos \( 0_A \) y \( 0_B \) y últimos elementos \( 1_A \) y \( 1_B \), respectivamente. Un homomorfismo de álgebras de Boole es una función \( f\colon A\to B \) de modo que cumpla las siguientes condiciones:

1) \( f(\overline{a})=\overline{f(a)} \).

2) \( f(a\lor b)=f(a)\lor'f(b) \).

3) \( f(a\land b)=f(a)\land'f(b) \).

4) \( f(0_A)=0_B \).

5) \( f(1_A)=1_B \).

Definición 4 Sea \( f \) un homomorfismo de álgebras de Boole \( A \) y \( B \). Si \( f \) es biyectiva, se denomina isomorfismo de álgebras de Boole y se denota por \( A\approx B \). Para ello es necesario que los conjuntos tengan cardinales iguales.
[cerrar]

Una forma de decir lo mismo sería probar que:

Sean \( (A,\lor,\land) \) y \( B=(\mathcal{P}(\atom(A)),\lor',\land') \) dos álgebras de Boole, con \( \atom(A)=\{m\in A\mid\forall x\in A(x\preceq m\to x=m\lor x=p)\land m\neq p\} \), donde \( A \) tiene primer elemento \( p \). Entonces \( A\approx B \).

¿Está bien escrito y traducido lo anterior? Estoy usando una caracterización algebraica pero bien podríamos haberlo tomado como una red ordenada (en el libro aclara que es un bicondicional).



Si es así, pienso que hay que definir \( f\colon A\to B \) una función y probar que es un isomorfismo. (¿Se debe probar que \( f \) es una función?)

Para ello hay que probar las 5 condiciones de la definición 3 y que \( f \) es biyectiva.

1) Sea \( a\in A \). Al ser \( A \) un álgebra de Boole sabemos que \( \overline{a}\in A \). Y a partir de aquí no sé cómo probar \( f(\overline{a})=\overline{f(a)} \).

Lo mismo me sucede con los otros puntos.

¿Pueden ayudarme por favor? Gracias!!

Saludos

15 Junio, 2020, 02:00 am
Respuesta #1

manooooh

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

He estado buscando y parece que Carlos Ivorra lo demuestra para cualquier tipo de álgebra de conjuntos finita, no solo la de Boole:

Teorema: Toda álgebra de conjuntos finita \( \mathcal B \) es isomorfa al álgebra \( \mathcal PA \), donde \( A \) es el conjunto de sus átomos.

Demostración
Sea \( h: \mathcal B\longrightarrow \mathcal PA \) la aplicación que a cada \( U\in \mathcal B \) le asigna el conjunto \( h(U)\subset A \) formado por todos los átomos de \( \mathcal B \) contenidos en \( U \). Veamos que se trata de un isomorfismo de álgebras.

Tenemos que \( h \) es inyectiva, pues si \( U\neq V \), entonces \( U\setminus V\neq \emptyset \) (o al revés, pero los dos casos se tratan igualmente). Como \( U\setminus V\in \mathcal B \) y ya hemos razonado que las álgebras finitas son atómicas, existe un átomo \( P\subset U\setminus V \), con lo que \( P\in h(U)\setminus h(V) \), luego \( h(U)\neq h(V) \).

También es suprayectiva, pues si \( V\in \mathcal PA \), se trata de una familia finita de elementos de \( \mathcal B \), luego \( U=\bigcup V\in \mathcal B \). Veamos que \( h(U)=V \). Ciertamente, todo \( P\in V \) es un átomo de \( \mathcal B \) contenido en \( U \), luego \( P\in h(U) \), luego \( V\subset h(U) \).

Recíprocamente, si \( P\in h(U) \), entonces es un átomo de \( \mathcal B \) contenido en \( U=\bigcup V \). Necesariamente, existe un \( Q\in V \) tal que \( P\cap Q\neq \emptyset \), pero como \( P \) y \( Q \) son átomos y \( P\cap Q\in \mathcal B \), tiene que ser \( P=P\cap Q=Q \), por definición de átomo (ninguno de los dos puede contener estrictamente un conjunto no vacío en \( \mathcal B \)). Por lo tanto \( P=Q\in V \) y tenemos la igualdad.

Con esto tenemos que \( h \) es biyectiva. Falta probar que es un homomorfismo de álgebras. En primer lugar, veamos que \( h(U\cup V)=h(U)\cup h(V) \). Si \( P\in h(U\cup V) \), entonces \( P \) es un átomo contenido en \( U\cup V \), luego \( P = P\cap (U\cup V)=(P\cap U)\cup (P\cap V) \), y ambas partes están en \( \mathcal B \). Como \( P \) es un átomo, o bien \( P\cap U=\emptyset \), en cuyo caso \( P\subset V \) y \( P\in h(V) \), o bien \( P\cap U=P \), en cuyo caso \( P\subset U \) y \( P\in h(U) \). Esto prueba que \( h(U\cup V)\subset h(U)\cup h(V) \).

Recíprocamente, si \( P\in h(U)\cup h(V) \), digamos que \( P\in h(U) \), con lo que es un átomo contenido en \( U \), luego en \( U\cup V \), luego \( P\in h(U\cup V) \) y tenemos la igualdad.

Similarmente, \( h(X\setminus U)=A\setminus h(U) \). En efecto, si \( P\in h(X\setminus U) \), entonces \( P \) es un átomo que no está contenido en \( U \), luego \( P\in A\setminus h(U) \). Recíprocamente, si \( P\in A\setminus h(U) \), tenemos que \( P \) es un átomo no contenido en \( U \). Por lo tanto \( P\cap U\neq P \), luego \( P\cap U=\emptyset \) (porque \( P \) es un átomo) luego \( P\subset X\setminus U \), luego \( P\in h(X\setminus U) \).

Esto prueba que \( h \) es un homomorfismo y, por consiguiente, un isomorfismo.
[cerrar]

Obviamente esa prueba escapa a mis estudios, pero por ahí a alguien se le ocurre algo similar a lo que propongo.

Saludos

15 Junio, 2020, 10:33 am
Respuesta #2

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
En realidad lo que prueba Carlos Ivorra es esencialmente lo mismo que quieres probar tú. Un álgebra de conjuntos es en particular un álgebra de Boole (con \( \wedge \) la intersección, \( \vee \) la unión y complemento el complemento del conjunto respecto del espacio total).
De hecho, la misma demostración sirve, prácticamente palabra por palabra (traduciendo algunos conceptos conjuntistas a los de álgebras de Boole abstractas), para tu caso.

En realidad no hay diferencias entee álgebras de Boole en general y álgebras de conjuntos, incluso en el caso infinito: toda álgebra de Boole es isomorfa a un álgebra de conjuntos.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

15 Junio, 2020, 04:22 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

Muchas gracias por tu respuesta!

Ah, mira... Yo pensé que toda álgebra de Boole era un caso particular de un álgebra de conjuntos. ¿Por qué es al revés?

¿Podrías por favor traducir los primeros párrafos a lo que tenemos que usar,por favor?

Por ejemplo no entiendo cómo se traduciría la contención ¿estricta? a nuestro caso ni por qué \( h(U)\subset A \) y no a partes de \( A \). Por otro lado, recuerdo que jamás hemos visto en la materia la aplicación de una función a un conjunto. Siempre era a un elemento.

Todo eso y otras cosas más son las que me imposibilitan ver en detalle la prueba, por más que en esencia sea la misma.

Saludos

15 Junio, 2020, 11:35 pm
Respuesta #4

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Ah, mira... Yo pensé que toda álgebra de Boole era un caso particular de un álgebra de conjuntos. ¿Por qué es al revés?

Un álgebra de Boole es una estructura abstracta: un conjunto \( B \) con unas operaciones definidas \( \wedge, \vee,... \) que cumplen una serie de axiomas. Un álgebra de conjuntos es el caso particular en que \( B \subset PA \) para cierto conjunto \( A \) (es decir, los elementos de esta álgebra de Boole son subconjuntos de un conjunto fijado \( A \)), \( \wedge \) se interpreta como \( \cap \) (intersección de conjuntos), \( 1 \) como \( A \), \( 0 \) como \( \emptyset \), etc.
En ese sentido un álgebra de conjuntos es un caso particular de álgebra de Boole. Pero por otro lado hay álgebras de Boole, como el retículo de los divisores de \( 6 \) por ejemplo, que no tienen una interpretación como álgebra de conjuntos (los elementos son números, no subconjuntos de un conjunto dado, \( \vee \) es el supremo y no la unión de conjuntos, etc). Otro tema es que esta álgebra sea isomorfa a un álgebra de conjuntos, pero ella no es un álgebra de conjuntos.

Citar
¿Podrías por favor traducir los primeros párrafos a lo que tenemos que usar,por favor?

Mañana si tengo tiempo adapto la prueba, pero es algo qurme deberías intentar por ti mismo. Se trata de traducir las operaciones conjuntistas en \( \mathcal{B} \) a operaciones generales de un álgebra de Boole: cambiar intersecciones por \( \wedge \), uniones por \( \vee \), inclusiones por \( \leq \), etc. Ten cuidado por eso en que \( PA \) sigue siendo un álgebra de conjuntos, así que no debes traducir las operaciones que hagan referencia a \( PA \), solamente las de \( \mathcal{B} \).

Citar
Por ejemplo no entiendo cómo se traduciría la contención ¿estricta? a nuestro caso
La contención (estricta) de conjuntos se traduce por \( \leq \) (\( < \)), el orden del álgebra de Boole.
Citar
ni por qué \( h(U)\subset A \) y no a partes de \( A \). Por otro lado, recuerdo que jamás hemos visto en la materia la aplicación de una función a un conjunto. Siempre era a un elemento.

Me da la sensación de que te has imaginado que \( h \) es un tipo de aplicación extraña pero es una aplicación normal y corriente.
Fíjate que \( h: \mathcal{B} \to PA \). Luego si \( U \in \mathcal{B} \), entonces \( h(U) \in PA \) (como toda aplicación). Ahora bien, los elementos de \( PA \) son por definición los subconjuntos de \( A \). Por eso, \( h(U) \in PA \) es equivalente a \( h(U) \subset A \).
La ecuación más bonita de las matemáticas: \( d^2=0 \)

15 Junio, 2020, 11:45 pm
Respuesta #5

manooooh

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

Un álgebra de Boole es una estructura abstracta: un conjunto \( B \) con unas operaciones definidas \( \wedge, \vee,... \) que cumplen una serie de axiomas. Un álgebra de conjuntos es el caso particular en que \( B \subset PA \) para cierto conjunto \( A \) (es decir, los elementos de esta álgebra de Boole son subconjuntos de un conjunto fijado \( A \)), \( \wedge \) se interpreta como \( \cap \) (intersección de conjuntos), \( 1 \) como \( A \), \( 0 \) como \( \emptyset \), etc.
En ese sentido un álgebra de conjuntos es un caso particular de álgebra de Boole. Pero por otro lado hay álgebras de Boole, como el retículo de los divisores de \( 6 \) por ejemplo, que no tienen una interpretación como álgebra de conjuntos (los elementos son números, no subconjuntos de un conjunto dado, \( \vee \) es el supremo y no la unión de conjuntos, etc). Otro tema es que esta álgebra sea isomorfa a un álgebra de conjuntos, pero ella no es un álgebra de conjuntos.

Tienes razón. De hecho \( (D_n,\mid)=(D_n,\gcd,\operatorname{lcm}) \).

Mañana si tengo tiempo adapto la prueba, pero es algo qurme deberías intentar por ti mismo. Se trata de traducir las operaciones conjuntistas en \( \mathcal{B} \) a operaciones generales de un álgebra de Boole: cambiar intersecciones por \( \wedge \), uniones por \( \vee \), inclusiones por \( \leq \), etc. Ten cuidado por eso en que \( PA \) sigue siendo un álgebra de conjuntos, así que no debes traducir las operaciones que hagan referencia a \( PA \), solamente las de \( \mathcal{B} \).

De acuerdo. Intentaré empezar yo. Gracias.

Me da la sensación de que te has imaginado que \( h \) es un tipo de aplicación extraña pero es una aplicación normal y corriente.
Fíjate que \( h: \mathcal{B} \to PA \). Luego si \( U \in \mathcal{B} \), entonces \( h(U) \in PA \) (como toda aplicación). Ahora bien, los elementos de \( PA \) son por definición los subconjuntos de \( A \). Por eso, \( h(U) \in PA \) es equivalente a \( h(U) \subset A \).

Es cierto... No lo he pensado así, es un resultado básico de teoría de conjuntos.

Saludos

16 Junio, 2020, 12:26 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

Voy a empezar a traducir el teorema de Carlos para su reinterpretación dentro de las álgebras de Boole:

Teorema Toda álgebra de Boole finita \( B \) es isomorfa al conjunto de partes de sus átomos \( P(A) \).

Demostración Sea \( h\colon B\to P(A) \) la función que a cada \( u\in B \) le asigna el conjunto \( h(u)\in P(A) \) formado por todos los átomos de \( B \) precedidos por \( u \). Veamos que se trata de un isomorfismo de álgebras.

Para ello consideremos:

Definición Un álgebra de Boole es atómica si todos sus elementos que no sean primer elemento están precedidos por al menos un átomo.

Duda
No sé si lo anterior es la misma definición de "átomo" que expresé en la definición 2 de mi primer mensaje.
[cerrar]

Lema Toda álgebra de Boole finita \( B \) de la forma \( P(A) \) es atómica.

Demostración Si \( a_0\in B \) no es el primer elemento y no le precede ningún átomo, en particular \( a_0 \) no es un átomo, luego existe un \( a_1\in B \) tal que \( 0_B\neq a_1\precnsim a_0 \), pero \( a_1 \) no puede ser un átomo (porque a \( a_0 \) no le precede ningún átomo), luego existe un \( a_2\in B \) tal que \( 0_B\precnsim a_2\precnsim a_1\precnsim a_0 \), y de este modo podemos construir una sucesión infinita de elementos de \( B \), contradiciendo el hecho de que \( B \) era finita.

Tenemos que \( h \) es inyectiva, pues si \( u,v\in B \) con \( u\neq v \), entonces \( u\land\overline{v}\neq0_B \) (o al revés, pero los dos casos se tratan igualmente). Como \( u\land\overline{v}\in B \) y ya hemos razonado que las álgebras finitas son atómicas, existe un átomo \( p<u\land\overline{v} \), con lo que \( p\in h(u)\color{red}\cap\color{black}\overline{h(v)} \), luego \( h(u)\neq h(v) \).

Duda
No sé si esta proposición: dados \( u,v\in B \) con \( u\neq v \), entonces \( u\land\overline{v}\neq0_B \) es cierto. Por ejemplo, el álgebra de Boole \( (\{0,1\},\leq) \) tiene primer elemento \( 0_B=0 \), y si elegimos \( u=0 \) y \( v=1 \) luego \( u\land\overline{v}=0\land\overline{1}=0\land0=0=0_B \) (se razonaba que fuera distinto).
[cerrar]

¿Cómo lo ven?

Gracias y saludos

Corregido

16 Junio, 2020, 09:39 am
Respuesta #7

geómetracat

  • Moderador Global
  • Mensajes: 4,065
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Sobre la primera duda: la definición de átomo es la que pusiste: Un átomo es un elemento de un álgebra de Boole que no es el mínimo, pero que no tiene ningún otro elemento entre el mínimo y él.
Lo que dices ahora es que llamas a una álgebra de Boole atómica si cada elemento que no sea el mínimo tiene un átomo menor o igual que él.
Puedes tener álgebras de Boole que tengan algún átomo pero que no sean atómicas (porque haya algún elemento que no tenga átomos por debajo).

Sobre la segunda duda: que \( u \neq v \) implique \( u \wedge \bar{v} = 0 \) es falso, como indica tu contraejemplo, pero es que Carlos no afirma eso, afirma que \( u \neq v \) implica \( u \wedge \bar{v}\neq 0 \) o al revés: \( \bar{u} \wedge v \neq 0 \). Pero como los dos casos son simétricos solo trata el primero.
Para ver esto vemos el contrarrecíproco: si tuvieras \( u \wedge \bar{v}=0, \bar{u}\wedge v = 0 \) entonces \( u=(u \wedge v) \vee (u \wedge \bar{v}) = u \wedge v = (u \wedge v) \vee (\bar{u} \wedge v) = v \).
Fíjate la analogía con los conjuntos: la afirmación en el caso de un álgebra de conjuntos es lo mismo que decir que \( U \neq V \) implica que \( U - V \neq \emptyset \) o \( V- U \neq \emptyset \).

Sobre la traducción hasta el momento, está bien, salvo que cuando escribes \( p \in h(u) \wedge \overline{h(v)} \) deberías poner \( p \in h(u) - h(v) \). Recuerda que los elementos \( h(u) \) viven en el álgebra de conjuntos \( PA \), así que aquí no debes traducir las operaciones, ya que siguen siendo conjuntos. Solo tienes que traducir lo que haga referencia a \( B \), que ahora es una álgebra de Boole abstracta.
La ecuación más bonita de las matemáticas: \( d^2=0 \)

20 Junio, 2020, 05:53 pm
Respuesta #8

manooooh

  • $$\Large \color{#9c57a6}\pi\,\pi\,\pi\,\pi\,\pi\,\pi$$
  • Mensajes: 4,791
  • País: ar
  • Karma: +1/-0
  • Sexo: Masculino
Hola geómetracat, muchas gracias por tus observaciones, las voy teniendo en cuenta.

Ahora sigo con la traducción, esta semana estuve bastante corto de tiempo :laugh:.

Saludos

20 Junio, 2020, 06:07 pm
Respuesta #9

manooooh

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

¿Podrías indicar algunos ejemplos de álgebras de Boole que no sean atómicas, por favor?

Pienso en cosas como \( (D_n,|) \) o \( (A\subseteq\Bbb{Z},\leq) \) pero todas ellas son atómicas. Si puede ser un ejemplo finito, sencillo y conocido mucho mejor.

Saludos