With all the commotion in the news lately, a lot of people are saying “Oh, yeah? Prove it!” (often in an angry voice). This helped Occupy Math to select his topic for this week which is about proof and interpretation. In math, a proof is a series of connected logical statements that draw a line between some things that you assume are true and something else that you are trying to demonstrate is true. The Pythagorean theorem is a good example: “If you have a right triangle then the sum of the squares of the lengths of the two shorter sides is equal to the square of the length of the longer side.” You are assuming that you have a right triangle and, if you do, the sometimes helpful fact about the side lengths holds.
There are several ways to prove this fact, including a beautiful picture-based proof taken from the link above. Both pictures have the same four triangles in them — but arranged so that the white areas are displayed differently. Since the identical triangles occupy the same space, so do the white areas, demonstrating the Pythagorean theorem is true.
Sometimes proofs cause real trouble — mostly because people make inappropriate interpretations. Mathematical proof does one — and only one thing; it connects a set of assumptions to one or more conclusions.
Probably the most misused mathematical theorems known are the incompleteness theorems proved by Kurt Gödel. The assumption and the conclusion that the incompleteness theorem connects are as follows. Assumption: suppose that you are in a formal system that, whatever else it may contain, contains simple arithmetic on whole numbers. Conclusion: no matter what set of assumptions you based the formal system on, there are true statements that you cannot prove starting with those assumptions. The proof is subtle, but not too hard once you’ve mastered the idea of proving things. A fairly good interpretation of this result is that, to finish describing a formal system complex enough to support simple arithmetic, you would need an infinite collection of additional assumptions. So far this is mostly clouds of air-castle logic. But what happens when people that don’t understand the limitations of mathematical proofs get ahold of this result?
There are some examples of wild conclusions that are mistakenly thought to follow from the incompleteness theorem. Occupy Math picked one document to examine. Here are some pull quotes from the linked article that seem bizarrely excessive to Occupy Math. The first consists of simply getting the math wrong. The second and third share a common problem: they think the universe is made of mathematics at its most basic level. In fact, math is a descriptive human construct that lets us understand the universe — it does not control the universe in any way.
“Any system of logic or numbers that mathematicians ever came up with will always rest on at least a few unprovable assumptions.” The problem with this is that its wrong about the meaning of the theorem. When the incompleteness theorem was published, the entire mathematical community already knew that any math rested on a set of assumptions. We call these assumptions axioms and, in fact, the idea that you needed assumptions was over 2000 years old at that point in history. What Gödel proved was that the number of assumptions needed in a complete description of a formal system was infinite!
“Gödel’s discovery not only applied to mathematics, but literally all branches of science, logic and human knowledge. It has truly earth-shattering implications.” Occupy Math’s objection to this is that, while much of science does obey laws that are most easily stated as mathematical formulas or algorithms, much of human knowledge does not have this property. Theology, for example, tries to explain the nature of the divine; it therefore worries extensively about what the correct assumptions are. Math works out the implications of assumptions — it does not worry about their correctness — that is a human prerogative.
“Therefore whatever is outside the largest circle is a conscious being.” The author of the linked article is equating a “circle” with a formal system and concluding that the added assumptions that Gödel proved necessary are what is outside of it. The quoted statement finishes a proof that God (or something very similar) exists. The author thinks he has proven the existence of God when a careful reading of the incompleteness theorem shows that what has in fact been demonstrated is that God is an unprovable assumption. This means the author has dropped us right back where theology is now: debating what our original assumptions should be.
Kurt Gödel accidentally, unintentionally trolled the living daylights out of a whole lot of people.
While Occupy Math is not a theologian, he is as sure as he can be (outside of the domain of formal mathematical proof) that the incompleteness theorems do not tell us anything of particular theological significance. They support or impeach no theory about the nature of the divine. People want them to, but that is not a mathematical issue. Let’s move on to another example.
Gödel managed to set to rest any hope that a complete description of math — a final answer — could ever be created. Oddly, this was good news for mathematicians because this means we can never run out of new math. It is like a permanent employment clause in the structure of the universe. Since we never, ever learn from one another’s errors, computer scientists had their own problems with trying to create a universal tool for solving problems — their own version of a final answer.
The no free lunch theorem in computer science says that, on average, no optimizer or search strategy is better than another, assuming you avoid stupid tricks like looking at the same potential solution more than once. Occupy Math has read through the proof and accepts it as correct. When this theorem first appeared, the broad reaction was “This cannot be right!”. This was because it meant that — no matter what your favorite method was — it was not better than other methods (possibly advocated for by your academic nemesis).
This is another beautiful example of an accidental mathematical troll.
Understanding the reason that the no free lunch result really causes almost no problems requires that you need to unpack the innocent looking statement “on average”. If you take a complete space of optimization problems, then almost all of those problems are pretty much random objects with no pattern or structure and, because of that, they are problems that no one would ever want to solve. The set of problems that anyone has any reason to ever care about in the history of the universe is microscopically tiny compared to the set of all problems.
Most people that optimize or solve problems use math, but are not mathematicians, and so really don’t understand the discipline of formal proof. Occupy Math once had to pull one of his students off the ceiling when a report on a paper he submitted demanded that he prove his assumptions (you can’t, it is not possible; see earlier comments about the need for unprovable axioms being a 2000-year-old discovery).
People who design problem-solving strategies start with example problems, try and extract general principles that cover all their examples and, commonly, many other interesting problems, and then publish or apply their findings. The no free lunch theorem sounded like “You idiots are wasting your time.” If you understood the proof, it did not say that at all! People who had always worked on special purpose methods for very, very limited problem domains had needless hysterics about a statement about an astronomically larger problem domain.
In fact the no free lunch theorem implies something helpful. If making a completely general problem-solver is impossible, you can stop trying to do that and instead develop techniques that are specific to particular types of problems. That, in turn, means that you want to explore diverse collections of problem-solving techniques. Occupy Math’s main research focus is to find different ways of representing problems which, in turn, enable different solution techniques. The no free lunch result transformed the search for the ultimate, universal solution into an endless series of manageable but fun quests into the kingdoms of math and the domains of algorithms.
What use is this?
Occupy Math’s first paragraph in today’s post uses politics as a hook. It is time to explain why this is actually relevant. Many of us have had political arguments that went nowhere. Too often we claim the other person is deluded or stupid, but our trip through the nature of mathematical proof implies another, more reasonable hypothesis for the enduring acrimony: the arguing parties have different unprovable assumptions. The only advice that flows from this is that you should be aware of and willing to double-check your own assumptions.
This edition of Occupy Math is in the deep theory end of the ocean — it touches on what math means at its deepest level — and I hope it has been interesting. The take-home lesson is that math means what it means and not what someone wants it to mean. Understanding what math cannot do is pretty important. Occupy Math thinks of it this way: you cannot turn off gravity by proving a theorem about gravity. When people are first introduced to the concept of proof, they find mathematics newly real and could actually worry about an anti-gravity theorem. So, don’t panic, just think about what the theorem actually means. Also, don’t be shy about asking for help. Do you have a mathematical result that upsets or intrigues you? Feel free to comment or tweet!
I hope to see you here again,
University of Guelph,
Department of Mathematics and Statistics