Аннотация:
In fragments of arithmetic, the pigeonhole principle may fail for definable partitions of finite sets. Dimicoupolous and Paris proved that over $I\Sigma_1$ the ordinary pigeonhole principle for $\Sigma_{n+1}$ partitions is equivalent to $B\Sigma_{n+1}$ ($n > 0$).
Later Kaye formulated several second order pigeonhole principles which are used to axiomatise $\kappa$-like models of arithmetic.
A first order fragment derived from one of Kaye's pigeonhole principles, known as $\Sigma_n$-cardinality scheme or $C\Sigma_n$, has interesting independence properties proved by Kaye himself and also proved useful in reverse mathematics.
Recently, we study another first order fragment of these pigeonhole principles, called Generalised Pigeonhole Principle ($\text{GPHP}$) by Kaye.
We shall introduce some progress concerning $\Sigma_{n+1}$-$\text{GPHP}$ from perspectives of both first order arithmetic and reverse mathematics.
Язык доклада: английский
|