Forum Scienze Matematiche

di **pic** il lun 8 feb 2010, 13:22

1. Provare che un'algebra di Boole (v. qui) finita e' sempre isomorfa all'insieme delle parti di un qualche insieme.

2. Esiste un'algebra di Boole che non lo sia?

di **Lord K** il gio 29 lug 2010, 17:06

Per risolvere il problema sto lavorando a questo approccio categorico:

Sia $\Gamma = (B, \wedge, \vee, \bot, \top)$ una algebra di Boole.

Sia definita la categoria $\mathcal C$ ove la freccia "orientamento" è $a \leq b \rightleftharpoons (a=a \wedge b) \text{ iff } (b=a \vee b)$ tra gli oggetti $a,b \in \Gamma$ .

Sia $\mathcal D$ la categoria dove gli oggetti sono sottoinsiemi di un insieme dato e le freccie definite come l'inclusione tra gli insiemi, ovvero se $A, B \in \mathcal D$ e $A \subseteq B$ allora esiste una freccia da $A$ a $B$ .

Congettura: Esiste un funtore $\mathfrak F: \mathcal C \to \mathcal D$ che ammette aggiunto sinistro!

Tra breve il prosieguo del caso :mrgreen:

di **killing_buddha** il gio 29 lug 2010, 17:40

Lord K ha scritto:Esiste un funtore $\mathfrak F: \mathcal C \to \mathcal D$ che ammette aggiunto sinistro!

Chiedo lumi pubblicamente, dato che il problema mi sembra interessante. Quello che intendi e' forse dire che per ogni algebra di Boole $\mathcal B$ (pensata ordinata dalle operazioni di $\lor$ e $\land$ , e dunque categoria ordinata) e per ogni insieme delle parti di un fissato insieme $X$ , pensato come parzialmente ordinato dalla relazione di inclusione,e quindi pensato come categoria ordinata, esiste un funtore $\mathfrak F\colon B\to \mathcal P(X)$ ? (edit) Nel caso finito, questo e' il teorema di Stone, che pic chiede di provare: vorresti dire che il tuo claim e' che

Per ogni algebra di Boole B esiste un isomorfismo con $\mathcal P(X)$ per qualche insieme $X$ ?

In attesa di una risposta, affermativa o negativa, mi limito a ricordare che, (fine edit) potendosi ricondurre il problema alla determinazione di una aggiunzione tra due preordini, vale il seguente

Teorema. Siano $\mathcal P$ e $\mathcal Q$ due preordini visti come categorie ordinate, e $\mathfrak L\colon\mathcal P\to \mathcal Q^\text{op}$ , $\mathfrak R\colon \mathcal Q^\text{op}\to \mathcal P$ due funzioni monotone viste come funtori. Allora $\mathfrak L$ e' aggiunto sinistro di $\mathfrak R$ se e solo se, per ogni $p\in P$ e $q\in Q$ ( $P,Q$ essendo gli insiemi sottostanti alle categorie $\mathcal P, \mathcal Q$ ) vale la condizione

$\mathfrak L(p)\ge q \iff p\le \mathfrak R(q)$
In tal caso esiste esattamente un modo di rendere $\mathfrak L\colon \mathcal P\to \mathcal Q^\text{op} \colon \mathfrak R$ una coppia di funtori aggiunti, l'unita' e la counita' della quale sono le due relazioni $p\le \mathfrak{RL}(p)$ e $q\le \mathfrak{LR}(q)$ .

di **Lord K** il ven 30 lug 2010, 10:30

Per poter dimostrare coerentemente il teorema di Stone (O dualità di Stone) ci vorrebbe un lungo processo di definizioni a riguardo (Spazi sobri) e credo che nel link ci siano tutti i dettagli intuitivi per comprendere il tutto.

Per quanto riguarda la mia congettura, pare sia errata, vista la letteratura sopra citata, anche se il teorema citato da KB la supporterebbe. Se fosse vera, infatti, ci sarebbe una equivalenza di categorie tra $\mathcal C$ e $\mathcal D$ che non renderebbe necessario il teorema di classificazione di Stone, quindi necessariamente dovrebbe essere non valida la condizione esposta da KB. Sbaglio?

di **killing_buddha** il ven 30 lug 2010, 10:45

Lord K ha scritto:Per quanto riguarda la mia congettura, pare sia errata, vista la letteratura sopra citata, anche se il teorema citato da KB la supporterebbe. Se fosse vera, infatti, ci sarebbe una equivalenza di categorie tra $\mathcal C$ e $\mathcal D$ che non renderebbe necessario il teorema di classificazione di Stone, quindi necessariamente dovrebbe essere non valida la condizione esposta da KB. Sbaglio?

