Quesito sugli ordinamenti deboli (weak orders)
Ciao a tutt*
in un articolo che sto leggendo ho trovato una definizione di weak order su $X$ come una relazione binaria transitiva e completa su $X$. Dato che la relazione è completa viene detto che è riflessiva. Questa cosa non mi torna molto. Se così fosse la relazione $>$ su qualunque insieme numerico non sarebbe un weak order o sbaglio?
Sempre nello stesso articolo si legge che se si aggiunge l'antisimmetria si ha un linear order e più oltre che un weak order può essere linearizzato in più modi diversi. Mi sono perso. Qualcuno può chiarirmi le idee magari dandomi qualche indicazione bibliografica di base?
Grazie.
Lorenzo
in un articolo che sto leggendo ho trovato una definizione di weak order su $X$ come una relazione binaria transitiva e completa su $X$. Dato che la relazione è completa viene detto che è riflessiva. Questa cosa non mi torna molto. Se così fosse la relazione $>$ su qualunque insieme numerico non sarebbe un weak order o sbaglio?
Sempre nello stesso articolo si legge che se si aggiunge l'antisimmetria si ha un linear order e più oltre che un weak order può essere linearizzato in più modi diversi. Mi sono perso. Qualcuno può chiarirmi le idee magari dandomi qualche indicazione bibliografica di base?

Grazie.

Lorenzo

Risposte
"fulcanelli":1 simmetria e asimmetria sono incompatibili,
Quanto segue funziona, ovviamente, se assumi LEM. L'altra si fa allo stesso modo.
Asimmetria significa che se \(R(a,b)\) allora \(\lnot R(b,a)\), simmetria significa che \(R(a,b) \iff R(b,a)\); supponi che \(R\) sia una relazione simmetrica e asimmetrica allo stesso tempo; allora per ogni (a,b) tale che \(R(a,b)\) deve valere
\[R(a,b) \Rightarrow \big(R(b,a)\land \lnot R(b,a)\big) \, = \, R(a,b) \Rightarrow \perp \,\, =\,\, \perp\]perché per ogni funzione proposizionale \(p\), \(p \Rightarrow \perp \,=\, \perp\), dove \(\perp\) è la proposizione costantemente falsa.
Perciò, l'unica relazione allo stesso tempo simmetrica e asimmetrica è la relazione vuota.
Ciao
grazie infinite. Mi pare di avere capito ammesso che il simbolo $=$ vada letto come "equivale a".
Un dubbio che mi è venuto dopo aver fatto il post precedente: per dimostrare che simmetria e antisimmetria sono compatibili non basta trovare una relazione che le soddisfa entrambe tipo la relazione $>=$?
Lorenzo

Avevo letto "incompatibili" anche nella seconda; simmetria e antisimmetria sono "compatibili" nel senso che esistono relazioni non vuote che soddisfano entrambe le proprietà, ma sono abbastanza banali...
"fulcanelli":
Avevo letto "incompatibili" anche nella seconda; simmetria e antisimmetria sono "compatibili" nel senso che esistono relazioni non vuote che soddisfano entrambe le proprietà, ma sono abbastanza banali...
cosa intendi per "banali"? Lo sono ad esempio $>=$ e simili sia sui numeri sia sugli insiemi.

L.

\(\ge\) è antisimmetrica; non è simmetrica.
"fulcanelli":
\(\ge\) è antisimmetrica; non è simmetrica.
Ok, vero.. detto una cavolata.
Un'altra cosa: sempre sul Roberts ho letto che se una relazione è asimmetrica allora è antisimmetrica ma la cosa mi lascia un po' perplesso. La relazione "padre di" è ovviamente asimmetrica ma che sia antisimmetrica mi torna poco perché vorrebbe dire essere padre di se stesso, non credi? Come se ne esce?
Lorenzo

E' logichetta da terza elementare.
Una relazione è asimmetrica se e solo se è antisimmetrica e irriflessiva; asimmetrica significa che \(R(a,b)\Rightarrow \lnot R(b,a)\), quindi l'antisimmetria è vera in quanto vuota. Ora, se $R$ è asimmetrica, e \(\Delta\) è la relazione identica, deve essere \(R\cap\Delta = \varnothing\), perché altrimenti \(R(a,a) \Rightarrow \lnot R(a,a)\) per ogni \(a\in R\cap\Delta\).
Una relazione è asimmetrica se e solo se è antisimmetrica e irriflessiva; asimmetrica significa che \(R(a,b)\Rightarrow \lnot R(b,a)\), quindi l'antisimmetria è vera in quanto vuota. Ora, se $R$ è asimmetrica, e \(\Delta\) è la relazione identica, deve essere \(R\cap\Delta = \varnothing\), perché altrimenti \(R(a,a) \Rightarrow \lnot R(a,a)\) per ogni \(a\in R\cap\Delta\).
"fulcanelli":
E' logichetta da terza elementare.
Una relazione è asimmetrica se e solo se è antisimmetrica e irriflessiva; asimmetrica significa che \(R(a,b)\Rightarrow \lnot R(b,a)\), quindi l'antisimmetria è vera in quanto vuota. Ora, se $R$ è asimmetrica, e \(\Delta\) è la relazione identica, deve essere \(R\cap\Delta = \varnothing\), perché altrimenti \(R(a,a) \Rightarrow \lnot R(a,a)\) per ogni \(a\in R\cap\Delta\).
Mi scuserai ma sono in seconda (elementare)


Lorenzo

Non esiste nessuna coppia (a,b) con la proprietà che a è il padre di b, e b è il padre di a. Perciò, è vacuamente vero che se a è il padre di b, e b è il padre di a, allora \(a=b\).
Ex falso quodlibet sequitur, pater numquam.
Ex falso quodlibet sequitur, pater numquam.
"fulcanelli":
Non esiste nessuna coppia (a,b) con la proprietà che a è il padre di b, e b è il padre di a. Perciò, è vacuamente vero che se a è il padre di b, e b è il padre di a, allora \(a=b\).
Ex falso quodlibet sequitur, pater numquam.
quindi dura lex sed lex: il falso implica qualunque cosa

L.
