Premium
The weak pigeonhole principle for function classes in S 1 2
Author(s) -
Danner Norman,
Pollett Chris
Publication year - 2006
Publication title -
mathematical logic quarterly
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.473
H-Index - 28
eISSN - 1521-3870
pISSN - 0942-5616
DOI - 10.1002/malq.200610015
Subject(s) - pigeonhole principle , mathematics , surjective function , injective function , function (biology) , combinatorics , discrete mathematics , polynomial , pure mathematics , mathematical analysis , evolutionary biology , biology
It is well known that S 1 2 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 1 2 for provably weaker function classes. (© 2006 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)