As I currently understand it, induction on formulas containing $N+1$ first-order quantifiers is required to prove the well-ordering of the ordinal $(\omega \uparrow\uparrow N) < \epsilon_0$, that is, $\omega^{\omega^\cdots}$ for $N$ layers of $\omega$. See e.g. the second answer to Why do stacked quantifiers in PA correspond to ordinals up to $\epsilon_0$?.

If this is so then by Godel's Completeness Theorem there must be models of (if I have this right) $PRA+I(\Pi^0_{N+1})$ within which $\omega \uparrow\uparrow N$ is well-ordered, but $\omega \uparrow\uparrow (N+1)$ is not well-ordered.

What would these nonstandard models look like? Is there any intuitive way to describe them via ultrapowers or something similar? Or can we say something about their structure, the way that $\mathbb{N} + \mathbb{Z}\cdot\mathbb{Q}$ is the structure for countable nonstandard models of full first-order arithmetic?

For concreteness: Is there any more specific way to describe a nonstandard model of PRA in which the Ackermann function is not complete, beyond "The Ackermann function is not complete"? Hopefully via some construction which will extend to "Kirby-Paris hydras of height $N+2$(?) always terminate, but some of height $N+3$(?) don't"? Obviously every primitive recursive function $f_n$ with $n \in \mathbb{N}$ is complete for every standard and nonstandard input, while the Ackermann function is incomplete for some input $\varpi$ which is a nonstandard number ($\varpi > 0, \varpi > 1, \dots$), likewise with non-terminating hydras where at least one branch has nonstandard width, but beyond this I cannot visualize anything about what the nonstandard model looks like.

(Understanding this would provide a direct, non-Godelian argument for why induction on $N+1$ quantifiers is *necessary* as well as *sufficient* to prove well-ordering of $\omega \uparrow\uparrow N$. It would also show in a direct, non-Godelian way that $PA$ cannot prove the well-ordering of $\epsilon_0$, since this would require induction on infinite quantifiers.)

orderingof the model, and it applies to all models of, say, IOpen. $\endgroup$ – Emil Jeřábek supports Monica Jun 2 '14 at 21:38Noinfinite recursive well order is going to be actually well ordered when interpreted in a nonstandard model of arithmetic, because already what the model thinks to be $\omega$ (= the model itself) is not well ordered. $\endgroup$ – Emil Jeřábek supports Monica Jun 2 '14 at 21:43