Relazione d'ordine

[thedarkhero]

Sia $n$ un numero naturale, $X$ un insieme di $n$ elementi e $A=P(X)$ l'insieme delle parti di $X$.
Sia $R={(B,C)inA^2:EEf:B->C$iniettiva$}$.
Mostrare che $R$ è relazione d'ordine parziale.

Proprietà riflessiva:
$AABinAEEf:B->B$ iniettiva. VERO
Proprietà transitiva:
$EEf:B->C$ iniettiva,$EEf:C->D$iniettiva$=>EEf:B->D$iniettiva. VERO
Proprietà antisimmetrica:
$EEf:B->C$iniettiva,$EEf:C->B$iniettiva$=>B=C$. FALSO

[adaBTTLS1]

chiedi conferma?
credi di aver finito oppure chiedi come continuare?
il fatto che esista una funzione iniettiva da $B$ a $C$ equivale a dire che $|B|<=|C|$,
e dunque provare che la relazione è d'ordine parziale è equivalente a individuare il reticolo dei sottoinsiemi di $X$.
queste cose per me sono vecchi ricordi...

[thedarkhero]

Chiedo conferma del fatto che la relazione non gode della proprietà antisimmetrica.
Il fatto che esista una funzione iniettiva da B a C ma anche una funzione iniettiva da C a B indica che B e C hanno la stessa cardinalità ma non che B=C.
Ma allora la relazione non è d'ordine e il testo si contraddice.
Confermate?

[adaBTTLS1]

esatto, ma ti dice che è una relazione d'ordine parziale, non totale.

[thedarkhero]

Si, ma perchè me lo dici?
Cioè, in ogni caso deve godere della proprietà antisimmetrica no?

[adaBTTLS1]

perché mi ricordavo la struttura di reticolo, di cui gode l'insieme delle parti.
ma quella vale se si parla di ordine stretto.
ho controllato su internet la questione, ed effettivamente se si parla genericamente di funzione "iniettiva" (che quindi può anche essere biunivoca), hai perfettamente ragione. ho il sospetto che qui si intenda "funzioni iniettive non suriettive", in tal caso la relazione è antiriflessiva, antisimmetrica, transitiva, e non è un ordine totale.
scusami se ti ho portato fuori strada.

[thedarkhero]

A parte che l'esercizio parla di funzioni iniettive (indipendentemente dal fatto che siano suriettive) ma nei punti successivi dice: dimostrare che la relazione è di ordine totale e trovarne i massimi e i minimi...

[adaBTTLS1]

bene...! allora non ci ho capito nulla...
ti posso solo dire che con l'altra interpretazione max e min esistono, ma non è un ordine totale.
sei certo del testo dell'esercizio e delle definizioni che dà sul testo su alcune paroline chiave?

[thedarkhero]

se l'altra interpretazione è che la funzione sia iniettiva e non suriettiva direi di no...intendevi questa?

[adaBTTLS1]

sì, intendevo questa.

sono andata a spulciare tra le mie vecchie dispense di algebra, e lì ho trovato che parla, in un esempio senza dimostrazione, di insieme ordinato a proposito dell'insieme delle parti di un insieme, ma mediante la relazione di "inclusione"...