16
$\begingroup$

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 then we know its consistency strength and computational power to some extent?

$\endgroup$

1 Answer 1

18
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .