Relazione riflessiva, transitiva, connessa, simmetrica e antisimmetrica
Ciao a tutti chi mi potrebbe aiutare a capire il perchè e come debba dare valori a x, y per dimostrare che una relazione su N sia riflessiva, antisimmetrica, transitiva, connessa e simmetrica?
Ad esempio su questa relazione come potrei fare: R={(x,y)| x$<=$y $vv$ x=2y}
Ad esempio su questa relazione come potrei fare: R={(x,y)| x$<=$y $vv$ x=2y}
Risposte
Assumiamo che una relazione $R$ su un dominio $D$ (non vuoto) abbia tutte quelle proprietà da te elencate.
Ora prendiamo a caso $x, y in D$. Se si ha $xRy$ segue che $yRx$ (perché simmetrica) e segue quindi anche che $x = y$ (perché antisimmetrica). Quindi
$xRy -> x = y$.
Se invece $not xRy$, supponiamo per assurdo $yRx$. Se è vero questo dalla simmetria di $R$ seguirebbe $xRy$ contro l'ipotesi. Quindi deve essere vero $not yRx$. Da $not xRy ^^ not yRx$ e dalla connessione (debole) segue quindi che $x = y$. Quindi
$not xRy -> x = y$.
Perciò in ogni caso $x = y$ qualsiasi siano gli $x, y in D$, quindi $D$ deve essere un singoletto e per l'unico elemento $a$ che vi appartiene vale $aRa$ (perché $R$ riflessiva per ipotesi). In conclusione questi sono gli unici modelli logici di una relazione $R$ che sia simmetrica, antisimmetrica, connessa e riflessiva (in questi modelli composti da un unico elemento in relazione con se stesso $R$ è anche transitiva dato che sarà vero che $aRa ^^ aRa -> aRa$). Non so se era questo che volevi sapere.
Più in generale data una qualsiasi $R in P(N^2)$ tutte le sottostrutture di $(N, R)$ (con $N$ sostegno o dominio di $R$) che godono delle proprietà da te elencate sono quelle presenti nell'insieme $A = {({a}, {(a, a)}) | a in N ^^ aRa}$. Se la relazione $R$ è antiriflessiva allora non ne esistono proprio di sottostrutture di questo tipo e $A$ è vuoto.
Osservazione: se $R$ è la relazione del tuo esempio le sotto strutture di $(N, R)$ riflessive, simmetriche, antisimmetriche, connesse (e conseguentemente transitive) sono tutte e sole quelle della forma $({a}, {(a,a)})$ con $a in N$.
P. S. Mi sono riferito alla proprietà di connessione debole per rispondere al quesito, appena ho tempo rispondo anche nel caso in cui ci si riferisce alla connessione forte.
Ora prendiamo a caso $x, y in D$. Se si ha $xRy$ segue che $yRx$ (perché simmetrica) e segue quindi anche che $x = y$ (perché antisimmetrica). Quindi
$xRy -> x = y$.
Se invece $not xRy$, supponiamo per assurdo $yRx$. Se è vero questo dalla simmetria di $R$ seguirebbe $xRy$ contro l'ipotesi. Quindi deve essere vero $not yRx$. Da $not xRy ^^ not yRx$ e dalla connessione (debole) segue quindi che $x = y$. Quindi
$not xRy -> x = y$.
Perciò in ogni caso $x = y$ qualsiasi siano gli $x, y in D$, quindi $D$ deve essere un singoletto e per l'unico elemento $a$ che vi appartiene vale $aRa$ (perché $R$ riflessiva per ipotesi). In conclusione questi sono gli unici modelli logici di una relazione $R$ che sia simmetrica, antisimmetrica, connessa e riflessiva (in questi modelli composti da un unico elemento in relazione con se stesso $R$ è anche transitiva dato che sarà vero che $aRa ^^ aRa -> aRa$). Non so se era questo che volevi sapere.
Più in generale data una qualsiasi $R in P(N^2)$ tutte le sottostrutture di $(N, R)$ (con $N$ sostegno o dominio di $R$) che godono delle proprietà da te elencate sono quelle presenti nell'insieme $A = {({a}, {(a, a)}) | a in N ^^ aRa}$. Se la relazione $R$ è antiriflessiva allora non ne esistono proprio di sottostrutture di questo tipo e $A$ è vuoto.
Osservazione: se $R$ è la relazione del tuo esempio le sotto strutture di $(N, R)$ riflessive, simmetriche, antisimmetriche, connesse (e conseguentemente transitive) sono tutte e sole quelle della forma $({a}, {(a,a)})$ con $a in N$.
P. S. Mi sono riferito alla proprietà di connessione debole per rispondere al quesito, appena ho tempo rispondo anche nel caso in cui ci si riferisce alla connessione forte.
Assumiamo che la connessione sia forte ossia $ (xRy vv yRx) forall x,y in D$ con $D$ non vuoto.
Supponiamo per assurdo che sia vero $not aRb$ per $a, b in D$, come prima, se fosse $bRa$ dalla simmetria si otterrebbe $aRb$, quindi deve essere vero per forza $not bRa$, ma se è così sarebbe vero $not aRb ^^ not bRa$ contro la connessione. Quindi dati $a, b in D$ deve essere per forza $aRb$. In conclusione tutti sono in relazione con tutti... Simmetria e connessione forte implicano che tutti sono in relazione con tutti. Quindi dati $x, y in D$ deve valere sia $xRy$ che $yRx$ ma dall'antisimmetricità si ottiene che $x = y$ e come prima ricadiamo in un dominio composto da un unico elemento.
Supponiamo per assurdo che sia vero $not aRb$ per $a, b in D$, come prima, se fosse $bRa$ dalla simmetria si otterrebbe $aRb$, quindi deve essere vero per forza $not bRa$, ma se è così sarebbe vero $not aRb ^^ not bRa$ contro la connessione. Quindi dati $a, b in D$ deve essere per forza $aRb$. In conclusione tutti sono in relazione con tutti... Simmetria e connessione forte implicano che tutti sono in relazione con tutti. Quindi dati $x, y in D$ deve valere sia $xRy$ che $yRx$ ma dall'antisimmetricità si ottiene che $x = y$ e come prima ricadiamo in un dominio composto da un unico elemento.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo