11
$\begingroup$

In 1965 Shepherdson proved that FLT is independent of the fragment of PA that uses only open induction and signature $0,S,+\times$. Indeed $2x+1\neq 2y$ is independent of that fragment. Schmerl gives a good general criterion for independence from that fragment in ``Diophantine equations in a fragment of number theory'' in the book Computation and Proof Theory, Springer Lecture Notes in Mathematics Volume 1104, 1984, pp 389-398.

Is FLT currently known to be independent of any larger fragment of PA?

$\endgroup$
3
  • $\begingroup$ I'll mention Hajek and Pudlak in Metamathematics of First-Order Arithmetic (1998) discuss Shepherdson's result without saying his independence results in 1965 extend to any larger fragment. Rather, they say Shepherdson's technique here is so different from the techniques for stronger fragments that they will not go into it. $\endgroup$ Apr 14, 2013 at 11:22
  • $\begingroup$ The L in FLT means Little or Last? $\endgroup$ Apr 16, 2013 at 11:59
  • $\begingroup$ Last. I had never seen FLT used to mean Fermat's Little Theorem until you put me on the track of it and I found a cryptography oriented website acunix.wheatonma.edu/bbloch/crypto/… using it that way. $\endgroup$ Apr 16, 2013 at 12:44

1 Answer 1

4
$\begingroup$

Leszek Kołodziejczyk has devised a method how to extend some type of Shepherdson-like models of IOpen into models of Buss’s theory $T^0_2$ (a weak subsystem of $I\Delta_0+\Omega_1$). In particular, he has shown that $T^0_2$ does not prove that $x^3+y^3=z^3$ has no nontrivial solution.

$\endgroup$
3
  • $\begingroup$ In light of the other answer, I should probably stress that $T^0_2$ is not a weak theory when it comes to Tennenbaum phenomena: it has no recursive nonstandard models, and in fact, every nonstandard countable model of $T^0_2$ has a nonstandard cut that is a model of PA. While the theory shows signs of pathological weakness (by Leszek’s results, it can’t prove that a power of $2$ is not divisible by $3$), the slightly stronger theory $T^0_2(\lfloor x/2^y\rfloor)$ is quite well-behaved, it can define all polynomial-time functions and prove induction for them (it is equivalent to $PV_1$). $\endgroup$ Apr 16, 2013 at 16:00
  • $\begingroup$ $T^0_2$ does include Robinson's $Q$, right? Specifically, it includes $x=0\vee \exists y(x=Sy)$? $\endgroup$ Apr 16, 2013 at 21:11
  • $\begingroup$ Yes. This is provable by open (and therefore $\Sigma^b_0$) induction: if $x$ is neither $0$ nor a successor, we can prove $y\ne x$ for every $y$ by induction on $y$, and taking $y=x$ gives a contradiction. $\endgroup$ Apr 22, 2013 at 11:25

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.