Partial order e catene
Salve,
vorrei chiarimi qualche dubbio o ruggine sui poset e le catene.
Scrivo le varie definizioni, così questa volta c'è tutto il necessario
DEF Se ho una struttura algebrica $(D,<=)$ che rappresenta un Poset (riflessività, antisimmetria, transitività), da cui la scrittura $d_1<=d_2$ viene letto come: $d_1$ è meno definito di $d_2$.
i diagrammi (di Hasse mi sembra) sottostanti:
1.
1 $\ \ \ $2$\ \ \ $ 3 ...
\ $\ \ \ $|$\ \ \ $ /
$\ \ \ \ $\(\perp\)
è l'insieme dei numeri naturali, dove 1,2... sono inconfrontabili e \(\perp\) è meno definito di tutti, cioè è il minimo.
2.
...
|
1
|
0
|
-1
|
...
è l'insieme dei numeri interi, con la relazioni di ordinamento $<=$
DEF Un poset P è una catena se:
$AA x,y in P\ ,\ x<=y vv y<=x$
cioè esite una relazione di total order (giusto?), e perciò tutti gli elementi sono confrontabili.
Ora lasciando da parte la definizione di well-founded, non mi è chiaro perchè gli interi sono "confrontabili" (ovvio, mi direte, per via della relazione $<=$) e invece i naturali no?
dalla defiizione di catena sui naturali:
$1<=2$ sì
$2<=1$ no
dalla definizione di catena sugli interi:
$-1<=-2$ no
$-2<=-1$ sì
embè? a vedere ciò mi vengono tanti dubbi sugli interi non mi sembrano TUTTI confrontabili e la definzione di catena se ne và (lasciando la definizione di well-founded o di esistenza del minimo da parte per un attimo).
Se non ho detto assurdità, chiedo se potete chiarirmi le idee.
Ringrazio
EDIT:
la relazione d'ordine di 1. sui naturali è la relazione di identità, l'ordinamento di questo tipo è chiamato "flat" (o discreto).
vorrei chiarimi qualche dubbio o ruggine sui poset e le catene.
Scrivo le varie definizioni, così questa volta c'è tutto il necessario
DEF Se ho una struttura algebrica $(D,<=)$ che rappresenta un Poset (riflessività, antisimmetria, transitività), da cui la scrittura $d_1<=d_2$ viene letto come: $d_1$ è meno definito di $d_2$.
i diagrammi (di Hasse mi sembra) sottostanti:
1.
1 $\ \ \ $2$\ \ \ $ 3 ...
\ $\ \ \ $|$\ \ \ $ /
$\ \ \ \ $\(\perp\)
è l'insieme dei numeri naturali, dove 1,2... sono inconfrontabili e \(\perp\) è meno definito di tutti, cioè è il minimo.
2.
...
|
1
|
0
|
-1
|
...
è l'insieme dei numeri interi, con la relazioni di ordinamento $<=$
DEF Un poset P è una catena se:
$AA x,y in P\ ,\ x<=y vv y<=x$
cioè esite una relazione di total order (giusto?), e perciò tutti gli elementi sono confrontabili.
Ora lasciando da parte la definizione di well-founded, non mi è chiaro perchè gli interi sono "confrontabili" (ovvio, mi direte, per via della relazione $<=$) e invece i naturali no?
dalla defiizione di catena sui naturali:
$1<=2$ sì
$2<=1$ no
dalla definizione di catena sugli interi:
$-1<=-2$ no
$-2<=-1$ sì
embè? a vedere ciò mi vengono tanti dubbi sugli interi non mi sembrano TUTTI confrontabili e la definzione di catena se ne và (lasciando la definizione di well-founded o di esistenza del minimo da parte per un attimo).
Se non ho detto assurdità, chiedo se potete chiarirmi le idee.
Ringrazio
EDIT:
la relazione d'ordine di 1. sui naturali è la relazione di identità, l'ordinamento di questo tipo è chiamato "flat" (o discreto).
Risposte
Ciao,
guarda io sto studiando i poset e gli ordini proprio in questo periodo, quindi mi riservo dal dare una risposta, ma la tua domanda mi ha incuriosito e c'è una cosa che non capisco: cosa vuol dire "meno definito di"?
Per il poco che so, posso solo dirti che il fatto che un insieme sia catena o anticatena dipende solo dalla relazione d'ordine di cui viene dotato quell'insieme. Dato che non ho capito quale sarebbe la relazione d'ordine di cui parli, non so davvero come risponderti
Ciauz
EDIT: Ah sì, i diagrammi sono quelli di Hasse.
guarda io sto studiando i poset e gli ordini proprio in questo periodo, quindi mi riservo dal dare una risposta, ma la tua domanda mi ha incuriosito e c'è una cosa che non capisco: cosa vuol dire "meno definito di"?
Per il poco che so, posso solo dirti che il fatto che un insieme sia catena o anticatena dipende solo dalla relazione d'ordine di cui viene dotato quell'insieme. Dato che non ho capito quale sarebbe la relazione d'ordine di cui parli, non so davvero come risponderti
Ciauz
EDIT: Ah sì, i diagrammi sono quelli di Hasse.
ti ringrazio molto della risposta
mi hai dato un input illuminante, mi ha chiarito alcune cose che avevo preso per corrette.
Ho capito che il mio dubbio non ha senso come è scritto.
guarda mi sono venuti parecchi dubbi su ciò.
Penso che su $NN$ ci sia la relazione $<$ così si garantisce la inconfrontabilità come è scritta nei Diagrammi di Hasse (grazie della conferma). Però ora ho il dubbio se la relazione fosse quella di successore, l'inconfrontabilità sarebbe comunque garantita? cioè con relazione \(x \prec y\) dove \(y=\text{succ}(x)\) o ancora meglio se c'è una relazione basata sulla divisibilità?
Poi perchè diamine sui naturali c'è la relazione di ordine totale, se su di essi non ci sono catene? (stesso discorso che dipende dalla relazione d'ordine?)
Se sai chiarimi questi dubbi, che pensavo risolti da tempo
PS:
sì è un po' una definizione apportata all'argomento che sto studiando, ma lascia stare se questo complica il riuscire a capire i miei dubbi
comunque per $x<=y$ intendo:
"$x$ approssima $y$" oppure "in $x$ c'è meno informazione di $y$"
Per il poco che so, posso solo dirti che il fatto che un insieme sia catena o anticatena dipende solo dalla relazione d'ordine di cui viene dotato quell'insieme.
mi hai dato un input illuminante, mi ha chiarito alcune cose che avevo preso per corrette.
Ho capito che il mio dubbio non ha senso come è scritto.
Dato che non ho capito quale sarebbe la relazione d'ordine di cui parli
guarda mi sono venuti parecchi dubbi su ciò.
Penso che su $NN$ ci sia la relazione $<$ così si garantisce la inconfrontabilità come è scritta nei Diagrammi di Hasse (grazie della conferma). Però ora ho il dubbio se la relazione fosse quella di successore, l'inconfrontabilità sarebbe comunque garantita? cioè con relazione \(x \prec y\) dove \(y=\text{succ}(x)\) o ancora meglio se c'è una relazione basata sulla divisibilità?
Poi perchè diamine sui naturali c'è la relazione di ordine totale, se su di essi non ci sono catene? (stesso discorso che dipende dalla relazione d'ordine?)
Se sai chiarimi questi dubbi, che pensavo risolti da tempo
PS:
cosa vuol dire "meno definito di"?
sì è un po' una definizione apportata all'argomento che sto studiando, ma lascia stare se questo complica il riuscire a capire i miei dubbi
comunque per $x<=y$ intendo:
"$x$ approssima $y$" oppure "in $x$ c'è meno informazione di $y$"
Ti premetto innanzi tutto che (mi baso su quanto ho capito dal tuo profilo) anche io studio informatica quindi non farti scrupoli a dirmi cosa intendi per "meno definito" 
Anzi, qualsiasi richiamo all'informatica mi interessa particolarmente.
Poi mi scuso se non colgo immediatamente le convenzioni, perché sono piuttosto inesperto e ogni volta che leggo qualcosa di nuovo trovo le relazioni d'ordine con simboli diversi
Attenzione a non confondere la relazione d'ordine $<$ con quella di copertura $\prec$ (uso questo simbolo perché questo forum non sembra supportare quello che uso di solito).
I diagrammi di Hasse usano le relazioni di copertura (per gli archi) e non quelle d'ordine. In breve la relazione di copertura dice che non può esserci un altro elemento "in mezzo" a due elementi se questi sono in relazione.
Da quanto ho capito, la copertura $\prec$ è definita per mezzo della relazione d'ordine di cui è dotato l'insieme in questione, con la condizione che non debba esistere, appunto, un elemento in mezzo e i due elementi debbano essere distinti.
Sui naturali e sugli interi, la relazione di copertura corrisponde al successore: $a \prec b \iff b = \text{succ}(a)$
La relazione di copertura definita dal successore vale in ugual modo sia su $NN$ che su $ZZ$, quindi i due diagrammi dovrebbero essere entrambi lineari ed entrambi $NN$ e $ZZ$ sarebbero ordinati nel modo classico tramite $<$ e quindi la relazione sarebbe totale (tutti confrontabili).
Un insieme che è totalmente ordinato È una catena Infatti si dice anche che è linearmente ordinato... Certo, il fatto che l'insieme sia o meno una catena dipende dalla relazione d'ordine che si usa. $(NN;\leq)$ ad esempio è la classica catena dei naturali.
Chiaramente puoi definire una relazione d'ordine basata sulla divisione (che indico con $|$), in cui $a | b \iff \exists r : a\cdot r = b$, e questa relazione d'ordine porterebbe ad un ordine non lineare (non tutti i naturali sono divisibili tra loro).
A questo punto l'insieme $(NN;|)$ è ordinato dalla divisione e NON è più una catena (ma non è neanche una anticatena, dove tutti gli elementi non sono confrontabili tra loro).
Forse su $NN$ e $ZZ$ ci sarebbero delle diversità nei diagrammi, perché in $ZZ$ un numero è divisibile anche per il suo opposto, cosa che non è chiaramente possibile in $NN$, ma ad essere sincero non ho approfondito molto la divisione come ordine quindi non ti so dire molto altro a riguardo.
Ah un'ultima cosa: io non credo che tu possa usare il successore come relazione d'ordine (ed è per questo che ho detto che la copertura è definita usando l'ordine che deve già esserci su un insieme), perché il successore manca di una proprietà che è fondamentale per gli ordini: la transitività! Infatti $2 = \text{succ}(1)$ e $3 = \text{succ}(2)$ ma $3 \ne \text{succ}(1)$.
Spero di essere stato utile!
Ciauz
Anzi, qualsiasi richiamo all'informatica mi interessa particolarmente.Poi mi scuso se non colgo immediatamente le convenzioni, perché sono piuttosto inesperto e ogni volta che leggo qualcosa di nuovo trovo le relazioni d'ordine con simboli diversi
Attenzione a non confondere la relazione d'ordine $<$ con quella di copertura $\prec$ (uso questo simbolo perché questo forum non sembra supportare quello che uso di solito).
I diagrammi di Hasse usano le relazioni di copertura (per gli archi) e non quelle d'ordine. In breve la relazione di copertura dice che non può esserci un altro elemento "in mezzo" a due elementi se questi sono in relazione.
Da quanto ho capito, la copertura $\prec$ è definita per mezzo della relazione d'ordine di cui è dotato l'insieme in questione, con la condizione che non debba esistere, appunto, un elemento in mezzo e i due elementi debbano essere distinti.
Sui naturali e sugli interi, la relazione di copertura corrisponde al successore: $a \prec b \iff b = \text{succ}(a)$
La relazione di copertura definita dal successore vale in ugual modo sia su $NN$ che su $ZZ$, quindi i due diagrammi dovrebbero essere entrambi lineari ed entrambi $NN$ e $ZZ$ sarebbero ordinati nel modo classico tramite $<$ e quindi la relazione sarebbe totale (tutti confrontabili).
Un insieme che è totalmente ordinato È una catena
Infatti si dice anche che è linearmente ordinato... Certo, il fatto che l'insieme sia o meno una catena dipende dalla relazione d'ordine che si usa. $(NN;\leq)$ ad esempio è la classica catena dei naturali.Chiaramente puoi definire una relazione d'ordine basata sulla divisione (che indico con $|$), in cui $a | b \iff \exists r : a\cdot r = b$, e questa relazione d'ordine porterebbe ad un ordine non lineare (non tutti i naturali sono divisibili tra loro).
A questo punto l'insieme $(NN;|)$ è ordinato dalla divisione e NON è più una catena (ma non è neanche una anticatena, dove tutti gli elementi non sono confrontabili tra loro).
Forse su $NN$ e $ZZ$ ci sarebbero delle diversità nei diagrammi, perché in $ZZ$ un numero è divisibile anche per il suo opposto, cosa che non è chiaramente possibile in $NN$, ma ad essere sincero non ho approfondito molto la divisione come ordine quindi non ti so dire molto altro a riguardo.
Ah un'ultima cosa: io non credo che tu possa usare il successore come relazione d'ordine (ed è per questo che ho detto che la copertura è definita usando l'ordine che deve già esserci su un insieme), perché il successore manca di una proprietà che è fondamentale per gli ordini: la transitività! Infatti $2 = \text{succ}(1)$ e $3 = \text{succ}(2)$ ma $3 \ne \text{succ}(1)$.
Spero di essere stato utile!
Ciauz
Ti devo ringraziare, mi hai chiarito alcune cose che erano nebulose e che non avevo chiarito ai tempi che le avevo viste la prima volta.
compagno informatico
se interessa, i diagrammi di Hasse, i reticoli, ordinamenti parziali, sono le basi generali su cui poggia la semantica denotazionale (cpo in primis), se conosci la "semantica dei linguaggi".
con "meno definito" si intende proprio cercare di dare "un'ordinamento" all'informazione (con uno spazio di funzioni, un insieme di regole chiuse, ecc...) per definire un linguaggio (abusando delle definizioni, non è proprio così).
un esempio carino, se vedi la mia firma:
\(\lfloor\text{Free will}\rfloor\sqsubseteq〚\text{Life}〛\)
si intende dire che, per raggiungere il significato semantico della "vita" bisogna, nel tempo, fare delle piccole scelte, lemme lemme, dettate dal "libero arbitrio"
Anche se conosco la semantica denotazionale standard, queste cose che ho chiesto non le avevo approfondite, perciò erano "nebulose"
io ne ho viste almeno quattro tipi di relazioni di ordine (o copertura che non conoscevo questo termine). Per la sem den di solito si usa \(\sqsubseteq\), almeno io ho sempre visto questo
"akiross":
Ti premetto innanzi tutto che (mi baso su quanto ho capito dal tuo profilo) anche io studio informatica
compagno informatico
quindi non farti scrupoli a dirmi cosa intendi per "meno definito"
se interessa, i diagrammi di Hasse, i reticoli, ordinamenti parziali, sono le basi generali su cui poggia la semantica denotazionale (cpo in primis), se conosci la "semantica dei linguaggi".
con "meno definito" si intende proprio cercare di dare "un'ordinamento" all'informazione (con uno spazio di funzioni, un insieme di regole chiuse, ecc...) per definire un linguaggio (abusando delle definizioni, non è proprio così).
un esempio carino, se vedi la mia firma:
\(\lfloor\text{Free will}\rfloor\sqsubseteq〚\text{Life}〛\)
si intende dire che, per raggiungere il significato semantico della "vita" bisogna, nel tempo, fare delle piccole scelte, lemme lemme, dettate dal "libero arbitrio"
Anche se conosco la semantica denotazionale standard, queste cose che ho chiesto non le avevo approfondite, perciò erano "nebulose"
"akiross":
Poi mi scuso se non colgo immediatamente le convenzioni, perché sono piuttosto inesperto e ogni volta che leggo qualcosa di nuovo trovo le relazioni d'ordine con simboli diversi
io ne ho viste almeno quattro tipi di relazioni di ordine (o copertura che non conoscevo questo termine). Per la sem den di solito si usa \(\sqsubseteq\), almeno io ho sempre visto questo
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo