Diferença simétrica

Diagrama de Venn de   A △ B {\displaystyle ~A\triangle B}
A diferença simétrica é
a união tirando a interseção:
  ∖   {\displaystyle ~\setminus ~}   =   {\displaystyle ~=~}

Em matemática, a diferença simétrica de dois conjuntos é o conjunto de elementos que estão em um dos conjuntos, e não em sua interseção. A diferença simétrica dos conjuntos A e B é comumente denotada por

A △ B , {\displaystyle A\,\triangle \,B,}

ou

A ⊖ B , {\displaystyle A\ominus B,}

ou

A ⊕ B . {\displaystyle A\oplus B.}

Por exemplo, a diferença simétrica dos conjuntos { 1 , 2 , 3 } {\displaystyle \{1,2,3\}} e { 3 , 4 } {\displaystyle \{3,4\}} é { 1 , 2 , 4 } {\displaystyle \{1,2,4\}} .

O conjunto das partes de qualquer conjunto torna-se um grupo abeliano sob a operação de diferença simétrica, sendo o conjunto vazio como o elemento neutro do grupo e cada elemento deste grupo o seu próprio inverso. O conjunto das partes de qualquer conjunto se torna um anel booleano usando a diferença simétrica como a adição do anel e intersecção como a multiplicação do anel.

Propriedades

Diagrama de Venn de   A △ B △ C {\displaystyle ~A\triangle B\triangle C}   △   {\displaystyle ~\triangle ~}   =   {\displaystyle ~=~}

A diferença simétrica é equivalente à união de ambas as diferenças, que é:

A △ B = ( A ∖ B ) ∪ ( B ∖ A ) , {\displaystyle A\,\triangle \,B=(A\smallsetminus B)\cup (B\smallsetminus A),\,}

A diferença simétrica também pode ser expressa usando a operação XOR, ⊕, sobre os predicados que descrevem os dois conjuntos da seguinte forma:

A △ B = { x : ( x ∈ A ) ⊕ ( x ∈ B ) } . {\displaystyle A\,\triangle \,B=\{x:(x\in A)\oplus (x\in B)\}.}

A diferença simétrica também pode ser expressa como a união de dois conjuntos, menos a sua interseção:

A △ B = ( A ∪ B ) ∖ ( A ∩ B ) , {\displaystyle A\,\triangle \,B=(A\cup B)\smallsetminus (A\cap B),}

Em particular, A △ B ⊆ A ∪ B {\displaystyle A\triangle B\subseteq A\cup B} ; a igualdade na inclusão não-estrita ocorre se, e somente se, A {\displaystyle A} e B {\displaystyle B} são conjuntos disjuntos. Além disso, se denotamos D = A △ B {\displaystyle D=A\triangle B} e I = A ∩ B {\displaystyle I=A\cap B} , então D {\displaystyle D} e I {\displaystyle I} sempre são disjuntos, e portanto  D {\displaystyle D} e I {\displaystyle I}  formam uma partição de  A ∪ B {\displaystyle A\cup B} . Consequentemente, assumindo interseção e diferença simétrica como operações primitivas, a união de dois conjuntos pode ser bem definido em termos de diferença simétrica pelo lado direito da igualdade

A ∪ B = ( A △ B ) △ ( A ∩ B ) {\displaystyle A\,\cup \,B=(A\,\triangle \,B)\,\triangle \,(A\cap B)} .

A diferença simétrica é comutativa e associativa (e, consequentemente, o conjunto de parênteses na expressão anterior foi, portanto, desnecessário):

A △ B = B △ A , {\displaystyle A\,\triangle \,B=B\,\triangle \,A,\,} ( A △ B ) △ C = A △ ( B △ C ) . {\displaystyle (A\,\triangle \,B)\,\triangle \,C=A\,\triangle \,(B\,\triangle \,C).\,}

A primeira dessas (comutatividade) tem sua demonstração com poucos e simples passos, uma vez que sabemos que a união também é comutativa:

A △ B = ( A ∖ B ) ∪ ( B ∖ A ) = ( B ∖ A ) ∪ ( A ∖ B ) = B △ A {\displaystyle A\,\triangle \,B=(A\smallsetminus B)\cup (B\smallsetminus A)=(B\smallsetminus A)\cup (A\smallsetminus B)=B\,\triangle \,A}

Já a segunda, a associatividade, exige um pouco mais de passos para sua demonstração:

( A △ B ) △ C = ( ( A △ B ) ∖ C ) ∪ ( C ∖ ( A △ B ) ) = ( ( ( A ∖ B ) ∪ ( B ∖ A ) ) ∖ C ) ∪ ( C ∖ ( ( A ∖ B ) ∪ ( B ∖ A ) ) ) {\displaystyle (A\,\triangle \,B)\,\triangle \,C=((A\,\triangle \,B)\smallsetminus C)\cup (C\smallsetminus (A\,\triangle \,B))=(((A\smallsetminus B)\cup (B\smallsetminus A))\smallsetminus C)\cup (C\smallsetminus ((A\smallsetminus B)\cup (B\smallsetminus A)))}

A partir daí, vamos separar a expressão em duas partes para prosseguir a demonstração. A primeira parte da expressão será o lado esquerdo do operador de união principal, onde usaremos a propriedade de distributividade pela esquerda da diferença de conjuntos, depois a propriedade de "diferença da união":

( ( A ∖ B ) ∪ ( B ∖ A ) ) ∖ C = ( ( A ∖ B ) ∖ C ) ∪ ( ( B ∖ A ) ∖ C ) = ( A ∖ ( B ∪ C ) ) ∪ ( B ∖ ( A ∪ C ) ) {\displaystyle ((A\smallsetminus B)\cup (B\smallsetminus A))\smallsetminus C=((A\smallsetminus B)\smallsetminus C)\cup ((B\smallsetminus A)\smallsetminus C)=(A\smallsetminus (B\cup C))\cup (B\smallsetminus (A\cup C))}

Na segunda parte da expressão principal, serão utilizadas propriedades de complemento de conjuntos (encontradas na mesma página sobre diferença de conjuntos), novamente a propriedade de diferença da união, além de propriedades de distributividade entre união e intersecção:

C ∖ ( ( A ∖ B ) ∪ ( B ∖ A ) ) = ( C ∖ ( A ∖ B ) ) ∖ ( B ∖ A ) = C ∩ ( A ∖ B ) ∁ ∩ ( B ∖ A ) ∁ = C ∩ ( A ∁ ∪ B ) ∩ ( B ∁ ∪ A ) = {\displaystyle C\smallsetminus ((A\smallsetminus B)\cup (B\smallsetminus A))=(C\smallsetminus (A\smallsetminus B))\smallsetminus (B\smallsetminus A)=C\cap (A\smallsetminus B)^{\complement }\cap (B\smallsetminus A)^{\complement }=C\cap (A^{\complement }\cup B)\cap (B^{\complement }\cup A)=}

C ∩ ( ( A ∁ ∩ ( B ∁ ∪ A ) ) ∪ ( B ∩ ( B ∁ ∪ A ) ) ) = C ∩ ( ( A ∁ ∩ B ∁ ) ∪ ( B ∩ A ) ) = ( C ∖ ( A ∪ B ) ) ∪ ( C ∩ B ∩ A ) {\displaystyle C\cap ((A^{\complement }\cap (B^{\complement }\cup A))\cup (B\cap (B^{\complement }\cup A)))=C\cap ((A^{\complement }\cap B^{\complement })\cup (B\cap A))=(C\smallsetminus (A\cup B))\cup (C\cap B\cap A)}

Por fim, ao juntar essas duas partes, substituindo na expressão inicial suas equivalências encontradas e utilizando as propriedades de comutatividade, temos:

( A △ B ) △ C = ( A ∖ ( B ∪ C ) ) ∪ ( B ∖ ( A ∪ C ) ) ∪ ( C ∖ ( A ∪ B ) ) ∪ ( C ∩ B ∩ A ) = {\displaystyle (A\,\triangle \,B)\,\triangle \,C=(A\smallsetminus (B\cup C))\cup (B\smallsetminus (A\cup C))\cup (C\smallsetminus (A\cup B))\cup (C\cap B\cap A)=}

( B ∖ ( C ∪ A ) ) ∪ ( C ∖ ( B ∪ A ) ) ∪ ( A ∖ ( B ∪ C ) ) ∪ ( A ∩ C ∩ B ) = ( B △ C ) △ A = A △ ( B △ C ) ◻ {\displaystyle (B\smallsetminus (C\cup A))\cup (C\smallsetminus (B\cup A))\cup (A\smallsetminus (B\cup C))\cup (A\cap C\cap B)=(B\,\triangle \,C)\,\triangle \,A=A\,\triangle \,(B\,\triangle \,C)\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\Box }

O conjunto vazio é neutro, e cada conjunto é o seu próprio inverso:

A △ ∅ = A , {\displaystyle A\,\triangle \,\varnothing =A,\,} A △ A = ∅ . {\displaystyle A\,\triangle \,A=\varnothing .\,}

A intersecção é distributiva em relação à diferença simétrica:

A ∩ ( B △ C ) = ( A ∩ B ) △ ( A ∩ C ) , {\displaystyle A\cap (B\,\triangle \,C)=(A\cap B)\,\triangle \,(A\cap C),}

e isso mostra que o conjunto de potência de X torna-se um anel com diferença simétrica como a adição e a intersecção de multiplicação. Este é um exemplo de um anel booleano.

Mais propriedades da diferença simétrica:

A diferença simétrica pode ser definida em qualquer álgebra Booleana da seguinte maneira:

x △ y = ( x ∨ y ) ∧ ¬ ( x ∧ y ) = ( x ∧ ¬ y ) ∨ ( y ∧ ¬ x ) = x ⊕ y . {\displaystyle x\,\triangle \,y=(x\lor y)\land \lnot (x\land y)=(x\land \lnot y)\lor (y\land \lnot x)=x\oplus y.}

Esta operação tem as mesmas propriedades que a diferença simétrica de conjuntos.

Diferença simétrica em espaços de medida

Enquanto houver uma noção de "quão grande " é um conjunto, a diferença simétrica entre dois conjuntos pode ser considerada uma medida de quão "longe" eles estão. Primeiro, considere um conjunto finito S e a medida de contagem em subconjuntos dada pelo seu tamanho. Agora, considere dois subconjuntos de S e defina distância como o tamanho da sua diferença simétrica. Esta distância é, na verdade, uma métrica de modo que o conjunto das partes de S é um espaço métrico. Se S tem n elementos, então a distância a partir do conjunto vazio de S é n, e este é o máximo de distância, para qualquer par de subconjuntos.

Usando as ideias da teoria da medida, a separação de conjuntos mensuráveis pode ser definida como a medida de sua diferença simétrica. Se μ é uma medida σ-finita definida em uma σ-algebra Σ, a função

d μ ( X , Y ) = μ ( X △ Y ) {\displaystyle d_{\mu }(X,Y)=\mu (X\,\triangle \,Y)}

é uma pseudométrica em Σ. dμ torna-se uma métrica se Σ é considerada módulo da relação de equivalência X ~Y se, e somente se, μ ( X △ Y ) = 0 {\displaystyle \mu (X\,\triangle \,Y)=0} . O espação métrico resultante é separável se e somente se L2(μ) é separável.

Se μ ( X ) , μ ( Y ) < ∞ {\displaystyle \mu (X),\mu (Y)<\infty } , temos: | μ ( X ) − μ ( Y ) | ≤ μ ( X △ Y ) {\displaystyle |\mu (X)-\mu (Y)|\leq \mu (X\,\triangle \,Y)} . De fato,

| μ ( X ) − μ ( Y ) | = | ( μ ( X ∖ Y ) + μ ( X ∩ Y ) ) − ( μ ( X ∩ Y ) + μ ( Y ∖ X ) ) | = | μ ( X ∖ Y ) − μ ( Y ∖ X ) | ≤ | μ ( X ∖ Y ) | + | μ ( Y ∖ X ) | = μ ( X ∖ Y ) + μ ( Y ∖ X ) = μ ( ( X ∖ Y ) ∪ ( Y ∖ X ) ) = μ ( X Δ Y ) {\displaystyle {\begin{aligned}|\mu (X)-\mu (Y)|&=|(\mu (X\setminus Y)+\mu (X\cap Y))-(\mu (X\cap Y)+\mu (Y\setminus X))|\\&=|\mu (X\setminus Y)-\mu (Y\setminus X)|\\&\leq |\mu (X\setminus Y)|+|\mu (Y\setminus X)|\\&=\mu (X\setminus Y)+\mu (Y\setminus X)\\&=\mu ((X\setminus Y)\cup (Y\setminus X))\\&=\mu (X\Delta Y)\end{aligned}}}

Seja  S = ( Ω , A , μ ) {\displaystyle S=\left(\Omega ,{\mathcal {A}},\mu \right)}  um espaço de medida e sejam  F , G ∈ A {\displaystyle F,G\in {\mathcal {A}}} e D , E ⊆ A {\displaystyle {\mathcal {D}},{\mathcal {E}}\subseteq {\mathcal {A}}} .

A diferença simétrica é mensurável: F △ G ∈ A {\displaystyle F\triangle G\in {\mathcal {A}}} .

Podemos escrever F = G {\displaystyle F=G\left} se, e somente se  μ ( F △ G ) = 0 {\displaystyle \mu \left(F\triangle G\right)=0} . A relação " = {\displaystyle =\left} " é uma relação de equivalência em a conjuntos  A {\displaystyle {\mathcal {A}}} -mensuráveis.

Podemos escrever D ⊆ E {\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left} se, e somente se, para cada D ∈ D {\displaystyle D\in {\mathcal {D}}} existir algum  E ∈ E {\displaystyle E\in {\mathcal {E}}} de tal forma que D = E {\displaystyle D=E\left} . A relação " ⊆ {\displaystyle \subseteq \left} " é uma ordem parcial sobre a família de subconjuntos de A {\displaystyle {\mathcal {A}}} .

Podemos escrever D = E {\displaystyle {\mathcal {D}}={\mathcal {E}}\left} se, e somente se,  D ⊆ E {\displaystyle {\mathcal {D}}\subseteq {\mathcal {E}}\left} e E ⊆ D {\displaystyle {\mathcal {E}}\subseteq {\mathcal {D}}\left} . A relação " = {\displaystyle =\left} " é uma relação de equivalência entre os subconjuntos de A {\displaystyle {\mathcal {A}}} .

O "fecho simétrico" de D {\displaystyle {\mathcal {D}}} é o conjunto de todos os conjuntos A {\displaystyle {\mathcal {A}}} -mensuráveis que são = {\displaystyle =\left} para algum D ∈ D {\displaystyle D\in {\mathcal {D}}} . O fecho simétrico de  D {\displaystyle {\mathcal {D}}} contém D {\displaystyle {\mathcal {D}}} . Se D {\displaystyle {\mathcal {D}}} é um sub- σ {\displaystyle \sigma } -álgebra de A {\displaystyle {\mathcal {A}}} , o fecho simétrico em questão também será.

Distância de Hausdorff vs. Diferença Simétrica

Duas sequências de formatos ilustrando as diferenças entre a distância de Hausdorff e a diferença simétrica.

A distância de Hausdorff e a (área da) diferença simétrica são ambos pseudométricas sobre o conjunto formas geométricas mensuráveis. No entanto, eles se comportam de forma bastante diferente. A figura ao lado mostra duas sequências de formas, "Vermelho" e "Vermelho ∪ Verde". Quando a distância de Hausdorff entre eles torna-se menor, a área da diferença simétrica entre eles torna-se maior, e vice-versa. Continuando estas sequências em ambas as direções, é possível obter duas seqüências tais que a distância de Hausdorff entre eles irá convergir para 0 e a distância simétrica irá divergir, ou vice-versa.

Veja também

Referências

  1. ↑ Claude Flament (1963) Aplicações da Teoria dos grafos para a Estrutura do Grupo, página 16, Prentice-Hall MR 0157785