Difference between revisions of "User-blog:Julian Barathieu/Ordinal analyses"

From Cantor's Attic
Jump to: navigation, search
(Created page with "Currently in construction. Do not edit. == Arithmetical theories == == Set theories == == Ordinal-collapsing functions == == Table of proof-theoretic ordinals and their co...")
 
 
(4 intermediate revisions by the same user not shown)
Line 15: Line 15:
 
! Set theories
 
! Set theories
 
! References
 
! References
! Ordinal name
+
! Notes
 +
|-
 +
| $\omega^\omega$
 +
| $\text{RCA}_0,\text{WKL}_0$
 +
|
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
|
 
|-
 
|-
 
| $\varepsilon_0$
 
| $\varepsilon_0$
| $ACA_0$
+
| $\text{ACA}_0$
| $KP\setminus Inf$
+
| $\text{KP}\setminus\text{\{Infinity\}}$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf][http://www.mathematik.uni-muenchen.de/~buchholz/articles/BuchholzGentzCent1.pdf]
 +
| First epsilon number
 +
|-
 +
| $\varepsilon_{\varepsilon_0}$
 +
| $\text{ACA}$
 
|
 
|
| Epsilon zero
+
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
|
 +
|-
 +
| $\psi_{\Omega_1}(\Omega^{\omega})=\varphi(\omega,0)$
 +
| $\Delta^1_1-\text{CR}$
 +
|
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
|
 +
|-
 +
| $\psi_{\Omega_1}(\Omega^{\varepsilon_0})=\varphi(\varepsilon_0,0)$
 +
| $\Delta^1_1-\text{CA},\Sigma^1_1-\text{AC}$
 +
|
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
|
 +
|-
 +
| $\psi_{\Omega_1}(\Omega^\Omega)=\Gamma_0$
 +
| $\text{ATR}_0,\Delta^1_1-\text{CA}+\text{BR}$
 +
| $\text{KPi}^-,\text{CZF}^-+\exists\kappa(\kappa\text{ is inaccessible})$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
|
 +
|-
 +
| $\theta(\delta_n,0)$
 +
| $\text{ACA}_0+(\Pi^1_{n+1}-\text{BI})$
 +
| $\text{KP}^-+(\Pi_{n+1}-\text{Foundation})$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/FRAGMENT.pdf]
 +
| $\delta_1=\Omega^\omega,\delta_{n+1}=\Omega^{\delta_n}$
 +
|-
 +
| $\theta(\eta_n,0)$
 +
| $\text{ACA}+(\Pi^1_{n+1}-\text{BI})$
 +
| $\text{KP}^-+\text{IND}+(\Pi_{n+1}-\text{Foundation})$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/FRAGMENT.pdf]
 +
| $\eta_1=\Omega^{\varepsilon_0},\eta_{n+1}=\Omega^{\eta_n}$
 
|-
 
|-
| $\psi_0(\varepsilon_{\Omega+1})$
+
| $\psi_{\Omega_1}(\varepsilon_{\Omega+1})$
| $ACA+BI$
+
| $\text{ACA}+\text{BI}$
| $KP$
+
| $\text{KP}$
 
| [https://www1.maths.leeds.ac.uk/~rathjen/realm.pdf]
 
| [https://www1.maths.leeds.ac.uk/~rathjen/realm.pdf]
 
| Bachmann-Howard ordinal
 
| Bachmann-Howard ordinal
 
|-
 
|-
| $\psi_0(\Omega_\omega)$
+
| $\psi_{\Omega_1}(\Omega_\omega)$
| $\Pi^1_1-CA_0, \Delta^1_2-CA_0$
+
| $\Pi^1_1-\text{CA}_0, \Delta^1_2-\text{CA}_0$
 
|
 
|
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
|
 
|
 
|-
 
|-
| $\psi_0(\Omega_\omega\epsilon_0)$
+
| $\psi_{\Omega_1}(\Omega_\omega\varepsilon_0)$
| $\Pi^1_1-CA$
+
| $\Pi^1_1-\text{CA}$
 
|
 
|
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
|
 
|
 
|-
 
|-
| $\psi_0(\varepsilon_{\Omega_\omega+1})$
+
| $\psi_{\Omega_1}(\varepsilon_{\Omega_\omega+1})$
| $\Pi^1_1-CA+BI$
+
| $\Pi^1_1-\text{CA}+\text{BI}$
|
+
| $\text{KPl}$
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
| Takeuti-Feferman-Buchholz ordinal
 
| Takeuti-Feferman-Buchholz ordinal
 
|-
 
|-
| $\psi_0(\Omega_{\varepsilon_0})$
+
| $\psi_{\Omega_1}(\Omega_{\omega^\omega})$
| $\Delta^1_2-CA$
+
| $\Delta^1_2-\text{CR}$
 
|
 
|
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 
|
 
|
 
|-
 
|-
 +
| $\psi_{\Omega_1}(\Omega_{\varepsilon_0})$
 +
| $\Delta^1_2-\text{CA}$
 +
|
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
|
 +
|-
 +
| $\psi_{\Omega_1}(\varepsilon_{\mathcal{I}+1})$
 +
| $\Delta^1_2-\text{CA}+\text{BI}$
 +
| $\text{KPi}$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf]
 +
| $\mathcal{I}$ is the least weakly inaccessible cardinal
 +
|-
 +
| $\psi_{\Omega_1}(\Omega_{\mathcal{I}_\omega})$
 +
|
 +
| $\text{KPh}$
 +
|
 +
|
 +
|-
 +
| $\psi_{\Omega_1}(\varepsilon_{\mathcal{M}+1})$
 +
| $\Delta^1_2-\text{CA}+\text{BI}+\text{(M)}$
 +
| $\text{KPM}$
 +
| [http://www.mathematik.uni-muenchen.de/~buchholz/articles/M1.pdf][https://pdfs.semanticscholar.org/a3ff/6ef9ca7db754139d541dbae579a73ee784db.pdf]
 +
| $\mathcal{M}$ is the least weakly Mahlo cardinal
 +
|-
 +
| $\psi_{\Omega_1}(\Omega_{\mathcal{M}+\omega})$
 +
|
 +
| $\text{KPM}^+$
 +
|
 +
|
 +
|-
 +
| $\Psi^0_{\Omega_1}(\varepsilon_{\mathcal{K}+1})$
 +
| $\text{ACA}+\text{BI}+(\Pi^1_4-\beta\text{-model Reflection})$
 +
| $\text{KP}+(\Pi_3-\text{Reflection})$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/Ehab.pdf]
 +
| $\mathcal{K}$ is the least $\Pi^1_1$-indescribable cardinal
 +
|-
 +
| $\Psi^{\varepsilon_{\Xi+1}}_\mathbb{X}$
 +
| $\text{ACA}+\text{BI}+\beta\text{-model Reflection}$
 +
| $\text{KP}+(\Pi_\omega-\text{Reflection})$
 +
| [https://d-nb.info/1017849250/34]
 +
| $\Xi$ is the least $\Pi^2_0$-indescribable cardinal
 +
|-
 +
| $\Psi^{\varepsilon_{\Upsilon+1}}_\mathbb{H}$
 +
|
 +
| $\text{Stability},\text{KPi}+\forall\alpha\exists\kappa$ $L_\kappa\prec_1 L_{\kappa+\alpha}$
 +
| [https://d-nb.info/1017849250/34][https://www1.maths.leeds.ac.uk/~rathjen/NSTAB.ps]
 +
| $\Upsilon$ is the least subtle cardinal
 +
|-
 +
| $\Psi^{\varepsilon_{\mathbf{\text{I}}+1}}_\mathbb{K}$
 +
| $\Delta^1_2-\text{CA}+\text{BI}+\text{ parameter-free}$ $\Pi^1_2-\text{CA}$
 +
| $\text{KP}+\exists M(\text{Trans(M)}\land M\prec_1 V)$
 +
| [https://www1.maths.leeds.ac.uk/~rathjen/pime.pdf]
 +
| See (*)
 
|}
 
|}
  
 
+
== Notes ==
- $\text{ACA}_0 + $ Kruskal's Tree Theorem (full analysis), $\text{ACA}_0 + \Pi^1_n-\text{BI}$ (full analysis):
+
(*) $\mathbf{\text{I}}$ is not the least weakly inaccessible $\mathcal{I}$. It has a somewhat technical definition; cf the reference given.
https://www1.maths.leeds.ac.uk/~rathjen/KRUSKAL.neu.pdf
+
<!-- phi(A,B,C,D) = psi() -->
 
+
 
+
- Fragments of KP (restricted foundation) (full analysis): [https://www1.maths.leeds.ac.uk/~rathjen/FRAGMENT.pdf]
+
 
+
- $\text{KPi}$, $\Delta^1_2-\text{CA+BI}$ (full cut elimination): [https://arxiv.org/pdf/1606.04194.pdf]
+
 
+
- $\text{KPM}$ (full analysis): [https://www1.maths.leeds.ac.uk/~rathjen/WELL.pdf], [https://www1.maths.leeds.ac.uk/~rathjen/KPM-Ordinal-Analysis.pdf]
+
 
+
- $\Delta^1_2-\text{CA+BI +}$ parameter-free $\Pi^1_2-\text{CA}$ (full analysis): [https://www1.maths.leeds.ac.uk/~rathjen/pime.pdf]
+
 
+
- $\text{KP +}$ strong reflection principles (full analysis): [https://d-nb.info/1017849250/34]
+
 
+
- $\text{Stability}, \text{KP +}$ "for all $\alpha$, there is a $\alpha$-stable ordinal " (full analysis): [https://d-nb.info/1017849250/34], [https://www1.maths.leeds.ac.uk/~rathjen/NSTAB.ps]
+
 
+
- $\Pi^1_2-\text{CA}_0, \Pi^1_2-\text{CA+BI}, \Delta^1\_3-\text{CA}$: [https://www1.maths.leeds.ac.uk/~rathjen/BULF.pdf]
+
 
+
- $\text{KP + V=L +}$ "there is an uncountable regular cardinal" (full cut elimination): [https://arxiv.org/pdf/1801.10025.pdf]
+
 
+
https://www1.maths.leeds.ac.uk/~rathjen/Sepp-chiemsee.pdf
+
- Pi^1\_1-CA0, ID<w, Pi^1\_1-CA
+
- Pi^1\_1-CA+BI, IDw, Delta^1\_2-CR
+
- Delta^1\_2-CA, Delta^1\_2-CA+BI = KPi
+

Latest revision as of 12:59, 12 February 2018

Currently in construction. Do not edit.

Arithmetical theories

Set theories

Ordinal-collapsing functions

Table of proof-theoretic ordinals and their corresponding theories

Proof-theoretic ordinal Arithmetical theories Set theories References Notes
$\omega^\omega$ $\text{RCA}_0,\text{WKL}_0$ [1]
$\varepsilon_0$ $\text{ACA}_0$ $\text{KP}\setminus\text{\{Infinity\}}$ [2][3] First epsilon number
$\varepsilon_{\varepsilon_0}$ $\text{ACA}$ [4]
$\psi_{\Omega_1}(\Omega^{\omega})=\varphi(\omega,0)$ $\Delta^1_1-\text{CR}$ [5]
$\psi_{\Omega_1}(\Omega^{\varepsilon_0})=\varphi(\varepsilon_0,0)$ $\Delta^1_1-\text{CA},\Sigma^1_1-\text{AC}$ [6]
$\psi_{\Omega_1}(\Omega^\Omega)=\Gamma_0$ $\text{ATR}_0,\Delta^1_1-\text{CA}+\text{BR}$ $\text{KPi}^-,\text{CZF}^-+\exists\kappa(\kappa\text{ is inaccessible})$ [7]
$\theta(\delta_n,0)$ $\text{ACA}_0+(\Pi^1_{n+1}-\text{BI})$ $\text{KP}^-+(\Pi_{n+1}-\text{Foundation})$ [8] $\delta_1=\Omega^\omega,\delta_{n+1}=\Omega^{\delta_n}$
$\theta(\eta_n,0)$ $\text{ACA}+(\Pi^1_{n+1}-\text{BI})$ $\text{KP}^-+\text{IND}+(\Pi_{n+1}-\text{Foundation})$ [9] $\eta_1=\Omega^{\varepsilon_0},\eta_{n+1}=\Omega^{\eta_n}$
$\psi_{\Omega_1}(\varepsilon_{\Omega+1})$ $\text{ACA}+\text{BI}$ $\text{KP}$ [10] Bachmann-Howard ordinal
$\psi_{\Omega_1}(\Omega_\omega)$ $\Pi^1_1-\text{CA}_0, \Delta^1_2-\text{CA}_0$ [11]
$\psi_{\Omega_1}(\Omega_\omega\varepsilon_0)$ $\Pi^1_1-\text{CA}$ [12]
$\psi_{\Omega_1}(\varepsilon_{\Omega_\omega+1})$ $\Pi^1_1-\text{CA}+\text{BI}$ $\text{KPl}$ [13] Takeuti-Feferman-Buchholz ordinal
$\psi_{\Omega_1}(\Omega_{\omega^\omega})$ $\Delta^1_2-\text{CR}$ [14]
$\psi_{\Omega_1}(\Omega_{\varepsilon_0})$ $\Delta^1_2-\text{CA}$ [15]
$\psi_{\Omega_1}(\varepsilon_{\mathcal{I}+1})$ $\Delta^1_2-\text{CA}+\text{BI}$ $\text{KPi}$ [16] $\mathcal{I}$ is the least weakly inaccessible cardinal
$\psi_{\Omega_1}(\Omega_{\mathcal{I}_\omega})$ $\text{KPh}$
$\psi_{\Omega_1}(\varepsilon_{\mathcal{M}+1})$ $\Delta^1_2-\text{CA}+\text{BI}+\text{(M)}$ $\text{KPM}$ [17][18] $\mathcal{M}$ is the least weakly Mahlo cardinal
$\psi_{\Omega_1}(\Omega_{\mathcal{M}+\omega})$ $\text{KPM}^+$
$\Psi^0_{\Omega_1}(\varepsilon_{\mathcal{K}+1})$ $\text{ACA}+\text{BI}+(\Pi^1_4-\beta\text{-model Reflection})$ $\text{KP}+(\Pi_3-\text{Reflection})$ [19] $\mathcal{K}$ is the least $\Pi^1_1$-indescribable cardinal
$\Psi^{\varepsilon_{\Xi+1}}_\mathbb{X}$ $\text{ACA}+\text{BI}+\beta\text{-model Reflection}$ $\text{KP}+(\Pi_\omega-\text{Reflection})$ [20] $\Xi$ is the least $\Pi^2_0$-indescribable cardinal
$\Psi^{\varepsilon_{\Upsilon+1}}_\mathbb{H}$ $\text{Stability},\text{KPi}+\forall\alpha\exists\kappa$ $L_\kappa\prec_1 L_{\kappa+\alpha}$ [21][22] $\Upsilon$ is the least subtle cardinal
$\Psi^{\varepsilon_{\mathbf{\text{I}}+1}}_\mathbb{K}$ $\Delta^1_2-\text{CA}+\text{BI}+\text{ parameter-free}$ $\Pi^1_2-\text{CA}$ $\text{KP}+\exists M(\text{Trans(M)}\land M\prec_1 V)$ [23] See (*)

Notes

(*) $\mathbf{\text{I}}$ is not the least weakly inaccessible $\mathcal{I}$. It has a somewhat technical definition; cf the reference given.