Charles Explorer logo
🇬🇧

On strong fragments of Peano arithmetic

Publication at Faculty of Arts |
2015

Abstract

The classical proof of Paris and Kirby, showing that Sigma_{n+1}-collection is not provable using Sigma_{n}-induction, is analyzed. It is shown that a weaker principle than Sigma_{n+1}-collection, saying that there is no \Sigma_{n+1}-definable bounded one-one function, is also violated in the model constructed by Paris and Kirby.

Further, details of a proof that from a \Sigma_{n+1}-definable bounded one-one function one can construct a \Sigma_{n+1}-definable bounded one-one function whose range is an interval is elaborated. This last fact is due tu Paris and is probably unpublished.