# symmetric difference on a finite number of sets

## Primary tabs

Type of Math Object:
Derivation
Major Section:
Reference
Groups audience:

## Mathematics Subject Classification

### SymDiff = +

Just a comment, as I spent some time on this once, but it may ease things at some point to observe that the symmetric difference is just the natural field or ring operation usually signified by "+", and so it inherits all of the usual properties of that. JA

### Re: SymDiff = +

Yes I realize that. But I am not sure how that would help in proving the proposition...

### Re: SymDiff = +

There's a discussion in this old application paper of mine:

http://www.mywikibiz.com/Directory:Jon_Awbrey/Papers/Differential_Logic_...

Let B = {0, 1}

Let x_i for i = 1 to n be the characteristic functions
of the sets A_i, i = 1 to n, all subsets of universe X.

Consider the "factoring" of a proposition f : X -> B,
where f is 1 of the 2^(2^n) functions based on the x_i,
as the composite function f*(c(x)), where c : X -> B^n
is the "coding" of each x in X as an n-bit string in B^n,
and where f* is the mapping of these code n-tuples into B.

............ X ... f ... B
............. o-------->o
.............. \ ..... ^
{x_1, ..., x_n) \ ... / f*
................ \ . /
................. v /
.................. o
................. B^n

There are 2^n linear functions h : B^n -> B,
with (n choose k) linear functions of rank k,
for k = 0 to n.

These linear functions are the same things as the
symmmetric differences of rank k, for k = 0 to n.

A typical one can be written as a k-fold sum,
x_i_1 + x_1_2 + ... x_i_(k-1) + x_i_k, where
"+" signifies the GF(2) addition, also known
as exclusive disjunction (XOR) or Sym.Diff.

I hope I got this right -- it's been a while.
(You may have to insert leading spaces into
the diagram in order to make it display right.)