It’s been a long time since any mathematical content was posted on this blog. This is in part because I have been diverting my mathematical efforts more to the Tricki (not to mention my own research), and indeed the existence of the Tricki means that this blog will probably become less active, though I may publish some Tricki articles here as well. But there are certain quasi-philosophical questions that I want to discuss and that are better discussed here. I have already written about one of my favourites: when are two proofs essentially the same? Another that is closely related is the question of how it can be that two mathematical statements are equivalent to each other and yet one is clearly “stronger”. This phenomenon will be familiar to all mathematicians, but here is an example that illustrates it particularly well. (The example is also familiar as a good example of the phenomenon).Hall’s theorem, sometimes known as Hall’s marriage theorem, is the following result. Let be a bipartite graph with finite vertex sets and of the same size. A perfect matching in is a bijection such that and are neighbours for every . Given a subset , the neighbourhood of is the set of all vertices in that are joined to at least one vertex in . A trivial necessary condition for the existence of a perfect matching is that for every subset the neighbourhood is at least as big as , since it must contain , which has the same size as . This condition is called Hall’s condition.
What is not trivial at all is that Hall’s condition is also sufficient for the existence of a perfect matching. Here’s one of the shortest proofs. Let be a bipartite graph with vertex sets and of size and suppose by induction that the result is true for all bipartite graphs with smaller vertex sets. Now we split into two cases. If there is a proper subset with , then by induction we can find a perfect matching from to . Let be the complement of in . Then any subset has at least neighbours in , or else would have fewer than neighbours. So we can find a matching from to as well. Putting the two together gives a perfect matching of and .
Now suppose that for every proper subset . In that case we can pick an arbitrary and let be an arbitrary neighbour of . Let and let . Then since we have removed just one vertex from , the restriction of to the vertex sets and satisfies Hall’s condition, so by induction we have a perfect matching of and and again we are done.
There can be no doubt that one of the directions of this equivalence is trivial compared with the other. And we are also tempted to say that the condition that has a perfect matching is “stronger” than Hall’s condition, since it trivially implies it. So Hall’s theorem has the flavour of obtaining a strong conclusion from a weak hypothesis. But how can this be if the hypothesis and conclusion are equivalent?
Before thinking about how to answer this question, it is perhaps a good idea to think about why exactly it seems mysterious, if indeed it does. This would be my suggestion. Normally when we say that condition P is stronger than condition Q we mean that P has consequences that Q does not have, or, more simply, that some objects satisfy Q without satisfying P. For example, the condition that a natural number is an odd prime is stronger than the condition that it is odd. But here we find ourselves wanting to say that one graph property is stronger than another even though the two properties have precisely the same consequences and pick out precisely the same set of graphs.
The solution to this little puzzle seems to be that it depends on a confusion between actual logical consequences and what we can easily perceive to be logical consequences. Or at least, that’s one suggestion for a solution, though I’m not sure I’m entirely satisfied by it. It does at least cover the case of Hall’s theorem: we could say that the existence of a perfect matching is psychologically stronger than Hall’s condition, since it trivially implies, and is not trivially implied by, Hall’s condition.
But I’d like to say something more “objective” somehow, and not tied to what people happen to find easy. To see what I might mean by this, consider another difference between the two conditions. If you were asked to check whether some bipartite graph satisfied Hall’s condition, what would you do? You could check the sizes of the neighbourhoods one by one, but there are exponentially many of them, so this would not be an appealing prospect. Alternatively, you could use a well-known polynomial-time algorithm that finds perfect matchings when they exist. This would clearly be much better. Is there some precise sense in which an efficient check that a graph satisfies Hall’s condition “has to” find a perfect matching?
Another thought is that Hall’s theorem is false for infinite graphs. For instance, if you let and both be and join in to all of , and all other in to , then Hall’s condition is satisfied but there is no perfect matching. On the other hand, the existence of a perfect matching still trivially implies Hall’s condition. So we can generalize the two conditions in a natural way and we find that one is now stronger than the other in the precise formal sense. (It seems unlikely that we can do something like this systematically for all examples where one direction of an equivalence is trivial and the other hard. But it would be interesting to come up with other equivalences where it can be done.)
Since I’m throwing out questions here, I may as well mention the fact that is rarely talked about but is surely noticed by almost all mathematicians, which is that the notion of equivalence itself is used in an informal way. Why don’t we say that Fermat’s last theorem is equivalent to the four-colour theorem? After all, here’s a proof that FLT implies 4CT (in ZFC): obviously FLT+ZFC implies ZFC, and we know that ZFC implies 4CT. And similarly in the opposite direction. An answer to this question takes us back to ideas that were discussed in some of the responses to the post on sameness of proofs: one would like to say that when mathematicians talk of one statement implying another, the implication should not be “homotopic” to a silly implication such as the one just given of 4CT from FLT. (I feel some kind of structural property should be involved and not mere length of proof, but that is just a feeling that I can’t back up in any adequate way.)
One final remark is that questions of this kind show just how incomplete a picture of mathematics was provided by some philosophers early in the twentieth century, who held that it was merely a giant collection of tautologies. The way that tautologies relate to each other is fascinating and important, so even if one believes that mathematics consists of tautologies, the “merely” is unacceptable. It should be said that this particular view of mathematics went out of fashion fairly soon after it came into fashion, so it doesn’t really need attacking, but it would be interesting to develop this particular line of attack. Indeed, I’m fairly sure that theoretical computer scientists can say something precise about how Boolean tautologies relate to each other: that could perhaps provide a good toy model for “sensible” implications and “non-obvious” directions of equivalences.