What are Symmetric Differences made of ?

by Arjun Jain

Here, I extend the notion of symmetric differences of 2 sets to a finite family of sets and present some results regarding a unique representation of symmetric differences. The style of the article follows Paul Halmos’s advocacy of using “words more than numbers” in mathematical exposition (Paul R. Halmos, I want to be a Mathematician, Springer- Verlag, 1985). Also, provided are illustrations, which apart from reinforcing the main results graphically, also display the aesthetic beauty of symmetric differences and lead into a fascinating question related to rotationally symmetric venn diagrams. Although this is my own work, I have found that, similar theorems do exist in literature (Chi Woo, Symmetric difference on a finite number of sets, (version 5), PlanetMath.org).

1. Symmetric Differences

The symmetric difference of two sets A and B is specified as {A\Delta B=(A\setminus B)\cup (B\setminus A)}.

1.1. Symmetric differences are commutative, as can be seen by interchanging A and B in the definition.

1.2. If all sets considered have the same parent set, then {A\Delta B=(A\cap B')\cup (A'\cap B)}. Similarly, {(A\Delta B)\Delta C}, on simplification, is equal to {(A\cap B'\cap C')\cup (A'\cap B\cap C')\cup (A'\cap B'\cap C)\cup (A\cap B\cap C)}. From subsection 1.1, as {\Delta} is commutative, {(A\Delta B)\Delta C=C\Delta (A\Delta B)} . Also, as the simplified form of {(A\Delta B)\Delta C} is symmetric with respect to A, B and C, therefore {C\Delta (A\Delta B)=A\Delta (B\Delta C)} and so {\Delta} is associative. Note that now, {A\Delta (B\Delta C)} can be written as {A\Delta B\Delta C}, i.e., without brackets.

1.3. The power set of a set X, P(X), with {\Delta} as addition and {\cap} as multiplication is a ring with identity as:

a) From subsection 1.1, {\Delta} is commutative.

b) From subsection 1.2, {\Delta} is associative.

c) {\varnothing} is the additive identity, as for any subset of X, say A, {A\Delta\varnothing=A}.

d) Also, each set is its own additive inverse as {A\Delta A=\varnothing}.

e) {\cap} is associative and commutative.

f) The set X is the multiplicative identity, as {A\cap X=A} for any A in P(X).

g) {\cap} is distributive over {\Delta}.

The proof of g) is as follows: {A\cap (B\Delta C)} {=A\cap ((B\cap C')\cup (C\cap B'))} {=(A\cap (B\cap C'))\cup (A\cap (C\cap B'))} {=((A\cap B)\cap C')\cup ((A\cap C)\cap B')} {=((A\cap B)\cap (C'\cup A'))\cup ((A\cap C)\cap (B'\cup A'))} {=((A\cap B)\cap (C\cap A)')\cup ((A\cap C)\cap (B\cap A)')} {=(A\cap B)\Delta (A\cap C)}.

1.4. The notion of symmetric differences is not restricted to only 2 or 3 sets. In fact, subsections 1.1 and 1.2 permit us to speak of the symmetric difference of a finite family of sets. As an example, given the symmetric difference of 3 sets, as in subsection 1.2, we can form the symmetric difference of 4 sets, by taking the symmetric difference of a new set, say D, with the given symmetric difference of 3 sets. This would be written as {A\Delta B\Delta C\Delta D}. Therefore, given a family of sets whose terms are, say {A_1,A_2,\dotsc,A_{n-1},A_n} , the symmetric difference of the family can be written as {A_1\Delta A_2\dotsc A_{n-1}\Delta A_n}, without any brackets as such. Also, the order in which the symmetric differences are taken does not matter, i.e., rearranging the brackets, if any, does not change the value.

1.5. We now set up some notation, terminology, and related basic facts:

i) Let r and n be natural numbers with {0\leq r<n} and {n\geq 2}. For {r\geq1}, an r-dashed intersection of a family of sets {\{ A_i\}} (where r varies over natural numbers {\leq} n and {\geq 1}), is {A'_1\cap A'_2\dotsc\cap A'_{r-1}\cap A'_r\cap A_{r+1}\cap A_{r+2}\dotsc\cap A_{n-1}\cap A_n}, where { '} is used to indicate the complement of the set, in a universal set X. The indices can be permuted to give different r-dashed intersections of the given family. The 0-dashed intersection of a family is simply the intersection of all its terms.

ii) The symmetric difference of a family whose terms are n given sets is abbreviated as The symmetric difference of n sets. Similarly, An r-dashed intersection of a family whose terms are n given sets is abbreviated as an r-dashed intersection of n sets.

iii) Note that any two different r-dashed intersections of the same family(if all constituent sets are distinct) are disjoint.

iv) As observed in subsection 1.2 :

a) The symmetric difference of 2 sets is the union of all 1-dashed intersections of the 2 given sets.

b) The symmetric difference of 3 sets is the union of all 0-dashed and 2-dashed intersections of the 3 given sets.

Theorem 1.6: Let {n\geq 2}.

I) If n is even, the symmetric difference of n sets, not necessarily distinct, is the union of all r-dashed intersections of the n given sets, where r varies over odd numbers less than n.

II) If n is odd, the symmetric difference of n sets, not necessarily distinct, is the union of all r-dashed intersections of the n given sets, where r varies over even numbers less than n.

III) The number of sets, not necessarily distinct or non empty, in the representation of the symmetric difference of n sets is {2^{n-1}}. In particular, the number of sets representing the symmetric difference of n sets in an n-Venn diagram( According to Stan Wagon and Peter Webb, Venn symmetry and prime numbers: a seductive proof revisited, American Mathematical Monthly 115 (2008), 645 – 648 , an n-Venn diagram is a Venn diagram on n sets, which is defined to be a collection of n Jordan curves {C_1,C_2,\dotsc ,C_n} in the plane such that any two intersect in finitely many points and each of the {2^n} sets of the form {\cap C_i ^{\epsilon _i}} is nonempty and connected, where {\epsilon _i} is one of “interior” or “exterior”. Thus the Venn regions are all bounded except for the region exterior to all curves; each bounded region is the interior of a Jordan curve. An n-Venn diagram is symmetric if each curve {C_i} is {\rho ^i (C_1)}, where {\rho} is a rotation of order n about some center. The universally familiar three-circle Venn diagram is symmetric, as is the one on two sets using two circles. According to Lewis, Clarence Irving (1918). A Survey of Symbolic Logic. Berkeley: University of California Press. p. 157., the “principle of these diagrams is that classes [or sets] be represented by regions in such relation to one another that all the possible logical relations of these classes can be indicated in the same diagram. That is, the diagram initially leaves room for any possible relation of the classes, and the actual or given relation, can then be specified by indicating that some particular region is null or is not-null”.) is {2^{n-1}}.

In short, statement I) will be expressed as: the symmetric difference of n sets, where n is odd is the union of all evenly-dashed intersections of the n given sets. Similarly, statement II) will be expressed as the symmetric difference of n sets, where n is even is the union of all oddly-dashed intersections of the n given sets.

Joint Proof of statements I) and II):

For all {n\in\mathbb{N}} and {n\geq 1}, let {S_n} denote the following two phrases: a) Statement I) for the symmetric difference of 2n sets b) Statement II) for the symmetric difference of 2n+1 sets.  {S_n} is said to be true when both a) and b) corresponding to {S_n} are true.

From part iv) of subsection 1.5, {S_1} is true. Suppose that {S_n} is true. According to subsection 1.4, rearranging the brackets in the expression for the symmetric difference of 2(n+1) sets does not change its value. Thus, the symmetric difference of 2(n+1) sets can be written as the symmetric difference of the first 2n+1 sets and the (2n+2)th set. This is equal to (((2n+2)th set{)'\cap}(union of all evenly-dashed intersections of first 2n+1 sets)){\cup}((union of all evenly-dashed intersections of first 2n+1 sets{)'\cap}((2n+2)th set)). The next step is explained in the NOTE below. Now by De Morgan’s Laws, this is equal to (((2n+2)th set{)')\cap}(union of all evenly-dashed intersections of first 2n+1 sets){\cup}((intersection of all oddly-dashed unions of first 2n+1 sets){\cap}((2n+2)th set))). So, this is equal to (union of all oddly-dashed intersections of 2(n+1) sets where each intersection contains ((2n+2)th set{)'}) {\cup} (union of all oddly-dashed intersections of 2(n+1) sets where each intersection contains ((2n+2)th set)). This is equal to the union of all oddly-dashed intersections of 2(n+1) sets. Similarly, we can show that the symmetric difference of 2(n+1)+1 sets is the union of all evenly-dashed intersections of 2(n+1)+1 sets. Therefore {S_{n+1}} is true. Therefore, as {S_1} is true, and if {S_n} is true, then {S_{n+1}} is also true; by induction {S_n} is true for all n.

