[MCTB019-17] §6 — Relações

Se ${A_1,A_2,\dots,A_n}$ são conjuntos não vazios, um subconjunto ${R\subseteq \prod_{i=1}^n A_i}$ é uma relação ${n}$ -ária. No caso de dois conjuntos, digamos ${A}$ e ${B}$ , temos uma relação binária de ${A}$ para ${B}$ ou, simplesmente, dizemos relação. Uma relação binária ${R}$ sobre ${A}$ é uma relação binária de ${A}$ para ${A}$ .

Notação: Escrevemos ${a\mathrel{R}b}$ com o significado de ${(a,b)\in R}$ . Escrevemos ${a\not\mathrel{R}b}$ com o significado de ${(a,b)\not\in R}$ .

São exemplos de relações (binárias)

${< \;\subset\, {\mathbb N}\times{\mathbb N}}$ é uma relação binária e ${(2,3) \in <}$ , mas usamos ${2<3}$ .
${| \;\subset\, {\mathbb Z}^+ \times{\mathbb Z}^+}$ é uma relação binária e ${(2,4) \in |}$ , mas usamos ${2|4}$ .
${\;\subseteq\, \subset 2^{\mathbb N} \times 2^{\mathbb N}}$ é uma relação binária e ${\big(\{1,2\},\{1,2,3\}\big) \in \subseteq}$ , mas usamos ${\{1,2\}\subseteq \{1,2,3\}}$ .

6.1. Composição e inversa

Assim como as funções, as relações podem ser compostas. Dadas as relações ${R\subseteq A\times B}$ e ${S\subseteq B \times C}$ definimos

$\displaystyle (S\circ R)\subset A \times C$

pela regra ${(x, z)\in (S\circ R)}$ se, e somente se, existe ${y\in B}$ tal que ${(x, y)\in R}$ e ${(y, z)\in S}$ . Em notação infixa

$\displaystyle x \mathrel{(S\circ R)} z \Leftrightarrow \exists y( x\mathrel{R}y \land y\mathrel{S}z)$

Não é difícil ver que a composição ordinária de funções é um caso especial de composição de relação.

Por exemplo, considere as relações

$\displaystyle \begin{array}{rcl} R &=& \{(1, 1), (1, 4), (2, 3), (3, 1), (3, 4)\}\\ S &=& \{(1, 0), (2, 0), (3, 1), (3, 2), (4, 1)\} \end{array}$

A composição delas é

$\displaystyle S\circ R = \{(1, 0), (1, 1), (2, 1), (2, 2), (3, 0), (3, 1)\}$

As relações também têm inversa

$\displaystyle x\mathrel {R^{-1}} y \Leftrightarrow y\mathrel{R}x.$

Ao contrário das funções, toda relação tem uma inversa.

Por exemplo, tome ${A = \{1, 2, 3\}}$ e

$\displaystyle R = \{(1, 2), (1, 3), (2, 3)\}$

A relação inversa é

$\displaystyle R^{-1} =\{ (2, 1), (3, 1), (3, 2)\}.$

Ademais

$\displaystyle \begin{array}{rcl} R^{-1}\circ R &=& \{(1, 1), (1, 2), (2, 2), (2, 1)\}\\ R\circ R^{-1} &=& \{(2, 2), (2, 3), (3, 3), (3, 2)\} \end{array}$

Exercício 25 Qual é inversa da relação ${<}$ sobre ${{\mathbb N}}$ ?

Notação: Para uma relação genérica, usamos símbolos como ${\sim}$ , ${\equiv}$ , ${\simeq}$ , ${\approx}$ ao invés de ${R}$ .

6.2. Classificação de relações

Uma relação binária ${\sim}$ sobre um conjunto ${A}$ pode ou não ter uma das seguintes propriedades:

reflexiva para todo ${a\in A}$ , ${a\sim a}$ ;
irreflexiva para todo ${a\in A}$ , ${a\not\sim a}$ ;
simétrica para todo ${a\in A}$ , para todo ${b\in A}$ , se ${a\sim b}$ então ${b\sim a}$ ;
antissimétrica para todo ${a\in A}$ , para todo ${b\in A}$ , se ${a\sim b}$ e ${b\sim a}$ então ${b=a}$ ;
transitiva para todo ${a\in A}$ , para todo ${b\in A}$ , para todo ${c\in A}$ , se ${a\sim b}$ e ${b\sim c}$ então ${a\sim c}$ .

Por exemplo, em ${{\mathbb R}}$ a relação ${x\sim y}$ se, e só se, ${|x-y|< 1}$ é reflexiva, simétrica e transitiva.

