Esempio POSET
Ciao ragazzi, avrei bisogno di un vostro parere che mi sta mandando in confusione.
Sia $A={2,3,4,5,6,60}$ un insieme parzialmente ordinato dalla relazione d'ordine:
$xRy hArr x|y$, cioè x divide y.
Si mostra facilmente che è un insieme parzialmente ordinato (vale riflessiva, transitiva e antisimmetrica).
Adesso mi chiedo se questo insieme è completo.
Un poset $a$ è completo se $AA b sube a EE vvb$, dove $vvb=$sup(b)=minimo dei maggioranti di b
Un elemento m è maggiorante dell'insieme b se $AA x in b rArr x|m$
Io risponderei che è completo. Ogni sottoinsieme ha un sup come da definizione (che nella maggior parte dei casi è 60)!
Eppure la prof ha dimostrato che un poset completo ha un minimo. In questo caso chi è il minimo? Se prendo 2, non posso dire che 2|3 (cioè 2<3) quindi non sarà di certo un minimo! E così con tutti gli altri elementi. Non esiste il minimo, cioè quell'elemento piu piccolo di tutti perchè non tutti gli elementi sono confrontabili tra loro! Se ci fosse 1 sarebbe lui il minimo, ma non è nell'insieme. Dov'è l'errore? Forse non è completo l'insieme?
Grazie mille
Sia $A={2,3,4,5,6,60}$ un insieme parzialmente ordinato dalla relazione d'ordine:
$xRy hArr x|y$, cioè x divide y.
Si mostra facilmente che è un insieme parzialmente ordinato (vale riflessiva, transitiva e antisimmetrica).
Adesso mi chiedo se questo insieme è completo.
Un poset $a$ è completo se $AA b sube a EE vvb$, dove $vvb=$sup(b)=minimo dei maggioranti di b
Un elemento m è maggiorante dell'insieme b se $AA x in b rArr x|m$
Io risponderei che è completo. Ogni sottoinsieme ha un sup come da definizione (che nella maggior parte dei casi è 60)!
Eppure la prof ha dimostrato che un poset completo ha un minimo. In questo caso chi è il minimo? Se prendo 2, non posso dire che 2|3 (cioè 2<3) quindi non sarà di certo un minimo! E così con tutti gli altri elementi. Non esiste il minimo, cioè quell'elemento piu piccolo di tutti perchè non tutti gli elementi sono confrontabili tra loro! Se ci fosse 1 sarebbe lui il minimo, ma non è nell'insieme. Dov'è l'errore? Forse non è completo l'insieme?
Grazie mille
Risposte
Ma sei sicuro che abbia dimostrato che un poset completo ha minimo? Non era un reticolo completo magari?
Purtroppo non so cosa sia un reticolo.
La dimostrazione è abbastanza elementare:
Il minimo del nostro poset completo $a$ è proprio sup($\emptyset$)
Infatti:
sup($\emptyset$) $= min{y in a | x<=y AA x in \emptyset} = min {y in A}$ e so che esiste proprio perchè l’insieme $a$ essendo completo mi garantisce l’esistenza del sup di tutti i suoi sottoinsiemi (compreso $\emptyset$).
Non ti convince?
La dimostrazione è abbastanza elementare:
Il minimo del nostro poset completo $a$ è proprio sup($\emptyset$)
Infatti:
sup($\emptyset$) $= min{y in a | x<=y AA x in \emptyset} = min {y in A}$ e so che esiste proprio perchè l’insieme $a$ essendo completo mi garantisce l’esistenza del sup di tutti i suoi sottoinsiemi (compreso $\emptyset$).
Non ti convince?
Si ok scusa stavo pensando un po' ad un'altra cosa, allora quello che hai portato ad esempio non è completo, non ti torna?
Non è completo: è proprio il vuoto a non avere sup, perché quel poset non ha minimo (2 e 3 sono inconfrontabili).
Giusto!! Mi era sfuggito di controllare il vuoto! Ma appunto avevo notato che non c’era minimo.
Ovviamente ho dimostrato “Completo —> esiste minimo” e quindi vale la contronominale “non esiste minimo —> non completo”
Quindi se definisco $A={1,2,3,4,5,6,60}$ con la stessa relazione d’ordine, questo sarebbe un insieme parz ordinato e completo. Giusto?
Grazie mille!!
Ovviamente ho dimostrato “Completo —> esiste minimo” e quindi vale la contronominale “non esiste minimo —> non completo”
Quindi se definisco $A={1,2,3,4,5,6,60}$ con la stessa relazione d’ordine, questo sarebbe un insieme parz ordinato e completo. Giusto?
Grazie mille!!
Sì, 1 è il minimo.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo