Set difference

Characteristic Function of a Set

Suppose that

A

is a set, then it's characteristic function is defined as

χ_{A} (x) = {\begin{cases} 1 & , if x \in A \\ 0 & , if x \notin A \end{cases}

Set Equality through the Characteristic

A = B ⟺ χ_{A} = χ_{B}

Symmetric Difference

Suppose

A, B

are two sets, then we define

A Δ B := (A ∖ B) \cup (B ∖ A)

using the set difference

Symmetric Difference Characterization

Suppose that

A, B

are sets then

x \notin A Δ B ⟺ (x \in A \cap B \lor (x \notin A \land x \notin B))

Characteristic Version of Symmetric Difference

χ_{A Δ B} = χ_{A} \oplus χ_{B}

Symmetric Difference is Associative

For any three sets

A, B, C

we have

(A Δ B) Δ C = A Δ (B Δ C)

\begin{aligned} χ_{(A Δ B) Δ C} & = (χ_{A} \oplus χ_{B}) \oplus χ_{C} \\ = χ_{A} \oplus (χ_{B} \oplus χ_{C}) \\ = χ_{A Δ (B Δ C)} \end{aligned}

therefore

(A Δ B) Δ C = A Δ (B Δ C)

Characteristic Version of Symmetric Difference Generalized

Let

n \in N_{2}

, prove that for any collection of sets

A_{1}, A_{2}, \dots, A_{n}

we have that

χ_{A_{1} Δ A_{2} Δ \dots Δ A_{n}} = χ_{A_{1}} \oplus χ_{A_{2}} \oplus \dots \oplus χ_{A_{n}}

Holds by induction using previous facts to help with the induction step.

Element is in the Fold of Symmetric Differences iff it is an an odd Number of Sets

Let

n \in N_{2}

, prove that for any collection of sets

A_{1}, A_{2}, \dots, A_{n}

the set

A_{1} Δ A_{2} Δ \dots Δ A_{n}

contains exactly those elements

x

which are present in an odd number of the sets

Recall this property of the exclusive or therefore combining this with our previous proposition the function on the right hand side will only evaluate to true iff

χ_{A_{i}} (x) = 1

for an odd number of

i

's therefore we've proved the statement true.