symmetric difference on a finite number of sets


Recall that the symmetric differenceMathworldPlanetmathPlanetmath operationMathworldPlanetmath on sets is commutativePlanetmathPlanetmathPlanetmathPlanetmath and associative. Therefore, one can speak of the symmetric difference of a finite collectionMathworldPlanetmath of sets. More precisely, let A1,A2,,An be sets, not necessarily pairwise distinct. The set

A:=nΔi=1Ai,

the symmetric difference of the sets Ai, is well-defined.

Let A,A1,,An be defined as above. There is a curious property on A:

Proposition 1.

xA iff x belongs to an odd number of the sets Ai.

Before proving this fact, let us make some quick observations. If there are two sets A1,A2, then A=A1ΔA2=(A1A2)(A1A2) (here we are assuming that A1 and A2 are subsets of some universePlanetmathPlanetmath U, so the the complementPlanetmathPlanetmath makes sense). So xA iff xA1A2 or xA1A2 iff xA1 or xA2, which conforms with the statement of the propositionPlanetmathPlanetmathPlanetmath above. If n=3, then A has conjunctive normal formMathworldPlanetmath

A1ΔA2ΔA3=(A1A2A3)(A1A2A3)(A1A2A3)(A1A2A3),

(for a proof of this, see here (http://planetmath.org/ProofOfTheAssociativityOfTheSymmetricDifferenceOperator)). Then xA iff x belongs any one of the four intersectionsMathworldPlanetmathPlanetmath in the CNF above. In each of the four cases, x belongs to an odd number of sets. For example, if xA1A2A3, then xA1.

From the two examples above, it seems that the approach to proving the proposition is to express the symmetric difference in CNF, and this is indeed the case.

To facilitate with the proof, let us introduce some notations. Start with sets A1,,An, which are assumed to be subsets of some set U. Let I and C be the identityPlanetmathPlanetmathPlanetmathPlanetmathPlanetmath and complementation operations taking AU to A and A respectively. Let 𝐧 be the set {1,,n}. Let Fn be the set of all functions from 𝐧 into {I,C}. For every fFn, we write fi for f(i). Finally, we partition Fn into two sets En and On, where En (On) consists of all functions f such that |f-1(I)| is even (odd), respectively.

The proposition can now be restated as a single equation:

nΔi=1Ai=fOni=1nfi(Ai)
Proof.

We prove this equation by inductionMathworldPlanetmath on n, for n2. The case when n=2 is already discussed above. Now,

n+1Δi=1Ai=(nΔi=1Ai)ΔAn+1=XY,

where

X=(nΔi=1Ai)An+1  and  Y=An+1(nΔi=1Ai).

By the induction hypothesis,

nΔi=1Ai=fOni=1nfi(Ai),

so that

X=(fOni=1nfi(Ai))An+1=fOni=1n+1f^i(Ai),

where f^:(𝐧+𝟏){I,C} is given by f^i=fi if i𝐧, and f^n+1=C.

Now, for any xU, x is either in an even number of Ai’s, or an odd number of Ai’s. This means that

xfEni=1nfi(Ai)  or  xfOni=1nfi(Ai)

and never both. This shows that U can be partitioned into the two sets above. In other words,

(fOni=1nfi(Ai))=fEni=1nfi(Ai).

As a result,

Y=An+1(fEni=1nfi(Ai))=fEni=1n+1f¯i(Ai),

where f¯:(𝐧+𝟏){I,C} is given by f¯i=fi if i𝐧, and f^n+1=I.

Every function gOn+1 can be obtained from a function in fFn so that gi=fi for i𝐧. If fOn, then gn+1=C, and if fEn, then gn+1=I. This means that On+1 can be partitioned into two sets O and E, where O (or E) contains all functions whose restrictionPlanetmathPlanetmath to 𝐧 are in On (or En).

Therefore,

gOn+1i=1n+1gi(Ai) = (gOi=1n+1gi(Ai))(gEi=1n+1gi(Ai))
= (fOni=1n+1f^i(Ai))(fEni=1n+1f¯i(Ai))
= XY=n+1Δi=1Ai.

Title symmetric difference on a finite number of sets
Canonical name SymmetricDifferenceOnAFiniteNumberOfSets
Date of creation 2013-03-22 18:02:24
Last modified on 2013-03-22 18:02:24
Owner CWoo (3771)
Last modified by CWoo (3771)
Numerical id 8
Author CWoo (3771)
Entry type Derivation
Classification msc 03E20