Relação de equivalência

Na matemática, uma relação de equivalência é uma relação binária que é reflexiva, simétrica e transitiva. A relação "é igual a" é o exemplo canônico de uma relação de equivalência, onde para qualquer objeto a, b e c:

• a = a (propriedade reflexiva),
• se a = b então b = a (propriedade simétrica), e
• se a = b e b = c então a = c (propriedade transitiva).

As 52 relações de equivalência em um conjunto de 5 elementos representadas por matrizes lógicas 5 × 5 (campos coloridos, incluindo aqueles em cinza claro, representam os uns; campos brancos por zeros.) Os índices de linha e coluna de células não brancas são os elementos relacionados, enquanto as cores diferentes, exceto cinza claro, indicam as classes de equivalência (cada célula cinza claro é sua própria classe de equivalência).

Como consequência das propriedades reflexivas, simétricas e transitivas, qualquer relação de equivalência fornece uma partição do conjunto subjacente em classes de equivalência desconexas. Dois elementos do conjunto dado são equivalentes entre si se e somente se pertencem à mesma classe de equivalência.

Notação

Várias notações são usadas na literatura para denotar que dois elementos a e b de um conjunto são equivalentes em relação a uma relação de equivalência R; os mais comuns são "a ~ b" e "a ≡ b", que são usados quando R está implícito e variações de "a ~_R b", "a ≡_R b", ou "aRb" para especificar R explicitamente. A não equivalência pode ser escrita "a ≁ b" ou "${\displaystyle a\not \equiv b}$".

Definição

Uma dada relação binária ${\displaystyle R}$ sobre um conjunto X é considerada uma relação de equivalência se e somente se for reflexiva, simétrica e transitiva. Isto é, para todos a, b e c em X:

${\displaystyle \forall a\in X,\ aRa}$ (reflexividade)

${\displaystyle \forall a,b\in X,\ aRb\Rightarrow \;bRa}$ (simetria)

${\displaystyle \forall a,b,c\in X,\ a\,R\,b\land b\,R\,c\;\Rightarrow a\,R\,c}$ (transitividade)

A classe de equivalência de ${\displaystyle a}$ sob ${\displaystyle R}$, denotada ${\displaystyle [a]}$, é definida como ${\displaystyle [a]=\{b\in X\mid a\sim b\}}$.

Exemplos

Exemplo simples

Considere que o conjunto ${\displaystyle \{a,b,c\}}$ tem a relação de equivalência ${\displaystyle \{(a,a),(b,b),(c,c),(b,c),(c,b)\}}$. Os conjuntos a seguir são classes de equivalência dessa relação:

${\displaystyle [a]=\{a\},~~~~[b]=[c]=\{b,c\}}$.

O conjunto de todas as classes de equivalência para esta relação é ${\displaystyle \{\{a\},\{b,c\}\}}$. Este conjunto é uma partição do conjunto ${\displaystyle \{a,b,c\}}$.

Relações de equivalência

A seguir, todas as relações de equivalência:

• "É igual a" no conjunto de números. Por exemplo, ${\displaystyle {\tfrac {1}{2}}}$ é igual a ${\displaystyle {\tfrac {4}{8}}}$.
• "Tem o aniversário no mesmo dia que" no conjunto de todas as pessoas.
• "É semelhante a" no conjunto de todos os triângulos.
• "É congruente a" no conjunto de todos os triângulos.
• "É congruente a, módulo n" nos inteiros.
• "Tem a mesma imagem sob uma função" nos elementos do domínio da função.
• "Tem o mesmo valor absoluto" no conjunto de números reais
• "Tem o mesmo cosseno" no conjunto de todos os ângulos.

Relações que não são equivalências

