-1
$\begingroup$

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?

$\endgroup$
7
  • 1
    $\begingroup$ Pythagoras' theorem $\endgroup$ Commented Nov 1, 2018 at 5:46
  • $\begingroup$ Please post with explanation. Is Euler characteristic of planar graph provable? $\endgroup$
    – Turbo
    Commented Nov 1, 2018 at 5:50
  • $\begingroup$ @edm explicit and implicit are same if principle exists in proof. $\endgroup$
    – Turbo
    Commented Nov 1, 2018 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$ Commented Nov 1, 2018 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$ Commented Nov 1, 2018 at 14:30

1 Answer 1

7
$\begingroup$

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.

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

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .