Entries Tagged as 'difference'

Symmetric difference

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 equivalent of the exclusive disjunction (XOR operation) in Boolean logic. The symmetric difference of the sets A and B is commonly denoted by

<math> A \Delta B\,.</math>

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:

<math>A \Delta B = (A - B) \cup (B - A),\,</math>

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

<math>A \Delta B = (A \cup B) - (A \cap B),</math>

or with the XOR operation:

<math>A \Delta B = \{x : (x \in A) \mbox{ XOR } (x \in B)\}.</math>

The symmetric difference is commutative and associative:

<math>A \Delta B = B \Delta A,\,</math>
<math>(A \Delta B) \Delta C = A \Delta (B \Delta C).\,</math>

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:

<math>(A \Delta B) \Delta (B \Delta C) = A \Delta C.\,</math>

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:

<math>A \Delta \varnothing = A,\,</math>
<math>A \Delta A = \varnothing.\,</math>

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:

<math>A \cap (B \Delta C) = (A \cap B) \Delta (A \cap C),</math>

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

<math> x \Delta y = (x \lor y) \land \lnot(x \land y) = (x \land \lnot y) \lor (y \land \lnot x) = x \oplus y.</math>

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:

<math>\triangle M = \left\{ a \in \bigcup M\ |\ \#\{A\in M|a \in A\}\ \mbox{is odd}\right\}</math>.

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


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,

<math>d(X,Y) = \mu(X \Delta Y)</math>

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


See also

  • Algebra of sets
  • Boolean function
  • Fuzzy set
  • Logical graph
  • Minimal negation operator
  • Set theory
  • Symmetry
  • Zeroth order logic

Tags: Uncategorized by admin
No Comments »

Distinction without a difference

A distinction without a difference is a type of argument where one word or phrase is preferred to another, but results in no difference to the final outcome. It is particularly used when a word or phrase has connotations associated with it that one party to an argument prefers to avoid.

“In legal terminology it means a change in definition which does not change the set which is defined. For example changing ‘unseparated married men’ to ‘males who have a non-separated spouse’ is a distinction without a difference.”

One of Alan King’s jokes about the legal industry was about a lawyer who chastised him for not having a will, on the grounds that “if you die without a will, you would die intestate.”


References

Difference set

For the concept of set difference, see complement (set theory).

In combinatorics, a <math>(v,k,\lambda)</math> difference set is a subset <math>D</math> of a group <math>G</math> such that the order of <math>G</math> is <math>v</math>, the size of <math>D</math> is <math>k</math>, and every nonidentity element of <math>G</math> can be expressed as a product <math>d_1d_2^{-1}</math> of elements of <math>D</math> in exactly <math>\lambda</math> ways.


Basic facts

  • A simple counting argument shows that there are exactly <math>k^2-k</math> pairs of elements from <math>D</math> that will yield nonidentity elements, so every difference set must satisfy the equation <math>k^2-k=(v-1)\lambda</math>.
  • If <math>D</math> is a difference set, and <math>g\in G</math>, then <math>gD=\{gd:d\in D\}</math> is also a difference set, and is called a translate of <math>D</math>.
  • The set of all translates of a difference set <math>D</math> forms a symmetric design (a special kind of combinatorial design). In such a design there are <math>v</math> elements (mostly called points) and <math>v</math> blocks. Each block of the design consists of <math>k</math> points, each point is contained in <math>k</math> blocks. Any two blocks have exactly <math>\lambda</math> elements in common and any two points are “joined” by <math>\lambda</math> blocks. The group <math>G</math> then acts as an automorphism group of the design. It is sharply transitive on points and blocks.
  • Since every difference set gives a combinatorial design, the parameter set must satisfy the Bruck-Chowla-Ryser theorem.
  • Not every combinatorial design gives a difference set.

In particular, if <math>\lambda=1</math>, then the difference set gives rise to a projective plane.
An example of a (7,3,1) difference set in the group <math>\mathbb{Z}/7\mathbb{Z}</math> is the set <math>\{1,2,4\}</math>. The translates of this difference set gives the Fano plane.


Multipliers

It has been conjectured that if <math>p</math> is a prime dividing <math>k-\lambda</math> and does not divide <math>v</math>, then the group automorphism defined by <math>g\mapsto g^p</math> fixes some translate of <math>D</math>. It is known to be true for <math>p>\lambda</math>, and this is known as the First Multiplier Theorem. A more general known result, the Second Multiplier Theorem, first says to choose a divisor <math>m>\lambda</math> of <math>k-\lambda</math>. Then <math>g\mapsto g^t</math>, <math>t</math> coprime with <math>v</math>, fixes some translate of <math>D</math> if for every prime <math>p</math> dividing <math>m</math>, there exists an integer <math>i</math> such that <math>t\equiv p^i\bmod v^*</math>, where <math>v^*</math> is the exponent (the least common multiple of the orders of every element) of the group.
For example, 2 is a multiplier of the (7,3,1) difference set mentioned above.


Parameters

Every difference set known to mankind to this day has one of the following parameters or their complements:

  • <math>((q^{n+2}-1)/(q-1), (q^{n+1}-1)/(q-1), (q^n-1)/(q-1))</math>-difference set for some prime power <math>q</math> and some positive integer <math>n</math>.
  • <math>(4n-1,2n-1,n-1)</math>-difference set for some positive integer <math>n</math>.
  • <math>(4n^2,2n^2-n,n^2-n)</math>-difference set for some positive integer <math>n</math>.
  • <math>(q^{n+1}(1+(q^{n+1}-1)/(q-1)),q^n(q^{n+1}-1)/(q-1),q^n(q^n-1)(q-1))</math>-difference set for some prime power <math>q</math> and some positive integer <math>n</math>.
  • <math>(3^{n+1}(3^{n+1}-1)/2,3^n(3^{n+1}+1)/2,3^n(3^n+1)/2)</math>-difference set for some positive integer <math>n</math>.
  • <math>(4q^{2n}(q^{2n}-1)/(q-1),q^{2n-1}(1+2(q^{2n}-1)/(q+1)),q^{2n-1}(q^{2n-1}+1)(q-1)/(q+1))</math>-difference set for some prime power <math>q</math> and some positive integer <math>n</math>.


Known difference sets

  • Singer <math>((q^{n+2}-1)/(q-1), (q^{n+1}-1)/(q-1), (q^n-1)/(q-1))\overline{}</math>-Difference Set:

Let <math>G={\rm GF}(q^{n+2})^*/{\rm GF}(q)^*=\{\overline{x}~|~x\in{\rm GF}(q^{n+2})^*\}</math>, where <math>{\rm GF}(q^{n+2})\overline{}</math> and <math>{\rm GF}(q)\overline{}</math> are Galois fiels of order <math>q^{n+2}\overline{}</math> and <math>q\overline{}</math> respectively and <math>{\rm GF}(q^{n+2})^*\overline{}</math> and <math>{\rm GF}(q)^*\overline{}</math> are their respective multiplicative groups of non-zero elements. Then the set <math>D=\{\overline{x}\in G~|~{\rm Tr}_{q^{n+2}/q}(x)=0\}</math> is a <math>((q^{n+2}-1)/(q-1), (q^{n+1}-1)/(q-1), (q^n-1)/(q-1))\overline{}</math>-difference set, where <math>{\rm Tr}_{q^{n+2}/q}:{\rm GF}(q^{n+2})\rightarrow{\rm GF}(q)</math> is the trace function <math>{\rm Tr}_{q^{n+2}/q}(x)=x+x^q+\cdots+x^{q^{n+1}}</math>.


Application

It is found by Xia, Zhou and Giannakis that, difference sets can be used to construct a complex vector codebook that achieves the difficult Welch bound on maximum cross correlation amplitude. The so-constructed codebook also forms the so-called Grassmannian manifold.


References

  • W D Wallis, Combinatorial Designs, Marcel Dekker, 1988. ISBN 0-8247-7942-8.
  • Daniel Zwillinger, CRC Standard Mathematical Tables and Formulae, CRC Press, 2003. ISBN 1-58488-291-3 (page 246)
  • P. Xia, S. Zhou, and G. B. Giannakis, “Achieving the Welch Bound with Difference Sets,” IEEE Transactions on Information Theory, vol. 51, no. 5, pp. 1900-1907, May 2005.

Tags: Uncategorized by admin
No Comments »

Spot the difference

Spot the difference is a name given to a puzzle where two versions of an image are shown side by side, and the player has to find differences between them. Usually, the image on the left is the original, and the image on the right has the alterations.

Spot the difference puzzles are often found in children’s puzzle books, and in newspapers.

When a difference is found, the player usually draws a ring around the area in the second image. There is usually a notice above the puzzle stating how many differences there are to find. The solution is often given on either an answer page (puzzle book) or written upside-down beneath the puzzle (newspaper).

Tags: Uncategorized by admin
No Comments »