Operações e fechos de relações

Domínio e matriz

Para $R\subseteq A\times B$:

$$\operatorname{dom}(R)=\{a:\exists b,\ aRb\},\qquad \operatorname{rng}(R)=\{b:\exists a,\ aRb\}.$$

O domínio e a imagem podem ser menores que os conjuntos $A$ e $B$. A relação inversa $R^{-1}$ troca os pares; $\operatorname{id}_A=\{(a,a)\}$ é a identidade; o complemento é relativo a $A\times B$.

Na matriz booleana, a linha é a origem e a coluna é o destino. A matriz da inversa é a transposta. Sobre um conjunto $A$:

• A reflexividade exige a diagonal toda a 1; a irreflexividade exige-a toda a 0.
• A simetria exige $M[i,j]=M[j,i]$ para todos os índices.
• A antissimetria proíbe dois 1 opostos fora da diagonal.

Composição

Se $R\subseteq A\times B$ e $S\subseteq B\times C$:

$$S\circ R=\{(a,c):\exists b\,(aRb\land bSc)\}.$$

Em $S\circ R$ aplica-se primeiro $R$. Um par aparece uma vez na composição mesmo com várias testemunhas intermédias.

O produto matricial booleano usa $\land$ em vez de multiplicação e $\lor$ em vez de soma:

$$M_{S\circ R}[i,k]=\bigvee_j(M_R[i,j]\land M_S[j,k]).$$

A composição é associativa e em geral não é comutativa. $R\circ\operatorname{id}_A=R=\operatorname{id}_B\circ R$.

Fechos

Para $R$ sobre $A$, $R^0=\operatorname{id}_A$. A potência $R^n$ liga por exatamente $n$ passos. A transitividade equivale a $R^2\subseteq R$.

O fecho é a menor relação que contém $R$ e tem a propriedade pedida:

Fecho	Relação
Reflexivo	$R\cup\operatorname{id}_A$
Simétrico	$R\cup R^{-1}$
Transitivo	$R^+=\bigcup_{n\ge1}R^n$
Reflexivo e transitivo	$R^*=\operatorname{id}_A\cup R^+$

Em $\{(1,2),(2,3)\}$: $R^+$ junta $(1,3)$; $R^*$ junta ainda os três laços. Com $(3,1)$ acrescentado, $R^+$ dá os nove pares e deixa de ser antissimétrica.

Se $|A|=N$, então $R^+=R\cup\cdots\cup R^N$. Um ciclo que regressa à origem pode precisar de $N$ passos; não reduzas sempre a $N-1$. A transitividade preserva-se por interseção, mas a união pode criar novas cadeias.

Com a totalidade, as inclusões $R^{-1}\subseteq R$ e $R^2\subseteq R$ dão uma equivalência. Sem a totalidade, a relação vazia num conjunto não vazio refuta a implicação.

Fecho transitivo e cálculo matricial.