ECCC-Report TR13-149https://eccc.weizmann.ac.il/report/2013/149Comments and Revisions published for TR13-149en-usFri, 01 Nov 2013 15:49:25 +0200
Paper TR13-149
| The Ordering Principle in a Fragment of Approximate Counting |
Albert Atserias,
Neil Thapen
https://eccc.weizmann.ac.il/report/2013/149The ordering principle states that every finite linear order has a least element. We show that, in the relativized setting, the surjective weak pigeonhole principle for polynomial time functions does not prove a Herbrandized version of the ordering principle over $\mathrm{T}^1_2$. This answers an open question raised in [Buss, Ko{\l}odziejczyk and Thapen, 2012] and completes their program to compare the strength of Je\v{r}\'abek's bounded arithmetic theory for approximate counting with weakened versions of it.
Fri, 01 Nov 2013 15:49:25 +0200https://eccc.weizmann.ac.il/report/2013/149