Relação de equivalência

Uma relação de equivalência é uma relação binária em um conjunto que é reflexiva, simétrica e transitiva.

Motivação

A relação de equivalência representa uma espécie de refinamento da relação de igualdade. Sempre podemos decidir se dois elementos de um conjunto são iguais, isto é, se a = b. Mas às vezes nos convém descobrir se dois elementos são apenas parecidos, não necessariamente iguais. Ou seja — se têm em comum alguma propriedade fundamental. Por exemplo, podemos considerar dois livros parecidos se são do mesmo gênero — ou, usando a equivalência: dois livros são equivalentes se são do mesmo gênero.

O que esperaríamos de uma equivalência assim? Vamos tomar outro exemplo. Duas palavras são parecidas/equivalentes se têm o mesmo comprimento.

Provavelmente esperaríamos que, ao medir a semelhança de duas palavras idênticas, resultasse que elas são parecidas. Ou seja, para todas as palavras deve valer que são parecidas/equivalentes a si mesmas. Na linguagem das relações: uma relação de equivalência deve ser reflexiva.

Além disso, se a palavra “carro” é parecida/equivalente à palavra “livro”, então certamente esperamos que a palavra “livro” também seja equivalente à palavra “carro”. Em outras palavras, a ordem não importa. Na linguagem das relações: uma relação de equivalência deve ser simétrica.

E, por fim, se a palavra “casa” é parecida/equivalente à palavra “pato” e a palavra “pato” é equivalente à palavra “mesa”, então esperamos que o par de palavras “casa” e “mesa” também seja equivalente. Ou seja, uma relação de equivalência deve ser também transitiva.

Não esperamos mais nada de uma equivalência.

Exemplos

Outros exemplos de equivalências:

• Morar na mesma cidade. Pedro certamente mora na mesma cidade que Pedro (reflexividade). Se Pedro mora na mesma cidade que Lucas, então Lucas também mora na mesma cidade que Pedro (simetria). E se Lucas mora na mesma cidade que Gabriel, então Pedro também mora na mesma cidade que Gabriel (transitividade).
• Estudar na mesma turma. Ana certamente estuda na mesma turma que Ana (reflexividade). Se Ana e Beatriz estudam na mesma turma, então Beatriz e Ana também estudam na mesma turma (simetria). E se Beatriz e Júlia estudam na mesma turma, então Ana e Júlia também estudam na mesma turma (transitividade).
• (a, b) ∈ R se e somente se a − b é um número par; a, b são números inteiros. Reflexividade: a − a = 0, e zero é um número par. Simetria: seja c = a − b. Então b − a = −(a − b) = −c. Se c é par, então −c também deve ser par. Transitividade: sejam p = a − b e q = b − c. Sabemos que p e q são números pares. Agora temos de demonstrar que a − c é um número par. Nessa expressão, substituímos c por c = b − q: a − (b − q), que é igual a a − b + q. Das hipóteses, sabemos que a − b é um número par. Se somarmos a um número par outro número par q, obtemos novamente um número par.
• Igualdade. A igualdade é uma equivalência e, ao mesmo tempo, é a menor equivalência em qualquer conjunto M.

Equivalência trivial

Seja M um conjunto não vazio. Qual é a menor equivalência possível R no conjunto M? O menor subconjunto possível do produto cartesiano M × M é o conjunto vazio ∅. O conjunto vazio cumpre as condições de uma equivalência?

Essa relação certamente é simétrica: como a relação R não tem nenhum elemento, a condição de simetria é cumprida automaticamente e de forma trivial. O mesmo vale para a transitividade. O problema está na reflexividade. A definição diz que, para todos os elementos x do conjunto M, vale (x, x) ∈ R. Isso é cumprido? O conjunto M é não vazio, portanto contém algum elemento, por exemplo q. O par (q, q) está na relação R? Não está. Logo, a relação R não é reflexiva.

Qual é a menor relação que cumpre a reflexividade? A relação de igualdade. A relação R deve conter no mínimo os pares (x, x) para todos os elementos de M. E essa é justamente a relação identidade. Essa relação é simétrica? É fácil ver que sim. Do mesmo modo, é fácil ver que ela também é transitiva. A menor relação de equivalência no conjunto M é, portanto, a relação identidade, que representamos por id_M e que contém os pares (x, x) para todo x ∈ M.

Qual é a maior equivalência possível no conjunto M? O maior subconjunto é o conjunto inteiro M × M. Ele cumpre as condições de uma equivalência? É provavelmente óbvio que sim.

Classe de equivalência

Toda equivalência divide o conjunto M em um sistema de conjuntos disjuntos, que chamamos de classes de equivalência.

Considere o conjunto de todas as palavras M e a equivalência R palavras de mesmo comprimento. Ou seja, (a, b) ∈ R se e somente se as palavras a e b têm o mesmo comprimento. Essa equivalência divide o conjunto de palavras em vários conjuntos menores, que sempre conterão palavras do mesmo comprimento. As classes de equivalência individuais podem ser distinguidas por um índice inferior, que ao mesmo tempo indicará o comprimento das palavras no conjunto em questão:

• M₁ = {a, e, o, …}
• M₂ = {de, em, se, eu, um, …}
• M₃ = {mas, por, sem, que, …}
• M₄ = {casa, pato, mesa, vida, …}
• …

Repare em duas coisas: 1) os conjuntos individuais são disjuntos entre si, não têm nenhum elemento em comum. 2) todos os elementos de cada conjunto individual são equivalentes entre si. Todas as palavras do conjunto M₃ são equivalentes entre si, porque todas as palavras têm comprimento três, ou seja, o mesmo comprimento, que é a condição da equivalência.

Além disso, cada elemento define de forma única a sua classe de equivalência. Isso costuma ser escrito com a notação M[x], em que x ∈ M. Se escrevêssemos M[mas], definiríamos de forma única a classe de equivalência que já tínhamos chamado de M₃.

Como encontramos, afinal, a classe de equivalência se conhecemos algum x ∈ M? Percorremos todos os elementos de M e verificamos quais deles são equivalentes ao elemento x. Esses serão todos os elementos que farão parte da classe de equivalência M[x].

Para M[mas], percorreríamos todas as palavras de M e guardaríamos em M₃ as palavras que têm comprimento três.

Definição e propriedades da classe de equivalência

Podemos definir a classe de equivalência assim. Considere um conjunto M e, nele, uma equivalência R definida. Então, por classe de equivalência que contém o elemento x ∈ M entendemos:

$$M[x]=\{y\in M;(x,y)\in R\}$$

A definição diz que são todos os y equivalentes ao elemento dado x. Como a relação de equivalência é reflexiva, desse modo entra ali também o próprio elemento x — porque x é equivalente a si mesmo.

Por partição da equivalência entendemos, então, o conjunto de todas as classes de equivalência. Assim, a partição do conjunto de todas as palavras seria o conjunto {M₁, M₂, M₃, …}.

Propriedades básicas das classes de equivalência:

• (a, b) ∈ R se e somente se M[a] = M[b]. Se temos dois elementos a, b que são equivalentes, então as suas classes de equivalência devem ser iguais.
• Ao contrário, se não vale (a, b) ∈ R, então também M[a] ≠ M[b], mais precisamente M[a] ∩ M[b] = ∅. Se temos dois elementos que não são equivalentes, então as suas classes da partição são disjuntas.
• A união de todas as classes de equivalência deve dar o conjunto original M: M₁ ∪ M₂ ∪ … ∪ M_n = M. (A notação anterior vale apenas para um número finito de classes de equivalência, mas em geral pode haver infinitas.)

Exemplos de partições de uma equivalência

Primeiro exemplo, números ímpares e pares:

Considere uma equivalência simples R definida nos números naturais não nulos N. (a, b) ∈ R se e somente se a e b são ambos ímpares ou a e b são ambos pares. Exemplos de elementos: (1, 7), (13, 9), (4, 6), (8, 136). Vamos agora determinar a partição dessa equivalência em classes de equivalência.

Vamos por partes. A que será igual a classe N[1]? Precisamos encontrar todos os números equivalentes ao número um. Pela condição da equivalência, são todos os números ímpares, portanto N[1] = {1, 3, 5, 7, 9, …}.

A que será igual a classe N[2]? Encontramos todos os números equivalentes ao dois. São todos os números pares: N[2] = {2, 4, 6, 8, 10, …}.

Agora N[3]. Quais números são equivalentes ao três? Todos os números ímpares. Mas, com isso, obtemos o conjunto N[1], que calculamos dois parágrafos atrás. Do mesmo modo para N[4]: ali, novamente, o conjunto dos números pares.

Vemos que, daqui em diante, os mesmos conjuntos continuariam se repetindo. Isso também se vê pelo fato de que, qualquer que seja o outro número natural n que tomemos, valerá n ∈ N[1] ou n ∈ N[2]. Não temos outros números naturais além dos ímpares e dos pares, portanto esses dois conjuntos formam a partição da equivalência.

É parecido com imaginar uma equivalência no conjunto de pessoas, a e b são ambos homens ou a e b são ambas mulheres. Então obteríamos, como partição, o conjunto das mulheres e o conjunto dos homens.

Segundo exemplo, valor absoluto:

Considere a equivalência R no conjunto dos números inteiros Z definida assim: (a, b) ∈ R se e somente se |a| = |b|. (Essas barras verticais são o valor absoluto.) Novamente, vamos por partes:

• Z[0] = {0}. O zero está em relação apenas com o zero.
• Z[1] = {−1, 1}. O um está em relação com o um e com o menos um, porque |1| = |−1|.
• Z[2] = {−2, 2}. O dois está em relação com o dois e com o menos dois.
• Z[3] = {−3, 3}.
• …

Provavelmente está claro como isso continua. A partição completa seria, então, o conjunto de classes:

$$\{\{a,-a\};a\in {\mathbb{Z}}_0^{+}\}$$

(Ou seja, todos os pares a, −a, em que a é um número inteiro não negativo.) Você vê que há infinitas classes.