Dimostrazione proprietà tra relazioni

[milos144]

Buongiorno, sto cercando di dimostrare che date 3 relazioni su un insieme $A$
$(RUS)∘F= (R∘F) uu (S ∘F )$
Provo a dimostrare prima che
$(R∘F ) uu (S ∘F ) rArr (RUS)∘F$
Siamo $r,s,f in A$ e supponiamo che $(f,r) in (R∘F) uu (S ∘F )$, allora, per definizione di unione,
$ (f,r) in (R∘F ) vv (f,r) in (S ∘F )$
Ora se $ (f,r) in (R∘F)$ allora $EE (f,s) in F ^^ (s,r) in R$, per cui abbiamo
$1)$ $(f,s) in F$
$2$ $ (s,r) in R rArr (s,r) in RuuS $
da questo segue che $(f,r) in (R∘F) rArr (f,r) in (RUS)∘F$ e dunque $(R∘F ) sube (RUS)∘F$
Allo stesso modo
se $ (f,r) in (S∘F)$ allora $EE (f,s) in F ^^ (s,r) in S$, per cui abbiamo
$1)$ $(f,s) in F$
$2$ $ (s,r) in S rArr (s,r) in RuuS $
da questo segue che $(f,r) in (S∘F) rArr (f,r) in (RUS)∘F$ e dunque $(S∘F ) sube (RUS)∘F$

In entrambi i casi
$ (R∘F) sube (RUS)∘F$
$ (S ∘F ) sube(RUS)∘F$
pertanto
$ (R∘F) uu (S ∘F ) sube(RUS)∘F $
Cosa ne pensate? Grazie sempre

[G.D.5]

"milos144":Provo a dimostrare prima che
$(R∘F ) uu (S ∘F ) rArr (RUS)∘F$

Suppongo che qui volessi scrivere che per prima cosa provi a dimostrare che \[ ( R \circ F ) \cup ( S \circ F ) \subseteq ( R \cup S ) \circ F \] quindi con \( \subseteq \) al posto di \( \implies \).

"milos144":Ora se $ (f,r) in (R∘F)$ allora $EE (f,s) in F ^^ (s,r) in R$

"milos144":Allo stesso modo se $ (f,r) in (S∘F)$ allora $EE (f,s) in F ^^ (s,r) in S$

Scritta così non va bene. Ho capito quello che vuoi dire, quello che vuoi dire è giusto ma è scritto male. Affianco al quantificatore esistenziale ci vuole un termine: \[ \exists s \in A : (f,s) \in F \land (s,r) \in R \\ \exists s \in A : (f,s) \in F \land (s,r) \in S \]

"milos144":In entrambi i casi
$ (R∘F) sube (RUS)∘F$
$ (S ∘F ) sube(RUS)∘F$
pertanto
$ (R∘F) uu (S ∘F ) sube(RUS)∘F $

Anche qui, come sopra, si capisce quello che vuoi dire, è giusto ma è detto male. Dire "In entrambi i casi..." significa dire che sia nel primo caso sia nel secondo si giunge alla stessa conclusione, che in questo caso è rappresentata dalle due inclusioni \( R \circ F \subseteq ( R \cup S ) \circ F \) e \( S \circ F \subseteq ( R \cup S ) \circ F \). Ma non è questo quello che è successo. Nel primo caso sei giunto alla conclusione che vale l'inclusione \( R \circ F \subseteq ( R \cup S ) \circ F \), e nel secondo caso sei giunto alla conclusione che vale \( S \circ F \subseteq ( R \cup S ) \circ F \). A questo punto, sapendo che in generale \( \forall A, B, C, ( A \subseteq C \land B \subseteq C \to A \cup B \subseteq C ) \), hai concluso la tesi da quelle due inclusioni. A questo punto c'è un "però". Un "però" che più che propriamente matematico è logico.

Sei partito dal supporre \( (f,r) \in (R \circ F) \cup (S \circ F) \) e, usando la definizione di unione, ti sei reso conto che questa condizione equivale a \( (f,r) \in R \circ F \lor (f,r) \in S \circ F \). A questo punto hai spezzato questa ipotesi in due e hai analizzato i due casi \( (f,r) \in R \circ F \) e \( (f,r) \in S \circ F \). Hai fatto cioè una dimostrazione per casi. Ebbene: tecnicamente quando si fa una dimostrazione per casi si dovrebbe giungere alla medesima conclusione in entrambi i casi in quanto la dimostrazione per casi si basa su quanto segue[nota]Esposto con qualche licenza[/nota]:

