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.
So we also have T^8 = T^2 etc (for bifurcated trees). Set of 8 trees maps onto the set of 2 trees. And so for every set and 7 fewer trees.
Harold; yes, though this is easy. A set of eight trees is the same thing as a set of seven trees plus a tree. The set of seven trees corresponds (under the original Blass correspondence) to a single tree, so the set of eight trees corresponds to a single tree plus a tree, i.e. a pair of trees.
“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.”
I think I might be missing something important. Isn’t every proposition either true or false? Therefore, wouldn’t all the algebraic manipulation be superfluous? It seems like pure coincidence that the specific equation proposed turned out to be meaningful, especially in light of a rule that any nonsensical mathematical proposition is either true or false.
For example: Maybe the following equation proves the unified field theory… a^6 – 9 = ([30 + E]mc)^(e* pi)
That statement is clearly either perfectly true or utter nonsense. We could apply what we know about physics to determine which is the case, but isn’t that just an extra, unnecessary step?
RPLong: Surely every statement is either false or true. But not every statement is either obviously false or true.
“There are exactly 10^89 elementary particles in the Universe” is not obviously false, but that doesn’t mean it has to be true.
I must be missing something. I think there is an easily describable one-to-one correspondence between trees and pairs of trees. One of the following statements must be false. Which one?
1. The set of trees is a countably infinite set.
2. The set of trees can be arranged in a one-to-one correspondence with the natural numbers (which, of course, proves 1.). I think this can be done in the order 1. Single dot; 2. simplest three dot tree; 3. Use 2 and add a branch to the left dot; 4. Use two and add a branch to the right dot; etc. By etc. I mean start with 3. and add all possible single extra branches. Then start with 4. and add all possible single extra branches. Then start with 5 … I don’t believe this misses any trees (I could be wrong) although I believe it creates duplicates. If you encounter a duplicate of a previous tree, just skip it.
3. The set of pairs of trees can be arranged in one-to-one correspondence with trees as described by the original post (except there is no match for the single dot tree). Line up the pairs below the single trees, but they start one position to the right of the starting position of the single trees.
4. Shift the row of pairs of trees one position to the left.
Does the procedure above not work? If so, which step is wrong?
Or, is the procedure above not “simple” under the technical conditions?
This is a serious question, not a rhetorical one.
That was pretty cool.
Something bothers me, though. Suppose I consider trees with only one arm. The set of all such trees, T, is equivalent to the set of natural numbers (including zero), N, since each tree is just identified by its length. Similarly, the set of all pairs of trees is N^2. And I know that these two sets can be put into 1-1 correspondence.
However, if I use similar reasoning to what you did above, I get a different answer. I can try to map pairs of (one-armed) trees onto single trees by stacking the first on top of the second and then linking them together. This procedure, however, still can never produce a tree of length zero. So I apparently again get T = T^2 + 1. And this, presumably, will lead me to all sorts of wrong answers.
Did I do something wrong here?
By the way, does this tree problem have any cool physical applications that you know of?
Eric (#5): Given a tree, your procedure requires me to look arbitrarily far down the tree before I can tell which pair of trees it’s matched with. This makes your procedure not simple by the rules of the game.
Notice that in the procedure for matching septuples with single trees (linked to in the paragraph beginning “The correspondence….”), you never have to look below level 4 to see what anything is matched with.
Brian (#6): Your stacking procedure fails to be a one-one correspondence not only because of the omitted tree, but also because (for example) the pair consisting of a length-5 tree and a length-2 tree maps to the same tree as the pair consisting of a length-4 tree and a length-3 tree.
Oh right, good point. Thanks!
I think I have a lot more to learn here. I’m going to re-read this one a few times and give it a lot more thought.
Steve (#8),
So is the issue that with 7-tuples, you can typically determine in under a minute what tree it maps to, but with pairs it could take lifetimes if the tree is long enough?
Is it true that a k-tuple of (rooted binary) trees has an “easy” map to (rooted binary) trees iff k=1 mod 6?
Seems like if k=1 mod 6, we can take the first 7 trees and send them to 1 tree to get k-6 trees and repeat this until we have 1 tree (is this still easy?). Is it true that no easy map exists for any k not equal to 1 mod 6?
Doesn’t Eric’s example (#5, point 2) suffer from the same problem as highlighted by Steve in #9? There are two possible 5-node binary trees, and each can be extended into three possible 7-node trees. However, the possible number of 7-node trees is five, not six, because one extension of the left 5-node tree is the same as an extension of the right 5-node tree.
What is their standard for “obvious”?
Wonks Anonymous (#15):
What is their standard for “obvious”?
I think the best answer I can give is to point you to the papers. If you’ve got the sort of background that makes them readable for you, the answers are right there; if you don’t, I fear I’m not skillful enough to make it comprehensible.
Note that “obvious” is part of my interpretation of what they’ve proved; the word “obvious” does not appear in the precise statements of the theorems.
Eric (#12):
So is the issue that with 7-tuples, you can typically determine in under a minute what tree it maps to, but with pairs it could take lifetimes if the tree is long enough?
Essentially, yes. More precisely, the “under a minute” part is not what matters; what matters is that there’s *some* bound that applies to every 7-tuple, whereas in the case of pairs, no matter how long you need to check one of them, there’s another that will need even longer.
And they’re blocking my view of the forest!
So, with trees that can have either 0 or 3 branches at every node, I get T^3+1 = T. The complex roots of this aren’t on the unit circle, so T^n can’t ever equal T. Does this mean there’s no “simple” 1-1 correspondence between these trees and tuples of these trees?
Mike H:
Does this mean there’s no “simple” 1-1 correspondence between these trees and tuples of these trees?
It at least means you can’t prove it by this method.
On the other hand, T^3+1=T does imply, for example, that T^5+T^4+T=T^3, which does have a clear interpretation here.
Does 2005 count as a “recent proof” in Category Theory?
This talk on “The Algebra of Algebraic Data Types” employs similar tricks to show, among other things, how to differentiate a binary tree.
@Steve #4:
I suppose you mean in a mathematical sense only. What about dialetheism, though? As with the old chestnut, “This statement is false.”
Today I learned that there are contexts in which the most ludicrous reasoning is guaranteed to lead you to a correct conclusion.
Steve has just summarized my blog.
Tony N, dialetheism is not enough to resolve the liar pardadox. Just consider the version “This statement is only false.”. If it’s only true, then it’s only false, which is impossible. If it’s only false, then it’s true, which is impossible. If it’s true and false, then it’s only false, which is impossible.
Keshav Srinivasan (#25). Nice example; I hadn’t seen this before.
#25. I confess I had not even heard of dialetheism before, but was intrigued enough to look it up. I don’t see how your addition to the liar paradox changes this in any material way. If we are to accept that sentences can be false and true, your construction does not change anything – does it?
The law of non-contradiction seems so fundamental that it is difficult to think about things where it does not apply. So if it is only true, then it is only false becomes possible, does it not?
Good thoughts– both 25 and 27. Not sure where I come down on this. In any event, I wasn’t propounding dialetheism as something I subscribe to or not. It was merely suggested as a possible challenge to Steve’s claim that something is either true or false.
That said, Keshav, invalidating dialetheism would challenge only the idea that something is BOTH true and false. The other side of the liar-paradox coin remains, i.e. some statements are NEITHER true nor false. Therefore, the liar paradox still presents a problem for Steve’s #4. Btw, challenging #4 isn’t meant to be pedantic, it seems germane given the post.
Tony N, saying that statements are neither true nor false is not enough to resolve the liar paradox either. Consider the statement “This statement is not true.” If it’s neither true nor false, then in particular it’s not true, so it is true, which is impossible.
#29 ” then in particular it’s not true, so it is true, which is impossible.” But under dialetheism it is not impossible. It can be true and not true.