Return to Answer

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$, and using this number, we can interpret a larger model of fPA. Simply use quadruples of numbers $abcd$ to represent larger numbers in base $m$. We know how to add and multiply such numbers in that representation, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers from the original model now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express those notions entirely in the original model simply by using the base $m$ representation. Any concept that could be expressed in the context of the larger models can also be expressed in the original model.

Iterating. The further observation is that we can simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

[Update As explained by Emil Jeřábek in the comments below and in Ali Enayat's answer, this theory has been well studied in models of arithmetic and is known as $\text{PA}^{\text{top}}$. The observations below about $I\Delta_0$ are evidently due originally to Jeff Paris.]

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$, and using this number, we can interpret a larger model of fPA. Simply use quadruples of numbers $abcd$ to represent larger numbers in base $m$. We know how to add and multiply such numbers in that representation, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers from the original model now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express those notions entirely in the original model simply by using the base $m$ representation. Any concept that could be expressed in the context of the larger models can also be expressed in the original model.

Iterating. The further observation is that we can simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$. Now, we can interpret a larger model of fPA by using quadruples of numbers $abcd$, basically, four digits in base $m$. We know how to add and multiply such numbers, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express primality etc. of numbers in the original model simply by using the base $m$ representation. That is, in the original model we can define a notion of primality for numbers, even when their factors may be too big, because they won't be too big in the interpreted model, where multiplication of any two numbers in the original model is now defined.

Iterating. Next, we simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$, and using this number, we can interpret a larger model of fPA. Simply use quadruples of numbers $abcd$ to represent larger numbers in base $m$. We know how to add and multiply such numbers in that representation, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers from the original model now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express those notions entirely in the original model simply by using the base $m$ representation. Any concept that could be expressed in the context of the larger models can also be expressed in the original model.

Iterating. The further observation is that we can simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$. Now, we can interpret a larger model of fPA by using quadruples of numbers $abcd$ in base $m$. We know how to add and multiply them, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express primality etc. of numbers in the original model simply by using the base $m$ representation. That is, in the original model we can define a notion of primality for numbers, even when their factors may be too big, because they won't be too big in the interpreted model, where multiplication of any two numbers in the original model is now defined.

Iterating. Next, we simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.

Victoria Gitman and I recently looked at the first-order version of this theory, which we called fPA, to contrast it with the theory FPA, which Woodin has looked into, which is a possibly stronger version.

So the language of fPA is the same as the ordinary language of arithmetic, except that there is possibly a largest number (without a successor), and the operations of + and $\cdot$ are merely partial, but defined as far as they can be according to the usual recursive definitions. Meanwhile, we have the first-order induction scheme.

The main observation we made is that if you have a model of fPA with a largest number $N$, then there is some largest number $m$ whose square exists $m^2\leq N$. Now, we can interpret a larger model of fPA by using quadruples of numbers $abcd$, basically, four digits in base $m$. We know how to add and multiply such numbers, and this requires only arithmetic for numbers less than $m$, which works fine. Using this method, we can build a larger model of fPA in which $N^2$ exists. Basically, every model of fPA interprets a larger model of fPA, in which any two numbers now have a product.

Answer to your question. The main point I want to make is that the base $m$ method provides a means to express primality etc. also in your context. Since the interpreted model is definable in the original model using quadruples, we can express primality etc. of numbers in the original model simply by using the base $m$ representation. That is, in the original model we can define a notion of primality for numbers, even when their factors may be too big, because they won't be too big in the interpreted model, where multiplication of any two numbers in the original model is now defined.

Iterating. Next, we simply iterate the interpretation construction $\omega$ many times, interpreting to larger and larger models of fPA. The union model is a model of $I\Delta_0$, since bounded induction amounts to unbounded induction in the individual models.

Conclusion. The models of fPA with a largest number all arise by chopping a model of $I\Delta_0$ at some number $N$.

For this reason, questions about what is or what is not provable in fPA amount to the corresponding questions about $I\Delta_0$, which is an intensely studied theory and there are many open questions.

FPA. Woodin had looked into the first-order theory FPA in which one adopts the pigeon-hole principle as a fundamental axiom scheme, rather than just the first-order induction scheme. PHP implies the induction scheme, but it is open whether they are equivalent.