Finite Combinatorics and Fragments of Arithmetic

Wei Wang (SYSU, Guangzhou)

Aug 07. 2025, 11:30 — 12:30

In fragments of first order arithmetic, definable maps on finite domains could behave very differently from finite maps.

Here combinatorial properties of $\Sigma_{n+1}$-definable maps on finite domains are compared in the absence of $B\Sigma_{n+1}$.

It is shown that $\operatorname{GPHP}(\Sigma_{n+1})$ (the $\Sigma_{n+1}$-instance of Kaye's General Pigeonhole Principle) lies strictly between $\operatorname{CARD}(\Sigma_{n+1})$ and $\operatorname{WPHP}(\Sigma_{n+1})$ (Weak Pigeonhole Principle for $\Sigma_{n+1}$-maps), and also that $\operatorname{FRT}(\Sigma_{n+1})$ (Finite Ramsey's Theorem for $\Sigma_{n+1}$-maps) does not imply $\operatorname{WPHP}(\Sigma_{n+1})$.

Further Information
Venue:
ESI Schrödinger and Boltzmann Lecture Hall
Recordings:
Recording
Associated Event:
Reverse Mathematics (Thematic Programme)
Organizer(s):
Juan Aguilera (TU Vienna)
Linda Brown Westrick (Penn State U)
Noam Greenberg (Victoria U of Wellington)
Denis Hirschfeldt (U of Chicago)