# What mathematics cannot be reduced to pigeonhole?

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?

• Pythagoras' theorem – Hagen von Eitzen Nov 1 '18 at 5:46
• Please post with explanation. Is Euler characteristic of planar graph provable? – Turbo Nov 1 '18 at 5:50
• @edm explicit and implicit are same if principle exists in proof. – Turbo Nov 1 '18 at 6:06
• 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)? – Noah Schweber Nov 1 '18 at 14:29
• 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. – Noah Schweber Nov 1 '18 at 14:30

## 1 Answer

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.

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