Verificare un esercizio su relazioni di equivalenza

Messaggioda Nandone169 » 30/05/2020, 09:23

Ciao, ho cominciato a trattare le relazioni di equivalenza e sto svolgendo questo esercizio:
Dato l'insieme di caratteri \(V = { a,e,i,o,u } \)
quante relazioni diverse possono essere definite?
quante di essere sono sia simmetriche che riflessive?
fare un esempio di relazione di equivalenza r su V che soddisfi le condizioni:
\(aRe , a(NOT R)u \).
Allora per quanto riguarda il primo punto, dovrebbero essere 25 considerando tutte le
\(Riflessive, Simmetriche, Transitive \) .
Per il secondo punto,invece, dato che solo le relazioni riflessive sono anche simmetriche, dovrebbero essere 5.
Infine,per il terzo punto,dato che chiede UNA sola relazione di equivalenza che soddisfi DUE condizioni, dovrei considerare un qualsiasi sottoinsieme di V che verifichi la \(Riflessività,Simmetria,Transitività \) tra a ed e ma non tra a ed u; Per esempio: \((a.e),(a,a),(e,e),(e,a),(e,u),(a,u) \).
Questo è l'approccio correto?
Nandone169
Starting Member
Starting Member
 
Messaggio: 1 di 6
Iscritto il: 29/05/2020, 21:12

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda ProPatria » 03/06/2020, 15:47

Ciao :-D
Nandone169 ha scritto:quante relazioni diverse possono essere definite?

Allora per quanto riguarda il primo punto, dovrebbero essere 25 considerando tutte le
\(Riflessive, Simmetriche, Transitive \) .

Hai scritto relazioni, non relazioni di equivalenza. Le relazioni possibili sono tutti i possibili sottoinsiemi di $VxxV$ che è un insieme di 25 elementi, dunque sono $2^25$.

Nandone169 ha scritto:Per il secondo punto,invece, dato che solo le relazioni riflessive sono anche simmetriche, dovrebbero essere 5.

Prova a pensarci, sapendo che "riflessiva" vuol dire che, di questo insieme $VxxV$ di 25 elementi, vogliamo considerare il numero dei suoi sottoinsiemi che hanno sempre al loro interno 5 elementi (cioè $(a,a)(e,e), ...$). La condizione per la simmetria invece è che alcuni di questi elementi vadano "a coppia", ossia (ad esempio) non possiamo avere un sottoinsieme di $VxxV$ che abbia dentro solo $(a,e)$ e non $(e,a)$, dunque i due dobbiamo trattarli "come un unico elemento".

Nandone169 ha scritto:Infine,per il terzo punto,dato che chiede UNA sola relazione di equivalenza che soddisfi DUE condizioni, dovrei considerare un qualsiasi sottoinsieme di V che verifichi la \(Riflessività,Simmetria,Transitività \) tra a ed e ma non tra a ed u; Per esempio: \((a.e),(a,a),(e,e),(e,a),(e,u),(a,u) \).

Non hai capito. Una relazione su $V$ è di equivalenza se e solo se tutti gli elementi in $V$ soddisfano quelle tre proprietà. Dunque non puoi avere che a, e soddisfino le proprietà ma non u in quanto u è un elemento di $V$ (come anche i, o) ed essendo questa una relazione di equivalenza di $V$ tutti i suoi elementi devono soddisfare le tre proprietà. In altre parole nella relazione devono esserci, per la proprietà riflessiva, $(a,a), (e,e), ..., (u,u)$ (e per questo il tuo esempio non vale) altrimenti non sarebbe una relazione di equivalenza; per la simmetricità se c'è $(e,u)$ deve esserci anche $(u,e)$ (e anche per questo il tuo esempio non vale). Allo stesso modo anche la transitività deve valere sempre. Prova a ripensarci ora
《Hold on to
That light
Keep the future in sight
Or all will be lost.》
-Niwaka Ame Nimo Makezu
ProPatria
New Member
New Member
 
