The undeserved status of the pigeon-hole principle (1991)
cs.utexas.edu
cs.utexas.edu
1. When you formulate the pigeonhole principle in propositional logic, its resolution proofs are exponentially large. Since modern SAT solvers are basically very fancy propositional resolution provers, this gives you a nice way to find hard instances for them. It also makes the question of when propositional proof systems can be more succinct than one another is also a fundamental question in complexity theory.
2. It also arises in geometry: a compactness for metric spaces is essentially the statement that the pigeonhole principle applies to the space.
I don't have a unified perspective of these two facts, but either one of them is really striking. As a result I'm okay with giving the pigeonhole principle its own natural language name.
https://williewong.wordpress.com/2010/03/18/compactness-part...
Most modern SAT solvers will still have trouble with the pigeon-hole style problems (although some have inbuilt explicit detection, or symmetry breaking, which will let them solve it efficiently).
Rare? He was often biased by his preferences, teaching styles, and opinions, in his notes, as opposed to pure science/logic.
Firstly, when you break down your proof on the pigeonhole principle, you've shown that the problem reduces to something simple and understandable. It's basically a nicer version of "q.e.d.".
Secondly, and much more important: Integrating the principle allows the reader to understand the end of the proof more easily. I.e., if I find the principle mentioned in the end, I know that I need to look for "pigeons" and "holes" and that the proof is a way to get to those - allowing me to understand the proof from the conclusion going backwards, or at least helps doing so.
Of course, this varies per person and depends a bit on how much you're trained in reading proofs, too. But it's enough to justify naming it in my opinion.
Conversely, in research papers, or in conversations among math researchers (at least in my discipline) the Pigeonhole Principle is seldom mentioned by name. The idea is considered too "obvious" to need a name.
a) The history of mathematics is littered with examples of assumed "obvious" results that turned out to have drastic implications. This is especially true of combinatorics, which was blissfully ignorant to the axiom of choice for so long and now must wrestle with it forever. Strict adherence to some formalism may be justifiably understood, and it's a little shocking to find EWD of all people arguing otherwise for such a pragmatic reason as pedagogical clarity.
b) Comparing 0) and 1) as EWD suggests, the first thing I notice is the sudden appearance of the word "finite" which never appears again in the article (nor in negation; also the inelegant but mostly harmless introduction of "nonempty"). The generalization of the principle to support reals costs it its trivial generalization over infinite bags, which is also often valuable (a classic example being Siegel's lemma).
This isn't just exclusive to mathematics. It's similar to the reason people bring in single-line Node.JS packages; a fear of re-inventing the wheel when they don't actually need a wheel in the first place, or when the wheel is trivial to re-state in a more natural form for the proof / program.
Say you're trying to find a way to compress every n+1 bit string into an n bit string. Losslessness means that you have to come up with a function d from n bit string to n+1 bit string that decompresses. The number of n+1 bit string is larger, so there must be n+1 bit strings that are not in the image of d, which means that such a function d cannot exist.
We might as well call this "the whole-pigeon principle."
When you compress a file, you are representing a big number with a small number.
There are more big numbers than there are small numbers.
Specifically, they were looking for how you write the can't-always-compress proof using formulation (1)
Compressing (n+1)-bit input to n-bit output makes the average output correspond to 2^(n+1)/2^n = 2 inputs. By Dijkstra's rephrasing of the pigeonhole principle, the maximum number of inputs colliding on the same output must be at least 2.
Or we could make it more robust and say we're compressing to n-bit-or-smaller output. Then the average output corresponds to 2^(n+1)/(2^(n+1)-1) inputs. That average is still strictly greater than 1, so the maximum number of inputs colliding on the same output must also be strictly greater than 1 (at least 2, since that's the smallest natural which is greater than 1).
Sure, maybe, in some instances, some people, might, perhaps make a little too much out of using the pigeon hole principle. But here, he make too much out of that situation.
(I usually like Dijkstra's works but the quote does make a person smile.)
Even in the realm of "infinite" mathematics like analysis, theorems like the Heine-Borel Theorem and the Bolzano-Weierstrass theorem rely on pigeonhole-like arguments. Of course, that statement can be made rigorous in reverse mathematics.
I like the metaphor, it helps me to understand the principle in the first place. I doubt I'm the only one who feels this way.
Counting things is one of the simplest things in mathematics. Much simpler than "averages", "real numbers" (a very complicated subject) and other things Dijkstra mentions in his alternative formulation.
It seems like he's sacrificing simplicity and ease of understanding for other properties that aren't generally applicable.