Skip to main content
MathOverflow

Return to Answer

Bounty Ended with 50 reputation awarded by BPP
deleted 23 characters in body
Source Link
user44143
user44143

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 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 open problem due to Wilkie)

$I\Delta_0$ cannot prove (assuming consistency) 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 to Parikh; the Pell equation result is due 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 due to Friedman.)

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 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 open problem due to Wilkie)

$I\Delta_0$ cannot prove (assuming consistency) 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 to Parikh; the Pell equation result is due 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 due to Friedman.)

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 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 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 to Parikh; the Pell equation result is due 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 due to Friedman.)

corrected in response to comments
Source Link
user44143
user44143

Since no one else is biting, I'll answer, and I'm happythanks to be corrected on any points.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
  • 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 existenceevery prime of a solution to the Pell equationform $x^2-Ny^2=1$$4m+1$ can be written as $a^2+b^2$

(The first two areis a well-known open problem due to Wilkie; the thirdWilkie)

$I\Delta_0$ cannot prove (assuming consistency) 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 presumably not provable becausedue to Parikh; the solutionsPell equation result is grow so large so quicklydue 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 due to Friedman.)

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.)

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 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 open problem due to Wilkie)

$I\Delta_0$ cannot prove (assuming consistency) 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 to Parikh; the Pell equation result is due 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 due to Friedman.)

Source Link
user44143
user44143

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.)