• A relação "≥" entre números reais é reflexiva e transitiva, mas não simétrica. Por exemplo, 7 ≥ 5 não implica que 5 ≥ 7. É, no entanto, uma ordem total.
• A relação "tem um fator comum maior que 1 com" entre números naturais maiores que 1, é reflexiva e simétrica, mas não transitiva. (Exemplo: Os números naturais 2 e 6 têm um fator comum maior que 1, e 6 e 3 têm um fator comum maior que 1, mas 2 e 3 não têm um fator comum maior que 1).
• A relação vazia R em um conjunto não vazio X (isto é, aRb nunca é verdadeira) é vagamente simétrica e transitiva, mas não reflexiva. (Se X também for vazio, então R é reflexiva.)
• A relação "é aproximadamente igual a" entre números reais, mesmo que definida com mais precisão, não é uma relação de equivalência, porque embora reflexiva e simétrica, não é transitiva, pois múltiplas pequenas mudanças podem se acumular para se tornar uma grande mudança. Entretanto, se a aproximação é definida assintoticamente, por exemplo, dizendo que duas funções f e g são aproximadamente iguais perto de algum ponto, se o limite de f - g é 0 naquele ponto, então isto define uma relação de equivalência.

Conexões com outras relações

• Uma ordem parcial é uma relação reflexiva, antissimétrica e transitiva.
• Igualdade é tanto uma relação de equivalência quanto uma ordem parcial. Igualdade é também a única relação em um conjunto que é reflexiva, simétrica e antissimétrica. Em expressões algébricas, variáveis iguais podem ser substituídas umas pelas outras, uma facilidade que não está disponível para variáveis relacionadas à equivalência. As classes de equivalência de uma relação de equivalência podem substituir uma a outra, mas não indivíduos dentro de uma classe.
• Uma ordem parcial estrita é irreflexiva, transitiva e assimétrica.
• Uma relação de equivalência parcial é transitiva e simétrica. Transitiva e simétrica implica reflexiva se e somente se para todo a ∈ X, existe um b ∈ X tal que a ~ b.
• Uma relação reflexiva e simétrica é uma relação de dependência, se finita, e uma relação de tolerância, se infinita.
• Uma pré-ordem é reflexiva e transitiva.
• Uma relação de congruência é uma relação de equivalência cujo domínio X é também o conjunto subjacente para uma estrutura algébrica e que respeita a estrutura adicional. Em geral, as relações de congruência desempenham o papel de núcleos de homomorfismos, e o quociente de uma estrutura por uma relação de congruência pode ser formado. Em muitos casos importantes, as relações de congruência têm uma representação alternativa como subestruturas da estrutura na qual elas são definidas. Por exemplo. as relações de congruência nos grupos correspondem aos subgrupos normais.
• Qualquer relação de equivalência é a negação de uma relação de separação, embora a afirmação inversa se mantenha apenas na matemática clássica (em oposição à matemática construtiva), uma vez que é equivalente à lei do terceiro excluído.
• Uma relação de série ~ satisfaz ∀ a ∃ b a ~ b. Evidentemente, é suficiente que uma relação de série seja simétrica e transitiva, pois também é reflexiva. De fato, desde que a relação é de série, todo elemento está na relação. Então, usando simetria, a reflexividade pode ser concluída a partir da transitividade, identificando a primeira e a terceira variáveis no axioma transitivo. Portanto, uma relação de equivalência pode ser alternativamente definida como uma relação de série, transitiva e simétrica.

Bem definida sob uma relação de equivalência

Se ~ é uma relação de equivalência em X, e P(x) é uma propriedade de elementos de X, tal que, quando x ~ y, P(x) é verdadeiro se P(y) é verdadeiro, então a propriedade P é dita como sendo bem definida ou invariante de classe sob a relação.

Um caso particular frequente ocorre quando f é uma função de X para outro conjunto Y; se x₁ ~ x₂ implica f(x₁) = f(x₂) então f é dito ser um morfismo a ~, uma classe invariante sob ~, ou simplesmente invariante sob ~. Isto ocorre, por exemplo, na teoria dos caracteres de grupos finitos. O último caso com a função f pode ser expresso por um triângulo comutativo _(invariante). Alguns autores usam "compatível com ~" ou apenas "respeitando ~" em vez de "invariante sob ~".

Mais geralmente, uma função pode mapear argumentos equivalentes (sob uma relação de equivalência ~_A) para valores equivalentes (sob uma relação de equivalência ~_B). Tal função é conhecida como morfismo de ~_A a ~_B.

Classe de equivalência, conjunto quociente, partição

Sejam ${\displaystyle a,b\in X}$. Algumas definições:

Classe de equivalência

Ver artigo principal: Classe de equivalência

Um subconjunto Y de X tal que a ~ b vale para todos a e b em Y, e nunca para a em Y e b fora de Y, é chamado uma classe de equivalência de X por ~. Seja ${\displaystyle [a]:=\{x\in X\mid a\sim x\}}$ denota a classe de equivalência a qual pertence. Todos os elementos de X equivalentes são também elementos da mesma classe de equivalência.

Conjunto quociente

Ver artigo principal: Conjunto quociente

O conjunto de todas as classes de equivalência possíveis de X por ~, denotado ${\displaystyle X/{\mathord {\sim }}:=\{[x]\mid x\in X\}}$, é o conjunto quociente de X por ~. Se X é um espaço topológico, existe um modo natural de transformar X/~ em um espaço topológico _{(veja espaço quociente para mais detalhes)}.

Projeção

Ver artigo principal: Projeção (álgebra relacional)

A projeção de ~ é a função ${\displaystyle \pi :X\to X/{\mathord {\sim }}}$ definida por ${\displaystyle \pi (x)=[x]}$que mapeia elementos de X em suas respectivas classes de equivalência por ~.

Teorema sobre projeções:^[1] Seja a função f:X → B tal que a ~ b → f(a) = f(b). Então existe uma função única g:X/~ → B, tal que f = gπ. Se f é uma sobrejeção e a ~ b ↔ f(a) = f(b), então g é uma bijeção.

Equivalência kernel

A equivalência kernel de uma função f é a relação de equivalência definida por ${\displaystyle x\sim y\iff f(x)=f(y)}$. O núcleo de equivalência de uma injeção é a relação de identidade.

Partição

Ver artigo principal: Partição de um conjunto

Uma partição de X é um conjunto P de subconjuntos não-vazios de X, de forma que todo elemento de X é um elemento de um único elemento de P. Cada elemento de P é uma célula da partição. Além disso, os elementos de P são separados por pares e sua união é X.

Contando partições possíveis

Seja X um conjunto finito com n elementos. Como toda relação de equivalência sobre X corresponde a uma partição de X e vice-versa, o número de relações de equivalência possíveis em X é igual ao número de partições distintas de X, que é o n-ésimo número de Bell B_n:

${\displaystyle B_{n}={\frac {1}{e}}\sum _{k=0}^{\infty }{\frac {k^{n}}{k!}},}$

onde o acima é uma das maneiras de escrever o n-ésimo número de Bell.

Teorema fundamental das relações de equivalência

Um resultado chave liga relações de equivalência e partições:^[2][3][4]

• Uma relação de equivalência ~ em um conjunto X partições X.
• Por outro lado, correspondendo a qualquer partição de X, existe uma relação de equivalência ~ em X.

Em ambos os casos, as células da partição de X são as classes de equivalência de X por ~. Como cada elemento de X pertence a uma célula única de qualquer partição de X, e como cada célula da partição é idêntica a uma classe de equivalência de X por ~, cada elemento de X pertence a uma classe de equivalência única de X por ~. Assim, há uma bijeção natural entre o conjunto de todas as possíveis relações de equivalência em X e o conjunto de todas as partições de X.

Comparando relações de equivalência

Se ~ e ≈ são duas relações de equivalência no mesmo conjunto S, e a ~ b implica a≈b para todo a, b ∈ S, então ≈ é dito ser uma relação mais grosseira do que ~, e ~ é uma relação mais fina que ≈ . Equivalentemente,

• ~ é mais fino do que ≈ se toda classe de equivalência de ~ é um subconjunto de uma classe de equivalência de ≈, e, portanto, toda classe de equivalência de ≈ é uma união de classes de equivalência de ~.
• ~ é mais fino que ≈ se a partição criada por ~ for um refinamento da partição criada por ≈.

A relação de equivalência de igualdade é a melhor relação de equivalência em qualquer conjunto, enquanto a relação trivial que torna todos os pares de elementos relacionados é a mais grosseira.

A relação "~ é mais fina que ≈" na coleção de todas as relações de equivalência em um conjunto fixo é em si uma relação de ordem parcial, que torna a coleção uma rede geométrica.^[5]

Gerando relações de equivalência

Dada qualquer relação binária ${\displaystyle A\subset X\times X}$ em ${\displaystyle X}$, a relação de equivalência gerada por ${\displaystyle A}$ é a intersecção das relações de equivalência em ${\displaystyle X}$ que contêm ${\displaystyle A}$. (Já que ${\displaystyle X\times X}$ é uma relação de equivalência, a interseção é não trivial.)

• Dado qualquer conjunto X, existe uma relação de equivalência sobre o conjunto [X → X] de todas as funções possíveis X → X. Duas dessas funções são consideradas equivalentes quando seus respectivos conjuntos de pontos de fixação possuem a mesma cardinalidade, correspondendo a ciclos de comprimento um em uma permutação. Funções equivalentes desta maneira formam uma classe de equivalência em [X → X], e estas classes de equivalência particionam [X → X].
• Uma relação de equivalência em X é o núcleo de equivalência de sua projeção sobrejetiva π: X → X/~.^[6] Por outro lado, qualquer sobrejeção entre conjuntos determina uma partição em seu domínio, o conjunto de pré-imagens de unidades no contradomínio. Assim, uma relação de equivalência sobre X, uma partição de X e uma projeção cujo domínio é X, são três formas equivalentes de especificar a mesma coisa.
• A interseção de qualquer coleção de relações de equivalência sobre X (relações binárias vistas como um subconjunto de X × X) também é uma relação de equivalência. Isto produz uma maneira conveniente de gerar uma relação de equivalência: dada qualquer relação binária R em X, a relação de equivalência gerada por R é a menor relação de equivalência contendo R. Concretamente, R gera a relação de equivalência a ~ b se e somente se existirem elementos x₁, x₂,…, x_n em X tal que a = x₁, b = x_n, e (x_i, x_i+1) ∈ R ou (x_i+1, x_i) ∈ R, i = 1,…, n-1.

Observe que a relação de equivalência gerada dessa maneira pode ser trivial. Por exemplo, a relação de equivalência gerada por qualquer ordem total em X tem exatamente uma classe de equivalência, X em si, porque x ~ y para todo x e y. Como outro exemplo, qualquer subconjunto da relação de identidade em X tem classes de equivalência que são unidades de X.

• Relações de equivalência podem construir novos espaços "colando coisas". Seja X a unidade cartesiana quadrada [0, 1] × [0, 1], e seja a relação de equivalência em X definida por ∀a, b ∈ [0, 1] ((a, 0) ~ (a, 1) ∧ (0, b) ~ (1, b)). Então o espaço quociente X/~ pode ser naturalmente identificado (homeomorfismo) com um toro: pegue um pedaço quadrado de papel, dobre e cole a borda superior e inferior para formar um cilindro, então dobre o cilindro resultante para colar o seu duas extremidades abertas, resultando em um toro.

Estrutura algébrica

Grande parte da matemática está fundamentada no estudo de equivalências e relações de ordem. A teoria da retícula captura a estrutura matemática das relações de ordem. Embora as relações de equivalência sejam tão onipresentes na matemática quanto as relações de ordem, a estrutura algébrica das equivalências não é tão conhecida quanto a das ordens. A estrutura anterior baseia-se principalmente na teoria dos grupos e, em menor escala, na teoria das redes, categorias e grupos.

Teoria dos grupos

Assim como as relações de ordem são fundamentadas em conjuntos ordenados, conjuntos fechados sob supremo e ínfimo pareados, as relações de equivalência são fundamentadas em conjuntos particionados, que são conjuntos fechados sob bijeções que preservam a estrutura da partição. Como todas essas bijeções mapeiam uma classe de equivalência em si mesmas, essas bijeções também são conhecidas como permutações. Assim, os grupos de permutação (também conhecidos como grupos de transformação) e a noção relacionada de órbita esclarecem a estrutura matemática das relações de equivalência.

Seja '~' denota uma relação de equivalência sobre algum conjunto não vazio, chamado universo ou conjunto subjacente. Seja G o conjunto de funções bijetivas sobre A que preservam a estrutura de partição de A: ∀x ∈ A ∀g ∈ G (g (x) ∈ [x]). Então, os três teoremas conectados a seguir mantêm-se:^[7]

• ~ partições A em classes de equivalência. (Este é o Teorema Fundamental das Relações de Equivalência, mencionado acima);
• Dada uma partição de A, G é um grupo de transformação em composição, cujas órbitas são as células da partição;^[11]

• Dado um grupo de transformação G sobre A, existe uma relação de equivalência sobre A, cujas classes de equivalência são as órbitas de G.^[12][13]

Em suma, dada uma relação de equivalência entre A , existe um grupo de transformação G sobre A cujas órbitas são as classes de equivalência de A sob ~.

Essa caracterização do grupo de transformação das relações de equivalência difere fundamentalmente da maneira como as [redes] (lattice - lattice) caracterizam as relações de ordem. Enquanto isso, os argumentos das operações do grupo de transformação composição e inversão são elementos de um conjunto de bijeções, A → A .

Movendo-se para grupos em geral, deixe H ser um subgrupo de algum grupo G . Seja uma relação de equivalência em G , tal que a ~ b ↔ ( ab⁻¹ ∈ H ). As classes de equivalência de ~ — também chamadas de órbitas da ação de H em G — são as direitas 'subconjunto s 'de' 'H' 'em' 'G' '. Intercambiando a e b produz os subconjuntos restantes.

O pensamento relacionado pode ser encontrado em Rosen (2008: cap. 10).

Categorias e Grupóides

Seja G um conjunto e deixe "~" denotar uma relação de equivalência sobre G. Então podemos formar um grupóide representando essa relação de equivalência como segue. Os objetos são os elementos de G, e para quaisquer dois elementos x e y de G, existe um morfismo único de x para y se e somente se x ~ y.

As vantagens de considerar uma relação de equivalência como um caso especial de um grupóide incluem:

• Considerando que a noção de "relação de equivalência livre" não existe, aquela de um grupóide livre em um grafo dirigido faz. Assim, é significativo falar de uma "apresentação de uma relação de equivalência", isto é, uma apresentação do correspondente grupóide;
• Grupos de grupos, grupos de ação, conjuntos e relações de equivalência podem ser considerados como casos especiais da noção de grupóide, um ponto de vista que sugere várias analogias;
• Em muitos contextos, "quociente" e, portanto, as relações de equivalência apropriadas, frequentemente chamadas de congruências, são importantes. Isso leva à noção de um grupóide interno em uma categoria.^[14]

Notas

1. Garrett Birkhoff and Saunders Mac Lane, 1999 (1967). Algebra, 3rd ed. p. 35, Th. 19. Chelsea.
2. Wallace, D. A. R., 1998. Groups, Rings and Fields. p. 31, Th. 8. Springer-Verlag.
3. Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. p. 3, Prop. 2. John Wiley & Sons.
4. Karel Hrbacek & Thomas Jech (1999) Introduction to Set Theory, 3rd edition, pages 29–32, Marcel Dekker
5. Birkhoff, Garrett (1995), Lattice Theory, ISBN 9780821810255, Colloquium Publications, 25 3rd ed. , American Mathematical Society. Sect. IV.9, Theorem 12, page 95
6. Garrett Birkhoff and Saunders Mac Lane, 1999 (1967). Algebra, 3rd ed. p. 33, Th. 18. Chelsea.
7. Rosen (2008), pp. 243–45. Less clear is §10.3 of Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press.
8. Bas van Fraassen, 1989. Laws and Symmetry. Oxford Univ. Press: 246.
9. Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 22, Th. 6.
10. Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 24, Th. 7.
11. Proof.^[8] Deixe que composição da função interprete a multiplicação do grupo e a função inversa interprete o inverso do grupo. Então G é um grupo em composição, significando que ∀x ∈ A ∀g ∈ G ([ g ( x ' ')] = [' 'x' ']), porque' 'G' 'satisfaz as quatro condições seguintes:

    • G está fechado na composição . A composição de quaisquer dois elementos de G existe, porque o domínio e codomain de qualquer elemento de G é A . Além disso, a composição das bijeções é bijetiva;^[9]
    • Existência de função de identidade . A função identidade, eu ( x ) = x , é um elemento óbvio de G ;
    • Existência de função inversa . Cada função bijetiva g tem um inverso g ^{& menos; 1 </ sup>, tal que gg −1 </ sup> = I;}
    • Composição associados . f ( gh ) = ( fg ) h . Isso vale para todas as funções em todos os domínios.^[10]

    Let f and g be any two elements of G. By virtue of the definition of G, [g(f(x))] = [f(x)] and [f(x)] = [x], so that [g(f(x))] = [x]. Hence G is also a transformation group (and an automorphism group) because function composition preserves the partitioning of A. ${\displaystyle \square }$
12. Wallace, D. A. R., 1998. Groups, Rings and Fields. Springer-Verlag: 202, Th. 6.
13. Dummit, D. S., and Foote, R. M., 2004. Abstract Algebra, 3rd ed. John Wiley & Sons: 114, Prop. 2.
14. Borceux, F. and Janelidze, G., 2001. Galois theories, Cambridge University Press, ISBN 0-521-80309-8

Referências

• Brown, Ronald, 2006. Topology and Groupoids. Booksurge LLC. ISBN 1-4196-2722-8.
• Castellani, E., 2003, "Symmetry and equivalence" in Brading, Katherine, and E. Castellani, eds., Symmetries in Physics: Philosophical Reflections. Cambridge Univ. Press: 422-433.
• Robert Dilworth and Crawley, Peter, 1973. Algebraic Theory of Lattices. Prentice Hall. Chpt. 12 discusses how equivalence relations arise in lattice theory.
• Higgins, P.J., 1971. Categories and groupoids. Van Nostrand. Downloadable since 2005 as a TAC Reprint.
• John Randolph Lucas, 1973. A Treatise on Time and Space. London: Methuen. Section 31.
• Rosen, Joseph (2008) Symmetry Rules: How Science and Nature are Founded on Symmetry. Springer-Verlag. Mostly chpts. 9,10.
• Raymond Wilder (1965) Introduction to the Foundations of Mathematics 2nd edition, Chapter 2-8: Axioms defining equivalence, pp 48–50, John Wiley & Sons.

Ligações externas

• Hazewinkel, Michiel, ed. (2001), «Equivalence relation», Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer
• Bogomolny, A., "Equivalence Relationship" cut-the-knot. Accessed 1 September 2009
• Equivalence relation at PlanetMath
• Predefinição:OEIS el