Relação de equivalência - Equivalence relation

Em 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.

Cada relação de equivalência fornece uma partição do conjunto subjacente em classes de equivalência disjuntas . Dois elementos de um determinado conjunto são equivalentes um ao outro, se e somente se eles pertencem à mesma classe de equivalência.

Notação

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

Definição

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

• ${\ displaystyle a \ sim a.}$( Reflexividade )
• ${\ displaystyle a \ sim b}$se e somente se ( simetria )${\ displaystyle b \ sim a.}$
• Se e então ( transitividade )${\ displaystyle a \ sim b}$${\ displaystyle b \ sim c}$${\ displaystyle a \ sim c.}$

${\ displaystyle X}$junto com a relação é chamado de setoide . A classe de equivalência de sub denotada é definida como${\ displaystyle \, \ sim \,}$${\ displaystyle a}$${\ displaystyle \, \ sim,}$${\ displaystyle [a],}$${\ displaystyle [a] = \ {x \ in X: x \ sim a \}.}$

Exemplos

Exemplo simples

Deixe o conjunto ter a relação de equivalência Os seguintes conjuntos são classes de equivalência desta relação: ${\ displaystyle \ {a, b, c \}}$${\ displaystyle \ {(a, a), (b, b), (c, c), (b, c), (c, b) \}.}$

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

Relações de equivalência

As seguintes relações são todas relações de equivalência:

• "É igual a" no conjunto de números. Por exemplo, é igual a${\ displaystyle {\ tfrac {1} {2}}}$${\ displaystyle {\ tfrac {4} {8}}.}$
• "Faz aniversário no mesmo dia que" no set de todas as pessoas.
• "É semelhante a" no conjunto de todos os triângulos .
• "É congruente com" no conjunto de todos os triângulos .
• "É congruente com, módulo " nos inteiros .${\ displaystyle n}$
• "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 os números reais é reflexiva e transitiva, mas não simétrica. Por exemplo, 7 ≥ 5 não implica que 5 ≥ 7.
• A relação "tem um fator comum maior que 1 com" entre os números naturais maiores que 1, é reflexiva e simétrica, mas não transitiva. Por 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 vazio R (definido de modo que aRb não é verdadeiro) em não-vazia conjunto X é vacuously simétrica e transitória, mas não reflexivo. (Se X também estiver vazio, R é reflexivo.)
• A relação "é aproximadamente igual a" entre os números reais, ainda que definida de forma mais precisa, não é uma relação de equivalência, pois embora reflexiva e simétrica, não é transitiva, uma vez que múltiplas pequenas mudanças podem se acumular para se tornar uma grande mudança. No entanto, se a aproximação é definido asymptotically, por exemplo, dizendo que duas funções f e g são aproximadamente iguais perto algum momento, se o limite de f - g é 0 nesse 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.
• A igualdade é uma relação de equivalência e uma ordem parcial. A igualdade também é a única relação em um conjunto que é reflexiva, simétrica e anti-simétrica. Em expressões algébricas , variáveis ​​iguais podem ser substituídas umas pelas outras, um recurso 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 umas às outras, mas não os 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. Tal relação é reflexiva se e somente se for serial , isto é, se para todos existir algum. Portanto, uma relação de equivalência pode ser definida alternativamente como uma relação simétrica, transitiva e serial.${\ displaystyle a,}$${\ displaystyle b {\ text {tal que}} a \ sim b.}$
• Uma relação de equivalência ternária é um análogo ternário da relação de equivalência usual (binária).
• 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é - encomenda é reflexiva e transitiva.
• Uma relação de congruência é uma relação de equivalência cujo domínio é 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 são definidas (por exemplo, as relações de congruência nos grupos correspondem aos subgrupos normais ).${\ displaystyle X}$
• Qualquer relação de equivalência é a negação de uma relação de separação , embora a afirmação inversa só seja válida na matemática clássica (em oposição à matemática construtiva ), uma vez que é equivalente à lei do meio excluído .

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

Se é uma relação de equivalência e é uma propriedade de elementos de tal que sempre que for verdadeiro se for verdadeiro, então a propriedade é considerada bem definida ou uma invariante de classe sob a relação${\ displaystyle \, \ sim \,}$${\ displaystyle X,}$${\ displaystyle P (x)}$${\ displaystyle X,}$${\ displaystyle x \ sim y,}$ ${\ displaystyle P (x)}$${\ displaystyle P (y)}$${\ displaystyle P}$${\ displaystyle \, \ sim.}$

Um caso particular frequente ocorre quando é uma função de um outro conjunto se implica , em seguida, é dito ser um morfismo para uma invariante sob classe ou simplesmente invariante sob Isto ocorre, por exemplo, na teoria de caracteres de grupos finitos. O último caso com a função pode ser expresso por um triângulo comutativo. Veja também invariante . Alguns autores usam "compatível com " ou apenas "aspectos " em vez de "invariante sob ". ${\ displaystyle f}$${\ displaystyle X}$${\ displaystyle Y;}$${\ displaystyle x_ {1} \ sim x_ {2}}$${\ displaystyle f \ left (x_ {1} \ right) = f \ left (x_ {2} \ right)}$${\ displaystyle f}$${\ displaystyle \, \ sim,}$ ${\ displaystyle \, \ sim,}$ ${\ displaystyle \, \ sim.}$${\ displaystyle f}$${\ displaystyle \, \ sim}$${\ displaystyle \, \ sim}$${\ displaystyle \, \ sim}$

Mais geralmente, uma função pode mapear argumentos equivalentes (sob uma relação de equivalência ) para valores equivalentes (sob uma relação de equivalência ). Essa função é conhecida como morfismo de para${\ displaystyle \, \ sim _ {A}}$${\ displaystyle \, \ sim _ {B}}$${\ displaystyle \, \ sim _ {A}}$${\ displaystyle \, \ sim _ {B}.}$

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

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

Classe de equivalência

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

Conjunto de quociente

O conjunto de todas as classes de equivalência de X por ~, denotado é o conjunto quociente de X por ~. Se X é um espaço topológico , existe uma maneira natural de se transformar em um espaço topológico; veja espaço de quociente para os detalhes. ${\ displaystyle X / {\ mathord {\ sim}}: = \ {[x]: x \ em X \},}$${\ displaystyle X / \ sim}$

Projeção

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

Teorema sobre projeções : seja a função tal que se então então há uma função única tal que If é uma sobreposição e então é uma bijeção .${\ displaystyle f: X \ to B}$${\ displaystyle a \ sim b}$${\ displaystyle f (a) = f (b).}$${\ displaystyle g: X / \ sim \ to B}$${\ displaystyle f = g \ pi.}$${\ displaystyle f}$${\ displaystyle a \ sim b {\ text {se e somente se}} f (a) = f (b),}$${\ displaystyle g}$

Kernel de equivalência

O kernel de equivalência de uma função é a relação de equivalência ~ definida por O kernel de equivalência de uma injeção é a relação de identidade . ${\ displaystyle f}$${\ displaystyle x \ sim y {\ text {se e somente se}} f (x) = f (y).}$

Partição

Uma partição de X é um grupo P de subconjuntos não vazios de X , de tal modo que cada 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 disjuntos dois a dois e a sua união é X .

Contando partições

Seja X um conjunto finito com n elementos. Uma vez que cada 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 em X é igual ao número de divisórias distintos de X , que é o N ° série de Bell B _n :

${\ displaystyle B_ {n} = {\ frac {1} {e}} \ sum _ {k = 0} ^ {\ infty} {\ frac {k ^ {n}} {k!}} \ quad}$( Fórmula de Dobinski ).

Teorema fundamental das relações de equivalência

Um resultado chave liga relações de equivalência e partições:

• Uma relação de equivalência ~ em um conjunto X partições X .
• Por outro lado, correspondendo a qualquer divisão do 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 ~. Uma vez que cada elemento de X pertence a uma célula única de qualquer partição de X , e uma vez que 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 natural, bijection entre o conjunto de todas as 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 implica a ≈ b para todos, então ≈ é considerado uma relação mais grosseira do que ~, e ~ é uma relação mais fina do que ≈. Equivalentemente, ${\ displaystyle a \ sim b}$${\ displaystyle a, b \ in S,}$

• ~ é mais fino que ≈ se cada classe de equivalência de ~ é um subconjunto de uma classe de equivalência de ≈ e, portanto, cada classe de equivalência de ≈ é uma união de classes de equivalência de ~.
• ~ é melhor do 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 universal, que relaciona todos os pares de elementos, é a mais grosseira.

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

Gerando relações de equivalência

• Dado qualquer conjunto, uma relação de equivalência sobre o conjunto de todas as funções pode ser obtida como segue. Duas funções são consideradas equivalentes quando seus respectivos conjuntos de pontos fixos têm a mesma cardinalidade , correspondendo a ciclos de comprimento um em uma permutação .${\ displaystyle X,}$${\ displaystyle [X \ to X]}$${\ displaystyle X \ to X}$
• Uma relação de equivalência em é o núcleo de equivalência de sua projeção sobrejetiva. Por outro lado, qualquer sobreposição entre conjuntos determina uma partição em seu domínio, o conjunto de pré-imagens de singletons no codomínio . Assim, uma relação de equivalência sobre uma partição de e uma projeção cujo domínio é são três maneiras equivalentes de especificar a mesma coisa.${\ displaystyle \, \ sim \,}$${\ displaystyle X}$ ${\ displaystyle \ pi: X \ to X / \ sim.}$${\ displaystyle X,}$${\ displaystyle X,}$${\ displaystyle X,}$
• A interseção de qualquer coleção de relações de equivalência sobre X (relações binárias vistas como um subconjunto de ) também é uma relação de equivalência. Isso 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 interseção de todas as relações de equivalência contendo R (também conhecida como a menor relação de equivalência contendo R ). Concretamente, R gera a relação de equivalência 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 ,${\ displaystyle X \ times X}$${\ displaystyle a \ sim b}$ ${\ displaystyle i = 1, \ ldots, n-1.}$
  A relação de equivalência gerada desta 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, o próprio X.
• As relações de equivalência podem construir novos espaços ao "colar as coisas". Seja X o quadrado cartesiano unitário e seja ~ a relação de equivalência em X definida por para todos e para todos Então o espaço quociente pode ser identificado naturalmente ( homeomorfismo ) com um toro : pegue um pedaço de papel quadrado, dobre e cole o borda superior e inferior para formar um cilindro, então dobre o cilindro resultante de modo a colar suas duas extremidades abertas, resultando em um toro.${\ displaystyle [0,1] \ times [0,1],}$${\ displaystyle (a, 0) \ sim (a, 1)}$${\ displaystyle a \ in [0,1]}$${\ displaystyle (0, b) \ sim (1, b)}$${\ displaystyle b \ in [0,1],}$ ${\ displaystyle X / \ sim}$

Estrutura algébrica

Grande parte da matemática é baseada no estudo de equivalências e relações de ordem . A teoria da rede 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 primeira estrutura baseia-se principalmente na teoria dos grupos e, em menor grau, na teoria das redes, categorias e grupóides .

Teoria do grupo

Assim como as relações de ordem são baseadas em conjuntos ordenados , conjuntos fechados sob supremo e ínfimo par , as relações de equivalência são baseadas em conjuntos particionados , que são conjuntos fechados sob bijeções que preservam a estrutura de partição. Uma vez que todas essas bijeções mapeiam uma classe de equivalência sobre si mesmas, tais bijeções também são conhecidas como permutações . Conseqüentemente, grupos de permutação (também conhecidos como grupos de transformação ) e a noção relacionada de órbita lançam luz sobre a estrutura matemática das relações de equivalência.

Deixe '~' denotar uma relação de equivalência sobre algum conjunto não vazio A , chamado de universo ou conjunto subjacente. Deixe G denotar o conjunto de funções bijetivas sobre A que preservam a estrutura de partição de A , o que significa que para todos e Então os três teoremas conectados a seguir são válidos: ${\ displaystyle x \ in A}$${\ displaystyle g \ in G, g (x) \ in [x].}$

• ~ particiona 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 sob composição, cujas órbitas são as células da partição;

• Dado um grupo transformação G sobre um , existe uma relação de equivalência ~ sobre um , cujas classes equivalência são as órbitas de L .

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

Esta caracterização do grupo de transformação das relações de equivalência difere fundamentalmente da maneira como as redes caracterizam as relações de ordem. Os argumentos das operações teoria do retículo encontram e se juntar são elementos de algum universo A . Enquanto isso, os argumentos das operações do grupo transformação composição e inversa são elementos de um conjunto de bijeções , Um → Uma .

Movendo-se a grupos em geral, deixe H ser um subgrupo de um grupo L . Vamos ~ ser uma relação de equivalência em G , tal que as classes de equivalência de ~ -também chamados as órbitas da acção de H em G -são as certas classes laterais de H em G . A permuta entre um e b produz as classes laterais esquerdos. ${\ displaystyle a \ sim b {\ text {se e somente se}} ab ^ {- 1} \ em H.}$

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

Categorias e grupóides

Deixe G ser um conjunto e deixe "~" denotam 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 objectos são os elementos de L , e para quaisquer dois elementos de x e y de L , existe um único morfismo de x para y se e somente se ${\ displaystyle x \ sim y.}$

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

• Enquanto a noção de "relação de equivalência livre" não existe, a de um grupóide livre em um grafo direcionado existe . Portanto, é significativo falar de uma "apresentação de uma relação de equivalência", isto é, uma apresentação do grupóide correspondente;
• Pacotes de grupos, ações de grupo , 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 uma série de analogias;
• Em muitos contextos, o "quociente" e, portanto, as relações de equivalência apropriadas, freqüentemente chamadas de congruências , são importantes. Isso leva à noção de um grupóide interno em uma categoria .

Treliças

As relações de equivalência em qualquer conjunto X , quando ordenadas por inclusão de conjunto , formam uma rede completa , chamada de Con X por convenção. O canônica mapa ker : X ^ X → Con X , relata a monoid X ^ X de todas as funções no X e Con X . ker é sobrejetivo, mas não injetivo . Menos formalmente, a relação de equivalência ker em X , leva cada função f : X → X ao seu núcleo ker f . Da mesma forma, ker (ker) é uma relação de equivalência em X ^ X .

Relações de equivalência e lógica matemática

As relações de equivalência são uma fonte pronta de exemplos ou contra-exemplos. Por exemplo, uma relação de equivalência com exatamente duas classes de equivalência infinitas é um exemplo fácil de uma teoria que é ω- categórica , mas não categórica para qualquer número cardinal maior .

Uma implicação da teoria do modelo é que as propriedades que definem uma relação podem ser provadas independentes umas das outras (e, portanto, partes necessárias da definição) se e somente se, para cada propriedade, podem ser encontrados exemplos de relações que não satisfazem a propriedade dada enquanto satisfazem todas as outras propriedades. Portanto, as três propriedades definidoras das relações de equivalência podem ser provadas mutuamente independentes pelos três exemplos a seguir:

• Reflexiva e transitória : A relação ≤ em N . Ou qualquer pedido antecipado ;
• Simétrica e transitiva : A relação R em N , definida como aRb ↔ ab ≠ 0. Ou qualquer relação de equivalência parcial ;
• Reflexiva e simétrica : A relação R em Z , definida como aRb ↔ " a - b é divisível por pelo menos um de 2 ou 3." Ou qualquer relação de dependência .

Propriedades definíveis na lógica de primeira ordem que uma relação de equivalência pode ou não possuir incluem:

• O número de classes de equivalência é finito ou infinito;
• O número de classes de equivalência é igual ao número natural (finito) n ;
• Todas as classes de equivalência têm cardinalidade infinita ;
• O número de elementos em cada classe de equivalência é o número natural n .

Relações euclidianas

Euclides 's The Elements inclui o seguinte "noção comum 1":

Coisas que são iguais à mesma coisa também são iguais umas às outras.

Hoje em dia, a propriedade descrita pelo conceito comum 1 é chamada de Euclidiana (substituindo "igual" por "estão em relação com"). Por "relação" entende-se uma relação binária , na qual aRb é geralmente distinto de bRa . Uma relação euclidiana, portanto, vem em duas formas:

( ARc ∧ bRc ) → aRb (relação Esquerda-euclidiana)

( cRa ∧ cRb ) → aRb (relação direito-euclidiana)

O seguinte teorema conecta relações euclidianas e relações de equivalência:

Teorema

Se uma relação é (esquerda ou direita) euclidiana e reflexiva , também é simétrica e transitiva.

Prova de uma relação euclidiana esquerda

( ARc ∧ bRc ) → aRb [ a / c ] = ( aRa ∧ bRa ) → aRb [ reflexiva ; apagar T ∧] = bRa → aRb . Portanto, R é simétrico .

( ARc ∧ bRc ) → aRb [ simetria ] = ( aRc ∧ cRb ) → aRb . Logo, R é transitivo .${\ displaystyle \ blacksquare}$

com uma prova análoga para uma relação direito-euclidiana. Portanto, uma relação de equivalência é uma relação euclidiana e reflexiva . Os Elementos não mencionam simetria nem reflexividade, e Euclides provavelmente teria considerado a reflexividade da igualdade muito óbvia para justificar uma menção explícita.

Veja também

• Relação de apartness
• Aula de Conjugação
• Equipollence (geometria)
• Quociente por uma relação de equivalência
• Conjugação topológica
• Até

Notas

Referências

• Brown, Ronald, 2006. Topology and Groupoids. Booksurge LLC. ISBN  1-4196-2722-8 .
• Castellani, E., 2003, "Symmetry and equivalence" em Brading, Katherine e E. Castellani, eds., Symmetries in Physics: Philosophical Reflections . Cambridge Univ. Imprensa: 422–433.
• Robert Dilworth e Crawley, Peter, 1973. Algebraic Theory of Lattices . Prentice Hall. Chpt. 12 discute como as relações de equivalência surgem na teoria da rede .
• Higgins, PJ, 1971. Categorias e grupóides. Van Nostrand. Disponível para download desde 2005 como uma reimpressão do TAC.
• John Randolph Lucas , 1973. A Treatise on Time and Space . Londres: Methuen. Seção 31.
• Rosen, Joseph (2008) Symmetry Rules: How Science and Nature are Found on Symmetry . Springer-Verlag. Principalmente capítulos. 9,10.
• Raymond Wilder (1965) Introdução aos Fundamentos da Matemática 2ª edição, Capítulo 2-8: Axiomas definindo equivalência, pp 48–50, John Wiley & Sons .

links externos

• "Relação de equivalência" , Encyclopedia of Mathematics , EMS Press , 2001 [1994]
• Bogomolny, A. , " Equivalence Relationship " cut-the-knot . Acessado em 1 de setembro de 2009
• Relação de equivalência no PlanetMath
• Sequência OEIS A231428 (matrizes binárias que representam relações de equivalência)