Messaggio: 74 di 82
Iscritto il: 02/02/2019, 12:56
Località: Italia

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda Nandone169 » 05/06/2020, 09:47

Grazie per la risposta. Per il primo punto: dato che la relazione è definita come un sottoinsieme del prodotto cartesiano, rappresentano tutte le coppie ordinate formate dagli elementi dell'insieme, quindi come potrebbero mai essere \(2^{25} \) (non so perché non mette il 5 ad esponente :smt012 ).
Per il secondo punto il dubbio è sempre lo stesso: perché un sottoinsieme deve avere più di due elementi?
Per il terzo, invece, stai dicendo praticamente che non posso definire un esempio di relazione di equivalenza \( \sim \) di quel tipo, cioè, \(a \sim e \) ma NON \(a \sim u \) ? Queste cose ancora non mi sono chiare...
Ultima modifica di gugo82 il 06/06/2020, 11:14, modificato 1 volta in totale.
Motivazione: Per inserire gli esponenti servono le parentesi.
Nandone169
Starting Member
Starting Member
 
Messaggio: 4 di 6
Iscritto il: 29/05/2020, 21:12

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda ProPatria » 06/06/2020, 02:28

Nandone169 ha scritto:Per il primo punto: dato che la relazione è definita come un sottoinsieme del prodotto cartesiano, rappresentano tutte le coppie ordinate formate dagli elementi dell'insieme, quindi come potrebbero mai essere \(2^25 \) (non so perché non mette il 5 ad esponente :smt012 ).

Il prodotto cartesiano è un insieme formato da tutte le coppie ordinate degli elementi dell'insieme. Una relazione (e non necessariamente di equivalenza) tuttavia è un sottoinsieme qualsiasi di $VxxV$ prodotto cartesiano. Dunque essendo il prodotto cartesiano formato da $5×5=25$ elementi noi vogliamo calcolare quanti sono i possibili sottoinsiemi dell'insieme $VxxV$ che ha 25 elementi. E poichè il numero di sottoinsiemi di un insieme di $n$ elementi è sempre $2^n$ (questo puoi prenderlo per buono ma ragionandoci un pò si capisce... si dimostra per induzione) allora $2^25$ è il numero di sottoinsiemi di $VxxV$ e dunque il numero delle possibili relazioni (poichè a ugni sottoinsieme del prodotto cartesiano corrisponde una sola relazione).

Per il secondo punto il dubbio è sempre lo stesso: perché un sottoinsieme deve avere più di due elementi?

In realtà deve avere almeno 5 elementi affinchè questa relazione sia riflessiva come ti chiede, dunque devono esserci come minimo $(a,a), (e,e), (i,i), (o,o), (u,u)$. In più deve valere la simmetricità

Per il terzo, invece, stai dicendo praticamente che non posso definire un esempio di relazione di equivalenza \( \sim \) di quel tipo, cioè, \(a \sim e \) ma NON \(a \sim u \) ? Queste cose ancora non mi sono chiare...

Volendo si puoi farlo, ma se c'è $a~e$ per la simmetria deve esserci anche $e~a$. Inoltre (ad esempio) se tu ci metti $a~e$ e anche $e~i$ allora per la transitività ci sarà pure $a~i$. Dunque (rimanendo sempre nell'esempio) per la simmetricità avremo anche $e~a, i~e, i~a$. E ovviamente per la riflessività non mancheranno mai $a~a, e~e, ... , u~u$.
Dimmi se non è chiaro
《Hold on to
That light
Keep the future in sight
Or all will be lost.》
-Niwaka Ame Nimo Makezu
ProPatria
New Member
New Member
 
Messaggio: 77 di 82
Iscritto il: 02/02/2019, 12:56
Località: Italia

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda Nandone169 » 06/06/2020, 07:32

ok ora è più chiaro: essendo tutte le relazioni binarie degli insiemi e degli elementi distinti, l'insieme delle parti contiene \( 2^n \) sottoinsiemi, e questo mi era proprio sfuggito :cry: .
Infine, quindi, per rispondere al terzo, dovrei prendere un sottoinsieme qualsiasi dove sono verificate tutte le proprietà per la relazione d'equivalenza con e? Ovviamente la transitività implicherà il dover inserire le relazioni con gli altri elementi: \( \{ (a,e), (a,a), (e,e), (e,a), (e,i), (i,e), (a,i) (i,a), (i,i) \} \)? Questa dovrebbe essere di equivalenza, però a quanto ho capito non mi permette di verificare che a non è in relazione con u, per questo avevo fatto quell'esempio: io posso avere una relazione d'equivalenza se sono vere tutte le proprietà, quindi, \(\{(a,a), (e,e), (a,e), (e,a) \}\) mi basterebbe questo per dire che è d'equivalenza, mentre \(\{(a,a), (e,e), (a,e)\} \) non lo è perché \(\ aRe -> eRa \) è falsa. Non so se sono stato chiaro, però sarebbe solo questo il mio dubbio ora.
Nandone169
Starting Member
Starting Member
 
Messaggio: 5 di 6
Iscritto il: 29/05/2020, 21:12

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda gugo82 » 06/06/2020, 11:24

Il fatto che la relazione sia riflessiva ti dice che essa deve contenere la diagonale di $V$, quindi deve contenere $\{ (a,a),(e,e),(i,i),(o,o),(u,u)\}$.
I sottoinsiemi di $V^2$ che contengono la coppia $(a,a)$ sono $2^(25)/2=2^(24)$; di questi, solo $2^(24)/2=2^(23)$ contengono $(e,e)$; tra questi ultimi solo $2^(22)$ contengono $(i,i)$; solo $2^(21)$ contengono anche $(o,o)$; ed infine solo $2^(20)$ contengono pure $(u,u)$. Dunque le relazioni riflessive su $V$ sono $2^(20)$.

Tra queste $2^(20)$, dobbiamo scremare quelle simmetriche, cioè quelle che $(x,y) in R => (y,x) in R$.
Qui ci si deve pensare un attimo... Ma credo che il ragionamento non sia tanto complesso.
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 24027 di 24337
Iscritto il: 12/10/2007, 23:58
Località: Napoli

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda ProPatria » 06/06/2020, 14:46

Nandone169 ha scritto:Infine, quindi, per rispondere al terzo, dovrei prendere un sottoinsieme qualsiasi dove sono verificate tutte le proprietà per la relazione d'equivalenza con e? Ovviamente la transitività implicherà il dover inserire le relazioni con gli altri elementi: \( \{ (a,e), (a,a), (e,e), (e,a), (e,i), (i,e), (a,i) (i,a), (i,i) \} \)? Questa dovrebbe essere di equivalenza, però a quanto ho capito non mi permette di verificare che a non è in relazione con u, per questo avevo fatto quell'esempio: io posso avere una relazione d'equivalenza se sono vere tutte le proprietà, quindi, \(\{(a,a), (e,e), (a,e), (e,a) \}\) mi basterebbe questo per dire che è d'equivalenza, mentre \(\{(a,a), (e,e), (a,e)\} \) non lo è perché \(\ aRe -> eRa \) è falsa. Non so se sono stato chiaro, però sarebbe solo questo il mio dubbio ora.

Si credo che hai capito bene. Gli esempi che hai fatto sono quasi validi ma come dice @gugo82 in una relazione di equivalenza non può mai mancare la diagonale. Quindi negli esempi che hai fatto $(a,a), (e,e), (i,i), (o,o), (u,u)$ devono esserci sempre tutti (per soddisfare la riflessività)

Questa dovrebbe essere di equivalenza, però a quanto ho capito non mi permette di verificare che a non è in relazione con u

$(a,u)!inR$, e dunque poichè R è di equivalenza (quindi simmetrica) vale anche $(u,a)!inR$. Questo ci basta per dire che i due non sono in relazione.
《Hold on to
That light
Keep the future in sight
Or all will be lost.》
-Niwaka Ame Nimo Makezu
ProPatria
New Member
New Member
 
