Consistency Hierarchy

Consistency Results

We say that a theory $S$ is consistent relative to another theory $T$ if $Con(T)\to Con(s)$ $\to$Where $Con(T)$ denotes that $T$ does not prove a contradiction (i.e., $T⊢(\phi \wedge \neg \phi )$ for some $\phi$ in the language of $T$).

Consistency Strength: We say that a theory $T$ is at least as strong as some theory $S$, denoted $T\ge S$, if $T⊢Con(S)$. We say that a theory $T$ is strictly stronger then a theory $S$, denoted $T>S$, if $T\ge S$ and $S\ngeqq T$. That is, $T⊢Con(S)$ but $S/⊢Con(T)$. Two theories $T$ and $S$ have the same consistency strength, denoted $T\equiv S$ (equivalence relation), if $T\le S$ and $S\le T$. That is, $T⊢Con(S)$ and $S⊢Con(T)$.

Relative Consistency Results: For $S$ and $T$ are axiomatic theories, the following statement: $Con(T)\to Con(S)$ asserts “If $T$ is consistent, then $S$ is consistent.” This also means ”$S$ is consistent relative to $T$”

Such statements can be formulated in relatively weak meta-theories such as $PRA$ (Primitive-Recursive Arithmetic). $PRA$ is not proving the consistency of $T$ or $S$, but rather proving the relative consistency result “if $T$ is consistent then so is $S$”

Note: Consistency results are meta theorems.

Interpretability Hierarchy

Let $T_1$ and $T_2$ denote recursively enumerable sets of axioms. We say that $T_1$ is interpretable in $T_2$, denoted $T_1\le T_2$, if there is a translation $\tau$ from the language of $T_1$ to the language of $T_2$ such that for each sentence $\phi$ of $T_1$, $T_1⊢\phi ⟹T_2⊢\phi$.

$T_1<T_2$ if $T_1\le T_2$ and $T_2\nleqq T_1$ ($T_2$ can interpret $T_1$, but $T_1$ cannot interpret $T_2$)

$T_1\equiv T_2$, denotes that $T_1$ and $T_2$ are mutually interpretable, that is, $T_1\le T_2$ and $T_2\le T_1$ (i.e., they interpret each other). The equivalence class of all theories mutually interpretable with $T$ is called the interpretability degree of $T$.

Connection to Relative Consistency…

Proof-Theoretic Ordinals

An alternative way to determine the consistency strength of a theory.

The proof theoretic ordinal of a theory $T$ is the supremum of the order types of all ordinal notations that $T$ can prove is well-founded. That is, the supremum of all ordinal $\alpha$ for which there exists a notation $o$ such that $T$ proves that $o$ is an ordinal notation.

Let $\alpha$ be the proof theoretic ordinal of the theory $T$ and $\beta$ the proof-theoretic ordinal of another axiomatic theory $S$. If $\alpha \le \beta$, then $T\le S$ in consistency strength ($S$ is at least as strong as $T$).

Theories with the same proof-theoretic ordinals are equiconsistent.

Note: By necessity, the ordinal notations must be recursive, and so the supremum of proof-theoretic ordinals is the Church-Kleene ordinal ${\omega }_1^{CK}$. If a theory has a proof-theoretic ordinal equal or greater than ${\omega }_1^{CK}$, then it is inconsistent.

Transfinite Recursions of Consistency

(Turing PhD Thesis)

Defined recursively as follows:

• $T_0^{Con}:=T$
• $T_{\alpha +1}^{Con}:=T_{\alpha }^{Con}+Con(T_{\alpha }^{Con})$
• $T_{\lambda }^{Con}:=\bigcup _{\alpha <\lambda }{T}_{\alpha }^{Con}$ for $\lambda$ is a limit ordinal

This procedure has limit stage $T_{{\omega }_1^{CK}}^{Con}$

The ${\Sigma }_1$-reflection principle (or the uniform reflection principle):

A stronger form of consistency such that $T+RF{N}_{{\Sigma }_1}(T)$ proves the consistency of $T_n^{Con}$ for $n<w$. Thus, $T+RF{N}_{{\Sigma }_1}(T)$ is equivalent to $T_{\omega }^{Con}$. From this, we can define similarly:

• $T_0^{RFN}:=T$
• $T_{\alpha +1}^{RFN}:=T_{\alpha }^{RFN}+RFN(T_{\alpha }^{RFN})$
• $T_{\lambda }^{RFN}:=\bigcup _{\alpha <\lambda }{T}_{\alpha }^{RFN}$

This procedure can continue via considering stronger reflection principles.

References

The Hierarchy of Large Cardinals Ultraproducts & Ultrafilters [Ordinal Analysis](Ordinal analysis - Wikipedia)