Relação de equivalência

format_list_bulleted Contenido keyboard_arrow_down

ImprimirCitar

Conceito matemático para comparar objetos

Relações binárias transitivas

	Symmetric	Antisymmetric	Conectado	Bem fundada	Tem uniões	Tem encontros	Reflexão	Irreflexível	Assimétrico
			Total, Semiconnex					Anti- reflexivo
Relação de equivalência	Y	✗	✗	✗	✗	✗	Y	✗	✗
Pré-ordem (Quasiorder)	✗	✗	✗	✗	✗	✗	Y	✗	✗
Ordem parcial	✗	Y	✗	✗	✗	✗	Y	✗	✗
Entidade total	✗	✗	Y	✗	✗	✗	Y	✗	✗
Ordem total	✗	Y	Y	✗	✗	✗	Y	✗	✗
Pré-encomendamento	✗	✗	Y	Y	✗	✗	Y	✗	✗
Ordenamento bem-quasi	✗	✗	✗	Y	✗	✗	Y	✗	✗
Bem-ordenado	✗	Y	Y	Y	✗	✗	Y	✗	✗
Lattice	✗	Y	✗	✗	Y	Y	Y	✗	✗
Selecção	✗	Y	✗	✗	Y	✗	Y	✗	✗
Meet-semilattice	✗	Y	✗	✗	✗	Y	Y	✗	✗
Ordem parcial rigorosa	✗	Y	✗	✗	✗	✗	✗	Y	Y
Ordem fraca rigorosa	✗	Y	✗	✗	✗	✗	✗	Y	Y
Ordem total rigorosa	✗	Y	Y	✗	✗	✗	✗	Y	Y
	Symmetric	Antisymmetric	Conectado	Bem fundada	Tem uniões	Tem encontros	Reflexão	Irreflexível	Assimétrico
Definições, para todos $a,b$ e ${displaystyle Sneq varnothing:}$	${displaystyle {begin{aligned}&aRb\Rightarrow {}&bRaend{aligned}}}$	${displaystyle {begin{aligned}aRb{text{ and }}&bRa\Rightarrow a={}&bend{aligned}}}$	${displaystyle {begin{aligned}aneq {}&bRightarrow \aRb{text{ or }}&bRaend{aligned}}}$	${displaystyle {begin{aligned}min S\{text{exists}}end{aligned}}}$	${displaystyle {begin{aligned}avee b\{text{exists}}end{aligned}}}$	${displaystyle {begin{aligned}awedge b\{text{exists}}end{aligned}}}$	${displaystyle aRa}$	${displaystyle {text{not }}aRa}$	${displaystyle {begin{aligned}aRbRightarrow \{text{not }}bRaend{aligned}}}$

Y indica que a propriedade da coluna é sempre verdadeira o termo da linha (à esquerda), enquanto ✗ indica que a propriedade não é garantida em geral (pode, ou não, segure). Por exemplo, que cada relação de equivalência é simétrica, mas não necessariamente antissimétrica, é indicada por

Y na coluna "Simétrica" e ✗ na coluna "Antisymmetric", respectivamente.

Todas as definições requerem tacitamente a relação homogênea $R$ ser transitivo: para todos $a,b,c,$ se ${displaystyle aRb}$ e ${displaystyle bRc}$ então ${displaystyle aRc.}$
A definição de um termo pode exigir propriedades adicionais que não estão listadas nesta tabela.

As 52 relações de equivalência em um conjunto de 5 elementos descrito como

5times 5

matrizes lógicas (campos coloridos, incluindo aqueles em cinza claro, stand for ones; campos brancos para zeros). Os índices de linha e coluna de células não brancas são os elementos relacionados, enquanto as cores diferentes, além de cinza claro, indicam as classes de equivalência (cada célula cinza clara é sua própria classe de equivalência).

Na matemática, uma relação de equivalência é uma relação binária reflexiva, simétrica e transitiva. A relação de equipolência entre segmentos de reta em geometria é um exemplo comum de 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 do conjunto dado são equivalentes entre si 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 $a$ e $b$ de um conjunto são equivalentes em relação a uma relação de equivalência ${displaystyle R;}$ os mais comuns são " $asim b$ "e" $um) b)$ ", que são usados quando $R$ é implícito, e variações de " ${displaystyle asim _{R}b}$ ", $um) R b)$ ", ou " ${displaystyle {amathop {R} b}}$ " para especificar $R$ explicitamente. Não-equivalência pode ser escrita " $um ≁ b)$ "ou " $anot equiv b$ ".

Definição

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

${displaystyle asim a}$ (reflexividade).
$asim b$ se e somente se ${displaystyle bsim a}$ (simetria).
Se $asim b$ e ${displaystyle bsim c}$ então ${displaystyle asim c}$ (transitividade).

$X$ em conjunto com a relação $,sim,$ é chamado de setóide. A classe de equivalência $a$ abaixo ${displaystyle ,sim}$ denotado ${displaystyle [a],}$ é definido como ${displaystyle [a]={xin X:xsim a}.}$

Definição alternativa usando álgebra relacional

Em álgebra relacional, se $Rsubseteq Xtimes Y$ e $Ssubseteq Ytimes Z$ são relações, então a relação composta ${displaystyle SRsubseteq Xtimes Z}$ é definido de modo que ${displaystyle x,SR,z}$ se e somente se houver um $yin Y$ tal que ${displaystyle x,R,y}$ e ${displaystyle y,S,z}$ . Esta definição é uma generalização da definição de composição funcional. As propriedades de definição de uma relação de equivalência $R$ em um conjunto $X$ pode então ser reformulado da seguinte forma:

${displaystyle operatorname {id} subseteq R}$ (reflexividade). (Aqui, ${displaystyle operatorname {id} }$ denota a função de identidade em $X$ .)
${displaystyle R=R^{-1}}$ (simetria).
${displaystyle RRsubseteq R}$ (transitividade).

Exemplos

Exemplo simples

No conjunto ${displaystyle X={a,b,c}}$ , a relação ${displaystyle R={(a,a),(b,b),(c,c),(b,c),(c,b)}}$ é uma relação de equivalência. Os seguintes conjuntos são classes de equivalência desta relação:

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

O conjunto de todas as classes de equivalência $R$ o ${displaystyle {{a},{b,c}}.}$ Este conjunto é uma partição do conjunto $X$ com respeito a $R$ .

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, ${tfrac {1}{2}}$ é igual a ${displaystyle {tfrac {4}{8}}.}$
"Tem o mesmo aniversário que" no conjunto de todas as pessoas.
"É semelhante a" no conjunto de todos os triângulos.
"É congruente" no conjunto de todos os triângulos.
Dado um número natural $n$ "é congruente, modulo $n$ " nos inteiros.
Dada uma função $f:Xto Y$ , "tem a mesma imagem abaixo $f$ como" nos elementos de $f$ Domínio $X$ . Por exemplo, ${displaystyle 0}$ e $pi$ tem a mesma imagem abaixo $sin$ Viz. ${displaystyle 0}$ .
"Tem o mesmo valor absoluto que" no conjunto de números reais
"Tem a mesma cossena que" 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 mas não 5 ≥ 7.
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. 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 vazia R (definido para que ARTIGOS nunca é verdade) em um conjunto X é vacuamente simétrica e transitiva; no entanto, não é reflexiva (a menos X em si está vazio).
A relação "é aproximadamente igual a" entre números reais, mesmo que mais precisamente definido, não é uma relação de equivalência, porque 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 é 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 nesse ponto, então isso define uma relação de equivalência.

Conexões com outras relações

Uma ordem parcial é uma relação reflexiva, anti-simétricoe transitivo.
A igualdade é uma relação de equivalência e uma ordem parcial. A igualdade é também a única relação em um conjunto que é reflexivo, simétrico e antisimétrico. Em expressões algébricas, variáveis iguais podem ser substituídas uma pela outra, uma instalação 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 uns aos outros, mas não indivíduos dentro de uma classe.
Uma ordem parcial rigorosa é 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 total, isto é, se para todos $a,$ existe algum ${displaystyle b{text{ such that }}asim b.}$ Portanto, uma relação de equivalência pode ser definida como uma relação simétrica, transitiva e total.
Uma relação de equivalência ternary é um análogo ternary à relação de equivalência usual (binária).
Uma relação reflexiva e simétrica é uma relação de dependência (se finito) 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 em que são definidas (por exemplo, as relações de congruência em grupos correspondem aos subgrupos normais).
Qualquer relação de equivalência é a negação de uma relação de apartness, embora a declaração conversa apenas detém em matemática clássica (ao contrário da matemática construtiva), uma vez que é equivalente à lei do meio excluído.
Cada relação que é tanto reflexiva quanto esquerda (ou direita) Euclidiana é também uma relação de equivalência.

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

Se $,sim,$ é uma relação de equivalência $X,$ e $P(x)$ é uma propriedade de elementos de $X,$ tal que sempre ${displaystyle xsim y,}$ $P(x)$ é verdade se $P(y)$ é verdade, então a propriedade $P$ é dito ser bem definido ou um classe invariável sob a relação ${displaystyle ,sim.}$

Um caso particular frequente ocorre quando $f$ é uma função de $X$ para outro conjunto ${displaystyle Y;}$ se $x_1 sim x_2$ implica ${displaystyle fleft(x_{1}right)=fleft(x_{2}right)}$ então $f$ é dito ser um Morfismo para ${displaystyle ,sim}$ um classe invariável sob ${displaystyle ,sim}$ ou simplesmente invariante sob ${displaystyle ,sim.}$ Isso 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. Veja também invariante. Alguns autores usam "compatível com ${displaystyle ,sim }$ "ou apenas "respeitos ${displaystyle ,sim }$ " em vez de "invariante sob ${displaystyle ,sim }$ ".

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

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

Vamos. ${displaystyle a,bin X.}$ Algumas definições:

Classe de equivalência

Um subconjunto Y de X tal que $asim b$ para todos um e b) em Ye nunca para um em Y e b) fora Y, chama-se um classe de equivalência de X por ~. ${displaystyle [a]:={xin X:asim x}}$ denotar a classe de equivalência a que um pertence. Todos os elementos de X equivalentes uns aos outros também são elementos da mesma classe de equivalência.

Conjunto de quociente

O conjunto de todas as classes de equivalência X por ~, denotado ${displaystyle X/{mathord {sim }}:={[x]:xin X},}$ é o conjunto de citações de X Por ~. Se X é um espaço topológico, há uma maneira natural de transformar ${displaystyle X/sim }$ em um espaço topológico; ver espaço quociente para os detalhes.

Projeção

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

Teorem em projeções: Deixe a função

{displaystyle f:Xto B}

ser tal que se

asim b

então

{displaystyle f(a)=f(b).}

Então há uma função única

{displaystyle g:X/sim to B}

tal que

{displaystyle f=gpi.}

f

é um surjection e

{displaystyle asim b{text{ if and only if }}f(a)=f(b),}

então

g

é uma bijeção.

Núcleo de equivalência

O kernel de equivalência de uma função $f$ é a relação de equivalência ~ definida por ${displaystyle xsim y{text{ if and only if }}f(x)=f(y).}$ O núcleo de equivalência de uma injeção é a relação de identidade.

Partição

Uma partição de X é um conjunto P de subconjuntos não vazios de X, tal 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 pairwise e sua união é X.

Contando partições

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 em X é igual ao número de partições de X, que é o nº número de Bell B_n:

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

(A fórmula de Dobinski).

Teorema fundamental das relações de equivalência

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

Uma relação de equivalência ~ em um conjunto X partições X.
Inversamente, correspondendo a qualquer partição de X, existe uma relação de equivalência 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 única célula 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 única classe de equivalência de X por ~. Assim, existe uma bijeção natural 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 $sim$ e $approx$ são duas relações de equivalência no mesmo conjunto $S$ e $asim b$ implica $aapprox b$ para todos ${displaystyle a,bin S,}$ então $approx$ é dito ser um Coarser relação do que $sim$ e $sim$ é um mais fino relação do que $approx$ . Equivalentemente,

$sim$ é mais fino do que $approx$ se cada classe de equivalência $sim$ é um subconjunto de uma classe de equivalência $approx$ , e assim todas as classes de equivalência $approx$ é uma união de classes de equivalência $sim$ .
$sim$ é mais fino do que $approx$ se a partição criada por $sim$ é um refinamento da partição criada por $approx$ .

A relação de equivalência de igualdade é a relação de equivalência mais fina em qualquer conjunto, enquanto a relação universal, que relaciona todos os pares de elementos, é a mais grosseira.

A relação " $sim$ é mais fino do que $approx$ " na coleta de todas as relações de equivalência em um conjunto fixo é em si uma relação de ordem parcial, o que torna a coleção um reticulado geométrico.

Gerando relações de equivalência

Dado qualquer conjunto $X,$ uma relação de equivalência sobre o conjunto ${displaystyle [Xto X]}$ de todas as funções $Xto X$ pode ser obtido da seguinte forma. Duas funções são consideradas equivalentes quando seus respectivos conjuntos de pontos de correção têm a mesma cardinalidade, correspondendo a ciclos de comprimento um em uma permutação.
Uma relação de equivalência $,sim,$ sobre $X$ é o núcleo de equivalência de sua projeção subjetiva ${displaystyle pi:Xto X/sim.}$ Por outro lado, qualquer surjeção entre conjuntos determina uma partição em seu domínio, o conjunto de preimages de singletons no codomain. 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 $Xtimes X$ ) é 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 sobre X, a relação de equivalência gerado por R é a interseção de todas as relações de equivalência contendo R (também conhecido como a menor relação de equivalência contendo R). Concretamente, R gera a relação de equivalência

asim b

se existe um número natural

n

e elementos

{displaystyle x_{0},ldotsx_{n}in X}

tal que

{displaystyle a=x_{0}}

{displaystyle b=x_{n}}

{displaystyle x_{i-1}mathrel {R} x_{i}}

{displaystyle x_{i}mathrel {R} x_{i-1}}

, para

{displaystyle i=1,ldotsn.}

A relação de equivalência gerada desta forma pode ser trivial. Por exemplo, a relação de equivalência gerada por qualquer ordem total X tem exatamente uma classe de equivalência, X em si.

As relações de equivalência podem construir novos espaços ao "gluir as coisas juntos". Vamos. X ser a unidade quadrado cartesiano ${displaystyle [0,1]times [0,1],}$ e deixe ~ ser a relação de equivalência em X definido por ${displaystyle (a,0)sim (a,1)}$ para todos ${displaystyle ain [0,1]}$ e ${displaystyle (0,b)sim (1,b)}$ para todos ${displaystyle bin [0,1],}$ Então o espaço quociente ${displaystyle X/sim }$ pode ser naturalmente identificado (homeomorfismo) com um torus: tomar uma peça quadrada de papel, dobrar e cola em conjunto a borda superior e inferior para formar um cilindro, em seguida, dobrar o cilindro resultante de modo a colar juntos suas duas extremidades abertas, resultando em um torus.

Estrutura algébrica

Grande parte da matemática é fundamentada 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 de grupos

Assim como as relações de ordem são baseadas em conjuntos ordenados, conjuntos fechados sob supremo e ínfimo pairwise, 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. Como todas essas bijeções mapeiam uma classe de equivalência sobre si mesma, essas bijeções também são conhecidas como permutações. Portanto, 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.

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

~ partições A em classes de equivalência. (Este é o Teoria Fundamental das Relações com a 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 de transformação G sobre A, existe uma relação de equivalência A, cujas classes de equivalência são as órbitas de G.

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 forma como os reticulados caracterizam as relações de ordem. Os argumentos das operações da teoria da treliça se encontram e se unem são elementos de algum universo A. Já os argumentos das operações do grupo de transformação composição e inversa são elementos de um conjunto de bijeções, A → A.

Movendo-se para grupos em geral, deixe H. H. H. ser um subgrupo de algum grupo G. Seja uma relação de equivalência G, tal que ${displaystyle asim b{text{ if and only if }}ab^{-1}in H.}$ As classes de equivalência de ~ – também chamadas de órbitas da ação de H. H. H. sobre G—são o direito cosets de H. H. H. em G. Intercâmbio um e b) produz os cosets esquerdos.

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

Categorias e grupóides

Vamos. G ser um conjunto e deixar "~" denotar uma relação de equivalência sobre G. Então podemos formar um groupoid representando esta relação de equivalência como segue. Os objetos são os elementos de G, e para qualquer dois elementos x e Sim. de G, existe um morfismo único de x para Sim. se e somente se ${displaystyle xsim 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, a de um groupoid livre em um gráfico direcionado faz. Assim, é significativo falar de uma "apresentação de uma relação de equivalência", isto é, uma apresentação do grupoide 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 groupoid, um ponto de vista que sugere um número de analogias;
Em muitos contextos, as relações de equivalência, muitas vezes chamadas de congruências, são importantes. Isso leva à noção de um groupoid interno em uma categoria.

Retículas

As relações de equivalência em qualquer conjunto X, quando ordenadas por inclusão de conjunto, formam uma rede completa, chamada Con X por convenção. O mapa canônico ker: X^X → Con X, relaciona o monóide X^X de todas as funções em X e Con X. ker é sobrejetivo, mas não injetivo. Menos formalmente, a relação de equivalência ker em X, toma cada função f: X→X para seu kernel 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

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, exemplos podem ser encontrados de relações que não satisfazem o dado propriedade enquanto satisfaz 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 pré-ordem;
Simétrico e transitivo: A relação R sobre N, definido como ARTIGOS ↔ A ≠ 0. Ou qualquer relação de equivalência parcial;
Reflexivo e simétrico: A relação R sobre Z., definido como ARTIGOS O que é?um - Sim. b) é divisível por pelo menos um de 2 ou 3." Ou qualquer relação de dependência.

As 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 infinita cardinalidade;
O número de elementos em cada classe de equivalência é o número natural n.

Contenido relacionado

Más resultados...