Uma relação pode ser simétrica e antissimétrica ao mesmo tempo, ou pode não ser nem simétrica nem antissimétrica. Uma relação pode ser nem reflexiva e nem irreflexiva porém, se o conjunto ${A}$ não é vazio, uma relação não pode ser ao mesmo tempo reflexiva e irreflexiva sobre ${A}$ .

Por exemplo, as relações sobre ${A = \{1, 2, 3, 4\}}$

${R_1 = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (3, 4), (4, 1), (4, 4)\}}$ é reflexiva.
${ R_2 = \{(1, 1), (1, 2), (2, 1)\}}$ é simétrica.
${ R_3 = \{(1, 1), (1, 2), (2, 1), (2, 2), (3, 3), (4, 1), (1, 4), (4, 4)\}}$ é reflexiva e simétrica.
${R_4 = \{(2, 1), (3, 1), (3, 2), (4, 1), (4, 2), (4, 3)\}}$ é irreflexiva, antissimétrica e transitiva.
${R_5 = \{(1, 1), (1, 2), (1, 3), (1, 4), (2, 2), (2, 3), (2, 4), (3, 3), (3, 4), (4, 4)\}}$ é reflexiva, antissimétrica e transitiva.
${R_6 = {(3, 4)}}$ é irreflexiva, antissimétrica e transitiva.

Exercício 26 A seguir, considere ${A=\{1,2,3,4\}}$ e ${B=\{1,2,3\}}$ e classifique, quanto as propriedades acima, as relações

${R_1=\{(1,2),(2,1),(1,3),(3,1)\}}$ .

${R_2=\{(1,1),(2,2),(3,3)\}}$ .

${R_3=\{(1,1),(2,2),(3,3),(2,3)\}}$ .

${R_4=\{(1,1),(2,3),(3,3)\}}$ .

${R_5=\{(1,2),(2,3),(3,1)\}}$ .

6.3. Relações de equivalência

Uma relação é de equivalência se for reflexiva, simétrica e transitiva.

São exemplos de relações de equivalência

${=}$ é uma relação de equivalência em ${{\mathbb N}}$ .
${\leq }$ não é uma relação de equivalência em ${{\mathbb N}}$ .
Se ${T}$ e ${S}$ são triângulos no plano e ${T\cong S}$ se os triângulos são semelhantes, então ${\cong}$ é relação de equivalência sobre o conjunto de todos os triângulos no plano.
Semelhança de matriz é uma relação de equivalência sobre o conjuntos de todas as matrizes quadradas de ordem ${n}$ de números reais.
${\cong\pmod 3}$ é a relação dada pelos pares de inteiros que deixam o mesmo resto quando divididos por ${3}$ , é de equivalência.
${\subset}$ não é relação de equivalência sobre o conjunto das partes de ${A}$ .

Partição de um conjunto

O conjunto ${\mathcal{A}}$ é uma partição do conjunto ${A}$ se seus elementos são subconjuntos não-vazio de ${A}$ , disjuntos dois-a-dois e a união deles é ${A}$ , isto é,

(a) para todo ${B\in \mathcal A}$ , ${B\neq \emptyset}$ e ${B\subseteq A}$ ;
(b) para todos ${B}$ , ${C\in \mathcal A}$ , ${B\neq C\Rightarrow B\cap C =\emptyset}$ ;
(c) ${\displaystyle\bigcup \mathcal A =A}$ .

Por exemplo, sejam ${R_0}$ , ${R_1}$ e ${R_2}$ subconjuntos de ${{\mathbb Z}}$ definidos por

$\displaystyle R_i = \{n \in {\mathbb Z} : n \text{ dividido por } 3 \text{ deixa resto }i \}$

${\{R_0,R_1,R_2\}}$ é uma partição de ${{\mathbb Z}}$ .

Teorema 34 Se ${\mathcal{A}}$ é uma {partição} do conjunto ${A}$ , então a relação binária ${\sim}$ sobre ${A}$ dada por ${a\sim b}$ se, e só se, existe ${B\in \mathcal A}$ tal que ${\{a,b\} \subseteq B}$ é uma relação de equivalência.

Demonstração: Sejam ${A}$ , ${\mathcal A}$ e ${\sim}$ como dados no enunciado.

A relação ${\sim}$ é reflexiva pois para todo ${a\in A}$ existe um ${B\in \mathcal A}$ tal que ${a\in B}$ pelo item (c) da definição de partição.

A relação ${\sim}$ é simétrica pois para todos ${a,b\in A}$ se existe um ${B}$ tal que ${\{a, b\}\subseteq B}$ então ${\{b, a\}\subseteq B}$ .

A relação ${\sim}$ é transisiva pois para todos ${a,b,c\in A}$ se existe um ${B}$ tal que ${\{a, b\} \subseteq B }$ e existe um ${C}$ tal que ${\{b, c\}\subseteq C}$ então, como ${b\in B\cap C}$ , temos ${B=C}$ pelo item (b) da definição de partição. $\Box$

No exemplo acima ${\{R_0,R_1,R_2\}}$ é a partição de ${{\mathbb Z}}$ dada pelos restas da divisão por ${3}$ . Definimos ${\sim}$ sobre ${{\mathbb Z}}$ por

$\displaystyle a \sim b \text{ se existe } i\in \{0,1,2\} \text{ tal que }a,b\in R_i$

isto é, ${a}$ e ${b}$ estão na relação se deixam o mesmo resto quando divididos por ${3}$ .

Classes de equivalência

Seja ${\sim}$ uma relação de equivalência sobre o conjunto ${A\neq\emptyset}$ e ${a\in A}$

$\displaystyle [a]_\sim = \{ b\in A \colon b\sim a\}$

é o subconjunto de ${A}$ formado por todos os elementos equivalentes a ${a}$ , chamado de classe de equivalência de ${a}$ . O elemento dentro dos colchetes é chamado de representante da classe.

Por transitividade, qualquer elemento da classe pode ser seu representante. Seja ${b\in A}$ com ${b\sim a}$ . Para todo ${c\in [a]_\sim}$ vale ${c\sim a}$ , portanto, ${c\sim b}$ , logo ${c\in [b]_\sim}$ . Reciprocamente, se ${c\in [b]_\sim}$ então ${c\in [a]_\sim}$ , por argumento análogo. Assim ${[a]_\sim=[b]_\sim}$ . Também, se ${[a]_\sim=[b]_\sim}$ então de ${a\in [a]_\sim}$ temos ${a\in [b]_\sim}$ , portanto ${a \sim b}$ . Com isso provamos

$\displaystyle a\sim b \Leftrightarrow [a]_\sim=[b]_\sim. \ \ \ \ \ (33)$

O que podemos dizer no caso ${[a]_\sim\neq [b]_\sim}$ ? Imediatamente, por (33) que ${a\not\sim b}$ . Para qualquer ${c\in A}$ , se ${c\sim a}$ então ${b\not\sim c}$ , caso contrário teríamos uma contradição pela transitividade, de modo que ${[a]_\sim \cap [b]_\sim = \emptyset}$ .

Concluindo, dos parágrafos precedentes temos que para as classes de equivalência vale um dos casos: para quaisquer ${a,b\in A}$

${[a]_\sim=[b]_\sim}$ , ou
${[a]_\sim\cap [b]_\sim =\emptyset}$ .

O conjunto quociente de ${A}$ pela relação de equivalência ${\sim}$ é o conjunto das classes de equivalência da relação

$\displaystyle A/{\sim} = \{ [a]_\sim \colon a\in A\}. \ \ \ \ \ (34)$

Já provamos, no teorema 34, que um partição do conjunto não vazio ${A}$ define uma relação de equivalência. A recíproca também vale, uma relação de equivalência sobre ${A}$ define uma partição desse conjunto.

Teorema 35 Se ${\sim}$ é uma relação de equivalência sobre o conjunto ${A\neq\emptyset}$ então ${A/{\sim}}$ é uma partição de ${A}$ .

Demonstração: Exercício. $\Box$

Por exemplo, no caso de exemplo dos restos de divisão por ${3}$

$\displaystyle \begin{array}{rcl} R_0 = [0] &=& \{\dots,-9, -6,-3,0,3,6,9,12,15, \dots\} \\ R_1 = [1] &=& \{\dots,-8,-5,-2,1,4,7,10,13,16, \dots\} \\ R_2 = [2] &=& \{\dots,-7,-4,-1,2,5,8,11,14,17, \dots\} \end{array}$

Observemos que ${[0] =[3]=[6]}$ .

6.6. Relações de ordem

Uma relação ${\preccurlyeq}$ sobre um conjuto ${A}$ é uma relação de ordem se essa for

reflexiva,
antissimétrica e
transitiva.

Exemplo: ${\subseteq}$ é uma relação de ordem sobre ${2^{\mathbb Z}}$ e ${\leq }$ é uma relação de ordem sobre ${{\mathbb Z}}$ .

Há uma diferença importante entre as duas relações de ordem do exemplo anterior, na primeira, ${\subseteq}$ , pode haver elementos incomparáveis, por exemplo, os conjuntos ${\{1,2\}}$ e ${\{2,3\}}$ são incomparáveis

$\displaystyle \{1,2\} \not\subseteq \{2,3\} \text{ e } \{2,3\} \not\subseteq \{1,2\}$

enquanto que quaisquer dois números inteiros ${x}$ e ${y}$ são comparáveis

$\displaystyle x\leq y \text{ ou } y\leq x.$

Se em ${A}$ há elementos incomparáveis sob a relação de ordem ${\preccurlyeq}$ então

$\displaystyle (A,\preccurlyeq) \text{ \'e uma ordem parcial}$

ou, ${A}$ e conjunto parcialmente ordenado por ${\preccurlyeq}$ Caso contrário

$\displaystyle (A,\preccurlyeq) \text{ \'e uma ordem total}$

ou, ${A}$ é conjunto totalmente ordenado por ${\preccurlyeq}$ .

Exemplo: ${(2^A,\subseteq)}$ , ${({\mathbb Z},\leq)}$ e ${({\mathbb Z}^+,|)}$ são ordens parciais, somente ${({\mathbb Z},\leq)}$ é total.

Máximos e mínimos

Definição 19 Em ${(A,\preccurlyeq)}$ temos que ${x\in A }$ é um elemento minimal se, e só se, para todo ${y\in A}$ , ${y \preccurlyeq x}$ implica que ${y = x}$ .

Em ${(A,\preccurlyeq)}$ temos que ${x\in A}$ é um elemento maximal de ${A}$ se para todo ${y}$ , ${x \preccurlyeq y}$ implica que ${y = x}$ .

Um conjunto parcialmente ordenado pode ter qualquer número de elementos minimais: os números inteiros não têm mínimo, os naturais têm um mínimo e um conjunto com ${k}$ elementos nenhum dos quais são comparáveis entre si tem ${k}$ mínimos. As afirmações análogas para maximal também valem.

Exemplo: Sejam ${A = \{1, 2, 3, 4, 5, 6\}}$ e tomemos em ${A}$ a relação de ordem ${\preccurlyeq}$ dada por ${\{(1, 3), (2, 3), (1, 4), (2, 4), (3, 4), (5, 6), (1,1),(2,2),(3,3),(4,4),(5,5),(6,6)\}}$ . O número ${2\in A}$ , por exemplo, é um elemento minimal de ${(A, \preccurlyeq)}$ , pois não existe nenhum par ${(a, 2)}$ , ${a\neq 2}$ , na relação. Os elementos minimais ${(A, \preccurlyeq)}$ são ${1}$ , ${2}$ e ${5}$ .

Exemplo: Tomemos ${A = {\mathbb N}\setminus\{0, 1\}}$ e ${|}$ a relação “divide”. O número ${21}$ não é minimal pois, por exemplo, ${(3, 21)\in |}$ e ${3\neq 21}$ . O número ${17}$ é minimal pois não existe nenhum par ${(a, 17)}$ com ${a\neq 17}$ em ${|}$ (a única possibilidade seria o ${1}$ que não está no conjunto). Note que os elementos minimais de ${(A,\preccurlyeq)}$ são os números primos.

Quando ${A}$ é um conjunto de conjuntos e a relação de ordem é ${\subseteq}$ , um elemento minimal de ${(A,\subseteq)}$ é um conjunto que não contém propriamente nenhum outro elemento de ${A}$ . Por exemplo, se ${A = \{ \{2\} , \{1, 2\} , \{1, 3\} , \{1, 2, 4\} , \{3, 4, 5\} \}}$ então ${\{1, 2, 4\}}$ não é minimal (contém propriamente ${\{1, 2\}\in A}$ ). São os elementos minimais ${\{2\}}$ , ${\{1, 3\}}$ e ${\{3, 4, 5\}}$ . O elemento ${\{2\}}$ não é maximal (por que?). Os elementos maximais de são ${\{1, 3\}}$ , ${\{1, 2, 4\}}$ e ${\{3, 4, 5\}}$ .

Definição 20 Se um elemento ${x\in A}$ satisfaz ${x\preccurlyeq y}$ para todo ${y\in A}$ , então ${x}$ é um mínimo de ${A}$ .

Se um elemento ${x\in A}$ satisfaz ${y\preccurlyeq x}$ para todo ${y\in A}$ , então ${x}$ é um máximo de ${A}$ .

Um conjunto parcialmente ordenado tem no máximo um mínimo. Por exemplo, ${0}$ nos naturais é mínimo. Também pode não ter um mínimo como os inteiros negativos ou pode não ter mínimo porque tem mais de um elemento minimal. As afirmações análogas para máximo também valem.

Exemplo: Seja ${A = \{2, 4, 6, 8\}}$ e seja ${R}$ a relação ${\leq}$ (menor ou igual) sobre ${{\mathbb Z}}$ . O inteiro ${2}$ é um mínimo de ${(A, R)}$ . Por outro lado, se ${A}$ é o conjunto dos inteiros pares então ${(A, R)}$ não tem mínimo.

Exemplo: O elemento ${\{2, 4\}}$ de ${\{ \{1, 2, 4\} , \{2, 4\} , \{2, 3, 4\} , \{2, 4, 5\} , \{2, 3, 4, 6\} \}}$ , com a relação de inclusão, é mínimo

Exemplo: Exemplo da diferença entre um elemento maximal e um elemento máximo: considere o conjunto ${\mathcal P}$ de todos os subconjuntos de ${{\mathbb N}}$ com no máximo três elementos e ordenados por inclusão ${\subseteq}$ . Então ${\{0, 1, 2\}}$ é um elemento maximal de ${(\mathcal P,\subseteq)}$ pois ninguém de ${\mathcal P}$ o contém e ${\{0, 1, 2\}}$ não é máximo porque não contém o elemento ${\{3\}}$ de ${\mathcal P}$ .

Exercício 27 Determine os elementos maximais/minimais/máximo/mínimo em ${({\mathbb Z}^+, |)}$ .

Exercício 28 Prove que se ${(A,\preccurlyeq)}$ tem máximo então ele é único.

Exercício 29 Prove que todo elemento máximo de uma ordem é maximal.

Boa ordem

${(A,\preccurlyeq)}$ é boa ordem se ${\preccurlyeq}$ é uma ordem total e todo subconjunto não vazio de ${A}$ tem mínimo. A propriedade útil da Boa-ordem é que ela permite provas por indução, como nos naturais.

Notação: ${ a \prec b}$ significa ${ a \preccurlyeq b}$ e ${a\neq b}$ .

Teorema 36 (Princípio da Indução para conjuntos bem-ordenados) Seja ${(A,\preccurlyeq)}$ bem-ordenado e ${P}$ um predicado sobre ${A}$ . Se para todo ${y\in A}$

${P(x)}$ verdadeiro para todo ${x\in A}$ com ${x\prec y}$ implica que ${P(y)}$ é verdadeiro

então ${P(a)}$ é verdadeiro para todo ${a\in A}$ .

Em resumo

$\displaystyle \forall y\in A \left( \Big(\forall x\in A (x \prec y \Rightarrow P(x))\Big)\Rightarrow P(y)\right) \Rightarrow \forall a\in A,~P(a) \ \ \ \ \ (35)$

Demonstração: A prova é por contradição. Sejam ${(A,\preccurlyeq)}$ uma boa ordem e ${P}$ um predicado sobre ${A}$ .

Suponha que que para todo ${y\in A}$ vale que

$\displaystyle \Big(\forall x\in A (x \prec y \Rightarrow P(x))\Big)\Rightarrow P(y) \ \ \ \ \ (36)$

e assuma que existe ${a\in A}$ tal que ${P(a)}$ não é verdadeiro.

Defina

$\displaystyle S=\{a\in A \colon \text{n\~ao }P(a) \} \ \ \ \ \ (37)$

que, por hipótese é não vazio. Seja ${m}$ o menor elemento de ${S}$ com respeito a ordem ${\preccurlyeq}$ . Então, para todo ${x\prec m}$ vale ${P(x)}$ . Por (36), ${P(m)}$ é verdadeiro, uma contradição. $\Box$

Exercicio Considere a relação ${\trianglelefteq}$ sobre o conjunto ${{\mathbb Z}^-}$ dos inteiros negativos definida por

${a\trianglelefteq b}$ se, e somente se, ${|a|\leq |b|}$ .

Prove que ${\trianglelefteq}$ é uma relação de ordem sobre ${{\mathbb Z}^-}$ .
Prove que ${\trianglelefteq}$ é uma boa-ordem sobre ${{\mathbb Z}^-}$ .
Seja ${f:{\mathbb Z}^- \rightarrow {\mathbb Z}^-}$ dada por ${f(-1)=-1}$ e para ${n<-1}$ , ${f(n)=f(n+1)+n}$ .
Use o Princípio de Indução para conjuntos bem-ordenados em ${({\mathbb Z}^-,\trianglelefteq)}$ para provar que

$\displaystyle f(n) = -\frac{|n|(|n|+1)}2.$