Dualità reticolare

[maurer]

Abbiamo recentemente discusso di dualità in matematica (vedi qui). Propongo un'altra dualità rispetto a quelle di cui si parla nel thread citato.

Definizione. Siano [tex]A,B[/tex] due insiemi e sia [tex]\sigma \subseteq A \times B[/tex] una relazione. Diciamo relazione inversa la relazione [tex]\sigma^{-1}[/tex] definita da [tex]b \sigma^{-1} a \iff a \sigma b[/tex].

Esercizio 1. Mostrare che se [tex]\le[/tex] è una relazione d'ordine in [tex]L[/tex], allora [tex]\le^{-1}[/tex] è ancora una relazione d'ordine. Dimostrare inoltre che se [tex](L,\le)[/tex] era un reticolo, allora [tex](L,\le^{-1})[/tex] è ancora un reticolo (ogni coppia di elementi ammette estremi inferiore e superiore).

Definizione. Sia [tex](L,\le)[/tex] un reticolo ordinato. Diciamo reticolo duale il reticolo [tex](L,\le^{-1})[/tex]. Per comodità di scrittura, denoteremo quando non ci sia possibilità di confusione [tex]\le^{-1}[/tex] ancora con il simbolo [tex]\le[/tex] e scriveremo [tex]L^\circ[/tex] per intendere il reticolo duale.

Data ora una formula del prim'ordine [tex]\psi[/tex] nel linguaggio [tex]\mathcal L = \{\le\}[/tex], possiamo definire la formula duale [tex]\psi^\circ[/tex] come la formula ottenuta da [tex]\psi[/tex] scambiando membro destro e sinistro in ogni punto in cui compare il simbolo [tex]\le[/tex] (più intuitivamente e meno formalmente [tex]\psi^\circ[/tex] si ottiene da [tex]\psi[/tex] sostituendo [tex]\le[/tex] con [tex]\ge[/tex]).

Prove it! Sia [tex]T[/tex] la teoria dei reticoli. Mostrare che se [tex]T \vDash \psi[/tex] allora [tex]T \vDash \psi^\circ[/tex].

[salvozungri]

Ho un'idea per questo esercizio, la metto in spoiler, per adesso non posso scrivere i dettagli perché farò un uso massiccio di formule, diventa una cosa lunga.

L'esercizio 1. è "naturale", anche se è fondamentale, ci dice che \(T_{\text{OR}}\sim T_{\text{OR}}^\circ\) cioè la teoria degli ordini e il suo duale sono equivalenti, pertanto i modelli della teoria \(T_{\text{OR}}\) coincidono con quelli della \(T_{\text{OR}}^\circ\). La seconda parte dell'esercizio 1. ci dice che la teoria dei reticoli e il suo duale sono equivalenti, di conseguenza sia \(T\) che \(T^\circ\) hanno gli stessi modelli. Sfruttando questo penso di poter dimostrare che se \(\psi\) è una conseguenza logica di \(T\) allora \(\psi^\circ\) è una conseguenza logica di \(T\). So di non essere stato molto chiaro, appena avrò qualche ora di tempo tenterò d'essere il più formale possibile (come il linguaggio della logica matematica pretende )

[maurer]

Il primo esercizio non è niente di più di un riscaldamento da fare al mattino presto prima di colazione.

L'esercizio vero e proprio non è in sé difficile, ma l'ho trovato istruttivo riguardo alla nozione di dualità in matematica (sul perché funziona il teorema di dualità).

[salvozungri]

Definizione. Siano [tex]A,B[/tex] due insiemi e sia [tex]\sigma \subseteq A \times B[/tex] una relazione. Diciamo relazione inversa la relazione [tex]\sigma^{-1}[/tex] definita da [tex]b \sigma^{-1} a \iff a \sigma b[/tex].

Esercizio 1.

a)Mostrare che se [tex]\le[/tex] è una relazione d'ordine in [tex]L[/tex], allora [tex]\le^{-1}[/tex] è ancora una relazione d'ordine.

Premetto alcune definizioni:
Teoria e Modelli, connessioni di Galois: Vedi qui
Approfondimento sulle connessioni di Galois: Vedi qui

Insieme ordinato: Un insieme ordinato è la coppia \((X,\le)\), dove \(\le\) è una relazione di arietà 2 in \(X\) che soddisfa i seguenti enunciati:
\(\phi_1): \forall x(x\le x)\)
\(\phi_2):\forall x_1, x_2((x_1\le x_2\wedge x_2\le x_1)\longrightarrow x_1=x_2)\)
\(\phi_3):\forall x_1, x_2, x_3((x_1\le x_2\wedge x_2\le x_3)\longrightarrow x_1\le x_3)\)
La teoria degli ordini \(T_\text{OR}\) è l'insieme degli enunciati \(\phi_1, \phi_2, \phi_3\) espressi nel linguaggio \(\mathcal{L}\):
\[ T_\text{OR}= \left\{ \phi_1, \phi_2, \phi_3\right\} \]
Ogni modello \(\mathcal{A}\in\mathcal{P(M_L)}\) di \(T_\text{OR}\) è per definizione un insieme ordinato.

Definisco ora la teoria duale di \(T_\text{OR}\) in codesto modo:
\(T_\text{OR}^\circ\):= \(\left\{\phi_1^\circ, \phi_2^\circ, \phi_3^\circ\right\}\)
dove:
-\(\phi_1^\circ):\forall x(x{\le}^{-1} x)\)
-\(\phi_2^\circ):\forall x_1, x_2((x_1\le^{-1} x_2\wedge x_2\le^{-1} x_1)\longrightarrow x_1=^{-1}x_2)\)
-\(\phi_3^\circ):\forall x_1, x_2, x_3((x_1\le^{-1} x_2\wedge x_2\le^{-1} x_3)\longrightarrow x_1\le^{-1} x_3)\)

Sfruttando la definizione di relazione inversa, dimostrerò che \(\le\) è una relazione d'ordine allora lo sarà \(\le^{-1}\)
-\(\phi_1\longrightarrow \phi_1^\circ\)

\(\forall x(x\le x)\) implica \(\forall x(x\le^{-1}x)\) (la riflessività è banalmente verificata dalla definizione di relazione inversa)

-\(\phi_2\longrightarrow \phi_2^\circ\)
\(\forall x_1, x_2(x_1\le^{-1} x_2\wedge x_2\le^{-1} x_1)\) implica \(\forall x_1, x_2((x_2\le x_1\wedge x_1\le x_2)\longrightarrow x_2=x_1)\) da cui \(x_1=^{-1}x_2\).
Dovrei sprecare qualche parolina in più sul simbolo \(=^{-1}\) con il quale intendo la relazione inversa della relazione \(=\), in realtà le due relazioni coincidono, grazie alla simmetria di cui gode appunto \(=\).

-\(\phi_3\longrightarrow\phi_3^\circ\):
\(\forall x_1, x_2, x_3(x_1\le^{-1} x_2\wedge x_2\le^{-1} x_3)\) implica per definizione di relazione inversa \(\forall x_1, x_2, x_3((x_2\le x_1\wedge x_3\le x_2)\longrightarrow x_3\le x_1)\), pertanto \(x_1\le^{-1}x_3\).

In modo del tutto simile, si può dimostrare che se \(\le^{-1}\) è una relazione d'ordine allora lo sarà anche \(\le\). Ciò significa che presa una \(\mathcal{L}\)-struttura \(X\), \(X\vDash T_{\text{OR}}\iff X\vDash T_{\text{OR}}^\circ\) di conseguenza ogni modello della teoria \(T_{\text{OR}}\) è modello della teoria duale \(T_{\text{OR}}^\circ\), \(\text{Mod}(T_{\text{OR}})=\text{Mod}(T_{\text{OR}}^\circ)\), che è la definizione (che conosco) di teorie equivalenti.

b) Dimostrare inoltre che se [tex](L,\le)[/tex] era un reticolo, allora [tex](L,\le^{-1})[/tex] è ancora un reticolo (ogni coppia di elementi ammette estremi inferiore e superiore).

Reticolo (visto come struttura relazionale): Un reticolo è un insieme ordinato \((X, \le )\) tale che per ogni \(x_1, x_2\in X\) esistono \(\sup(x_1, x_2)\) e \(\inf(x_1, x_2)\).

