World Library  
Flag as Inappropriate
Email this Article

Symmetric difference

Article Id: WHEBN0000262288
Reproduction Date:

Title: Symmetric difference  
Author: World Heritage Encyclopedia
Language: English
Subject: Set theory, Boolean algebra (structure), Cycle basis, Boolean ring, Power set
Collection: Algebra, Basic Concepts in Set Theory, Binary Operations
Publisher: World Heritage Encyclopedia
Publication
Date:
 

Symmetric difference

Venn diagram of ~A \triangle B
The symmetric difference is
the union without the intersection:
~\setminus~ ~=~

In mathematics, the symmetric difference of two sets is the set of elements which are in either of the sets and not in their intersection. The symmetric difference of the sets A and B is commonly denoted by

A\,\triangle\,B,

or

A \ominus B,

or

A \oplus B.

For example, the symmetric difference of the sets \{1,2,3\} and \{3,4\} is \{1,2,4\}. The symmetric difference of the set of all students and the set of all females consists of all non-female students together with all female non-students.

The power set of any set becomes an abelian group under the operation of symmetric difference, with the empty set as the neutral element of the group and every element in this group being its own inverse. The power set of any set becomes a Boolean ring with symmetric difference as the addition of the ring and intersection as the multiplication of the ring.

Contents

  • Properties 1
  • n-ary symmetric difference 2
  • Symmetric difference on measure spaces 3
  • Hausdorff distance vs. Symmetric difference 4
  • See also 5
  • References 6

Properties

Venn diagram of ~A \triangle B \triangle C ~\triangle~ ~=~

The symmetric difference is equivalent to the union of both relative complements, that is:

A\,\triangle\,B = (A \smallsetminus B) \cup (B \smallsetminus A),\,

The symmetric difference can also be expressed using the XOR operation ⊕ on the predicates describing the two sets in set-builder notation:

A\,\triangle\,B = \{x : (x \in A) \oplus (x \in B)\}.

The same fact can be stated as the indicator function (which we denote here by \chi) of the symmetric difference being the XOR (or addition mod 2) of the indicator functions of its two arguments: \chi_{(A\,\triangle\,B)} = \chi_A \oplus \chi_B or using the Iverson bracket notation [x \in A\,\triangle\,B] = [x \in A] \oplus [x \in B].

The symmetric difference can also be expressed as the union of the two sets, minus their intersection:

A\,\triangle\,B = (A \cup B) \smallsetminus (A \cap B),

In particular, A\triangle B\subseteq A\cup B; the equality in this non-strict inclusion occurs if and only if A and B are disjoint sets. Furthermore, if we denote D = A\triangle B and I = A \cap B, then D and I are always disjoint, so D and I partition A \cup B. Consequently, assuming intersection and symmetric difference as primitive operations, the union of two sets can be well defined in terms of symmetric difference by the right-hand side of the equality

A\,\cup\,B = (A\,\triangle\,B)\,\triangle\,(A \cap B).

The symmetric difference is commutative and associative (and consequently the leftmost set of parentheses in the previous expression were thus redundant):

A\,\triangle\,B = B\,\triangle\,A,\,
(A\,\triangle\,B)\,\triangle\,C = A\,\triangle\,(B\,\triangle\,C).\,

The empty set is neutral, and every set is its own inverse:

A\,\triangle\,\varnothing = A,\,
A\,\triangle\,A = \varnothing.\,

Taken together, we see that the power set of any set X becomes an abelian group if we use the symmetric difference as operation. (More generally, any field of sets forms a group with the symmetric difference as operation.) A group in which every element is its own inverse (or, equivalently, in which every element has order 2) is sometimes called a Boolean group;[1][2] the symmetric difference provides a prototypical example of such groups. Sometimes the Boolean group is actually defined as the symmetric difference operation on a set.[3] In the case where X has only two elements, the group thus obtained is the Klein four-group.

Equivalently, a Boolean group is an Elementary abelian 2-group. Consequently, the group induced by the symmetric difference is in fact a vector space over the field with 2 elements Z2. If X is finite, then the singletons form a basis of this vector space, and its dimension is therefore equal to the number of elements of X. This construction is used in graph theory, to define the cycle space of a graph.

