Symmetric difference

Symmetric difference
Venn0110.svg
Venn diagram of ~A \Delta B

The symmetric difference is
the union without the intersection:
Venn0111.svg Venn0001.svg Venn0110.svg

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\,\Delta\,B\,

or

A \ominus 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 male 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

Venn 0110 1001.svg
Venn diagram of ~A \Delta B \Delta C

Venn 0110 0110.svg Venn 0000 1111.svg Venn 0110 1001.svg

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

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.

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 L2(μ) is separable.

See also

References


Wikimedia Foundation. 2010.

Игры ⚽ Нужна курсовая?

Look at other dictionaries:

  • symmetric difference — Math. the union of the relative complements of two sets. Also called Boolean sum. * * * …   Universalium

  • symmetric difference — noun The set that contains all elements belonging to either of given two sets but not to the both; the relative complement of the intersection in the union of given two sets …   Wiktionary

  • symmetric difference — Math. the union of the relative complements of two sets. Also called Boolean sum …   Useful english dictionary

  • Symmetric Digital Subscriber Line — (SDSL) is a Digital Subscriber Line (DSL) variant with T1/E1 like data rates (72 to 2320 kbit/s). It runs over one pair of copper wires, with a maximum range of about 3 kilometers or 1.86 miles. The main difference between ADSL and SDSL is that… …   Wikipedia

  • Symmetric algebra — In mathematics, the symmetric algebra S ( V ) (also denoted Sym ( V )) on a vector space V over a field K is the free commutative unital associative K algebra containing V .It corresponds to polynomials with indeterminates in V , without choosing …   Wikipedia

  • Difference set — For the concept of set difference, see complement (set theory). In combinatorics, a (v,k,λ) difference set is a subset D of a group G such that the order of G is v, the size of D is k, and every nonidentity element of G can be expressed as a… …   Wikipedia

  • Symmetric matrix — In linear algebra, a symmetric matrix is a square matrix, A , that is equal to its transpose:A = A^{T}. ,!The entries of a symmetric matrix are symmetric with respect to the main diagonal (top left to bottom right). So if the entries are written… …   Wikipedia

  • Elementary symmetric polynomial — In mathematics, specifically in commutative algebra, the elementary symmetric polynomials are one type of basic building block for symmetric polynomials, in the sense that any symmetric polynomial P can be expressed as a polynomial in elementary… …   Wikipedia

  • Madison Symmetric Torus — Infobox Magnetic Fusion Device name = Madison Symmetric Torus dev type=Reversed field pinch loc=Madison, Wisconsin, USA rad maj = 1.50 m rad min = 52 cm aspect = 2.88|The Madison Symmetric Torus (MST) is a reversed field pinch (RFP) physics… …   Wikipedia

  • Power sum symmetric polynomial — In mathematics, specifically in commutative algebra, the power sum symmetric polynomials are a type of basic building block for symmetric polynomials, in the sense that every symmetric polynomial with rational coefficients can be expressed as a… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”