When you met the late Armen Alchian on the street, he used to greet you not with “Hello” or “How ya doin’?”, but with “What did you learn today?” Today I learned that there are contexts in which the most ludicrous reasoning is guaranteed to lead you to a correct conclusion. This is too cool not to share.
But first a little context. The first part is a little less cool, but it’s still fun and it will only take a minute.
First, I have to tell you what a tree is. A tree is something that has a root, and then either zero or two branches growing out of that root, and then either zero or two branches (a “left branch” and a “right branch”) growing out of each branch end, and then either zero or two branches growing out of each of those branch ends, and so on. Here are some trees. (The little red dots are the branch ends and the big black dot is the root; these trees grow upside down.)
A pair of trees is, as you might guess, two trees — a first and a second.
There are infinitely many trees, and infinitely many pairs of trees, and purely abstract considerations tell us that there’s got to be a one-one correspondence between these two infinities. But what if we ask for a simple, easily describable one-one correspondence? Well, here’s an attempt: Starting with a pair of trees, you can create a single tree by creating a root with two branches, and then sticking the two trees from the pair onto the ends of the two branches. Like so:
That almost works. That is, it’s almost a one-one correspondence, except for one little detail: There’s one tree that’s not matched with any pair, namely the stupid tree that has just a root and no branches at all.
So this didn’t work. And it turns out that you can prove that nothing works. There is (provably) no simple one-one correspondence between pairs of trees on the one hand, and single trees on the other. (Of course to make this precise, one ought to specify what “simple” means, but I’ll omit the technicalities here.)
Nor is there any simple one-one correspondence between triples of trees on the one hand and single trees on the other, or between quadruples of trees on the one hand and single trees on the other, and likewise for quadruples, quintuples and sextuples of trees. The first surprise (though this not yet the really cool part) is that there is a simple one-one correspondence between septuples of trees on the one hand and single trees on the other.
That correspondence, discovered by the mathematician Andreas Blass, is just a hair too much of a distraction to include here in the post, so I’ve put it in a link consisting of an extended quote from Blass’s paper.
This is mildly surprising. What’s really cool is the way Blass (building on an idea of Bill Lawvere) discovered it. And what’s really really cool is the recent proof by Marcelo Fiore and Tom Leinster that this crazy method pretty much always works.
What’s the crazy method? It starts with our failed attempt to construct a simple bijection between pairs of trees and trees. We saw that there was one tree left over (namely the stupid tree with no branches). Let’s record this fact by writing down an equation:
Here T represents the set of all trees, T2 represents the set of all pairs of trees, the equal sign stands for a simple one-one correspondence, and the +1 means that if you try to set up a simple one-one correspondence, you’ll have one tree left over.
Now comes the cool part. Obviously, T is not a number, and this “equation” is in no sense an actual equation. But let’s pretend. Let’s act like T is a number, manipulate the equation, and see what we can learn.
Well, what we’ve got here is a quadratic equation, and somewhere in the back of most of our minds is the quadratic formula that allows us to solve this equation. One solution is:
Okay, that’s real nonsense. Taken literally, it says that the set of trees is equal to an irrational imaginary number. There’s no possible sense in which this can be true, because there’s no possible sense in which it can even be meaningful. But let’s not let that stop us. Instead, let’s, oh, raise each side of the equation to the sixth power.
If you take that irrational imaginary number and multiply it by itself 6 times, you’ll get 1. (Try it!) So our equation now becomes
This at least seems to make sense; given the rules we’ve adopted, it says that there is a simple one-one correspondence between the set of sextuples of trees on the one hand, and the single tree with no branches on the other. Meaningful, yes, but also clearly false because there are (obviously) an infinite number of sextuples of trees, and only one tree-with-no-branches, and the number one is not equal to infinity, even by the standards of precision allowable in empirical economics, let alone pure math.
But let’s not let that stop us. Let’s, oh, multiply each side of the equation by T:
In other words, there is a simple one-one correspondence between septuples of trees on the one hand, and individual trees on the other. This one happens to be both meaningful and true — it’s exactly the theorem of Andreas Blass that we met earlier in this post.
Now that looks like an odd coincidence. We started with a weird pseudo-equation, manipulated it as if it were meaningful, transformed it into a series of statements that were either meaningless or clearly false, and out popped something that happened to be true. What Blass essentially proved (and Fiore and Leinster generalized) is, in effect, is that this is no coincidence. More specifically, they’ve proved in a very broad context that if you manipulate this kind of equation, pretending that sets are numbers and not letting yourself get ruffled by the illegitimacy of everything you’re doing, the end result is sure to be either a) obviously false or b) true. The equation T7=T is not obviously false. Therefore it’s true.
And you can use the same method over and over. If you allow your trees to have single instead of dual branches, it’s not hard to “justify” the equation T = 1 + T + T2. A little manipulation then leads you to T = T5, so for this new kind of tree, it’s the quintuples, not the septuples that are one-one correspondence with individual trees. That’s not obviously true, but it’s also not obviously false, so it must be true.
I love this stuff.