[RISOLTO] CPO e reticoli
Ciao a tutti, ero alle prese con l'esercizio di cui posto il testo, ma temo di aver trovato un controesempio, e sottopongo la questione a qualche volenteroso.
Testo Sia \(\displaystyle (A,\le)\) un cpo tale che, per ogni coppia di elementi \(\displaystyle a_1 \) ed \(\displaystyle a_2 \) esiste \(\displaystyle a_1 \sqcup a_2 \) (least upper bound). Dimostrare che se \(\displaystyle A \) è finito allora è un reticolo.
Nella definizione di CPO considero che \(\displaystyle \bot \in A \) perché \(\displaystyle \sqcup \emptyset = \bot \), ma a me pare che quanto rappresentato sotto sia un CPO finito ma non un reticolo
Spero che il disegno sia comprensibile (se esistono metodi migliori di rappresentazione sono aperto a suggerimenti
). Mi chiedo: esiste \(\displaystyle a \sqcap b \)?
Testo Sia \(\displaystyle (A,\le)\) un cpo tale che, per ogni coppia di elementi \(\displaystyle a_1 \) ed \(\displaystyle a_2 \) esiste \(\displaystyle a_1 \sqcup a_2 \) (least upper bound). Dimostrare che se \(\displaystyle A \) è finito allora è un reticolo.
Nella definizione di CPO considero che \(\displaystyle \bot \in A \) perché \(\displaystyle \sqcup \emptyset = \bot \), ma a me pare che quanto rappresentato sotto sia un CPO finito ma non un reticolo
a b
|\/|
|/\|
c d
\ /
\(\displaystyle \bot \)
|\/|
|/\|
c d
\ /
\(\displaystyle \bot \)
Spero che il disegno sia comprensibile (se esistono metodi migliori di rappresentazione sono aperto a suggerimenti
). Mi chiedo: esiste \(\displaystyle a \sqcap b \)?
Risposte
Ciao,
bisogna stare un attimo attenti.
Infatti:
stai dando per scontato che sia un pointed cpo, cioè un CPO con l'elemento minimo bottom. Ma non dovrebbe fare molta differenza in questo caso. Poi te stai cercando di dimostrare che un CPO è un reticolo completo. In generale cosa falsa. E' vero il contrario, in generale, un reticolo completo è un CPO.
Così, a braccia, ti direi di passare per il fatto che se un insieme è finito ha sottinsiemi finiti, per implicazione (dato che è garantito essere un CPO) hai catene finite (il problema nasce se ci sono catene infinite). Unca catena finita ed ogni sottoinsieme finito ha sia lub che glb (in A). Da questo passi per la definizione di reticolo e dovresti concludere. Quasi certamente non puoi dimostrarne la completezza.
Ora, dovrei controllare se è corretto ciò che ho scritto perchè non ho mai pensato ad un'implicazione inversa.
"deino":
Ciao a tutti, ero alle prese con l'esercizio di cui posto il testo, ma temo di aver trovato un controesempio, e sottopongo la questione a qualche volenteroso.
Testo Sia \(\displaystyle (A,\le)\) un cpo tale che, per ogni coppia di elementi \(\displaystyle a_1 \) ed \(\displaystyle a_2 \) esiste \(\displaystyle a_1 \sqcup a_2 \) (least upper bound). Dimostrare che se \(\displaystyle A \) è finito allora è un reticolo.
bisogna stare un attimo attenti.
Infatti:
Nella definizione di CPO considero che \(\displaystyle \bot \in A \) perché \(\displaystyle \sqcup \emptyset = \bot \), ma a me pare che quanto rappresentato sotto sia un CPO finito ma non un reticolo
..
Mi chiedo: esiste \(\displaystyle a \sqcap b \)?
stai dando per scontato che sia un pointed cpo, cioè un CPO con l'elemento minimo bottom. Ma non dovrebbe fare molta differenza in questo caso. Poi te stai cercando di dimostrare che un CPO è un reticolo completo. In generale cosa falsa. E' vero il contrario, in generale, un reticolo completo è un CPO.
Così, a braccia, ti direi di passare per il fatto che se un insieme è finito ha sottinsiemi finiti, per implicazione (dato che è garantito essere un CPO) hai catene finite (il problema nasce se ci sono catene infinite). Unca catena finita ed ogni sottoinsieme finito ha sia lub che glb (in A). Da questo passi per la definizione di reticolo e dovresti concludere. Quasi certamente non puoi dimostrarne la completezza.
Ora, dovrei controllare se è corretto ciò che ho scritto perchè non ho mai pensato ad un'implicazione inversa.
Innanzitutto, grazie per la risposta. Comincio facendo ammenda, perché mi sono accorto che il mio controesempio nel primo post non funziona: si tratta di un CPO, ma non vale la proprietà aggiuntiva di un LUB per ogni coppia.
Il fatto di utilizzare la definizione di CPO con \(\displaystyle \bot \) è data dalla necessità di eliminare il seguente caso
che è un CPO con LUB per ogni coppia ma non è un reticolo perché non esiste \(\displaystyle a \sqcap d \). Ho trovato la definizione con \(\displaystyle \bot \) in letteratura, ad esempio in Davey, Priestley, Introduction to Lattices and Order Theory.
Quello che mi si chiede di dimostrare è che se un CPO ha least upper bound per ogni coppia ed è finito, allora è un reticolo (completo). L'unica cosa che non mi è ovvia è come mostrare che il GLB esiste sempre, ed in particolare per elementi non confrontabili, che non possono stare nella stessa catena.
Il fatto di utilizzare la definizione di CPO con \(\displaystyle \bot \) è data dalla necessità di eliminare il seguente caso
c / \ / \ a d
che è un CPO con LUB per ogni coppia ma non è un reticolo perché non esiste \(\displaystyle a \sqcap d \). Ho trovato la definizione con \(\displaystyle \bot \) in letteratura, ad esempio in Davey, Priestley, Introduction to Lattices and Order Theory.
Quello che mi si chiede di dimostrare è che se un CPO ha least upper bound per ogni coppia ed è finito, allora è un reticolo (completo). L'unica cosa che non mi è ovvia è come mostrare che il GLB esiste sempre, ed in particolare per elementi non confrontabili, che non possono stare nella stessa catena.
"deino":
Quello che mi si chiede di dimostrare è che se un CPO ha least upper bound per ogni coppia ed è finito, allora è un reticolo (completo). L'unica cosa che non mi è ovvia è come mostrare che il GLB esiste sempre, ed in particolare per elementi non confrontabili, che non possono stare nella stessa catena.
Uso le notazioni del Davey
Sia $L$ il nostro CPO. Dall'esistenza del LUB per ogni coppia di elementi segue l'esistenza dell'estremo superiore per ogni sottoinsieme finito. Considera una coppia di elementi ${x,y}$. Denotiamo con ${x,y}^l$ ($l$ sta per lower bounds) l'insieme ${t \in L : t <= x$ e $t <= y}$ dei minoranti di ${x,y}$. Questo insieme non è vuoto poichè $\bot \in {x,y}^l$ ed è finito, quindi ammette estremo superiore $z = \bigvee {x,y}^l$. Mostriamo che $z$ è il GLB di ${x,y}$. Infatti $x$ è un maggiorante dell'insieme ${x,y}^l$ e per la definizione di estremo superiore risulta $z <= x$. Con analogo ragionamento $z <= y$ , quindi $z \in {x,y}^l$ ovvero $z = max({x,y}^l)$ cioè $z = GLB({x,y})$
"perplesso":
Sia $L$ il nostro CPO. Dall'esistenza del LUB per ogni coppia di elementi segue l'esistenza dell'estremo superiore per ogni sottoinsieme finito. Considera una coppia di elementi ${x,y}$. Denotiamo con ${x,y}^l$ ($l$ sta per lower bounds) l'insieme ${t \in L : t <= x$ e $t <= y}$ dei minoranti di ${x,y}$. Questo insieme non è vuoto poichè $\bot \in {x,y}^l$ ed è finito, quindi ammette estremo superiore $z = \bigvee {x,y}^l$. Mostriamo che $z$ è il GLB di ${x,y}$. Infatti $x$ è un maggiorante dell'insieme ${x,y}^l$ e per la definizione di estremo superiore risulta $z <= x$. Con analogo ragionamento $z <= y$ , quindi $z \in {x,y}^l$ ovvero $z = max({x,y}^l)$ cioè $z = GLB({x,y})$
Wow, è proprio ciò che stavo cercando.
Ti ringrazio!
@perplesso: chapeau!
"perplesso":
Uso le notazioni del Davey
Sia $L$ il nostro CPO. Dall'esistenza del LUB per ogni coppia di elementi segue l'esistenza dell'estremo superiore per ogni sottoinsieme finito. Considera una coppia di elementi ${x,y}$. Denotiamo con ${x,y}^l$ ($l$ sta per lower bounds) l'insieme ${t \in L : t <= x$ e $t <= y}$ dei minoranti di ${x,y}$. Questo insieme non è vuoto poichè $\bot \in {x,y}^l$ ed è finito, quindi ammette estremo superiore $z = \bigvee {x,y}^l$. Mostriamo che $z$ è il GLB di ${x,y}$. Infatti $x$ è un maggiorante dell'insieme ${x,y}^l$ e per la definizione di estremo superiore risulta $z <= x$. Con analogo ragionamento $z <= y$ , quindi $z \in {x,y}^l$ ovvero $z = max({x,y}^l)$ cioè $z = GLB({x,y})$
Stavo ripensando a questa dimostrazione, e mi è sorto un dubbio... a me sembra che valga anche per insiemi infiniti. Infatti l'insieme ha minimo, quindi per ogni $x,y$ avremo che ${x,y}^l$ è finito, e quindi ammette LUB. Sbaglio?
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo