Home > Problem Solving, Set Theory > Symmetric difference is associative

Symmetric difference is associative

I’m sure that any mathematics university student came across in the first years of university, in some course of set theory, to proving the fact that the difference symmetric operation is associative:

A \Delta (B \Delta C)= (A\Delta B)\Delta C

where A \Delta B=(A\setminus B) \cup (B\setminus A)=(A\cup B)\setminus (A \cap B).

There are a few ways to do this. First there is the direct way using double inclusion: choose x in the LHS member of the equality and prove that it is also in the RHS member. This is probably the longest method around, but it can be done.

The second method beats the first one at high score. Using characteristic functions, it is very easy to express the characteristic function of each of the LHS or RHS in thems of the characteristic functions of A,B,C, and see that the result is the same.

The third method, mentioned in the following article of Halmos: DOES MATHEMATICS HAVE ELEMENTS? makes fun of both methods described above. It uses again the characteristic function, but in a totally different way. Note that \chi_{A\Delta B}=\chi_A+\chi_B \mod 2, and we are done, since by using the associativity of the integers \mod 2 we find that

\chi_{A\Delta (B\Delta C)}=\chi_{(A\Delta B)\Delta C} \mod 2

and the equality modulo 2 of two functions taking only values 0 and 1 implies their equality.

Categories: Problem Solving, Set Theory Tags: ,
  1. GP
    April 10, 2012 at 10:48 am

    Really nice post! Thanks for the link to Halmos’ article as well!

  1. No trackbacks yet.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s

%d bloggers like this: