Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

In Ordinal Analysis, Proof-theoretic Ordinal of a theory is thought as measure of a consistency strength and computational power.

Is it always the case? I. e. are there some general results about formal theories which say that if we know the ordinal measure of a formal theory than we would know its consistency strength and computational power to some extent?

share|improve this question
add comment

1 Answer

This is a very interesting question (and I really want to see what other answers you receive). I do not know of any general metatheorems ensuring that what you ask (in particular, about consistency strength) is the case, at least under reasonable conditions.

However, arguments establishing the proof theoretic ordinal of a theory $T$ usually entail this. You can find a nice summary in the paper "A Model-Theoretic Approach to Ordinal Analysis" by Jeremy Avigad and Richard Sommer, The Bulletin of Symbolic Logic, Vol. 3, No. 1, (Mar., 1997), pp. 17-52, available here.

What follows is their description of these arguments. Avigad and Sommer are assuming that $T$ is a theory in the language of arithmetic, but very little of the description needs to be modified if that is not the case.

Saying that the proof-theoretic ordinal of a theory $T$ is less than or equal to $\alpha$ usually entails all of the following results:

(1) There is some formula $\varphi (y)$ such that $T$ doesn't prove ${\rm TI}(\alpha, \varphi(y))$, where ${\rm TI}(\alpha, \varphi(y))$ formalizes transfinite induction up to $\alpha$ for the formula $\varphi(y)$.

(2) Over a weak base theory, ${\rm PRWO}(\alpha)$ proves the 1-consistency of $T$. Here ${\rm PRWO}(\alpha)$ is a scheme which asserts that there are no primitive recursive descending sequences beneath $\alpha$, and "the 1-consistency of $T$" is the formalized $\Pi^0_2$ assertion that if $T$ proves any $\Sigma^0_1$-formula (possibly with parameters) then that formula is true.

(3) If $T$ proves a recursive function $f$ to be total, then $f$ is $\prec\alpha$-recursive. [Where $\prec$ is the ordering on ordinal notations induced by the intended interpretation.] By "$T$ proves the recursive function $f$ to be total" we mean that $T$ proves $$\forall x\exists! y \varphi(x,y)$$ for some $\Sigma^0_1$ formula $\varphi$ that defines the graph of $f$ in the standard model.

(4) If $\lt$ is any recursive ordering and $T$ proves $(+)$: $$\forall X\hspace{1mm} {\rm TI}({\lt}, y \in X)$$ then the order-type of $\lt$ in the standard model is less than $\alpha$. (If $T$ doesn't allow for quantification over sets of numbers, we replace $(+)$ by $${\rm TI}({\lt}, X(y)),$$ where $X$ is a new predicate symbol that we allow to appear in the axiom schemata of $T$.)

Now, if the program above can be carried out, general theorems of speed-up of proofs (see for example Samuel R. Buss, "On Gödel's Theorems on Lengths of Proofs I: Number of Lines and Speedup for Arithmetics", The Journal of Symbolic Logic, Vol. 59, No. 3, (Sep., 1994), pp. 737-756) should guarantee that if $T_1$ has larger proof theoretic ordinal than $T_2$, then in fact the "computational power" of $T_1$ outruns that of $T_2$ in significant and quantifiable ways.

share|improve this answer
add comment

Your Answer

 
discard

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

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