You ever really thought about numbers? How weird is arithmetic? Numbers are purely in our minds; there is nothing in the world that corresponds to “7”—we just made it up. And when we stick it back to the world, it works. Every freaking time.
It’s not easy to see how truly fantastic it is that we can think about numbers and other mathematical objects and prove things about them. Not just say that they’re likely, but prove. Beyond a shadow of a doubt.
From 1956 to 1986, Martin Gardner wrote a column called “Mathematical Games” in Scientific American. If I found myself in my high school library, I often went to the magazine rack and browsed Sci Am. And usually, I’d check out Gardner’s column.
To be honest, I don’t remember very many of the columns, but I do remember that I read many of them. And one of them changed my life. It was my first experience of complete wonder—awe perhaps—at a mathematical thought. I have never re-read the column, because I don’t want to mess with the memory. I don’t really care if what I remember is accurate; I remember what I felt. And I’m going to try to bring some of that back today.
The idea is a simple one. Mathematical propositions are either true or false. 2+2=4 or it doesn’t. There is no third choice. Sometimes we don’t know if the proposition is true or false, but we always know that it is one or the other. The second part of the idea is that logic is consistent. If you start with a true proposition, and apply valid rules of math and logic to it, you’ll always get another true proposition. So, if 2+2=4, then we are guaranteed that 2+2+N=4+N for any number N. This is nice, but hardly awe-inspiring.
What this suggests is that if I don’t know if a proposition is true or false, and I apply valid rules to it until I get something that I know to be false turns up, I can conclude that the proposition was false in the first place. For example, suppose I tell you that I know the biggest whole number in the universe, and I call it N. You might reply, “Hold on, John. Suppose I add one to that number.” Suddenly my heart sinks: if N is a number, so is N+1. And N+1>N. Oh crap. I guess N isn’t the biggest number. But you, being the clever sort, recognize that the argument is perfectly general. The problem isn’t that I don’t know the biggest whole number, but that every possible candidate for the biggest whole number meets exactly the same objection. Therefore, any claim that there is a biggest whole number creates a contradiction. There is no biggest whole number!
What I love about this example is that even a small child can grasp it.
As I recall, Gardner spent a good portion of the article talking about the general structure of the argument, and used its Latin name reductio ad absurdum. In English, we usually say “proof by contradiction”. The strategy is simple. If you want to prove a proposition is true, you assume that it’s false and then use normal logic and math to create a false statement (often a direct contradiction of the assumption). You have shown that your assumption is incorrect, and that the proposition is true. So when I assume that there is a biggest number, I create a contradiction, proving that there is no biggest number.
Think about it for a second. Just by using a tiny bit of logic, you are able to prove that there are an infinite number of whole numbers. Our little finite brains demonstrate beyond a shadow of a doubt a fact about an uncountably large collection of numbers. This is big.
I’m not going to do any harder proofs today. I don’t think it’s necessary (but it is fun). In the Gardner article, he proved that there is an infinite number of prime numbers. And that took my breath away. The power of the human mind, applying itself to simple little problems is absolutely fantastic. I can’t remember if Gardner proved that √2 cannot be written as a fraction (for those who remember their school math, √2 is irrational); but that’s also a common proof and I might have learned it later.
If you’re moved at all, do a google search for proof by contradiction. Or not. Just enjoy what your mind has done today, and what you can do with it whenever you want.