What combinatorial and number-theoretic propositions can $I\Delta\_0$ prove? Obviously there are an infinitude of them, but what are some well known theorems that can be proved in $I\Delta\_0$, if any?



What can $I\Delta_0$ prove?
Since no one else is biting, I'll answer, and thanks to comments I now this is accurate:


$I\Delta\_0$ can prove several basic theorems:


* Every square equals 0 or 1 mod 4
* No prime has a rational square root
* The only solutions to $x^3+y^3=z^3$ or $x^4+y^4=z^4$ are trivial
* Every $x$ is divisible by a prime $p$ with $p \le x$


(The standard proofs can be reproduced in $I\Delta\_0$, since they do not require any lists or sequences or products thereof. The last claim is proved in $I\Delta\_0$ in a [paper](https://www.jstor.org/stable/2275173) by D'Aquino.)


$I\Delta\_0$ seems not to be able to prove that:


* there are arbitrarily large primes
* every prime of the form $4m+1$ can be written as $a^2+b^2$


(The first is a [well-known](https://www.cs.umd.edu/users/gasarch/TOPICS/provephp.pdf) open problem due to Wilkie)


$I\Delta\_0$ cannot prove that:


* the functions $x^{\log x}$, $x!$, or $x^y$ are total
* there are solutions to the Pell equation $x^2-Ny^2=1$


(The $x^{\log x}$ is [due](https://www.math.ucsd.edu/%7Esbuss/ResearchWeb/parikh/paper.pdf) to Parikh; the Pell equation result is [due](https://www.sciencedirect.com/science/article/pii/0168007295000186?via%3Dihub) to D'Aquino.)


But $I\Delta\_0(exp)$, i.e. the theory $I\Delta\_0$ in the language with exponentiation, seems to prove


* every theorem published in the Annals of Mathematics whose statement involves only finitary mathematical objects


(This is a well-known [conjecture](https://en.wikipedia.org/wiki/Elementary_function_arithmetic#Friedman%27s_grand_conjecture) due to Friedman.)


