Pigeonhole is a fundamental principle without which state of mathematics will be much different. However what examples of good mathematics has not yet been proved and cannot be proved with pigeonhole alone?

  • 1
    $\begingroup$ Pythagoras' theorem $\endgroup$ – Hagen von Eitzen Nov 1 '18 at 5:46
  • $\begingroup$ Please post with explanation. Is Euler characteristic of planar graph provable? $\endgroup$ – T.... Nov 1 '18 at 5:50
  • $\begingroup$ @edm explicit and implicit are same if principle exists in proof. $\endgroup$ – T.... Nov 1 '18 at 6:06
  • 1
    $\begingroup$ Establishing that a given result/technique isn't sufficient to prove a given theorem is generally extremely hard to do, mostly because precisely defining what that means is extremely subtle. For example, the reverse-mathematical approach Bjorn mentions below takes as "trivial" a large amount of non-trivial mathematics (e.g. the fundamental theorem of algebra). But there are many basic results for which the pigeonhole principle seems completely irrelevant; e.g. how would you use it to prove the Pythagorean theorem (per Hagen's comment above)? $\endgroup$ – Noah Schweber Nov 1 '18 at 14:29
  • 1
    $\begingroup$ So your starting instinct here should definitely be that the pigeonhole principle - or anything else specific, really - will not be sufficient to tackle most problems you'll come across. $\endgroup$ – Noah Schweber Nov 1 '18 at 14:30

The infinite pigeonhole principle is equivalent to B$\Sigma^0_2$ in the sense of reverse mathematics.

This implies that many theorems such as Heine-Borel, Konig's lemma, Ramsey's theorem are not provable from this Infinite Pigeonhole Principle.

  • $\begingroup$ Possible to be more explicit in applications? $\endgroup$ – T.... Nov 1 '18 at 6:08
  • 2
    $\begingroup$ @Brout That's a pretty explicit list of applications. Are you familiar with the theorems listed? $\endgroup$ – Noah Schweber Nov 1 '18 at 14:26
  • $\begingroup$ @NoahSchweber Except for Ramsey's theorem No. $\endgroup$ – T.... Nov 1 '18 at 17:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.