symmetric difference

The symmetric difference of two sets AA and BB (either pure sets or subsets of some fixed set), written ABA \uplus B (and a host of other ways), may be defined using exclusive disjunction:

AB={x|xAUnknown characterUnknown characterUnknown characterxB}. A \uplus B = \{ x \;|\; x \in A \;⊻\; x \in B \} .

You can also call this exclusive union, especially if you want to use it analogously to exclusive disjunction; then the exclusive union of nn sets consists of those elements xx that belong to exactly one of the nn sets.

The term symmetric difference, however, is usually used as the addition in a Boolean ring and so interpreted as an associative operation; then the symmetric difference of nn sets consists of those elements xx that belong to an odd number of the nn sets.

The empty set is the identity for this operation; it is the symmetric difference (or exclusive union, for that matter) of no sets.

In constructive mathematics, the symmetic difference cannot be proved associative and so becomes less useful (unless one restricts attention to sets with decidable equality, where it can be proved associative). This is a problem in measure theory; see Cheng measurable space for one way to fix this.

Note that the union, symmetric difference, and (internal, or external up to natural isomorphism) disjoint union of a family of (pairwise) disjoint sets are all the same. For a family that is not disjoint, however, the union and symmetric difference are different, the internal disjoint union does not make sense, and the external disjoint union is not isomorphic to either the union or the symmetric difference (at least not naturally, and in some cases not at all).

Created on August 12, 2009 21:31:34 by Toby Bartels (