Tuesday, March 25, 2014

Impossibility theorems, a counterexample (the seven bridges problem)

In mathematics and physics there are some results called no-go theorems, or impossibility theorems. To name just a few: Euler's solution to the problem of the seven bridges of Königsberg, Gödel's incompleteness theorems, Bell's theorem, Kochen-Specker theorem, Penrose and Hawking's singularity theorems.

Research is an adventurous activity - you can spend years on researching a dead end, or you can stumble by luck upon something worthy without even knowing (for example, the discovery by Penzias and Wilson of the cosmic microwave background radiation). To avoid spending years looking in the wrong places, researchers use various guiding lines. Impossibility results are some of them, which are by far the most reliable. Other guidelines are following the trends of the moment (also dictated by the need to publish and receive citations), following the opinions of authorities in the field, reading only what they read etc. I personally consider misguided the idea of interpreting the results and filtering what you read and research by using the eyes of the authorities, no matter who they are. But it is understandable that they may seem the best we have, and that anyway the "mainstream" follows them, so if you want to fit in, you have to do the same.

What about the impossibility theorems, aren't they more objective than just fashion trends dictated by authority figures? Of course they are. However, they apply to specific situations, contained in the hypothesis of the theorems. Moreover, they rely on a mathematical model of reality, and not on reality itself. While I think that the physical world is isomorphic to a mathematical model, this doesn't mean that it is isomorphic to the models we use.

I will give just a simple example. Remember the problem of the Seven Bridges of Königsberg. It was solved negatively by Euler in 1735, and led to graph theory and anticipated the idea of topology. The problem is to walk through the city by crossing each bridge once and only once. Here is a map, which is of course an idealization:

Euler reduced the problem to an even more idealized one. He denoted the shores and the islands by vertices, and the bridges by edges, and obtained probably the first graph in the history:


Euler was then able to show immediately that there is no way to walk and cross each of the bridges once and only once (without jumping like Mario or swimming in the river, or being teleported!). The reason is that an even number of edges have to meet at the vertices which are not those where you start or end the trip. But there are no such vertices in the above graph, so all four have to be starting or ending vertices. But at most two vertices can be used to start and end, so the problem has negative answer.

This illustrates the main point of this article. The problem has a negative answer, but this doesn't mean that in reality the answer is negative too. The mathematical model is an idealization, which forgets one thing: that the Pregel river has a spring, a source of origin. If we add the spring to the map, we obtain a different problem:


This problem has a simple solution, which is obtained by "going back to the origin":


This is "thinking outside the box", literally, because you have to go outside the original picture box. I came up with this solution years ago, when I was in school and read about Euler's solution. Of course, it doesn't contradict Euler's theorem, because the resulting graph is different than the one he considered, as we can see below:


Hence, Euler's theorem itself tells us how to solve the problem associated with this graph. The problem is solved by the very theorem which one considers to forbid the existence of a solution.

The main point of this simple example is that even in simple cases we don't actually know the true settings in which we apply the no-go theorems, or we ignore them to idealize the problem. We are applying the no-go theorems in the dark, so perhaps, rather than being guidelines, they are blocking our access to the real solutions of the real problems. While most researchers try to avoid being in contradiction with impossibility theorems, maybe it is good to reopen closed cases from time to time.