Chiusura transitiva di una relazione

[milos144]

Stavo provando a dimostrare che per ogni relazione $R$, vale la chiusura transitiva. Se qualcuno vuole dare un'occhiata e darmi dei consigli, ci sono sempre.
Posto
$R^1=R$ e $AA i in NN : i>0, R^(i+1) = R@R^i$
risulta
$R^+= bigcup_{i in NN}R^i$ è transitiva:

$ R sube R^+$: $R^+$ contiene per definizione tutti gli $R^i$ e in particolare $R$

Ora, se $(s_1,s_2),(s_2,s_3) in R^+$ allora $(s_1,s_2) in R^k ^^ (s_2,s_3) in R^t$, per qualche $k,t in NN$,
ed essendo poi la composizione associativa, $R^(k+t)= R^k@R^t$ e pertanto $(s_1,s_3) in R^(k+t)sube R^+$
Questo è quanto basta per dimostrare la chiusura transitiva.
Grazie

[G.D.5]

Ti manca di dimostrare che \(R^{+}\) è la più piccola (rispetto all'inclusione) relazione transitiva contenente \(R\).

[milos144]

Grazie G.D.!
Provo a dimostrare che $R^+$è la più piccola (rispetto all'inclusione) relazione transitiva contenente $R$
Sia $V$ una qualsiasi relazione transitiva contenente $R$ allora $R^+ sube V$.
Provo a dimostrare per induzione su $i$ che $R^i sube V, AA i $:

$R^1=R sube V$, segue per assunzione;

ipotesi induttiva: supponiamo ora che $R^i sube V$ vale per $AA i$
e $t_1,t_3 in V^(i+1) =R@R^i$ allora $(t_1,t_2) in R$ e
$t_2,t_3 in R^i$ per qualche $t_2$ per definizione di $@$, composizione di relazioni.
Segue che $(t_1,t_2), (t_2,t_3) in V$ per assunzione e per ipotesi induttiva e quindi
$t_1,t_3 in V$ per la transitività di $V$
Conclusione $R^i in V AA i rarr R^+ sube V$ per definizione di $R^+$

[G.D.5]

Riscrivi meglio il passo induttivo perché così com'è scritto, è scritto male.

[milos144]

Provo a sistemare il passo induttivo, spero vada meglio:

passo induttivo: per ipotesi considero vero che $R^i sube V AA i$ e provo a dimostrare la tesi: $R^i sube V rArr R^(i+1) =R^+sube V$:
se $t_1,t_3 in R^(i+1) =R@R^i$ allora $(t_1,t_2) in R$ e
$t_2,t_3 in R^i$ per qualche $t_2$ (definizione di $@$, composizione di relazioni).
Pertanto $(t_1,t_2), (t_2,t_3) in V$ per assunzione e per ipotesi induttiva e quindi
$t_1,t_3 in V$ per la transitività di $V$
Conclusione $R^i sube V AA i rarr R^+ sube V$ per definizione di $R^+$

[G.D.5]

"milos144":passo induttivo: per ipotesi considero vero che $R^i sube V AA i$ e provo a dimostrare la tesi: $R^i sube V rArr R^(i+1) =R^+sube V$

No:

[*:2juz6syz]l'ipotesi nel passo induttivo non è \(R^{i} \subseteq V, \forall i\), l'ipotesi nel passo induttivo è che \(R^{i} \subseteq V\) valga per un quale \(i \in \mathbb{N}\): se l'ipotesi fosse \(R^{i} \subseteq V, \forall i\), allora non ci sarebbe niente da dimostrare; [/*:m:2juz6syz][*:2juz6syz]la tesi nel passo induttivo non è \(R^{i} \subseteq V \implies R^{i+1} = R^{+} \subseteq V\): questa implicazione rappresenta l'intero passo induttivo nel quale l'antecedente di questa implicazione (i.e. \(R^{i} \subseteq V\)) è l'ipotesi induttiva di cui al punto precedente e \(R^{i+1} \subseteq V\) è la tesi del passo induttivo; [/*:m:2juz6syz][*:2juz6syz] \(R^{i+1} = R^{+}\) non è una uguaglianza vera e \(R^{+}\) non ha strettamente a che fare con la procedura per induzione: andando per induzione tu provi che tutte le componenti dell'unione generalizzata che definisce \(R^{+}\) sono sottoinsiemi di \(V\), da questo poi deriva che \(R^{+} \subseteq V\); [/*:m:2juz6syz][*:2juz6syz] \(R^{i} \subseteq V, \forall i\) è un pessimo modo di scrivere quello che vuoi dire, indipendentemente dal fatto che sia corretto o meno: \(\forall i \in \mathbb{N}, R^{i} \subseteq V\) è un modo più pulito di scrivere la formula, posto che, come detto, in questo caso è sbagliata.[/*:m:2juz6syz][/list:u:2juz6syz]



"milos144":se $t_1,t_3 in R^(i+1) =R@R^i$ allora $(t_1,t_2) in R$ e
$t_2,t_3 in R^i$ per qualche $t_2$ (definizione di $@$, composizione di relazioni).


Ti sei perso un paio di parentesi tonde: è \((t_{1}, t_{3}) \in R^{i+1}\) e \((t_{2}, t_{3}) \in R^{i}\).



"milos144":Pertanto $(t_1,t_2), (t_2,t_3) in V$ per assunzione e per ipotesi induttiva


Quale assunzione? Che sia \((t_{1}, t_{2} \in V\) non dipende da una assunzione, dipende dal passo base, che a sua volta dipende dal fatto che \(V\) includa \(R\), che non è una ipotesi della procedura induttiva, è una ipotesi dovuta al fatto che questa è una proprietà che \(V\) deve avere in quanto richiesta dalla definizione della chiusura transitiva.



"milos144":e quindi $t_1,t_3 in V$ per la transitività di $V$


Anche qui le parentesi: \((t_{1}, t_{3}) \in V\).



"milos144":Conclusione $R^i sube V AA i rarr R^+ sube V$ per definizione di $R^+$


Giusto per chiarire: \(\forall i \in \mathbb{N}, R^{i} \subseteq V\) è vero perché lo hai appena dimostrato per induzione, essendo vero ciò, per via della definizione di \(R^{+}\), puoi ora concludere \(R^{+} \subseteq V\).

[milos144]

Grazie G.D. per i chiarimenti. Provo a riscrivere il tutto per levarmi ogni dubbio:
passo induttivo:
suppongo per ipotesi che $R^i⊆V$ valga per un qualche $i∈N$ (ipotesi induttiva) qui potevo scrivere $EE i in NN | R^i⊆V$ ?
e provo a dimostrare che $R^(i+1)⊆V$ (tesi induttiva):

se $(t_1,t_3) in R^(i+1)=R∘R^i$ allora $(t_1,t_2) in R$ e $(t_2,t_3) in R^i$ per qualche $t_2$ (definizione di $∘$, composizione di relazioni).
Pertanto $(t_1,t_2),(t_2,t_3) in V$ (questo dipende dal passo base, che a sua volta dipende dal fatto che $V$ includa$ R$ e dal fatto che questa è una proprietà che V deve avere in quanto richiesta dalla definizione della chiusura transitiva), e quindi $(t_1,t_3) in V$ per la transitività di $V$

Conclusione: se $∀i in N,R^i⊆V$, come appena dimostrato, per via della definizione di $R^+$, posso ora concludere che $R^+⊆V$.
Grazie di nuovo!

Un chiarimento G.D.:il fatto che $(t_1,t_2),(t_2,t_3) in V$ non si può spiegare anche così:
$(t_1,t_2) in R sube V$, per tutti i motivi spiegati sopra,ma anche
$(t_2,t_3) in R^ì sube V$, per gli stessi motivi, perchè se $i>=1$ e $ì=1 rarr R^1=R subeV$?

[G.D.5]

"milos144":...suppongo per ipotesi che $R^i⊆V$ valga per un qualche $i∈N$ (ipotesi induttiva) qui potevo scrivere $EE i in NN | R^i⊆V$ ?

No. O meglio: non come lo vuoi intendere tu.

Il passo induttivo del principio di induzione si può formalizzare attraverso la formula \(\forall k, \mathcal{P}(k) \to \mathcal{P}(k+1)\). Quando si ha da provare una formula con un quantificatore universale senza alcuna condizione sulla variabile quantificata se non l'appartenenza di questa al dominio del discorso, si procede nel seguente modo: si mostra che la formula su cui agisce il quantificatore universale è vera per un generico ed arbitrario elemento del dominio del discorso, che in questo caso è l'insieme dei numeri naturali \(\mathbb{N}\). Si fa questo in virtù del fatto che l'eliminazione e l'introduzione del quantificatore universale sono governate rispettivamente dalla regola di istanziazione universale e dalla regola di generalizzazione: la regola di istanziazione dice che se sappiamo che è vera la formula \(\forall x, \phi(x)\), allora qualunque costante \(c\) presa dal dominio del discorso e sostituita alla variabile \(x\) produce una formula vera \(\phi(c)\); la regola di generalizzazione dice che se una formula \(\phi(x)\) è per una generica ed arbitraria costante \(c\) presa dal dominio del discorso e sostituita alla variabile \(x\) della formula, allora si può dedurre che è vera la formula chiusa dal quantificatore \(\forall x, \phi(x)\). Tornando ora al nostro passo induttivo, accade che, per provare la formula \(\forall k, \mathcal{P}(k) \to \mathcal{P}(k+1)\), in accordo con la regola di generalizzazione, dobbiamo prendere un generico ed arbitrario \(n \in \mathbb{N}\) e mostrare che vale \(\mathcal{P}(n) \to \mathcal{P}(n+1)\); a questo punto abbiamo un costrutto condizionale che è vacuamente vero se l'antecedente \(\mathcal{P}(n)\) è falso oppure se, essendo vero l'antecedente \(\mathcal{P}(n)\), è vero anche il conseguente \(\mathcal{P}(n+1)\). Ecco allora, infine, quello che facciamo nella pratica: supponiamo che \(\mathcal{P}(n)\) sia vera per un generico ed arbitrario \(n\) e dimostriamo che è conseguentemente vero \(\mathcal{P}(n+1)\). A questo punto tu mi dirai: "E qual è la differenza con \(\exists k : \mathcal{P}(k)\)?". Semplice: \(\exists k : \mathcal{P}(k)\) ti dice che esiste almeno una costante \(n\) che sostituita a \(k\) rende vera \(\mathcal{P}\) ma questo non significa che \(n\) è generica ed arbitraria!

"milos144":Pertanto $(t_1,t_2),(t_2,t_3) in V$ (questo dipende dal passo base, che a sua volta dipende dal fatto che $V$ includa$ R$ e dal fatto che questa è una proprietà che V deve avere in quanto richiesta dalla definizione della chiusura transitiva), e quindi $(t_1,t_3) in V$ per la transitività di $V$
...
Un chiarimento G.D.:il fatto che $(t_1,t_2),(t_2,t_3) in V$ non si può spiegare anche così:
$(t_1,t_2) in R sube V$, per tutti i motivi spiegati sopra,ma anche
$(t_2,t_3) in R^ì sube V$, per gli stessi motivi, perchè se $i>=1$ e $ì=1 rarr R^1=R subeV$?

Tu arrivi a dedurre che \((t_1,t_2) \in R\) e \((t_2,t_3) \in R^{i}\). A questo punto in virtù del passo base sai che \(R \subseteq V\) (e a sua volta sai che questo vale per come è caratterizzata \(V\) per ipotesi: in altre parole ci troviamo nella circostanza che il passo base coincide con l'ipotesi che definisce gli oggetti coinvolti nel passo base stesso), sicché \((t_1,t_2) \in V\); che sia anche \((t_2,t_3) \in V\) lo sai invece perché per ipotesi induttiva sai che \(R^{i} \subseteq V\).

[milos144]

Grazie G.D. per i chiarimenti!