Proprietà insieme parzialmente ordinato
Sia $P$ un insieme e sia $\le$ una relazione d'ordine parziale su definita su $P$.
Si supponga inoltre che per ogni $a,b \in P$ siano definiti $"inf"{a,b}$ e $"sup"{a,b}$.
Ho dimostrato che valgono le leggi di assorbimento:
$"inf"{a,"sup"{a,b}}=a$ in quanto $a \le "sup"{a,b}$;
$"sup"{a,"inf"{a,b}}=a$ in quanto $"inf"{a,b} \le a$.
Dovrebbero valere anche le proprietà commutative:
$"inf"{a,b}=inf{b,a}$;
$"sup"{a,b}="sup"{b,a}$.
Mi chiedevo se è possibile dimostrare anche le proprietà associative:
$"inf"{a,"inf"{b,c}}="inf"{"inf"{a,b},c}$;
$"sup"{a,"sup"{b,c}}="sup"{"sup"{a,b},c}$.
Si supponga inoltre che per ogni $a,b \in P$ siano definiti $"inf"{a,b}$ e $"sup"{a,b}$.
Ho dimostrato che valgono le leggi di assorbimento:
$"inf"{a,"sup"{a,b}}=a$ in quanto $a \le "sup"{a,b}$;
$"sup"{a,"inf"{a,b}}=a$ in quanto $"inf"{a,b} \le a$.
Dovrebbero valere anche le proprietà commutative:
$"inf"{a,b}=inf{b,a}$;
$"sup"{a,b}="sup"{b,a}$.
Mi chiedevo se è possibile dimostrare anche le proprietà associative:
$"inf"{a,"inf"{b,c}}="inf"{"inf"{a,b},c}$;
$"sup"{a,"sup"{b,c}}="sup"{"sup"{a,b},c}$.
Risposte
Sì, è possibile mostrare che \(\_\lor\_ : P\times P \to P : (x,y)\mapsto \sup\{x,y\}\) definisce una operazione binaria associativa (e altrettanto fa \(\_\land\_ : P\times P \to P : (x,y)\mapsto \inf\{x,y\}\)) usando unicamente la proprietà universale di \(\inf\) e \(\sup\). E' un esercizio elementare, prova a farlo!
Qual'è la proprietà universale di $"inf"$ e $"sup"$?
Qual è la definizione di inf e sup?
Si dice che $x="inf"{a,b}$ se:
$x \le a$ e $x \le b$;
per ogni $z \in P$ tale che $z \le a$ e $z \le b$ si ha che $z \le x$.
Analogamente, si dice che $y="sup"{a,b}$ se:
$a \le y$ e $b \le y$;
per ogni $z \in P$ tale che $a \le z$ e $b \le z$ si ha che $y \le z$.
$x \le a$ e $x \le b$;
per ogni $z \in P$ tale che $z \le a$ e $z \le b$ si ha che $z \le x$.
Analogamente, si dice che $y="sup"{a,b}$ se:
$a \le y$ e $b \le y$;
per ogni $z \in P$ tale che $a \le z$ e $b \le z$ si ha che $y \le z$.
Esatto, e questo è un esempio di quella che si chiama una "proprietà universale". Dimostra che se \(\sup\{a,b\}\) soddisfa quella proprietà, allora esso è unico (in un poset). E ora dimostra che $"sup"{a,"sup"{b,c}}="sup"{"sup"{a,b},c}$ mostrando che $"sup"{a,"sup"{b,c}} \le "sup"{"sup"{a,b},c}$ e che $"sup"{a,"sup"{b,c}} \ge "sup"{"sup"{a,b},c}$, usando la proprietà che li definisce.
Si ha che $a \le "sup"{a,"sup"{b,c}}$ e che $b \le "sup"{b,c} \le "sup"{a,"sup"{b,c}}$, allora $"sup"{a,b} \le "sup"{a,"sup"{b,c}}$.
Si ha che $c \le "sup"{b,c} \le "sup"{a,"sup"{b,c}}$.
Allora $"sup"{"sup"{a,b},c} \le "sup"{a,"sup"{b,c}}$.
Si ha che $a \le "sup"{a,b} \le "sup"{"sup"{a,b},c}$.
Si ha che $b \le "sup"{a,b} \le "sup"{"sup"{a,b},c}$ e che $c \le "sup"{"sup"{a,b},c}$, allora $"sup"{b,c} \le "sup"{"sup"{a,b},c}$.
Allora $"sup"{a,"sup"{b,c}} \le "sup"{"sup"{a,b},c}$.
Quindi $"sup"{a,"sup"{b,c}} = "sup"{"sup"{a,b},c}$.
Analogamente si ottiene l'altra proprietà associativa.
Intendevi qualcosa di questo genere?
Si ha che $c \le "sup"{b,c} \le "sup"{a,"sup"{b,c}}$.
Allora $"sup"{"sup"{a,b},c} \le "sup"{a,"sup"{b,c}}$.
Si ha che $a \le "sup"{a,b} \le "sup"{"sup"{a,b},c}$.
Si ha che $b \le "sup"{a,b} \le "sup"{"sup"{a,b},c}$ e che $c \le "sup"{"sup"{a,b},c}$, allora $"sup"{b,c} \le "sup"{"sup"{a,b},c}$.
Allora $"sup"{a,"sup"{b,c}} \le "sup"{"sup"{a,b},c}$.
Quindi $"sup"{a,"sup"{b,c}} = "sup"{"sup"{a,b},c}$.
Analogamente si ottiene l'altra proprietà associativa.
Intendevi qualcosa di questo genere?
Sì, esatto. Vedi? Era facile.
Ok, grazie mille!!
Ora provo a "tornare indietro", cioè mostrare che dato un insieme $S$ dotato di due operazioni binarie $\wedge$ e $\vee$ che soddisfano le proprietà associativa, commutativa e di assorbimento è possibile definire una relazione d'ordine $\le$ su $S$ ponendo $a \le b$ se e solo se $a=a \wedge b$ e inoltre per ogni coppia di elementi $a,b \in S$ si ha che $"inf"{a,b}=a\wedgeb$ e $"sup"{a,b}=a\veeb$.
Proprietà antisimmetrica: se $a\leb$ e $b\lea$ allora $a=a\wedgeb$ e $b=b\wedgea$, quindi $a=a\wedgeb=b\wedgea=b$;
Proprietà transitiva: se $a\leb$ e $b\lec$ allora $a=a\wedgeb$ e $b=b\wedgec$, allora $a=a\wedgeb=a\wedge(b\wedgec)=(a\wedgeb)\wedgec=a\wedgec$, quindi $a\lec$.
Proprietà riflessiva: devo mostrare che $a\lea$, cioè che $a=a\wedgea$. Ho a disposizione la proprietà associativa ($a\wedge(a\wedgea)=(a\wedgea)\wedgea$ e $a\vee(a\veea)=(a\veea)\vee$) e la proprietà di assorbimento ($a\wedge(a\veea)=a$ e $a\vee(a\wedgea)=a$) ma non riesco a concludere.
Ora provo a "tornare indietro", cioè mostrare che dato un insieme $S$ dotato di due operazioni binarie $\wedge$ e $\vee$ che soddisfano le proprietà associativa, commutativa e di assorbimento è possibile definire una relazione d'ordine $\le$ su $S$ ponendo $a \le b$ se e solo se $a=a \wedge b$ e inoltre per ogni coppia di elementi $a,b \in S$ si ha che $"inf"{a,b}=a\wedgeb$ e $"sup"{a,b}=a\veeb$.
Proprietà antisimmetrica: se $a\leb$ e $b\lea$ allora $a=a\wedgeb$ e $b=b\wedgea$, quindi $a=a\wedgeb=b\wedgea=b$;
Proprietà transitiva: se $a\leb$ e $b\lec$ allora $a=a\wedgeb$ e $b=b\wedgec$, allora $a=a\wedgeb=a\wedge(b\wedgec)=(a\wedgeb)\wedgec=a\wedgec$, quindi $a\lec$.
Proprietà riflessiva: devo mostrare che $a\lea$, cioè che $a=a\wedgea$. Ho a disposizione la proprietà associativa ($a\wedge(a\wedgea)=(a\wedgea)\wedgea$ e $a\vee(a\veea)=(a\veea)\vee$) e la proprietà di assorbimento ($a\wedge(a\veea)=a$ e $a\vee(a\wedgea)=a$) ma non riesco a concludere.
\(a\land a = a\land (a \lor (a\land a))=a\)
\(a\lor a = a\lor (a \land (a\lor a))=a\)
\(a\lor a = a\lor (a \land (a\lor a))=a\)
Grazie!
Quindi a partire da un insieme $S$ con le operazioni $\wedge$ e $\vee$ che soddisfano le proprietà associativa, commutativa e di assorbimento abbiamo definito una relazione d'ordine $\le$ su $S$.
Ora come posso provare che ogni coppia $(x,y)$ di elementi di $S$ ammette $"inf"$ e $"sup"$ rispetto alla relazione $\le$?
Quindi a partire da un insieme $S$ con le operazioni $\wedge$ e $\vee$ che soddisfano le proprietà associativa, commutativa e di assorbimento abbiamo definito una relazione d'ordine $\le$ su $S$.
Ora come posso provare che ogni coppia $(x,y)$ di elementi di $S$ ammette $"inf"$ e $"sup"$ rispetto alla relazione $\le$?
Non devi farlo, hai definito le cose in modo che sia vero...
Quando da un reticolo $(S,\le)$ ho voluto costruire un reticolo $(S,\wedge,\vee)$ ho posto $x\wedgey="inf"{x,y}$ e $x\veey="sup"{x,y}$ ma quando da un reticolo $(S,\wedge,\vee)$ ho voluto costruire un reticolo $(S,\le)$ non ho mai detto chi sono $"inf"$ e $"sup"$, giusto?
Ok, ora ho capito cosa vuoi. Bastava chiederlo fin dall'inizio: vuoi dimostrare l'equivalenza tra reticoli algebrici e ordo-teoretici (?).
Il pezzo che ti manca ora è che l'ordine \(\le\) che hai definito in termini della struttura di reticolo algebrico è tale per cui \(\lor\) e \(\land\) sono rispettivamente sup e inf binari in \((S,\le)\).
Il pezzo che ti manca ora è che l'ordine \(\le\) che hai definito in termini della struttura di reticolo algebrico è tale per cui \(\lor\) e \(\land\) sono rispettivamente sup e inf binari in \((S,\le)\).
Esatto, volevo mostrare l'equivalenza tra le due definizioni di reticolo.
Ho mostrato che in $(S, \le)$ si ha che $"inf"{x,y}=x\wedgey$ e che $"sup"{x,y}=x \vee y$.
Ricapitolando il senso di tutto il thread, ho mostrato che da un reticolo definito in modo relazionale posso costruire un reticolo definito in modo algebrico e viceversa.
Non dovrei ora dimostrare anche che le due costruzioni sono una l'inversa dell'altra?
Ho mostrato che in $(S, \le)$ si ha che $"inf"{x,y}=x\wedgey$ e che $"sup"{x,y}=x \vee y$.
Ricapitolando il senso di tutto il thread, ho mostrato che da un reticolo definito in modo relazionale posso costruire un reticolo definito in modo algebrico e viceversa.
Non dovrei ora dimostrare anche che le due costruzioni sono una l'inversa dell'altra?
Sì, infatti. Qual è il problema nel farlo?
Non dovrei ora dimostrare anche che le due costruzioni sono una l'inversa dell'altra?
Se partiamo da un reticolo algebrico $(S, \wedge_1, \vee_1)$ possiamo costruire un reticolo relazionale $(S,\le)$ dove $a \le b$ se e solo se $a = a \wedge_1 b$, $"inf"{a,b}=a \wedge_1 b$ e $"sup"{a,b}=a \vee_1 b$. Se ora da questo reticolo relazionale $(S,\le)$ torniamo indietro otteniamo un reticolo algebrico $(S, \wedge_2, \vee_2)$ in cui $a \wedge_2 b = "inf"{a,b}= a \wedge_1 b$ e $a \vee_2 b = "sup"{a,b} = a \vee_1 b$. Quindi tutto funziona nel senso che $\wedge_2=\wedge1$ e $\vee_2=\vee_1$.
Se invece partiamo da un reticolo relazionale $(S,\le_1)$ possiamo costruire un reticolo algebrico $(S, \wedge, \vee)$ dove $a \wedge b = "inf"_1{a,b}$ e $a \vee b = "sup"_1{a,b}$. Se ora da questo reticolo algebrico $(S, \wedge, \vee)$ torniamo indietro otteniamo un reticolo relazionale $(S, \le_2)$ dove $a \le_2 b$ se e solo se $a = a \wedge b$, $"inf"_2{a,b}=a \wedge b = "inf"_1{a,b}$ e $"sup"_2{a,b}=a \vee b="sup"_1{a,b}$.
Il mio dubbio è su come dimostrare che $\le_2 = \le_1$.
Forse basta osservare che $a \le_2 b$ se e solo se $a=a\wedgeb$ se e solo se $a="inf"_1{a,b}$ se e solo se $a \le_1 b$. Cosa dici?
Se invece partiamo da un reticolo relazionale $(S,\le_1)$ possiamo costruire un reticolo algebrico $(S, \wedge, \vee)$ dove $a \wedge b = "inf"_1{a,b}$ e $a \vee b = "sup"_1{a,b}$. Se ora da questo reticolo algebrico $(S, \wedge, \vee)$ torniamo indietro otteniamo un reticolo relazionale $(S, \le_2)$ dove $a \le_2 b$ se e solo se $a = a \wedge b$, $"inf"_2{a,b}=a \wedge b = "inf"_1{a,b}$ e $"sup"_2{a,b}=a \vee b="sup"_1{a,b}$.
Il mio dubbio è su come dimostrare che $\le_2 = \le_1$.
Forse basta osservare che $a \le_2 b$ se e solo se $a=a\wedgeb$ se e solo se $a="inf"_1{a,b}$ se e solo se $a \le_1 b$. Cosa dici?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo