论文标题
有界算术和鸽子原理变体的模型
Models of Bounded Arithmetic and variants of Pigeonhole Principle
论文作者
论文摘要
我们给出了基本的证据，表明理论$ t^1_2（r）$由弱的Pigeonhole原理增强，所有$δ^b_1（r）$ - 可定义的关系并未证明$ r $的五个鸽子洞原则。这可以从已知的更一般的结果中得出，但是我们的证明产生了$ t^1_2（r）$的模型，其中$ ontophp^{n+1} _n（r）$对于某些非标准元素$ n $而失败，而$ php^{m+1} _m $ complys的所有$δ^b_1（r）$ - $ - $ n $ - $ n $ - $ - $ - $ - $ - $ - pe^leq n lo n y le pect y- pe n y le pecte us $ - $ε> 0 $是固定标准有理参数。这可以看作是解决M. Ajtai提出的一个开放问题的一步。
We give elementary proof that theory $T^1_2(R)$ augmented by the weak pigeonhole principle for all $Δ^b_1(R)$-definable relations does not prove the bijective pigeonhole principle for $R$. This can be derived from known more general results but our proof yields a model of $T^1_2(R)$ in which $ontoPHP^{n+1}_n(R)$ fails for some nonstandard element $n$ while $PHP^{m+1}_m$ holds for all $Δ^b_1(R)$-definable relations and all $m \leq n^{1-ε}$, where $ε> 0$ is a fixed standard rational parameter. This can be seen as a step towards solving an open question posed by M. Ajtai.
