The undeserved status of the pigeon-hole principle (1991) • Hacker News Board

Re: The undeserved status of the pigeon-hole principle (1991)

#11

Post by tprice7 » Sat, Jul 04, 2020, 10:54 PM UTC

ogogmad wrote: post #6

neel_k wrote: post #5

This note represents a rare misstep by Dijkstra: the pigeonhole principle actually is a special and important principle worthy of a special name of its own. For example: 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…

Do you have a reference for 2? Thanks.

The fact that every infinite sequence of points in a compact metric space has a cluster point is sort of like the pigeonhole principle. The grandparent comment in my opinion makes much more sense if the phrase "a compactness for metric spaces" is replaced by "sequential compactness for metric spaces".

Re: The undeserved status of the pigeon-hole principle (1991)

#12

Post by andrepd » Sat, Jul 04, 2020, 11:56 PM UTC

neel_k wrote: post #5

This note represents a rare misstep by Dijkstra: the pigeonhole principle actually is a special and important principle worthy of a special name of its own. For example: 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…

SAT solvers overwhelmingly don't use resolution. Modern state of the art solvers use DPLL/CDCL.

Re: The undeserved status of the pigeon-hole principle (1991)

#13

Post by starchild_3001 » Sun, Jul 05, 2020, 12:09 AM UTC

I (or any math noob) can easily understand the pigeon hole principle. His more detailed arguments about max, avg and a bunch of other stuff is more obtuse and harder to follow. IMO, pigeon hole principle, where applicable, wins this argument. If you're dealing with a sequence of real numbers, you might need max >= avg.

Re: The undeserved status of the pigeon-hole principle (1991)

#14

Post by Sebb767 » Sun, Jul 05, 2020, 12:22 AM UTC

I think he's missing two important points.

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.

Re: The undeserved status of the pigeon-hole principle (1991)

#15

Post by 53x15 » Sun, Jul 05, 2020, 12:52 AM UTC

andrepd wrote: post #12

neel_k wrote: post #5

This note represents a rare misstep by Dijkstra: the pigeonhole principle actually is a special and important principle worthy of a special name of its own. For example: 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…

SAT solvers overwhelmingly don't use resolution. Modern state of the art solvers use DPLL/CDCL.

I think neel_k was referring to the fact that when a DPLL or CDCL solver concludes UNSAT you can take the trace its backtracking activity and rewrite it from the bottom up as a resolution refutation. So in this sense the solvers are finding resolution proofs.

Re: The undeserved status of the pigeon-hole principle (1991)

#16

Post by impendia » Sun, Jul 05, 2020, 12:56 AM UTC

Sebb767 wrote: post #14

I think he's missing two important points. 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…

Strongly agreed. I've taught university-level discrete math several times, and beginners to the subject need pegs to hang their hat on, something that serves as a goal and a signal that they're done. The Pigeonhole Principle is an ideal example of this.

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.

Re: The undeserved status of the pigeon-hole principle (1991)

#17

Post by sn41 » Sun, Jul 05, 2020, 2:11 AM UTC

I disagree with this note, even though I often read Dijkstra's notes for enlightenment. The pigeonhole principle is one of the basic tools we have to approach mathematics, and therefore deserves a name. We often assimilate proofs by "abbreviating" the major steps through naming them - "pigeonhole principle", "passing to subsequences" etc.

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.

Re: The undeserved status of the pigeon-hole principle (1991)

#18

Post by bloaf » Sun, Jul 05, 2020, 4:35 AM UTC

starchild_3001 wrote: post #13

I (or any math noob) can easily understand the pigeon hole principle. His more detailed arguments about max, avg and a bunch of other stuff is more obtuse and harder to follow. IMO, pigeon hole principle, where applicable, wins this argument. If you're dealing with a sequence of real numbers, you might need max >= avg.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

Re: The undeserved status of the pigeon-hole principle (1991)

#19

Post by booleandilemma » Sun, Jul 05, 2020, 5:28 AM UTC

The whole metaphor of objects and compartments is just a pain in the neck

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.

Re: The undeserved status of the pigeon-hole principle (1991)

#20

Post by atq2119 » Sun, Jul 05, 2020, 6:48 AM UTC

bloaf wrote: post #18

starchild_3001 wrote: post #13

I (or any math noob) can easily understand the pigeon hole principle. His more detailed arguments about max, avg and a bunch of other stuff is more obtuse and harder to follow. IMO, pigeon hole principle, where applicable, wins this argument. If you're dealing with a sequence of real numbers, you might need max >= avg.

I agree. I've seen some marvelous pigeon hole explanations of why you cannot write a general lossless compression algorithm that makes all files smaller. I have no idea what that explanation would look like in terms of maxes and averages, and I have to believe it would be much more difficult to understand.

That's really more about surjectivity and simple counting. Neither the pigeon hole principle not a max/average argument are really necessary.

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.