Messaggio: 79 di 82
Iscritto il: 02/02/2019, 12:56
Località: Italia

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda Nandone169 » 06/06/2020, 15:39

\)ok adesso mi mancherebbe capire cosa posso fare per la simmetria.Su ripmat vedendo la definizione: Diciamo che una relazione R e' simmetrica se come sottoinsieme del prodotto cartesiano AxA e' formata da un insieme simmetrico rispetto alla diagonale principale (che non conoscevo perché sul libro è molto più superficiale sull'argomento), più il disegno, mi sono fatto un'idea più chiara. Quindi assodato che la relazione sia riflessiva, cioè che contiene quelle 5 relazioni, basta considerare tutti gli insiemi su cui sono definiti i punti simmetrici rispetto a questa diagonale : \( \{..., (a,e), (e,a)
\} \) questa dovrebbe avere due punti simmetrici, mentre l'insieme di partenza li contiene tutti, e così via a trovare tutte le combinazioni possibili(quindi anche solo il sottoinsieme dove è presente solo la diagonale, poiché
i punti simmetrici coincidono).
Nandone169
Starting Member
Starting Member
 
Messaggio: 6 di 6
Iscritto il: 29/05/2020, 21:12

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda ProPatria » 06/06/2020, 21:01

Nandone169 ha scritto:\)ok adesso mi mancherebbe capire cosa posso fare per la simmetria.Su ripmat vedendo la definizione: Diciamo che una relazione R e' simmetrica se come sottoinsieme del prodotto cartesiano AxA e' formata da un insieme simmetrico rispetto alla diagonale principale (che non conoscevo perché sul libro è molto più superficiale sull'argomento), più il disegno, mi sono fatto un'idea più chiara. Quindi assodato che la relazione sia riflessiva, cioè che contiene quelle 5 relazioni, basta considerare tutti gli insiemi su cui sono definiti i punti simmetrici rispetto a questa diagonale : \( \{..., (a,e), (e,a)
\} \) questa dovrebbe avere due punti simmetrici, mentre l'insieme di partenza li contiene tutti, e così via a trovare tutte le combinazioni possibili(quindi anche solo il sottoinsieme dove è presente solo la diagonale, poiché
i punti simmetrici coincidono).

Esatto, hai capito. Allora viene da se che dovrai considerare gli elementi di $VxxV$ a coppia, ossia ad esempio $(a,e)$ va in coppia con $(e,a)$ e così via. Come hai detto tu anche il sottoinsieme della sola diagonale è simmetrico (e tra l'altro anche transitivo dunque è una relazione di equivalenza).
《Hold on to
That light
Keep the future in sight
Or all will be lost.》
-Niwaka Ame Nimo Makezu
ProPatria
New Member
New Member
 
Messaggio: 80 di 82
Iscritto il: 02/02/2019, 12:56
Località: Italia

Re: Verificare un esercizio su relazioni di equivalenza

Messaggioda gugo82 » 08/06/2020, 15:08

Per quanto riguarda la terza questione, osserva che determinare una relazione d'equivalenza su $V$ equivale, per un noto teorema, a determinare una partizione di $V$ (i cui membri sono le classi di equivalenza).
Le richieste che hai sono $a R e$ e $a cancel(R) u$, quindi puoi prendere come partizione:

$\{ \{ a,e\}, \{i\}, \{o\}, \{u\}\}$,

ossia la relazione:

$R = \{ (a,a), (a,e), (e,a), (e,e), (i,i), (o,o), (u,u)\}$.
Sono sempre stato, e mi ritengo ancora un dilettante. Cioè una persona che si diletta, che cerca sempre di provare piacere e di regalare il piacere agli altri, che scopre ogni volta quello che fa come se fosse la prima volta. (Freak Antoni)
Avatar utente
gugo82
Moderatore globale
Moderatore globale
 
Messaggio: 24048 di 24337
Iscritto il: 12/10/2007, 23:58
Località: Napoli


Torna a Algebra, logica, teoria dei numeri e matematica discreta

Chi c’è in linea

Visitano il forum: sofisofi e 18 ospiti