Quesito sugli ordinamenti deboli (weak orders)

cionilorenzo
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? :D
Grazie. 8-)
Lorenzo 8-)

Risposte
cionilorenzo
"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 8-)

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...

cionilorenzo
"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. 8-)
L. 8-)

fulcanelli
\(\ge\) è antisimmetrica; non è simmetrica.

cionilorenzo
"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 8-)

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\).

cionilorenzo
"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) :-D e non sono un Leonardo (da Vinci) come te :-D . La mia domanda era un po' diversa ma la riformulo. Visto che asimmetria $=>$ antisimmetria la relazione "padre di" (che è asimmetrica) è antisimmetrica per quale motivo visto che non è vuota?
Lorenzo 8-)

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.

cionilorenzo
"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 :-D
L. 8-)

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.