Proprietà nella composizione di relazioni

[chester92]

Ciao, mi aiutate a dimostrare che delle proprietà riflessiva, simmetrica e transitiva soltanto la riflessiva si conserva quando si vanno a comporre 2 relazioni?

Per la riflessiva direi:

Sia [tex]a \alpha a[/tex] e [tex]a \beta a \rightarrow a \alpha \beta a[/tex], questo perché componendo le 2 relazioni [tex]a \alpha a \rightarrow a[/tex], e [tex]a \beta a \rightarrow a[/tex].

Simmetrica:

Deve valere [tex]a \alpha \beta b \rightarrow b \alpha \beta a[/tex], ma mentre l'applicazione di [tex]\alpha[/tex] ad a da luogo all'associazione di un elemento c', l'applicazione di [tex]\beta[/tex] a b non è detto che dia sempre c', potrebbe dare anche un c'', quindi la simmetrica non vale.

Transitiva:
non ho idea...dovrebbe verificarsi che [tex]a \alpha\beta b[/tex] e [tex]b \alpha \beta c \rightarrow a \alpha \beta c[/tex], ma guardandola così a me viene che funziona, infatti mi esce la catena [tex]a \rightarrow c' \rightarrow b \rightarrow c'' \rightarrow c[/tex], questa non vuol dire forse che [tex]a \alpha \beta c[/tex] ?

[chester92]

Già che ci siamo aggiungo quest'altro quesito: in un esercizio, data una relazione di compatibilità su insieme A, mi si chiede di trovare per via grafica (ovvero attraverso la rappresentazione tramite grafo semplice) un ricoprimento completo di A.
Ora, se mi attengo alla definizione di ricoprimento completo:

Si dice ricoprimento completo di A rispetto una relazione [tex]\alpha[/tex] l'insieme di tutti gli insiemi compatibili massimali di A

, quindi teoricamente dovrei trovare dei massimali che coprano tutti i vertici e tutti gli spigoli di A.
Il problema è che nella soluzione di questo esercizio uno spigolo non viene cerchiato, insomma vengono coperti tutti i vertici ma non tutti gli spigoli, quindi vi chiedo: sbaglio io o chi ha svolto l'esercizio?

[liantar]

"chester92":Ciao, mi aiutate a dimostrare che delle proprietà riflessiva, simmetrica e transitiva soltanto la riflessiva si conserva quando si vanno a comporre 2 relazioni?

Per la riflessiva direi:

Sia [tex]a \alpha a[/tex] e [tex]a \beta a \rightarrow a \alpha \beta a[/tex], questo perché componendo le 2 relazioni [tex]a \alpha a \rightarrow a[/tex], e [tex]a \beta a \rightarrow a[/tex].

Simmetrica:

Deve valere [tex]a \alpha \beta b \rightarrow b \alpha \beta a[/tex], ma mentre l'applicazione di [tex]\alpha[/tex] ad a da luogo all'associazione di un elemento c', l'applicazione di [tex]\beta[/tex] a b non è detto che dia sempre c', potrebbe dare anche un c'', quindi la simmetrica non vale.

Transitiva:
non ho idea...dovrebbe verificarsi che [tex]a \alpha\beta b[/tex] e [tex]b \alpha \beta c \rightarrow a \alpha \beta c[/tex], ma guardandola così a me viene che funziona, infatti mi esce la catena [tex]a \rightarrow c' \rightarrow b \rightarrow c'' \rightarrow c[/tex], questa non vuol dire forse che [tex]a \alpha \beta c[/tex] ?

Puoi dimostrarlo considerando il prodotto tra matrici.Infatti la composizione di relazioni può essere rappresentata da due matrici.Efffettuando il prodotto righe per colonne si può dimostrare che nella composizione di due relazioni la riflessività si conserva

[chester92]

Ciao, la riflessività mi trovo che si conserva, il problema è la proprietà transitiva!