Symmetric difference: Definition from Answers.com

This article includes a list of references, related reading or external links, but its sources remain unclear because it lacks inline citations. Please improve this article by introducing more precise citations where appropriate. (March 2009)

In mathematics, the symmetric difference of two sets is the set of elements which are in one of the sets, but not in both. This operation is the set-theoretic kin of the exclusive disjunction (XOR operation) in Boolean logic. The symmetric difference of the sets A and B is commonly denoted by

$A\,\Delta\,B\,$

$A \ominus B.$

Venn diagram of A Δ B. The symmetric difference is red.

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 male students together with all female non-students.

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

$A\,\Delta\,B = (A \setminus B) \cup (B \setminus A),\,$

and it can also be expressed as the union of the two sets, minus their intersection:

$A\,\Delta\,B = (A \cup B) \setminus (A \cap B),$

or with the XOR operation:

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

The symmetric difference is commutative and associative:

$A\,\Delta\,B = B\,\Delta\,A,\,$

$(A\,\Delta\,B)\,\Delta\,C = A\,\Delta\,(B\,\Delta\,C).\,$

Thus, the repeated symmetric difference is an operation on a multiset of sets giving the set of elements which are in an odd number of sets.

The symmetric difference of two repeated symmetric differences is the repeated symmetric difference of the join of the two multisets, where for each double set both can be removed. In particular:

$(A\,\Delta\,B)\,\Delta\,(B\,\Delta\,C) = A\,\Delta\,C.\,$

This implies a kind of triangle inequality: 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.)

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

$A\,\Delta\,\varnothing = A,\,$

$A\,\Delta\,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. Because every element in this group is its own inverse, this is in fact a vector space over the field with 2 elements Z₂. 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.

Intersection distributes over symmetric difference:

$A \cap (B\,\Delta\,C) = (A \cap B)\,\Delta\,(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.

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

$x\,\Delta\,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.

1 n-ary symmetric difference
2 Symmetric difference on measure spaces
3 See also
4 References

n-ary symmetric difference

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

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(X,Y) = \mu(X\,\Delta\,Y)$

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

References

Symmetric difference on PlanetMath
Weisstein, Eric W., "Symmetric Difference" from MathWorld.
Symmetric difference of sets. In Encyclopaedia of Mathematics

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

	What is difference between symmetric and asymmetric nuclear matter? Read answer...
	What is the difference between symmetric and asymmetric cryptography? Read answer...
	Difference between a symmetrical shape and an asymmetrical shape? Read answer...

	What is difference between symmetric and asymmetric compression?
	What is the difference between the symmetric and commutative property?
	What are the differences between - and the pros and cons of - symmetric and asymmetric multiprocessing.?

		Sci-Tech Dictionary. McGraw-Hill Dictionary of Scientific and Technical Terms. Copyright © 2003, 1994, 1989, 1984, 1978, 1976, 1974 by McGraw-Hill Companies, Inc. All rights reserved. Read more
		Wikipedia. This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article "Symmetric difference". Read more

Symmetric difference

Contents

n-ary symmetric difference

Symmetric difference on measure spaces

See also

References