Operações e fechos de relações

Uma relação finita pode escrever-se como pares, desenhar-se como setas ou guardar-se numa matriz de zeros e uns. Estas representações dizem o mesmo, mas tornam visíveis aspetos diferentes. Assumimos as definições de relação e de quantificadores das duas lições anteriores. A composição procura uma ligação através de um objeto intermédio; o fecho transitivo procura qualquer sequência finita de ligações.

Domínio ativo, imagem e inversa

Para $R\subseteq A\times B$, $A$ é o domínio declarado e $B$ o contradomínio. O domínio ativo e o contradomínio ativo, ou imagem da relação, são:

Com $A=\{1,2,3\}$, $B=\{a,b,c\}$ e $R=\{(1,a),(1,b),(2,b)\}$, temos $\operatorname{dom}(R)=\{1,2\}$ e $\operatorname{rng}(R)=\{a,b\}$.

A inversa troca os elementos de cada par: $R^{-1}=\{(b,a):aRb\}$. Não pressupõe que $R$ seja uma função. A identidade é $\operatorname{id}_A=\{(a,a):a\in A\}$.

União, interseção e diferença tratam as relações como conjuntos de pares. O complemento de $R$ depende do produto declarado: $\overline R=(A\times B)\setminus R$. A restrição a $A'\times B'$ é $R\cap(A'\times B')$.

Matrizes booleanas

Ordena primeiro os elementos de $A$ e $B$. Na matriz $M_R$, a linha identifica a origem e a coluna identifica o destino:

A inversa corresponde à transposta. Numa relação sobre um só conjunto:

• Reflexividade exige 1 em toda a diagonal.
• Irreflexividade exige 0 em toda a diagonal.
• Simetria exige $M[i,j]=M[j,i]$.
• Antissimetria impede que $M[i,j]$ e $M[j,i]$ sejam ambos 1 quando $i\ne j$. Podem ser ambos 0.

No exemplo abaixo, começa com $1R2$ e $2R3$. Falta $1R3$ para haver transitividade. Liga esse par, depois acrescenta a diagonal para obter uma ordem parcial. Se ligares também $3R1$, aparecem novas exigências de transitividade.

Composição

Com $A=\{1,2\}$, $B=\{x,y\}$, $C=\{p\}$, sejam $R=\{(1,x),(2,y)\}$ e $S=\{(x,p),(y,p)\}$. A sequência $1RxSp$ liga 1 a $p$ através de $x$; $2RySp$ liga 2 a $p$ através de $y$. Logo, $S\circ R=\{(1,p),(2,p)\}$.

As setas tracejadas são os pares obtidos; não são uma terceira relação usada como passo intermédio. A definição generaliza a procura de uma testemunha:

Se $R\subseteq A\times B$ e $S\subseteq B\times C$, então:

Na escrita $S\circ R$, aplicamos primeiro $R$. Na escrita $R;S$, seguimos a ordem da esquerda para a direita. Confirma qual é a notação do enunciado.

Com $R=\{(1,a),(1,b),(2,b)\}$ e $S=\{(a,x),(b,x),(b,y)\}$:

O par $(1,x)$ tem duas testemunhas, $a$ e $b$, mas só aparece uma vez no conjunto. É a existência de uma ligação que conta, não o número de percursos.

O produto de matrizes é booleano: multiplicação passa a $\land$ e soma passa a $\lor$:

A ordem matricial é $M_R$ seguida de $M_S$, porque as linhas são origens. Um produto aritmético pode contar percursos; para recuperar a relação, reduz os valores positivos a 1.

A composição é associativa, mas não é em geral comutativa. As identidades têm de ter o conjunto certo: $R\circ\operatorname{id}_A=R=\operatorname{id}_B\circ R$.

Potências e transitividade

Para uma relação sobre $A$, $R^1=R$ e $R^{n+1}=R^n\circ R$. Podemos definir $R^0=\operatorname{id}_A$. O par $(a,b)$ pertence a $R^n$ se há uma sequência de exatamente $n$ ligações de $a$ a $b$.

Se $R=\{(1,2),(2,3),(3,4)\}$:

Uma relação é transitiva se e só se $R^2\subseteq R$. O quadrado contém precisamente os pares exigidos pela definição de transitividade.

A interseção de duas relações transitivas é transitiva: uma cadeia de dois pares na interseção pertence a ambas, e cada uma contém o par final. A união pode falhar: $\{(1,2)\}$ e $\{(2,3)\}$ são transitivas, mas a sua união não contém $(1,3)$.

Fechos

Um fecho é a menor relação que contém $R$ e satisfaz a propriedade pretendida. Acrescentamos pares, não retiramos os pares iniciais.

$R^+$ é o fecho transitivo. $R^*$ é o fecho reflexivo e transitivo. Um ciclo pode colocar pares da diagonal em $R^+$: se $1R2$ e $2R1$, então $(1,1)\in R^2$. Não excluas automaticamente os laços do fecho transitivo.

Na relação inicial da matriz interativa, $R=\{(1,2),(2,3)\}$, há só um par a acrescentar:

No estado inicial, $1R2R3$ exige $(1,3)$, que ainda falta. Nos outros dois estados, nenhuma cadeia exige um par ausente.

O segundo estado é $R^+$: é transitivo e qualquer relação transitiva que contenha $R$ tem de conter $(1,3)$. O terceiro é $R^*$. Acrescentar a diagonal conserva transitividade, porque uma passagem por um laço não exige um destino novo.

Se $A$ tem $N$ elementos, basta unir $R^1,\ldots,R^N$. Um percurso mais longo repete vértices e pode encurtar-se. Para chegar do vértice a ele próprio com pelo menos uma ligação, pode ser preciso um ciclo de comprimento $N$; por isso não substituímos sempre o limite por $N-1$.

Calcular o fecho de uma relação finita

No código, M[i][j] começa por indicar se o par $(A[i],A[j])$ pertence a $R$. Em cada passagem escolhemos um intermédio A[k]: se já podemos ir de A[i] a A[k] e daí a A[j], acrescentamos a ligação de A[i] a A[j]. Depois de considerar todos os intermédios, a matriz representa $R^+$.

A relação inicial é a cadeia $1R2R3$ da tabela. Acrescenta [3, 1] à lista R, obtendo o ciclo do exercício «Um fecho transitivo deixa de ser antissimétrico». Antes de executar, prevê quais os pares novos, incluindo a diagonal. A saída identifica também um par de elementos distintos ligado nas duas direções, caso a antissimetria falhe.

const A = [1, 2, 3];
const R = [
  [1, 2],
  [2, 3],
];

// Começamos só com R, sem acrescentar a diagonal.
const M = A.map((a) => A.map((b) => R.some(([x, y]) => x === a && y === b)));
for (let k = 0; k < A.length; k++) {
  for (let i = 0; i < A.length; i++) {
    for (let j = 0; j < A.length; j++) {
      M[i][j] = M[i][j] || (M[i][k] && M[k][j]);
    }
  }
}

const pares = [];
let opostos = null;
for (let i = 0; i < A.length; i++) {
  for (let j = 0; j < A.length; j++) {
    if (M[i][j]) pares.push(`(${A[i]},${A[j]})`);
    if (i < j && M[i][j] && M[j][i] && opostos === null) {
      opostos = [A[i], A[j]];
    }
  }
}
console.log(`R+ = {${pares.join(', ')}}`);
if (opostos === null) {
  console.log('Fecho antissimétrico: sim.');
} else {
  const [a, b] = opostos;
  console.log(`Fecho antissimétrico: não; (${a},${b}) e (${b},${a}).`);
}

Na cadeia, o único par novo é $(1,3)$ e não há pares opostos entre elementos distintos. No ciclo, qualquer vértice chega aos outros e regressa a si próprio, por isso aparecem os nove pares de $A\times A$. Os laços surgem pelos percursos, não por se ter acrescentado a identidade no início. O cálculo verifica esta relação finita; a justificação por caminhos explica por que o resultado é esse.

Provar uma equivalência a partir de operações

Suponhamos que $R$ é total, $R^{-1}\subseteq R$ e $R^2\subseteq R$. Total significa aqui que cada $a\in A$ tem pelo menos um $b$ com $aRb$.

A inclusão $R^{-1}\subseteq R$ dá simetria: de $aRb$, temos $(b,a)\in R^{-1}$ e portanto $bRa$. $R^2\subseteq R$ dá transitividade.

Para reflexividade, escolhe um $a$ arbitrário. Pela totalidade existe $b$ com $aRb$; pela simetria, $bRa$; pela transitividade, $aRa$. Assim, $R$ é uma equivalência. Sem a totalidade, $R=\emptyset$ num conjunto não vazio satisfaria as outras condições e não seria reflexiva.