From the property of the inverses in a Boolean group, it follows that the symmetric difference of two repeated symmetric differences is equivalent to the repeated symmetric difference of the join of the two multisets, where for each double set both can be removed. In particular:

(A\,\triangle\,B)\,\triangle\,(B\,\triangle\,C) = A\,\triangle\,C.\,

This implies triangle inequality:[4] the symmetric difference of A and C is contained in the union of the symmetric difference of A and B and that of B and C. (But note that for the diameter of the symmetric difference the triangle inequality does not hold.)

Intersection distributes over symmetric difference:

A \cap (B\,\triangle\,C) = (A \cap B)\,\triangle\,(A \cap C),

and this shows that the power set of X becomes a ring with symmetric difference as addition and intersection as multiplication. This is the prototypical example of a Boolean ring. Further properties of the symmetric difference:

  • A\triangle B=A^c\triangle B^c, where A^c,B^c is A's complement,B's complement, respectively, relative to any (fixed) set that contains both.
  • \left(\bigcup_{\alpha\in\mathcal{I}}A_\alpha\right)\triangle\left(\bigcup_{\alpha\in\mathcal{I}}B_\alpha\right)\subseteq\bigcup_{\alpha\in\mathcal{I}}\left(A_\alpha\triangle B_\alpha\right), where \mathcal{I} is an arbitrary non-empty index set.
  • If f : S \rightarrow T is any function and A, B \subseteq T are any sets in f's codomain, then f^{-1}\left(A \Delta B\right) = f^{-1}\left(A\right) \Delta f^{-1}\left(B\right).

The symmetric difference can be defined in any Boolean algebra, by writing

x\,\triangle\,y = (x \lor y) \land \lnot(x \land y) = (x \land \lnot y) \lor (y \land \lnot x) = x \oplus y.

This operation has the same properties as the symmetric difference of sets.

n-ary symmetric difference

The repeated symmetric difference is in a sense equivalent to an operation on a multiset of sets giving the set of elements which are in an odd number of sets.

As above, the symmetric difference of a collection of sets contains just elements which are in an odd number of the sets in the collection:

\triangle M = \left\{ a \in \bigcup M: |\{A\in M:a \in A\}| \mbox{ is odd}\right\}.

Evidently, this is well-defined only when each element of the union \bigcup M is contributed by a finite number of elements of M.

Suppose M=\{M_{1},M_{2}, \ldots , M_{n}\} is a multiset and n \ge 2. Then there is a formula for |\triangle M|, the number of elements in \triangle M, given solely in terms of intersections of elements of M:

|\triangle M| = \sum_{l=1}^{n} (-2)^{l-1} \sum_{i_{1} \ne i_{2} \ne \ldots \ne i_{l}} |M_{i_{1}} \cap M_{i_{2}} \cap \ldots \cap M_{i_{l}}|,

where i_{1} \ne i_{2} \ne \ldots \ne i_{l} is meant to indicate that \{i_{1}, i_{2}, \ldots, i_{l}\} is a subset of distinct elements of \{1,2,\ldots,n\}, of which there are \binom{n}{l}.

Symmetric difference on measure spaces

As long as there is a notion of "how big" a set is, the symmetric difference between two sets can be considered a measure of how "far apart" they are. Formally, if μ is a σ-finite measure defined on a σ-algebra Σ, the function

d_\mu(X,Y) = \mu(X\,\triangle\,Y)

is a pseudometric on Σ. dμ becomes a metric if Σ is considered modulo the equivalence relation X ~ Y if and only if \mu(X\,\triangle\,Y) = 0. The resulting metric space is separable if and only if L2(μ) is separable.

If \mu(X), \mu(Y) < \infty, we have: |\mu(X) - \mu(Y)| \leq \mu(X\,\triangle\,Y). Indeed,

\begin{align} |\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{align}

Let S=\left(\Omega,\mathcal{A},\mu\right) be some measure space and let F,G\in\mathcal{A} and \mathcal{D},\mathcal{E}\subseteq\mathcal{A}.

Symmetric difference is measurable: F\triangle G\in\mathcal{A}.

We write F=G\left[\mathcal{A},\mu\right] iff \mu\left(F\triangle G\right)=0. The relation "=\left[\mathcal{A},\mu\right]" is an equivalence relation on the \mathcal{A}-measurable sets.

We write \mathcal{D}\subseteq\mathcal{E}\left[\mathcal{A},\mu\right] iff to each D\in\mathcal{D} there's some E\in\mathcal{E} such that D=E\left[\mathcal{A},\mu\right]. The relation "\subseteq\left[\mathcal{A},\mu\right]" is a partial order on the family of subsets of \mathcal{A}.

We write \mathcal{D}=\mathcal{E}\left[\mathcal{A},\mu\right] iff \mathcal{D}\subseteq\mathcal{E}\left[\mathcal{A},\mu\right] and \mathcal{E}\subseteq\mathcal{D}\left[\mathcal{A},\mu\right]. The relation "=\left[\mathcal{A},\mu\right]" is an equivalence relationship between the subsets of \mathcal{A}.

The "symmetric closure" of \mathcal{D} is the collection of all \mathcal{A}-measurable sets that are =\left[\mathcal{A},\mu\right] to some D\in\mathcal{D}. The symmetric closure of \mathcal{D} contains \mathcal{D}. If \mathcal{D} is a sub-\sigma-algebra of \mathcal{A}, so is the symmetric closure of \mathcal{D}.

F=G\left[\mathcal{A},\mu\right] iff \left|\mathbf{1}_F-\mathbf{1}_G\right|=0 \left[\mathcal{A},\mu\right]-a.e.

Hausdorff distance vs. Symmetric difference

The Hausdorff distance and the (area of the) symmetric difference are both pseudo-metrics on the set of measurable geometric shapes. However, they behave quite differently. The figure at the right shows two sequences of shapes, "Red" and "Red ∪ Green". When the Hausdorff distance between them becomes smaller, the area of the symmetric difference between them becomes larger, and vice versa. By continuing these sequences in both directions, it is possible to get two sequences such that the Hausdorff distance between them converges to 0 and the symmetric distance between them diverges, or vice versa.

See also

References

  1. ^ Steven Givant; Paul Halmos (2009). Introduction to Boolean Algebras. Springer Science & Business Media. p. 6.  
  2. ^ Lloyd Humberstone (2011). The Connectives. MIT Press. p. 782.  
  3. ^ Joseph J. Rotman (2010). Advanced Modern Algebra. American Mathematical Soc. p. 19.  
  4. ^ Rudin, Walter (January 1, 1976). Principles of Mathematical Analysis (3rd ed.). McGraw-Hill Education. p. 306.  
  •  
This article was sourced from Creative Commons Attribution-ShareAlike License; additional terms may apply. World Heritage Encyclopedia content is assembled from numerous content providers, Open Access Publishing, and in compliance with The Fair Access to Science and Technology Research Act (FASTR), Wikimedia Foundation, Inc., Public Library of Science, The Encyclopedia of Life, Open Book Publishers (OBP), PubMed, U.S. National Library of Medicine, National Center for Biotechnology Information, U.S. National Library of Medicine, National Institutes of Health (NIH), U.S. Department of Health & Human Services, and USA.gov, which sources content from all federal, state, local, tribal, and territorial government publication portals (.gov, .mil, .edu). Funding for USA.gov and content contributors is made possible from the U.S. Congress, E-Government Act of 2002.
 
Crowd sourced content that is contributed to World Heritage Encyclopedia is peer reviewed and edited by our editorial staff to ensure quality scholarly research articles.
 
By using this site, you agree to the Terms of Use and Privacy Policy. World Heritage Encyclopedia™ is a registered trademark of the World Public Library Association, a non-profit organization.
 


Copyright © World Library Foundation. All rights reserved. eBooks from Project Gutenberg are sponsored by the World Library Foundation,
a 501c(4) Member's Support Non-Profit Organization, and is NOT affiliated with any governmental agency or department.