Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In several "proof-theory-for-dummies"-type texts I have read, $I\Delta_0+Exp$ or a theory equivalent to it shows up as a "base" theory, though in what sense it is minimal is not clearly addressed.

I realise this is a vague question but if I had the knowledge to make it more specific, I wouldn't need to ask it in the first place.

share|improve this question
add comment

1 Answer

up vote 4 down vote accepted

The main use of this theory is that it is strong enough to prove many truly basic facts about natural numbers, while still being weak enough that it carries little "baggage".

$I\Delta_0 + \text{Exp}$ is strong enough to define functions that encode and decode finite sequence of numbers (Goedel numbering) and, similarly, it can encode and decode finite sets of numbers as single numbers. This makes it possible to formalize many basic number-theoretic and proof-theoretic results in this theory. Those results, in turn, make it possible to use $I\Delta_0 + \text{Exp}$ as a base over which we can prove stronger statements are equivalent.

Harvey Friedman has made a somewhat polemical "grand conjecture" that every fact of elementary number theory proven in Annals of Mathematics can be proven in $I\Delta_0 + \text{Exp}$. This includes, for example, Fermat's Last Theorem. This is not to say that the original proofs will work - the proofs in $I\Delta_0 + \text{Exp}$ may be much more lengthy and complex. But the fact that this conjecture is even plausible speaks to the strength of $I\Delta_0 + \text{Exp}$. (The status of FLT here is not known.)

$I\Delta_0 + \text{Exp}$ is very weak in other senses. Its proof theoretic ordinal is $\omega^3$, which is extremely smaller than the ordinal of Peano arithmetic and even much smaller than the ordinal of the "next" canonical theory, $I\Sigma_1$. This is philosophically relevant in certain instances where we wish to keep our assumptions relatively weak (in terms of their proof-theoretic ordinal).

$I\Delta_0 + \text{Exp}$ is not "minimal" in a formal sense. We could work with ad hoc theories that are weaker, but still include the facts of number theory we need (perhaps as axioms). However, $I\Delta_0 + \text{Exp}$ has a relatively concrete and natural definition, which makes it more attractive to work with than some concocted system. (Of course, it may be that $I\Delta_0 + \text{Exp}$ is equivalent to some axiom $T$ over some even weaker base theory, in which case $I\Delta_0 + \text{Exp}$ would be minimal as an extension of the base theory that proves $T$.)

Another commonly used weak theory is $I\Sigma_1$. This theory extends $I\Delta_0 + \text{Exp}$ (modulo some definitional extensions) but $I\Sigma_1$ is still relatively weak (its ordinal is $\omega^\omega$). Many basic facts of number theory are easier to prove in $I\Sigma_1$, making it more convenient than $I\Delta_0 + \text{Exp}$ for various purposes, at the cost of a larger proof theoretic ordinal.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.