Per il resto, stai attento: il teorema di Stone e' molto piu' forte della semplice esistenza di una aggiunzione, e anche di una equivalenza aggiunta, tra le due categorie in oggetto. Non e' difficile trovare un esempio di categorie finite equivalenti che pero' non sono isomorfe, avendo insiemi degli oggetti non equipotenti: graficamente e' il caso delle categorie $\mathbf C=\{C;\text{id}_C\}$ e $\mathbf D=\{D_1,D_2; \text{id}_{D_1},\text{id}_{D_2}, \alpha, \alpha^{-1}\}$ definite da

$\left(\xymatrix{ C\ar@(dl,ul)[]^{\text{id}_C} }\right)\sim\left( \xymatrix{ D_1 \ar@<+.3em>[r]^\alpha \ar@(dl,ul)[]^{\text{id}_{D_1}} & \ar@<+.3em>[l]^{\alpha^{-1}} D_2 \ar@(dr,ur)[]_{\text{id}_{D_2}} }\right)$

di **killing_buddha** il ven 30 lug 2010, 10:51

Se non ti era noto (ma non credo, e' una delle prime cose che "si imparano"), ti invito a mostrare il fatto precedente. :bye:

di **pic** il ven 30 lug 2010, 20:09

Bello che qualcuno abbia ripescato il problema, tuttavia da come procede il thread temo che non capiro' l'eventuale soluzione. Ad ogni modo, per una soluzione elementare potete usare gli atomi.

Ps il 2 e' molto piu' facile.

di **killing_buddha** il ven 30 lug 2010, 20:13

da come procede il thread temo che non capiro' l'eventuale soluzione.

Male! Devi studiare, pic! :rotfl:

di **pic** il dom 1 ago 2010, 8:41

Ecco la mia.

Se non ci sono atomi la nostra algebra di Boole e' isomorfa a $P(\varnothing)$ .

Se ci sono $n>0$ atomi, sia $b$ uno di questi, $\neg b$ il complementare.

1. L'insieme $S:=\{a|a\leq \neg b\}$ e' isomorfo ad un'algebra di Boole con $n-1$ atomi: l'isomorfismo cercato manda ogni elemento in se e $\neg b$ in 1. Per verificare chr l'immagine e' un'agebra di Boole serve solo trovare i "complementari", cioe per $a \in S$ serve $x$ con $x\wedge a =0, x\vee a = \neg b$ ed a tale scopo si prenda $x=\neg a \wedge \neg b.$

2. L'insieme $T:=\{a|a\ge b\}$ e' isomorfo per simili conti ad un'algebra di Boole con $n-1$ elementi. L'isomorfismo manda $b\mapsto 0$ .

3. Ora basta mostrare che se $\{x_1=b,x_2,\ldots,x_n\}$ sono gli atomi allora ogni elemento della nostra algebra di Boole si scrive come
$x_{i_1}\vee\ldots \vee x_{i_k}$ per $i_1,\ldots, i_k \in \{1,\ldots,n\}$ per concludere.

di **killing_buddha** il dom 1 ago 2010, 19:36

Rammentiamo un po' di notazione e alcuni fatti preliminari.

1. Indichiamo con $\mathsf{BA}$ la categoria delle algebre di Boole, che ha per morfismi le funzioni $f\colon B\to B'$ tali che $f(a\lor b)=f(a)\lor' f(b)$ e analogamente per le altre operazioni.

2. $\mathsf{BA}$ ha un oggetto iniziale, ossia l'algebra di Boole $\mathbf{2}$ con la definizione obbligata delle operazioni di AND, OR e NOT

3. Un filtro in un'algebra di Boole e' un sottoinsieme $F\subseteq B$ tale che

$F$ contiene l'elemento massimale di $B$ ;
$a\in F$ e $a\le b$ implica che $b\in F$ ;
$a\in F$ e $b\in F$ implica che $a\land b\in F$ .

Un ultrafiltro e' un elemento massimale nell'insieme $\mathcal F(B)$ di tutti i filtri su una data algebra di Boole: indichiamo con $\text{Ult}(B)$ l'insieme di tutti gli ultrafiltri su $B$ .
Lemma. Esiste una corrispondenza naturale tra i morfismi di algebre di Boole $p\colon B\to \mathbf{2}$ e gli "ultrafiltri" di $B$ .
Dimostrazione. Definiamo una mappa $\text{Hom}(B,\mathbf{2})\to \txt{Ult}(B)\colon p\mapsto p^\leftarrow(1)$ . E' facile vedere che questo e' un ultrafiltro su $B$ . Viceversa, definiamo $\text{Ult}(B)\to \text{Hom}(B,\mathbf{2})\colon U\mapsto p_U$ , ove $p_U(U)=\{1\}$ e $p_U(B\setminus U)=\{0\}$ . E' facile vedere che questa corrispondenza e' biiettiva, e dunque

$\text{Hom}_{\mathsf{BA}}(B,\mathbf 2) \cong \text{Ult}(B)$

In maniera piu' raffinata (e a un volume di voce non troppo elevato) si puo' definire un funtore $\text{Ult}\colon \mathsf{BA}\to \mathsf{Sets}\colon B\mapsto \text{Ult}(B)$ che si scopre essere isomorfo al funtore dei sottoggetti relativo alla categoria $\mathsf{BA}$ : allora l'isomorfismo trovato non e' altro che la condizione per cui $\mathbf{2}$ sia il classificatore dei sottoggetti di $\mathsf{BA}$ ...

Esercizio. Trovare il morfismo (unico) $B\to \mathbf{2}$ tale che il diagramma

$\bfig \square/>`>->`>`>/[U`\mathbf 2`B`\mathbf 2; f`\iota`\text{id}` ] \efig$

(e gia' che ci siete trovate anche $f$ ...).

Cio' noto, discende che la corrispondenza $\text{Ult}$ e' funtoriale sui morfismi $h\colon B\to B'$ , nel senso che $\text{Ult}(h)$ e' un morfismo tra $\text{Ult}(B')$ e $\text{Ult}(B)$ (occhio alla controvarianza!).

Esercizio. Mostrare (se non lo si era fatto nella dimostrazione del Lemma) che dato un ultrafiltro $U\in \text{Ult}(B')$ , l'insieme $\text{Ult}(h)(U)=h^\leftarrow(U)$ e' un ultrafiltro su $B$ .

Vorrei dire quel che segue: il funtore $\text{Ult}$ ammette un aggiunto destro, e questo aggiunto destro e' il funtore controvariante potenza $\mathcal P^{BA}\colon \mathsf{Sets}\to \mathsf{BA}$ che manda ogni insieme $X$ nell'algebra di Boole naturalmente originata da $\mathcal P(X)$ .

Ora, consideriamo gli ultrafiltri "principali" di $\text{Ult}(\mathcal P^{BA}(X))$ (ossia quelli che sono "ultrafiltri degli intorni" di un qualche elemento, i.e. gli ultrafiltri tali che

$\exists\, x\in X \text{ tale che } \;\text{Ult}(B)=\{U\subseteq X\mid x\in U\}$

Il morfismo $\eta_X\colon X\to \mathcal{U}(X)=\text{Ult}(\mathcal P^{BA}(X))$ definito da $x\mapsto\{U\subseteq X\mid x\in U\}$ manda $x\in X$ in un ultrafiltro principale di $\mathcal{U}(X)$ , ed e' naturale in ogni componente $\eta_X$ :

$\begin{array}{ccc} (\mathcal{U}(f)\circ \eta_X)(x) &=& \{V\subseteq Y\mid f^\leftarrow(V)\in \eta_X(x)\} \\ &=& \{V\subseteq Y\mid x\in f^\leftarrow(V)\} \\ &=& \{V\subseteq Y\mid f(x)\in V\} = \eta_Y(f(x)) \end{array}$

$\bfig\square[X`\mathcal{U}(X)`Y`\mathcal{U}(Y); \eta_X`f`\mathcal U(f)`\eta_Y]\efig$

Potremmo pensare di aver fatto un buco nell'acqua, perche' non riusciamo a coprire tutti gli ultrafiltri. Studiamo pero' cosa succede alla counita' dell'aggiunzione: per ogni $B\in\text{Ob}_{\mathsf{BA}}$ c'e' un morfismo

$\phi_B\colon B\to \mathcal P^{BA}(\text{Ult}(B))\colon b\mapsto \{H\in \text{Ult}(B)\mid b\in H\}$

Esercizio 1. Per ogni $B\in\text{Ob}_{\mathsf{BA}}$ il morfismo $\phi_B$ e' iniettivo.
Esercizio 2. Se $\mathfrak F\colon \mathsf C\dashv \mathsf D\colon \mathfrak G$ e' una coppia di funtori aggiunti, $\mathfrak F$ e' un funtore fedele se e solo se ogni componente dell'unita' e' un monomorfismo.

Si conclude: $\phi_B(B)$ e' una sottoalgebra di Boole di $\mathcal P^{BA}(\text{Ult}(B))$ , di modo che ogni algebra di Boole si puo' pensare come una sottoalgebra di Boole di una che risulta dall'insieme delle parti di un opportuno insieme (che e', come si vede, l'insieme degli ultrafiltri su $B$ ). []

Note.
1. pic, comincia a leggere.
2. Lord K, sei contento?
3. Ho bisogno di una vacanza...

Forum Scienze Matematiche

Teorema di rappresentazione di Stone

Teorema di rappresentazione di Stone

Categorico!

aSTONEishing!

Chi c’è in linea