Relazioni NON transitive su un insieme di tre elementi
Mi è capitato di trovare questo test per un esame di matematica generale. A mio parere la giustificazione non è per nulla ovvia ed il test era inadeguato per un compito di 90 minuti che prevede 10 domande.
Sia $mathcal{R}$ l’insieme delle relazioni binarie NON transitive sull’insieme $A = {a, b, c}$. Quale delle seguenti
asserzioni è VERA?
I. $|mathcal{R}|>=2^8$
II. $|mathcal{R}|<=2^3$
III. Per ogni $Rin\mathcal{R}$, se ${(a,b), (b,c)}inR$, allora $(a,c)$ non appartiene ad $R$
IV. Non esiste $Rin\mathcal{R}$ tale che $R$ sia simmetrica e riflessiva
V. Nessuna delle altre risposte
Answer: Nessuna delle altre risposte.
Sol.
Falsiamo la IV.
${(a,a),(b,b),(c,c),(a,b),(b,c),(b,a)(c,a)}$ è una relazione simmetrica, riflessiva ma non transitiva.
Falsiamo la III.
$S={(a,b),(b,c),(a,c),(b,a)}$ è un contro esempio infatti $(a,a)$ non appartiene ad $S$ e ciò la rende non transitiva.
Falsiamo la II, ovvero proviamo che esistono più di otto relazioni non transitive.
Per esempio, supponiamo che ${(a,b),(b,c)}=R$ con $(a,c)$ non in $R$. Allora qualsiasi estensione di $R$ ottenuta aggiungendo qualcuna delle sei coppie diverse da $(a,b),(b,c),(a,c)$, continua ad essere una relazione non transitiva. Le possibilità sono $2^6$, da cui:
$|mathcal{R}|>=2^6$
Falsiamo la I, ovvero proviamo che:
$|mathcal{R}|<2^8$
L’insieme delle relazioni binarie su un insieme di tre elementi è costituito da $2^9$ elementi, infatti:
$|mathcal{P}(A×A)|=2^(3×3)=2^9=2×2^8$
Alla luce di ciò, occorre e basta provare che esistono più relazioni transitive che relazioni non transitive.
In una relazione R non transitiva, esistono almeno una coppia di elementi del tipo $(x,y),(y,z)inR$ e $(x,z)$ non in $R$. Quindi ogni relazione non transitiva ammette almeno un’estensione transitiva (ottenuta aggiungendo tutte tali coppie).
D’altra parte, esistono relazioni transitive (come la relazione vuota o i singleton) che non sono estensioni di alcuna relazione non transitiva.
---
Osservazioni? Specie sulla I. non sono sicurissimo
Sia $mathcal{R}$ l’insieme delle relazioni binarie NON transitive sull’insieme $A = {a, b, c}$. Quale delle seguenti
asserzioni è VERA?
I. $|mathcal{R}|>=2^8$
II. $|mathcal{R}|<=2^3$
III. Per ogni $Rin\mathcal{R}$, se ${(a,b), (b,c)}inR$, allora $(a,c)$ non appartiene ad $R$
IV. Non esiste $Rin\mathcal{R}$ tale che $R$ sia simmetrica e riflessiva
V. Nessuna delle altre risposte
Answer: Nessuna delle altre risposte.
Sol.
Falsiamo la IV.
${(a,a),(b,b),(c,c),(a,b),(b,c),(b,a)(c,a)}$ è una relazione simmetrica, riflessiva ma non transitiva.
Falsiamo la III.
$S={(a,b),(b,c),(a,c),(b,a)}$ è un contro esempio infatti $(a,a)$ non appartiene ad $S$ e ciò la rende non transitiva.
Falsiamo la II, ovvero proviamo che esistono più di otto relazioni non transitive.
Per esempio, supponiamo che ${(a,b),(b,c)}=R$ con $(a,c)$ non in $R$. Allora qualsiasi estensione di $R$ ottenuta aggiungendo qualcuna delle sei coppie diverse da $(a,b),(b,c),(a,c)$, continua ad essere una relazione non transitiva. Le possibilità sono $2^6$, da cui:
$|mathcal{R}|>=2^6$
Falsiamo la I, ovvero proviamo che:
$|mathcal{R}|<2^8$
L’insieme delle relazioni binarie su un insieme di tre elementi è costituito da $2^9$ elementi, infatti:
$|mathcal{P}(A×A)|=2^(3×3)=2^9=2×2^8$
Alla luce di ciò, occorre e basta provare che esistono più relazioni transitive che relazioni non transitive.
In una relazione R non transitiva, esistono almeno una coppia di elementi del tipo $(x,y),(y,z)inR$ e $(x,z)$ non in $R$. Quindi ogni relazione non transitiva ammette almeno un’estensione transitiva (ottenuta aggiungendo tutte tali coppie).
D’altra parte, esistono relazioni transitive (come la relazione vuota o i singleton) che non sono estensioni di alcuna relazione non transitiva.
---
Osservazioni? Specie sulla I. non sono sicurissimo
Risposte
Errata corrige...
La relazione simmetrica e riflessiva ma non transitiva su ${a,b,c}$ è la seguente:
${(a,a),(b,b),(c,c),(a,b),(b,c),(c,b),(b,a)}$
La relazione simmetrica e riflessiva ma non transitiva su ${a,b,c}$ è la seguente:
${(a,a),(b,b),(c,c),(a,b),(b,c),(c,b),(b,a)}$
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo