5 Relações de equivalência

5.1 Relações de equivalência

Definição 5.1 Seja $A$ um conjunto. Uma relação $R\subseteq A\times A$ é dita relação de equivalência se

$R$ é reflexiva (ou seja, $aRa$ para todo $a\in A$);
$R$ é simétrica (ou seja $aRb$ implica $bRa$ para todo $a,b\in A$); e
$R$ é transitiva (ou seja $aRb$ e $bRc$ implica $aRc$ para todo $a,b,c\in A$).

As relações de equivalência são normalmente denotados com os símbolos $\equiv$, $\cong$, etc, e escrevemos $a\equiv b$ ou $a\cong b$ em vez de $aRb$.

Exemplo 5.1 O protôtipo das relações de equivalência é a relação de igualdade. A relação de igualdade \[ \{(a,a)\mid a\in A\} \] é uma relação de equivalência para todo conjunto $A$.

Exemplo 5.2 Seja $A=\{1,2,3,4,5\}$ e seja \[ \equiv=\{(1,1),(2,2),(3,3),(4,4),(5,5),(1,2),(2,1),(3,4),(3,5),(4,3),(4,5),(5,3),(5,4)\} \] Então $\equiv$ é uma relação de equivalência.

Exemplo 5.3 Considere a relação $R$ em $\Z$ definido como \[ a\equiv b\quad\mbox{se e somente se $a-b$ é par}. \] Note que $\equiv$ é uma relação de equivalência. Também note que $a\equiv b$ se e somente se $a$ e $b$ tem a mesma paridade. Ou seja, $0\equiv 2$, $0\equiv -2$, $0\equiv 4$, $0\equiv -4$, $1\equiv -1$, $1\equiv 3$, $1\equiv -3$, etc, mas $2\not\equiv -1$.

5.2 Classes de equivalência

Definição 5.2 Seja $A$ um conjunto e $R$ uma relação de equivalência. Seja $a\in A$. O conjunto \[ [a]_\equiv=\{b\in A\mid a\equiv b\} \] é chamado de classe de equivalência de $a$ pela relação $\equiv$. Quando não tem perigo de ambiguidade, escrevemos $[a]$ em vez de $[a]_\equiv$. Note que $[a]\subseteq A$.

Exemplo 5.4 No Exemplo 5.1, a classe de equivalência de um elemento $a\in A$ é o conjunto $\{a\}$. No Exemplo 5.2, temos que \[ [1]=[2]=\{1,2\}\quad \mbox{e}\quad [3]=[4]=[5]=\{3,4,5\}. \] No Exemplo 5.2, temos que \[ [a]=\{0,\pm 2,\pm 4,\ldots\}=\{2k\mid k\in\Z\}\quad\mbox{se}\quad \mbox{$a$ é par}, \] e \[ [a]=\{\pm 1,\pm 3,\ldots\}=\{2k+1\mid k\in\Z\}\quad\mbox{se}\quad \mbox{$a$ é ímpar}. \] Ou seja, temos apenas duas classes de equivalência, uma formada pelos números pares, e a outra formada pelos números ímpares.

Lema 5.1 Seja $A$ um conjunto e assuma que $\equiv$ é uma relação de equivalência. Temos as seguintes propriedades para todo $a,b\in A$.

$a\in [a]$;
se $[a]\cap [b]\neq \emptyset$ então $[a]=[b]$.

Comprovação.

Note que $a\in[a]$ é equivalente a dizer que $a\equiv a$ e isso vale pois a relação $\equiv$ é reflexiva.
Assuma que $c\in [a]\cap [b]$. Isso quer dizer que $a\equiv c$ e $b\equiv c$. Por simetria temos também que $c\equiv a$. Afirmamos que $[a]=[b]$. Provaremos isso verificando que $[a]\subseteq [b]$ e $[b]\subseteq [a]$. Assuma primeiro que $x\in[a]$; ou seja $a\equiv x$. Então \[ b\equiv c\equiv a\equiv x. \] Aplicando a transitividade, obtemos que $b\equiv x$ e $x\in [b]$. Portanto obtemos que $[a]\subseteq [b]$. A inclusão que $[b]\subseteq [c]$ pode ser verificado por argumento similar.

5.3 Partições

Definição 5.3 Seja $A$ um conjunto. Um conjunto $\mathcal P$ de subconjuntos de $A$ é dito partição de $A$ se

todo elemento $a\in A$ pertence a um subconjunto $X\in \mathcal P$; e
se $X,Y\in \mathcal P$ são distintos, então $X\cap Y=\emptyset$.

Os conjuntos $X\in\mathcal P$ são chamados de partes ou blocos da partição $\mathcal P$.

Exemplo 5.5 Todo conjunto $A$ tem duas partições triviais: \[ \{A\}\quad\mbox{e}\quad \{\{a\}\mid a\in A\}. \] O conjunto $\{\{1,2\},\{3,4,5\}\}$ é uma partição do conjunto $\{1,2,3,4,5\}$. O conjunto dos números inteioros pode ser particionado como \[ \{\{2k\mid k\in \Z\},\{2k+1\mid k\in\Z\}\}. \] Ou seja, o conjunto dos inteiros pode ser particionado para o conjunto de pares e o conjunto de ímpares.

Teorema 5.1 Seja $A$ um conjunto. Se $\equiv$ é uma relação de equivalência sobre $A$, então o conjunto das classes de equivalência é uma partição de $A$.

Reciprocamente, se $\mathcal P$ é uma partição de $A$, então pode-se definir uma relação de equivalência $\equiv_{\mathcal P}$ pondo \[ a\equiv_{\mathcal P} b\quad \bicond\quad \mbox{$a$ e $b$ estão no mesma parte de $\mathcal P$} \] As classes de equivalência de $\equiv_{\mathcal P}$ são as partes de $\mathcal P$.

Comprovação. Assuma primeiro que $\equiv$ é uma relação de equivalência. Seja $\mathcal C$ o conjunto de classes de equivalência. Por item 1. do Lema 5.1, obtemos que $a\in [a]\in \mathcal C$ para todo $a\in A$. Então o item 1. da Definição 80.1 está verificada. O item 2. da Definição 80.1 está verdadeira para $\mathcal C$ por causa do item 2. do Lema 5.1.

Assuma agora que $\mathcal P$ é uma partição de $A$ e defina $\equiv_{\mathcal P}$ como no enunciado do teorema. Vamos verificar as três propriedades na definição Definição 5.1.

Reflexividade: se $a\in A$, então $a$ claramente pertence à mesma parte de $\mathcal P$ que $a$ e $a\equiv_{\mathcal P} a$. Logo $\equiv_{\mathcal P}$ é reflexiva.
Simetria: se $a\equiv_{\mathcal P}b$, então $a,b$ pertencem à mesma parte de $\mathcal P$. Logo $b,a$ também pertencem à mesma parte e assim $b\equiv_{\mathcal P}a$. Portanto $\equiv_{\mathcal P}$ é simétrica.
Transitividade: se $a\equiv_{\mathcal P}b$ e $b\equiv_{\mathcal P}c$, então $a$ e $b$ pertencem à mesma parte de $\mathcal P$ e $b$ e $c$ também pertencem à mesma parte de $\mathcal P$. Isso implica que $a$ e $c$ pertencem à mesma parte de $\mathcal P$. Portanto $a\equiv_{\mathcal P}c$ e a relação $\equiv_{\mathcal P}$ é transitiva.