NOTE:

(union of all evenly-dashed intersections of 2n+1 sets{)'} =(intersection of all (evenly-dashed intersections of 2n+1 sets{)')}. Consider a typical evenly dashed intersection of 2n+1 sets, say {A'_1\cap A'_2\dotsc\cap A'_{2r-1}\cap A'_{2r}\cap A_{2r+1}\cap A_{2r+2}\dotsc\cap A_{2n}\cap A_{2n+1}}, where {0\leq r\leq n}. Then {(A'_1\cap A'_2\dotsc\cap A'_{2r-1}\cap A'_{2r}\cap A_{2r+1}\cap A_{2r+2}\dotsc\cap A_{2n}\cap A_{2n+1})'} = {A_1\cup A_2\dotsc\cup A_{2r-1}\cup A_{2r}\cup A'_{2r+1}\cup A'_{2r+2}\dotsc\cup A'_{2n}\cup A'_{2n+1}}. This will be referred to as a (2(n-r)+1)-dashed union of 2n+1 sets. As {0\leq (n-r)\leq n}, all oddly-dashed unions of 2n+1 sets are produced by varying r. Therefore, (intersection of all (evenly-dashed intersections of 2n+1 sets{)')} = (intersection of all oddly-dashed unions of 2n+1 sets).

Proof of statement III) using construction in the joint proof of statements I) and II) and elementary combinatorics identities:

If n is odd, the number of evenly-dashed intersections of the n sets (not necessarily distinct or disjoint), occuring in the representation, is equal to {\displaystyle\sum_{r=even\, numbers\,\leq n}\ {n\choose r}=2^{n-1}}. Similarly, if n is even, the number of oddly-dashed intersections of the n sets (not necessarily distinct or disjoint), occuring in the representation, is equal to {\displaystyle\sum_{r=odd\, numbers\,\leq n}\ {n\choose r}=2^{n-1}}. The elementary identities used here can be obtained by substituting 1 and -1 in place of x in the binomial expansion of {(1-x)^n}.

Alternate proof of III:

When n sets intersect, the number of regions, excluding the space outside the union of the sets, formed in an n-Venn diagram is {2^n-1}. If the number of regions formed by the symmetric difference of n-1 sets is {p_{n-1}}, then the number of regions formed by the symmetric difference of n sets is maximum, when the nth set intersects all the {2^{n-1}} regions formed by the first n-1 sets, along with the {p_{n-1}} regions of the symmetric difference and is still left with some elements which are not in any of the other n-1 sets. As the symmetric difference of 2 sets does not contain their intersection, therefore the symmetric difference of n sets, will not contain {p_{n-1}} of the {2^{n-1}-1} regions formed by the intersection of n-1 sets. So, the number of regions formed by the symmetric difference of n sets, {p_n=(p_{n-1})+(2^{n-1}-1-p_{n-1})+1=2^{n-1}}.

An illustration of the above proved theorem is shown below.

Note: The diagrams on the left are ordinary Venn diagrams with pink, tan, blue, green and cyan used for the constituent sets. The Venn diagrams on the right represent the corresponding symmetric differences.

Colour key for diagrams on the Right:

0-dashed intersections: blue,

1-dashed intersections: green,

2-dashed intersections: yellow,

3-dashed intersections: red,

4-dashed intersections: white.

Image

Image

Note that the more aesthetically pleasing, rotationally symmetric diagram for 4 sets does not exist, due to the following: Rotationally symmetric Venn diagrams for n sets exist, if and only if n is prime.(David Henderson, Venn diagrams for more than four classes, Amer. Math. Monthly, 70, 1963, 425-426; Stan Wagon and Peter Webb, Venn symmetry and prime numbers: a seductive proof revisited, American Mathematical Monthly 115 (2008), 645 – 648 }; Jerry Griggs, Charles Killian, and Carla Savage, Venn diagrams and symmetric chain decompositions in the Boolean Lattice, Electronic Journal of Combinatorics, Volume 11, January 2, 2004.)

Advertisements