Skip to main content
1 of 3
user avatar
user avatar

Since no one else is biting, I'll answer, and I'm happy to be corrected on any points.

$I\Delta_0$ can prove several basic theorems:

  • Every square equals 0 or 1 mod 4
  • No prime has a rational square root
  • Every prime of the form $4m+1$ can be written as $a^2+b^2$
  • 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 by D'Aquino.)

$I\Delta_0$ seems not to be able to prove that:

  • there are arbitrarily large primes
  • the function $x^{\log x}$ is total
  • the existence of a solution to the Pell equation $x^2-Ny^2=1$

(The first two are a well-known open problem due to Wilkie; the third is presumably not provable because the solutions grow so large so quickly.)

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 due to Friedman.)

user44143