[*:3quyhwyv] supponiamo di voler provare che \( a \to r \)[/*:m:3quyhwyv]
[*:3quyhwyv] se sappiamo che \( a \equiv p \lor q \), allora \( a \to r \equiv (p \lor q) \to r \)[/*:m:3quyhwyv]
[*:3quyhwyv] a sua volta \( (p \lor q) \to r \equiv (p \to r) \land (q \to r) \)[/*:m:3quyhwyv]
[*:3quyhwyv] a questo punto prima dimostriamo che \( p \to r \), poi dimostriamo che \( q \to r \), ovvero dimostriamo che entrambe le "sotto-ipotesi" \(p\) e \(q\) in cui si spezza l'ipotesi \(a\) conducono alla stessa conclusione \(r\), sicché \(a\) stessa conduce a \(r\)[/*:m:3quyhwyv][/list:u:3quyhwyv]
È stata la consapevolezza di ciò, assunta inconsapevolmente nel corso dei tuoi studi, ad indurti inconsciamente ad esordire con "In entrambi i casi..."
La tua però, come detto, non è tecnicamente una dimostrazione per casi, perché spezzando l'ipotesi sei giunto a due conclusioni diverse seppur collegate, i.e. le due inclusioni (diverse ma molto simili) \(R \circ F \subseteq (R \cup S) \circ F\) e \(S \circ F \subseteq (R \cup S) \circ F\), e, sfruttando la validità di entrambe le conclusioni, sei giunto alla tesi passando per l'applicazione di una proprietà che vale in generale per tutti gli insiemi, i.e. la già sopra riportata \( \forall A, B, C, ( A \subseteq C \land B \subseteq C \to A \cup B \subseteq C ) \).
E allora perché alla fine funziona? Perché in questa circostanza procedendo per casi hai provato in ciascun caso un fatto più generale: dati un insieme \(U\) e tre relazioni \(X,Y,Z\) definite su esso, vale \( X \circ Z \subseteq ( X \cup Y ) \circ Z \), da cui ponendo \(X=R, Y=S, Z=F\) si ottiene la prima inclusione e ponendo \(X=S, Y=R, Z=F\) si ottiene la seconda grazie alla commutatività dell'unione[nota]Ed è in questo senso che le due inclusioni alle quali sei giunto sono collegate: se vale una, vale anche l'altra.[/nota]. Ovvero ciascun caso è in realtà la dimostrazione di questo fatto generale. Infatti se la consegna fosse stata "Provare che \( X \circ Z \subseteq (X \cup Y) \circ Z \)" cosa avresti fatto? Saresti partito con "Supponiamo che \( (a,b) \in X \circ Z \)...". E come iniziano i due casi? Iniziano con "Ora, se \( (f,r) \in R \circ F \)..." e "Allo stesso modo, se \( (f,r) \in S \circ F \)..."!

E questo è quanto.

[milos144]

Grazie tante G.D.! Ho guardato i vari punti e ho cercato di comprendere al meglio.

$1)$
 si intendevo $(R∘F)∪(S∘F)⊆(R∪S)∘F$

$2)$
A fianco al quantificatore esistenziale ci vuole un termine.
Qui pensavo :che una coppia come $(f,s) $ fosse un termine, per cui ho scritto  $EE(f,s) in F$
Quindi $EE$ deve essere seguito da un termine singolo?
$3) $
In entrambi i casi
$(R∘F)⊆(RUS)∘F$
$(S∘F)⊆(RUS)∘F$
pertanto
$(R∘F)∪(S∘F)⊆(RUS)∘F$
Penso di aver capito l'errore: dicendo in entrambi i casi, ho affermato che
$(R∘F)⊆(RUS)∘F rArr (R∘F)∪(S∘F)⊆(RUS)∘F$ 
$(S∘F)⊆(RUS)∘F rArr (R∘F)∪(S∘F)⊆(RUS)∘F$   
che non è vero. Se fosse stato così potevo parlare di dimostrazione per casi per il motivo che mi hai spiegato.
L'unica cosa vera é che $(R∘F)⊆(RUS)∘F ^^ (S∘F)⊆(RUS)∘F$ e sapendo che in generale $ ∀A,B,C,(A⊆C∧B⊆C→A∪B⊆C),$   concludo la tesi da quelle due inclusioni.
$4)$
La cosa:
In entrambi i casi
$(R∘F)⊆(RUS)∘F$
$(S∘F)⊆(RUS)∘F$
pertanto
$(R∘F)∪(S∘F)⊆(RUS)∘F$ perchè funziona?

Dati un insieme $ U$ e tre relazioni $X,Y,Z$ definite su esso, vale $X∘Z⊆(X∪Y)∘Z$, da cui ponendo $ X=R,Y=S,Z=F$ si ottiene la prima inclusione e ponendo $X=S,Y=R,Z=F$ si ottiene la seconda grazie alla commutatività dell'unione. La cosa funziona, non perchè la dimostrazione è per casi, ma perchè è stato dimostrato un fatto più generale cioè vale la proprietà commutativa. Spero di aver inteso bene la tua ottima spiegazione.

[fulcanelli]

"G.D.":[quote="milos144"]Provo a dimostrare prima che
$(R∘F ) uu (S ∘F ) rArr (RUS)∘F$

Suppongo che qui volessi scrivere che per prima cosa provi a dimostrare che \[ ( R \circ F ) \cup ( S \circ F ) \subseteq ( R \cup S ) \circ F \] quindi con \( \subseteq \) al posto di \( \implies \).[/quote] Le due notazioni sono circa intercambiabili, perché una funzione proposizionale \(\psi : X \to \{0,1\}\) è equivalente a un sottoinsieme \(A_\psi \subseteq X\) (sottoinsieme che ha esattamente \(\psi\) per funzione caratteristica). Date due funzioni proposizionali \(\phi,\psi\), si ha che \(\phi\Rightarrow\psi\) se e solo se \(A_\phi\subseteq A_\psi\), al punto tale che alcuni definiscono l'implicazione a quel modo, sicché...

[milos144]

Buongiorno a tutti e un grazie a G.D. e fulcanelli per l'aiuto. Ma le osservazioni per punti che ho fatto vanno poi bene? Grazie

[G.D.5]

I due casi li hai individuati all'inizio. Prima hai supposto \( (f,r) \in (R \circ F) \cup (S \circ F) \), poi hai detto che, per come è definita l'unione, da questa posizione deriva \( (f,r) \in R \circ F \lor (f,r) \in S \circ F \). A questo punto hai spezzato la disgiunzione \( \lor \) e hai percorso due strade:

[*:2j0vws4g] la prima quando \( (f,r) \in R \circ F \), che ti ha portato a \( R \circ F \subseteq (R \cup S) \circ F \);[/*:m:2j0vws4g]
[*:2j0vws4g] la seconda quando \( (f,r) \in S \circ F \), che ti ha portato a \( S \circ F \subseteq (R \cup S) \circ F \)[/*:m:2j0vws4g][/list:u:2j0vws4g]
Ebbene: le due condizioni che aprono le due strade, i.e. \( (f,r) \in R \circ F \) e \( (f,r) \in S \circ F \), sono i due casi. Il primo caso è \( (f,r) \in R \circ F \), il secondo caso è \( (f,r) \in S \circ F \).

Ora, come detto, quando si dimostra qualcosa procedendo per casi, occorre verificare che in tutti i casi si perviene alla stessa conclusione. Posto ciò, nel momento in cui scrivi



"milos144":
In entrambi i casi
\( R \circ F \subseteq (R \cup S) \circ F \\ S \circ F \subseteq (R \cup S) \circ F \) Pertanto
\( (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \)


fai capire che stai sostenendo due cose:
[list=1]
[*:2j0vws4g] fai capire che stai dicendo che sia quando sei partito da \( (f,r) \in R \circ F \) (i.e. il primo caso) sia quando sei partito da \( (f,r) \in S \circ F \) (i.e. il secondo caso) sei giunto alla conclusione rappresentata dalle due inclusioni \( R \circ F \subseteq (R \cup S) \circ F \) ed \( S \circ F \subseteq (R \cup S) \circ F \), stai cioè facendo passare l'idea che stai sostenendo che in entrambi i casi sei arrivato a tutte e due le inclusioni, invece nel primo caso sei arrivato solo alla prima inclusione e nel secondo sei arrivato solo alla seconda inclusione, sicché stai dicendo di essere giunto ad un risultato al quale non sei giunto;[/*:m:2j0vws4g]
[*:2j0vws4g]fai capire che stai dicendo che l'inclusione \( (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \) è una conseguenza del fatto che valgono simultaneamente le due inclusioni \( R \circ F \subseteq (R \cup S) \circ F \) e \( S \circ F \subseteq (R \cup S) \circ F \), che è vero ma non è la strada che hai percorso, giacché tu sei andato per casi e, generalmente, quando si va per casi prima vale un caso, con la relativa conclusione, poi vale l'altro caso, con la relativa conclusione, sicché a te a questo punto manca far vedere che ciascuna inclusione vale anche nell'altro caso, ovvero ti manca di far vedere che \( R \circ F \subseteq (R \cup S) \circ F \), la conclusione del caso \( (f,r) \in R \circ F \), vale anche nel caso \( (f,r) \in S \circ F \), che porta alla conclusione \( S \circ F \subseteq (R \cup S) \circ F \), e viceversa.[/*:m:2j0vws4g][/list:o:2j0vws4g]



"milos144":
... è stato dimostrato un fatto più generale cioè vale la proprietà commutativa.


Il punto di questo esercizio ed in particolare il punto relativo al tuo tentativo di dimostrare che vale l'inclusione \( (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \) consiste sì nel fatto che vale un fatto più generale ma questo fatto più generale non consiste nel fatto che vale la proprietà commutativa. Attenzione! Evidentemente mi sono espresso male io quando vi ho fatto riferimento: la proprietà commutativa alla quale io stavo facendo riferimento è quella dell'unione. Il fatto più generale che sta a monte della validità dell'inclusione \( (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \) è il seguente[nota]Ed anzi vale un fatto ancora più generale: dato un qualunque insieme \( A \), se \( B, C, D \) sono relazioni su \( A \), i.e. se sono sottoinsiemi del quadrato cartesiano \( A^{2} \), con \( B \subseteq C \), allora \( B \circ D \subseteq C \circ D \). Da ciò si può derivare non solo la proprietà sulla quale ci stiamo concentrando per fare uscire fuori le tue due inclusioni ma si potrebbero anche ottenere direttamente queste due inclusioni.[/nota]: dato un qualunque insieme \( U \), se \( X, Y, Z \) sono relazioni su \( U \), i.e. se sono sottoinsiemi del quadrato cartesiano \( U^{2} \), allora \( X \circ Z \subseteq (X \cup Y) \circ Z \). Valendo ciò, con \( U = A, X = R, Y = S, Z = F \) si ha \( R \circ F \subseteq (R \cup S) \circ F \), che è la prima inclusione alla quale tu eri giunto, e con \( U = A, X = S, Y = R, Z = F \) si ha \( S \circ F \subseteq (S \cup R) \circ F \), dove \( R \cup S = S \cup R \) per la proprietà commutativa dell'unione, sicché \( S \circ F \subseteq (S \cup R) \circ F \) è lo stesso che \( S \circ F \subseteq (R \cup S) \circ F \), che è la seconda inclusione alla quale tu eri giunto. A questo punto, poiché vale anche un altro fatto più in generale, e cioè che se due insiemi sono sottoinsiemi dello stesso insieme allora anche la loro unione è sottoinsieme dell'insieme in questione, si conclude che \( (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \).
Nei tuoi due casi non hai fatto altro che provare per due volte che \( X \circ Z \subseteq (X \cup Y) \circ Z \). Ecco perché poi la dimostrazione alla fine funziona.

Per quanto riguarda il quantificatore esistenziale: se scrivi \( \exists (f,s) \in F \land (s,r) \in R \), il quantificatore si riferisce solo a \( (f,s) \in F \). Io lo so che il senso di quello che volevi dire resta lo stesso e si capisce comunque ma l'uso dei quantificatori, così come quello dei connettivi, sottostà a delle precise regole di sintassi finalizzate alla formazione delle cosiddette formule ben formate. Non vanno usati con leggerezza. Quando ho detto che affianco al quantificatore esistenziale ci vuole un termine non intendevo dire che ce ne vuole uno nel senso della quantità o nel senso della natura dell'elemento. Intendevo dire che serve (almeno) un termine al quale il quantificatore deve fare riferimento e poi serve ovviamente la proprietà che coinvolge questo termine. E allora, per esempio, in questo caso si vuole dire che esiste un elemento \(s\) tale che le due coppie \((f,s)\) e \((s,r)\) rispettano certe appartenenze, sicché si scriverà \( \exists s \in A : (f,s) \in F \land (s,r) \in R \). Se invece per esempio io volessi dire che due relazioni \( B, C \) su un insieme \( A \) non sono disgiunte, allora oltre all'ovvio \( B \cap C \ne \varnothing \) posso anche scrivere \( \exists (x,y) \in A^{2} : (x,y) \in B \land (x,y) \in C \).

[G.D.5]

@fulcanelli

Ovviamente quello che dici è corretto e non contestabile.
Io tuttavia sono restio a digerire lo scambio delle due notazioni.

[milos144]

Grazie G.D., cerco di mettere ordine alla mia confuzione!
Quindi, grazie ai tuoi consigli, per arrivare alla prima parte della dimostrazione per casi dovevo procedere così:

date 3 relazioni su un insieme $A$
provo a dimostrare che
$(R∘F)∪(S∘F)sube(R ∪ S)∘F$
Siano $r,s,f∈A$ e supponiamo che 
$(f,r)∈(R∘F)∪(S∘F) rArr ((f,r)∈(R∘F)∨(f,r)∈(S∘F))$ (definizione di unione)
Ora se $(f,r)∈(R∘F)$ allora $∃(f,s)∈F∧ ∃ (s,r)∈R$, per cui abbiamo
$1) (f,s)∈F$
$2 ) (s,r)∈R⇒(s,r)∈R∪S$
da questo segue che $ (f,r)∈(R∘F)⇒(f,r)∈(R∪ S)∘F$ e dunque $(R∘F)⊆(R∪ S)∘F$
Allo stesso modo
se$ (f,r)∈(S∘F)$ allora $∃(f,s)∈F∧∃ (s,r)∈S$, per cui abbiamo
$1) (f,s)∈F$
$2 )(s,r)∈S⇒(s,r)∈R∪S$
da questo segue che$ (f,r)∈(S∘F)⇒(f,r)∈(R∪ S)∘F$ e dunque $ (S∘F)⊆(R ∪ S)∘F$
Pertanto
${[((f,r), in (R∘F) rArr (f,r) ∈(R∪ S)∘F) rArr (R∘F)⊆(R∪ S)∘F]^^[ ((f,r)∈(S∘F)⇒(f,r)∈(R∪ S)∘F) rArr (S∘F)⊆(R∪ S)∘F]} rArr ((f,r)∈(R∘F)∨(f,r)∈(S∘F) rArr (f,r) in (R ∪ S)∘F)) rArr (R∘F)∪(S∘F)sube(R ∪ S)∘F $

[G.D.5]

"milos144":Siano $r,s,f∈A$ e supponiamo che 
$(f,r)∈(R∘F)∪(S∘F) rArr ((f,r)∈(R∘F)∨(f,r)∈(S∘F))$

Se scrivi così fai capire che stai prendendo come ipotesi l'intero costrutto condizionale. No. Ciò che prendi come ipotesi è il solo antecedente: \( (f,r) \in (R \circ F) \cup (S \circ F) \). Da questo, per come è definita l'unione tra insiemi, hai: \( (f,r) \in R \circ F \lor (f,r) \in S \circ F \).

"milos144":$∃(f,s)∈F∧ ∃ (s,r)∈R$

No. Non va bene. Scritto così non va bene. Purtroppo \( \exists x : P(x) \land Q(x) \) non è lo stesso che \( \exists x : P(x) \land \exists x : Q(x) \). Esempio: \( \exists x : x < 1 \land x \ge 1 \) è falso mentre \( \exists x : x < 1 \land \exists x : x \ge 1 \) è vero, questo perché una volta legate da un quantificatore le variabili sono mute, possiamo dare loro il nome che vogliamo e i predicati su cui agiscono diventano (generalmente) degli enunciati. Quindi in \( \exists x : x < 1 \land \exists x : x \ge 1 \) la \( x \) non deve essere necessariamente la stessa, i due enunciati \( \exists x : x <1 \) e \( \exists x : x \ge 1 \) sono entrambi veri e tale è anche la loro congiunzione. Allo stesso modo se scrivi \( \exists (f,s) \in F \land \exists (s,r) \in R \) stai banalmente affermando che \( R \) e \( F \) sono non vuoti, quella \( s \) che si ripete non è obbligatorio che sia la stessa. E invece tu devi proprio dire che è la stessa: la composizione di due relazioni è definita proprio per mezzo di elementi che si ripetono, che prima sono presenti come seconda coordinata e sono presenti come prima coordinata. La scrittura corretta è: \( \exists x \in A : (f,s) \in F \land (s,r) \in R \).

"milos144":per cui abbiamo
$1) (f,s)∈F$
$2 ) (s,r)∈R⇒(s,r)∈R∪S$
da questo segue che $ (f,r)∈(R∘F)⇒(f,r)∈(R∪ S)∘F$ e dunque $(R∘F)⊆(R∪ S)∘F$

Ti devi fermare appena un passo prima! Se mi arrivi a \( R \circ F \subseteq ( R \cup S ) \circ F \) "impacchetti" il caso! Lo fai diventare la prova che vale l'inclusione \( R \circ F \subseteq ( R \cup S ) \circ F \). Se proprio vuoi procedere per casi ti basta fermarti a \( (f,r) \in R \circ F \to (f,r) \in (R \cup S) \circ F \): questa scrittura significa che partendo dall'ipotesi che \( (f,r) \in R \circ F \), i.e. il rimo caso, sei giunto alla conclusione che \( (f,r) \in (R \cup S) \circ F \).

"milos144":Allo stesso modo
se$ (f,r)∈(S∘F)$ allora $∃(f,s)∈F∧∃ (s,r)∈S$, per cui abbiamo
$1) (f,s)∈F$
$2 )(s,r)∈S⇒(s,r)∈R∪S$
da questo segue che$ (f,r)∈(S∘F)⇒(f,r)∈(R∪ S)∘F$ e dunque $ (S∘F)⊆(R ∪ S)∘F$

Come sopra:

[*:cyq7fmf3] \( \exists (f,s) \in F \land \exists (s,r) \in S \) non va bene, la scrittura giusta è \( \exists s \in A : (f,s) \in F \land (s,r) \in S \);[/*:m:cyq7fmf3]
[*:cyq7fmf3] ti devi fermare a \( (f,r) \in S \circ F \to (f,r) \in (R \cup S) \circ F \)[/*:m:cyq7fmf3][/list:u:cyq7fmf3]



"milos144":Pertanto
${[((f,r), in (R∘F) rArr (f,r) ∈(R∪ S)∘F) rArr (R∘F)⊆(R∪ S)∘F]^^[ ((f,r)∈(S∘F)⇒(f,r)∈(R∪ S)∘F) rArr (S∘F)⊆(R∪ S)∘F]} rArr ((f,r)∈(R∘F)∨(f,r)∈(S∘F) rArr (f,r) in (R ∪ S)∘F)) rArr (R∘F)∪(S∘F)sube(R ∪ S)∘F $



È scritto male. Perché ti sei portato dietro le inclusioni \( R \circ F \subseteq (R \cup S) \circ F \) e \( S \circ F \subseteq (R \cup S ) \circ F \). Se proprio lo vuoi scrivere tutto in formule (con un bel po' di licenza):

\[ [((f,r) \in R \circ F \to (f,r) \in (R \cup S) \circ F) \land ((f,r) \in S \circ F \to (f,r) \in (R \cup S) \circ F)] \\ \to [((f,r) \in R \circ F \lor (f,r) \in S \circ F) \to (f,r) \in (R \cup S) \circ F] \tag{1} \] \[ [((f,r) \in R \circ F \lor (f,r) \in S \circ F) \to (f,r) \in (R \cup S) \circ F] \\ \to [(f,r) \in (R \circ F) \cup (S \circ F) \to (f,r) \in (R \cup S) \circ F] \tag{2} \] \[ [(f,r) \in (R \circ F) \cup (S \circ F) \to (f,r) \in (R \cup S) \circ F] \\ \to \forall (f,r) ((f,r) \in (R \circ F) \cup (S \circ F) \to (f,r) \in (R \cup S) \circ F) \tag{3} \] \[ \forall (f,r) ((f,r) \in (R \circ F) \cup (S \circ F) \to (f,r) \in (R \cup S) \circ F) \\ \to (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \tag{4} \]
Dove:


[*:cyq7fmf3] \((1)\) è per la dimostrazione per casi;[/*:m:cyq7fmf3]
[*:cyq7fmf3] \((2)\) è per la definizione di unione tra insiemi;[/*:m:cyq7fmf3]
[*:cyq7fmf3] \((3)\) è per la regola di generalizzazione universale (i.e. puoi introdurre il quantificatore universale su una variabile se non hai fatto ipotesi speciali sulla variabile)[/*:m:cyq7fmf3]
[*:cyq7fmf3] \((4)\) è per la definizione di sottoinsieme e l'inclusione presente nel conseguente di questo condizionale costituisce la tesi.[/*:m:cyq7fmf3][/list:u:cyq7fmf3]

Ma ripeto: è un stato fatto prendendosi un bel po' di licenze. Si potrebbe (e sarebbe preferibile, non padroneggiando completamente quantificatori e connettivi) concludere molto più semplicemente così:


[*:cyq7fmf3] \( (f,r) \in R \circ F \to (f,r) \in (R \cup S) \circ F \), i.e. nel primo caso si ha \( (f,r) \in (R \cup S) \circ F \)[/*:m:cyq7fmf3]
[*:cyq7fmf3] \( (f,r) \in S \circ F \to (f,r) \in (R \cup S) \circ F \), i.e. anche nel secondo caso si ha \( (f,r) \in (R \cup S) \circ F \)[/*:m:cyq7fmf3]
[*:cyq7fmf3] in entrambi i casi si giunge alla stessa conclusione, quindi \( (f,r) \in R \circ F \lor (f,r) \in S \circ F \to (f,r) \in (R \cup S) \circ F \)[/*:m:cyq7fmf3]
[*:cyq7fmf3] a questo punto si conclude per la definizione di unione e di sottoinsieme: \( (R \circ F) \cup (S \circ F) \subseteq (R \cup S) \circ F \)[/*:m:cyq7fmf3][/list:u:cyq7fmf3]

[milos144]

Provo a dimostrare l'altra inclusione: spero sia andata meglio! Grazie G,D. per la pazienza.
$(R∪S)∘F⊆(R∘F)∪(S∘F)$
Siano $r,s,f∈A$ e supponiamo che $(f,r) in (R∪S)∘F$, allora

$∃s∈A:(f,s)∈F∧(s,r)∈R uu S$
Ora
$(s,r)∈R uu S rarr ((s,r)∈R vv (s,r) in S)$ definizione di unione

Pertanto
$(f,r) in (R∪S)∘F rarr ((f,s)∈F∧((s,r) ∈R vv (s,r) in S))$

$ ((f,s)∈F∧((s,r) ∈R vv (s,r) in S)) rarr ((f,r) in R∘F) vv ((f,r) in S∘F)$ proprietà distributiva di $nn$ rispetto a $uu$

$ ((f,r) in R∘F) vv ((f,r) in S∘F) rarr (f,r) in (R∘F)∪(S∘F)$

[G.D.5]

"milos144":
\( ((f,s) \in F \land ((s,r) \in R \lor (s,r) \in S)) \to ((f,r) \in R \circ F) \lor ((f,r) \in S \circ F) \) proprietà distributiva di \(\cap\) rispetto a \(\cup\).

Non hai usato la proprietà distributiva dell'intersezione sull'unione. Hai usato la proprietà distributiva della congiunzione sulla disgiunzione (e poi hai anche usato la definizione di composizione delle relazioni). Lo so che c'è un legame molto stretto tra questi connettivi e le due operazioni insiemistiche ma attenzione a non considerarlo un legame a doppio filo: infatti in questa circostanza il connettivo \( \land \) serve a definire la composizione delle relazioni, non l'intersezione degli insiemi.

[milos144]

Grazie G,D. !
Qui, quindi si doveva scrivere

$((f,s)∈F∧((s,r)∈R∨(s,r)∈S))→((f,r)∈R∘F)∨((f,r)∈S∘F)$ proprietà distributiva di $^^$ rispetto a $vv$ e applicazione della definizione di composizione delle relazioni.
Grazie di nuovo