La teoria dei reticoli è composta pertanto da 5 enunciati: \(T_{R}:= T_{\text{OR}}\cup \left\{\phi_4, \phi_5\right\}\)
dove:
-\(\phi_4) \forall x_1, x_2 \exists x_3 (x_1\le x_3\wedge x_2\le x_3\wedge \forall x_4 ((x_1\le x_4 \wedge x_2\le x_4)\longrightarrow x_3\le x_4))\)
-\(\phi_5) \forall x_1, x_2 \exists x_3 (x_3\le x_1\wedge x_3\le x_1\wedge \forall x_4 ((x_4\le x_1 \wedge x_4\le x_2)\longrightarrow x_4\le x_3)) \)

Nello spoiler precedente abbiamo visto che \(\phi_i\longrightarrow \phi_i^\circ, \quad i=1, 2, 3\), indicando con \(\phi_4^\circ, \phi_5^\circ\) gli enunciati duali di \(\phi_4, \phi_5\), è immediato mostrare che \(\phi_4\longrightarrow \phi_4^\circ\) e \(\phi_5\longrightarrow \phi_5^\circ\), in particolare se si svolge i conti ci si rendere conto che \(\phi_4\) è l'enunciato duale di \(\phi_5\) e viceversa.
Dunque se \((L, \le )\) è un reticolo allora \((L, \le^{-1})\) è un reticolo, in altre parole, siano \(T_{R}\) la teoria dei reticoli, \(T_{R}^\circ\) la sua teoria duale, allora se \(L\vDash T_{R}\) allora \(L\vDash T_{R}^\circ\)

Definizione. Sia [tex](L,\le)[/tex] un reticolo ordinato. Diciamo reticolo duale il reticolo [tex](L,\le^{-1})[/tex]. Per comodità di scrittura, denoteremo quando non ci sia possibilità di confusione [tex]\le^{-1}[/tex] ancora con il simbolo [tex]\le[/tex] e scriveremo [tex]L^\circ[/tex] per intendere il reticolo duale.

Data ora una formula del prim'ordine [tex]\psi[/tex] nel linguaggio [tex]\mathcal L = \{\le\}[/tex], possiamo definire la formula duale [tex]\psi^\circ[/tex] come la formula ottenuta da [tex]\psi[/tex] scambiando membro destro e sinistro in ogni punto in cui compare il simbolo [tex]\le[/tex] (più intuitivamente e meno formalmente [tex]\psi^\circ[/tex] si ottiene da [tex]\psi[/tex] sostituendo [tex]\le[/tex] con [tex]\ge[/tex]).

Prove it! Sia [tex]T[/tex] la teoria dei reticoli. Mostrare che se [tex]T \vDash \psi[/tex] allora [tex]T \vDash \psi^\circ[/tex].

Per ipotesi \(T\vDash \psi\implies \forall L\in \text{Mod}(T), L\vDash \psi\), ma \(L\in \text{Mod}(T^\circ)\) (segue dal fatto che \(\text{Mod}(T)= \text{Mod}(T^\circ)\) ) di conseguenza:
\(L\vDash\psi^\circ\quad\forall L\in \text{Mod}(T)\implies T\vDash\psi^\circ\)

Probabilmente non è la dimostrazione che t'aspettavi (se questa si può considerare una dimostrazione), inoltre questo risultato è così naturale che l'ho trovato molto difficile da provare. Fammi sapere se è corretto. Mi piacerebbe vedere il tuo approccio a questo esercizio.


Attenzione: Troverai dei bachi nella dimostrazione con probabilità \(=1\), non farti problemi nell'evidenziarli , spero solo non siano fatali

Avevo pensato di intraprendere un'altra strada, in cui interviene il concetto di dimostrazione (sequenza finita di assiomi della teoria atti a dimostrare la veridicità di un enunciato), ma poi ho lasciato perdere

[maurer]

Mi scuso per la mia (lunga) assenza. A me torna tutto quanto, ed è esattamente come ho fatto io. Personalmente, l'avevo trovato illuminante... e adesso che ho iniziato teoria delle categorie, vedo che è il modo corretto di affrontare l'argomento!

[salvozungri]

Grazie per aver controllato, purtroppo la teoria delle categorie non fa parte del mio piano di studi , so però che è un argomento interessantissimo, cercherò di approfondire per i fatti miei quando avrò un po' di tempo .
Se hai qualche riferimento bibliografico in proposito, sarò ben lieto di leggerlo. Grazie!

[maurer]

Ah! Non mi prendo di certo una simile responsabilità... di sicuro non dopo due giorni che ho iniziato a studiare sul MacLane. Prova a guardare qui: killing_buddha ne sa enormemente più di me!