11
$\begingroup$

In mathematics there are often two ways of answering a question,

  • Lots of thinking and little working,

  • Little thinking and lots of working.

I was wondering what the most extreme cases of this would be? Questions where the "usual" answer is just to plough through the working and hope everything turns out all right, but a much more subtle solution exists (and ideally this subtle solution would point out what makes the question "tick", as it were).

For example,

Question: Prove that the symmetric difference operation is associative.

The symmetric difference of two sets, $S \triangle T$, is defined to be $(S\cup T)\setminus (S \cap T)$. Now, one could simply plough through the working, but the working is tedious and there is a "trick" half way through it. However, a much more subtle solution exists. It requires a bit of setting-up, but is overall much neater.

Proof: The idea is that $S\triangle T$ "looks like" addition mod $2$. To see this, notice that,

  • If $x\in S$, $x\in T$ then $x\not\in S\triangle T$, which corresponds to $1+1=0 \text{ mod }2$

  • If $x\in S$, $x\not\in T$ then $x\in S\triangle T$, which corresponds to $1+0=1\text{ mod }2$

  • If $x\not\in S$, $x\in T$ then $x\in S\triangle T$, which corresponds to $0+1=1\text{ mod }2$

  • If $x\not\in S$, $x\not\in T$ then $x\not\in S\triangle T$, which corresponds to $0+0=0\text{ mod }2$

This means that showing $(S\triangle T)\triangle U=S\triangle (T\triangle U)$ now comes down to showing that addition mod $2$ is associative. And it is, which is easily checked. So we're done.

  • 0
    I wasn't sure how to tag this question - I went for the (big-list) tag, but this tag tells you to put another one with it, and I can't find another relevant one. As I didn't really want to create a "(broad-question)" or something tag, I just left it with the (big list) one...2012-01-20
  • 1
    "comes down to showing that addition mod 2 is associative. And it is, which is easily checked. So we're done." -- Sorry, I fail to understand how addition mod 2 being associative is any easier to check than the associativity of $\Delta$.2012-01-20
  • 1
    Last 10 digits of 50! Could be worked out the hard way, or it could be noticed that $5^{10}.2^{10}|50!$ so they are 0s.2012-01-20
  • 0
    @Srivatsan: Well...how would you prove the associativity of $\triangle$? When I do this with my second years they invariably plough through the question using the usual set-theoretic means and it takes them a page, if not more...2012-01-20
  • 0
    My point was not that associativity of $\Delta$ is easy to establish. It is also not that the connection between $\Delta$ and XOR (addition modulo 2) is not enlightening. (I acknowledge that the said connection is a very useful one.) My previous comment only said that I am skeptical that the associativity of XOR is any easier to prove than the associativity of $\Delta$.2012-01-20
  • 1
    @Srivatsan: Well, there are $8$ cases to prove...less if you factor in commutativity...or, we've reduced the question to something we known stuff about. I mean, if you've ever heard of a group, or have even just come across modular arithmetic at some point then you don't need to do anything...2012-01-20
  • 3
    And now you are simply waving your hands. At some stage, you need to _verify associativity_ to show that integers modulo 2 form an additive abelian group. I still don't see how that work got reduced.2012-01-20
  • 2
    @Srivatsan: this proof of associativity of the symmetric difference was addressed by Halmos in his article "Does mathematics have elements?" available here: http://www.math.uh.edu/~tomforde/Articles/Elements-Halmos.pdf see pages 3-4.2012-01-20
  • 0
    @Srivatsan: I fail to see how reducing a problem to something already known counts as "hand waving". Any anyway, as I said, you have $8$ cases to verify, which takes all of 30 second to do...that isn't hand waving either!2012-01-23

4 Answers 4