## Friday, November 30, 2007

### Should you go shopping?

This is a simple proof that you shouldn't. You cannot find anything useful in shops. And I am going to prove you this right now. The proof is by induction. I am going to prove that in any group of shops no matter how large, there is nothing interesting or useful.
Lets start with n=0 this is with the empty set. There are no shops in it so there is nothing interesting in them. Now lets suppose that we proved this for n=k. We just need to prove it now for n=k+1.
Lets therefore look at a random group of k+1 shops - {a1, a2, a3, a4 ....a(K+1)}. It can be viewed as a union of two groups - {a1,...,ak} and {a2,...,a(K+1)}. Since they both have the some number of shops in them - k, we know from our assumption that there is nothing interesting or useful in any shop in both of them. And since we don't get anything new when we unite the groups there is nothing interesting in the union also. And this completes the proof.

Now lets see another example. Lets suppose you have a random group of people. Is it true that all of them male or all of them female? In other words is it possible by choosing people randomly to get a group where there are both men and women? By now you probably think that I am crazy since I actually asked such a question, right?
Well lets see what math says about this. For n=1 we have a group with one human in it - either a a man or a woman obviously. Now lets suppose that we proved for n=k that any random group of size k has only men or only women. As in the previous example we can now look on a K+1 group as a union of two groups. And since we know that any group of the size k contains only men or only women they both contain only men or only women. Because a2 belongs to both groups and naturally has only one gender :) all the rest have to be the same gender - that is either male of female. And this completes the proof.

So now, after you saw this what do you think about mathematics?

Update: I guess I should have written this part in the first place but anyway: These proofs are wrong. It can be seen easily - just by simple example. In fact all the idea behind those proofs is that induction must be used with great care - or you might proof something that is plain wrong. A good way to check yourself is to try and prove your statement for n=3 and n=4. In the examples here there was no proof whatsoever. Induction is a very valuable and powerful tool but it is meant to be used for proving that some statement is correct for all n, when you know that it is correct for at least some n, and not for proving something you know that is not correct.