The weak pigeonhole principle for function classes in S12
Norman Danner, Chris Pollett · Mathematical logic quarterly · 2006
Abstract It is well known that S 12 cannot prove the injective weak pigeonhole principle for polynomial time functions unless RSA is insecure. In this note we investigate the provability of the surjective (dual) weak pigeonhole principle in S 12 for provably weaker function classes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)