Skip to main content
1 of 5
Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39

Two questions regarding the reverse mathematics of Siegel's lemma

In a short proof of the Roth theorem regarding the rational approximation of algebraic reals I found online (which made use of Seigel's Lemma), it was stated that "Seigel's lemma is a corollary of the 'pigeonhole principle'" In their paper, "Where Pigeonhole Principles Meet Konig Lemmas" (preprint arXiv:1912.03487v1 [math.LO] 7 Dec 2019), David Belanger, C.T. Chong, Wei Wang, Tin Lok Wong, and Yue Yang state that "the pigeonhole principle for $\Sigma_{2}$-definable injections with domain twice as large as as the codomain" is strictly weaker than "the usual pigeonhole principle for $\Sigma_{2}$-definable injections (so that one could possibly speak of a sequence of pigeonhole principles listed from weakest to strongest). My questions, then, are simply these:

  1. What is the weakest pigeonhole principle needed to derive Siegel's Lemma from, say, $RCA^*_0$ or $WKL^*_0$?

  2. Could one prove very weak pigeonhole principles directly from $RCA^*_0$ and/or $WKL^*_0$ which would derive Siegel's Lemma and if not, why not?

Thomas Benjamin
  • 6.1k
  • 1
  • 25
  • 39