Composizione n-aria di relazione

Composizione di una relazione con sè stessa

Sia A un insieme e $𝑅:𝐴 \leftrightarrow 𝐴$ una relazione su $*A$. *****Per ogni $𝑛 ∈ N$, $𝑅^𝑛$ è definita induttivamente come:

CLAUSOLA BASE: $𝑅^0 = 𝑖𝑑_𝐴$

CLAUSOLA INDUTTIVA: $𝑅^{𝑛+1} = 𝑅; 𝑅^𝑛$

Chiusura transitiva (n-aria)

La chiusura transitiva è la relazione su A definita come UNIONE

Questa unione è INFINITA, ed è diversa da quella utilizzata normalmente negli insiemi.

Perchè vorrebbe star a significare: $R^+ = R^1 \cup R^2 \cup R^3 \cup R^4 \cup ... R^n \cup ...$

Esempio:

Supponiamo di avere la relazione $R=\{(a,b),(b,c),(a,d),(c,a)\}$ su insieme $A =\{a,b,c,d\}$

$R^2$ contiene tutte le coppie componibili: $R^2 = \{(a,c) (b,a) (c,b) (c,d) \}$

$R^3$ sono tutte le coppie di A che si compongono ancora con qualcos’altro $R^3 = \{(a,a) (b,b) (c,c) (b,d) \}$

$R^4$ composizione tra r e r^3 $R^4 = \{(a,c) (b,c) (c,b) (c,d) \}$

Notiamo che $R^4 = R$, quindi ci fermiamo.

Quindi alla fine $R^+ = \{(a, b), (b, c), (a, d), (c, a), (a, c), (b, a), (c, b), (c, d), (a, a), (b, b), (c, c), (b, d)\}$