打开/关闭菜单
打开/关闭外观设置菜单
打开/关闭个人菜单
未登录
未登录用户的IP地址会在进行任意编辑后公开展示。

证明论序数

来自Googology Wiki

证明论序数(或称证明论强度序数,Proof-Theoretic Ordinal)是衡量形式理论强度的核心工具,通过将理论映射到序数上,刻画其能证明的良序关系的复杂度。该概念源于希尔伯特的证明论计划,旨在通过有限方法证明数学基础理论的一致性,后由阿克曼(Wilhelm Ackermann)和根岑(Gerhard Gentzen)发展为序数分析技术。

定义和性质

对形式理论 T,其证明论序数 |T|ord​(|T|PTO(T))定义为能用超限归纳证明的原始递归良序的序型最大值。

证明论序数满足:

  1. 对任意递归序数 β<|T|,理论 T 能证明“所有序数小于 β 的原始递归良序关系都是良序的”;对 α=|T|,理论 T 无法证明“所有序数小于 α 的原始递归良序关系都是良序的”。
  2. 存在一种递归记号系统,自然表示所有小于 |T| 的序数;理论 T 能通过超限归纳(序数是良序集的序型,满足超限归纳原理:α(β<α(P(β)P(α))αP(α)),其中 P 是任意性质)到 |T|,证明自身的一致性(即 T);理论 T 能证明所有初等递归函数在小于 |T| 的序数上总停止;对任意递归序数 β<|T|,至少不满足上述条件中的一条。
  3. 证明论序数必为递归序数(recursive ordinal),即存在递归关系定义其良序。

证明论序数表

证明论序数 算术论体系 集合论体系 其他体系
Q KP
ω2 RFA
IΔ0
ω3 RCA0*
WKL0*
IΔ0+exp
ωn IΔ0+n is total
ωω RCA0
WKL0
PRA
RCA02
CPRC
KP+Π1set Fondation+IND
ωωωω RCA0+(Π20)IND
ω(n+2) IΣn+1
ε0 PA
ACA0
Δ11CA0
Σ11AC0
KP EM0
ε1 ACA0+KPHT
εω ACA0+iRT
RCA0+YnX(TJ(n,X,Y))
εε0 ACA
FPnACA'0
FPnACA
ζ0 ACA0+XY(TJ(ω,X,Y))
ACA0+(BR)
p1(ACA0)
φ(2,ε0) ACA+XY(TJ(ω,X,Y))
RFN
φ(ω,0) Δ11CR
RCA0*+Π11CA
Σ11DC0
ID1#
EM0+JR
PID
AccID(Acc)
(Π00(P),PN)ID
(Π00(P),PN)ID(Acc)
φ(ν+1,0) ACA0+XY(TJ(ων,X,Y))
ψ(Ωε0) Δ11CA
Σ11AC
(Π10CA)<ε0
ψ(Ωψ(Ωω)) PRS ω
Γ0 ATR0
Δ11CA+BR
RCA0+Σ10RT
RCA0+Δ10RT
RCA0+Σ10det.
RCA0+Δ10det.
FP0
KPi
CZF+INAC
ID^<ω
ID^*
ML<ω
MLU
U(PA)
φ(1,0,ωω) KPl0+(Σ1Iω)
φ(1,0,ε0) ATR ID^ω
ψ(ΩΩ+1) RCA0+XM(XMMωATR0)
ψ(ΩΩ+ω) ATR0+Σ11DC ID^<ωω
ψ(ΩΩ+ε0) ATR+Σ11DC ID^<ε0
ψ(ΩΩ+Γ0) ID^<Γ0
MLS
φ(2,0,0) FTR0 KPh Aut(ID^)
φ(2,0,ε0) FTR
φ(2,ε0,0) KPh0+(FIω)
ψ(ΩΩω) KPM
φ(ε0,0,0) Σ11TDC
φ(1,0,0,0) p1(Σ11TDC0)
ψ(ΩΩω) RCA0*+Π11CA
p3(ACA0)
FIT
TID
ϑ(ΩΩ) p1(p3(ACA0))
θ(n+2)(Ωω)0 ACA0+Πn+21BI
Πn+11RFN
(Πn+21BI)0
(Πn+21BI)0
KPω+Πn+2setFoundation
θ(n+2)(Ωω)0 ACA+Πn+21BI
(Πn+21BI)
KPω+IND+Πn+2setFoundation
ψ(ψ1(0)) ACA+BI
ACA0+Π11CA
Π10FXP0
KP
KP+Π2setReflection
KP+(BI*)
KP+(ATR0*)
CZF
KPω2+Δ1CA+sΠ11ref
ID1
ID12
ML1 V
ψ(Ω2) RCA0+XM(XMMωACA+BI)
ψ(Ω2Ω2) ATR0
FP0
Σ11DC0+(SUB)
Σ11AC0+(SUB)
ID^<ω𝒰(ID1)
ψ(ψ2(0)) KP+ω1CK ID2
ID22
ψ(Ωω) Π11CA0
Δ21CA0
RCA0+Σ10Π10det.
RCA0+Δ20RT
KPlr
KPir
KPβr
ID<ω
(ID<ω2)0
ψ(Ωωωω) Π11CA0+Π21IND
ψ(Ωωε0) Π11CA WKPl WIDω
ID<ω2
ψ(ΩωΩ) Π11CA+BR
ψ(Ωωω) Π11CA0+Π21BI
ψ(Ωωωω) Π11CA0+Π21BI+Π31IND
ψ(ψω(0)) Π11CA+BI KPl IDω
BIDω2
ψ(Ωωω) Δ21CR
(Π11CA<ωω)
KPlωωr ID<ωω
ψ(Ωε0) Δ21CA
Σ21AC
(Π11CA<ε0)
KPlε0r
WKPi
WKPβ
ID<ε0
ID<ε02
BID<ε02
ψ(Ωνω) (Π11CAν+)0 KPlν+r ID<νω
(PIDν2)0
ψ(Ωγω) (Π11CAγ)0 KPlγr (NUIDγ2)0
ψ(Ωνωε0)) Π11CAν+ WKPlν+ WIDνω
PIDν2
ψ(Ωγε0) (Π11CAγ)
Π11CAγ
WKPlγ WIDγ
IDγ2
NUIDγ2
ψ(ΩνωΩ)) Π11CAν++BR PIDν2+BR
ψ(ΩγΩ) Π11CAγ+BR NUIDγ2+BR
ψ(Ωωγ) (Π11CAωγ)0
(Π11CA<ωγ)
(Π11CA<ωγ)+BI
(IDωγ2)0
ID<ωγ
BID<ωγ2
(ID<ν2)+BI
ψ(ψν(0)) (Π11CAν)0 KPlν IDν
(IDν2)0
ψ(ψν(ε0)) Π11CAν IDν2
ψ(ψν(Ω)) Π11CAν+BR IDν2+BR
ψ(ψν(ψν(0))) BIDν2
ψ(ψν+1(0)) Π11CAν+BI KPlν+1 IDν+1
IDν2+BI
ψ(ψνω(0)) Π11CAν++BI KPlν+ IDνω
PIDν2+BI
PBIDν2
ψ(ψγ(0)) (Π11CAγ)0
(Π11CAγ)+BI
Π11CAγ+BI
KPlγ IDγ
(IDγ2)0
IDγi(𝒪)BIDν2
IDγ2+BI
NUIDγ2+BI
ψ(ψΩ(0)) KPl*
KPlΩr
ID*
BID2*
ID2*+BI2
ψΩ1(ψI(0)) Π11TR0
Π11TR0+Δ21CA0
Δ21CA+BI(impl Σ21)
Δ21CA+BR(impl Σ21)
RCA0+Δ20det.
RCA0+Δ11RT
AutKPlr
AutKPlr+KPir
KPiω+FOUNDR(implΣ)
KPiω+FOUND(implΣ)
AutID0pos
AutID0mon
ψΩ1(ψI(0)ε0) Π11TR WAutKPl AutIDpos
AutIDmon
AutKPlω
ψΩ1(ψΩψI(0)+1(0)) Π11TR+BI AutKPl AutID2pos
AutID2mon
AutBID
ψΩ1(ψI(Iω)) Δ21TR0
Σ21TRDC0
Δ21CA0+Σ21BI
KPir+(ΣFOUND)
KPir+(ΣREC)
ψΩ1(ψI(Iε0)) Δ21TR
Σ21TRDC
Δ21CA+Σ21BI
KPiω+(ΣFOUND)
KPiω+(ΣREC)
ψΩ1(εI+1) Δ21CA+BI
Σ21AC+BI
KPi
KPβ
CZF+REA
T0
ψΩ1(ΩI+ω) KPi+ ML1 W
KP1 W
IARI
ψΩ1(εM+1) Δ21CA+BI+(M) KPM
CZFM
ψΩ1(ΩM+ω) KPM+ MLM
Agda
ΨΩ10(εK+1) ACA+BI+Π41β-model-Reflection KP+Π3set-Reflection
Ψ𝕏εξn+1 ACA+BI+Πn+51β-model-Reflection KP+Πn+4set-Reflection
Ψ𝕏εΞ+1 ACA+BIβ-model-Reflection KP+Πωset-Reflection
ΨεΥ+1 KPi+ακ(Lκ1Lκ+α)
ψ(Ω𝕊+ω) Π11CA0+Π21CA KPlr+M(Trans(M)M1V)
Ψ𝕂εI+1 Δ21CA+BI+Π21CA KPi+M(Trans(M)M1V)
ωω1CK Π21CA0
Δ31CA0
ω+1ω1CK Π21CA+BI KP+Σ1setSeparation
KPi+αβ(β>α)(β stable)
ε0ω1CK Δ31CA
Σ31AC
maybe ψΩ(ε𝕀+1) Δ31CA+BI
Σ31AC+BI
Σ31DC+BI
KP+Δ2set-Separation
ψΩ(ε𝕀+1) KP+Π1set-Collection
Πn+31CA+BI KP+Σn+2set-Separation
Πn+31CA+Σn+31AC+BI KP+Σn+2set-Separation+Σn+2set-Collection
Z2=Π1CA
Δ12CA0
Z2+Σ1AC
KP+Σωset-Separation
KP+Σωset-Separation+Σωset-Collection
ZFC=ZFCPowerset
Zn+3=Πn+2CA
Δ1n+3CA0
ZFC+V=L+ωn+1
Z=Π0CA Z
ZC
IZ
IZF=CZF+Powerset+ΠωsetReflection
ZF=CZF+LEM=IZF+LEM
ZFC
ZFC+V=L
AST
IST
NBG=GBC
GB

ZFC 相关证明论序数:

  • S0=(Ext)+(Null)+(Pair)+(Union)+(Diff) (Rudimentary set theory)
  • S1=S0+(Powerset)
  • M0=S1+(Δ0setSeparation)
  • M1=M0+(Regularity)+(Transitive Containment)
  • KP=S0+(Infinity)+(Δ0setSeparation)+(Δ0setCollection)
  • KP=S0+(Foundation)+(Δ0setSeparation)+(Δ0setCollection)
  • KP=KP+(Infinity)=KP+(Foundation)
  • KPl=KP+(universe limit of admissible sets)
  • KPi=KP+(recursively inaccessible universe)
  • KPh=KP+(recursively hyperinaccessible universe)
  • KPM=KP+(recursively Mahlo universe)
  • ZBQC=M0+(Regularity)+(Infinity)+(Choice)
    NFU+(Infinity)+(Choice)
  • MAC=M1+(Infinity)+(Choice)=ZBQC+(Transitive Containment)
  • MOST=MAC+(Δ0setCollection)=ZBQC+KP+(Σ1setSeparation)
  • Z=S1+(Regularity)+(Infinity)+(ΣωsetSeparation)
  • ZC=Z+(Choice)=ZBQC+(σωsetSeparation)
  • MAC+m(m exists)
    NFU+(Infinity)+(Choice)
  • Z+(Π2setReplacement)
    NFU*=NFU+(Counting)+(Strongly Cantorian Separation)
  • Z+(ΠmsetReplacement)
  • ZF=Z+(ΠωsetReplacement)
    AST
    GB
  • ZFC=ZF+(Choice)
    NBG=GBC=GB+(Global Choice)
  • ZFC+(there is a worldly cardinal)
  • NBG+(there is a stationary proper class of worldly cardinals)
  • NBG+(Class Forcing Theorem)
    NBG+(Clopen Class Game Determinacy)
  • MK=NBG+(ΠclassCA)
  • ZFC+(there is an inaccessible cardinal)
    ZFC+(Π11 Perfect Set Property)
    ZFC+(Σ31 Lebesgue measurability)
  • ZFC+(there are ω inaccessible cardinals)
    ZFC+(α(ωαω|VαL|=|α|))
  • ZFC+(there is a proper class of inaccessible cardinals)
    ZFC+(Grothendieck Universe Axiom)
  • ZFC+(there is a Σnset-reflecting cardinal)
  • ZFC+(there is a σωset-reflecting cardinal)
    ZFC+(Ord is Mahlo)
  • ZFC+(there is an uplifting cardinal)
    ZFC+(Resurrection Axioms)
  • ZFC+(there is a Mahlo cardinal)
  • SMAH=ZFC+(there is a n-Mahlo cardinal)n
    NFUA=NFU+(Infinity)+(Cantorian Sets)
  • SMAH+=ZFC+n(there is a n-Mahlo cardinal)
  • MK+(Ord is weakly compact)
    GPK+=GPK++(Infinity)
    NFUB=NFU+(Infinity)+(Cantorian Sets)+(Small Ordinals)
  • ZFC+(there is a weakly compact cardinal)
    ZFC+(ω2 has the tree property)
  • ZFC+(there is a totally indescribable cardinal)
  • ZFC+(there is a subtle cardinal)
  • ZFC+(there is an ineffable cardinal)
  • ZFC+α(α<ω1there is a α-Erdős cardinal)
  • ZFC+(0 exists)
    ZFC+(Lω is regular)
    ZFC+α(αω|VαL|=|α|)
    ZFC+(parameter-free Σ11-determinacy)
  • ZFC+x (xx exists)
    ZFC+(Σ11-determinacy)
  • ZFC+x (x exists)
    ZFC+(Σ21 universal Baireness)
  • ZFC+(there is an ω1-Erdős cardinal)
    ZFC+(Chang's Conjecture)
  • SRP=ZFC+(there is cardinal with the n-stationary Ramsey property)n
  • SRP+=ZFC+n (there is a cardinal with the n-stationary Ramsey property)
  • MK+(Ord is measurable)
    NFUM=NFU+(Infinity)+(Large Ordinals)+(Small Ordinals)
  • ZFM=ZFC+(there is a measurable cardinal)
    ZFC+(NSω1 is precipitous)
    ZF+(ω1 is measurable)
  • ZFC+(there is a measurable cardinal κ such that o(κ)=2)
    ZFC+(NSω2 is precipitous)
  • ZFC+(there is a measurable cardinal κ such that o(κ)=κ++)
    ZFC+¬SCH
    ZFC+(2ω=ω+2)
  • ZFC+(Ord is Woodin)
    ZFC+¬SCH
    Z2+(Δ21-determinacy) (conjectural)
  • MK+(Ord is Woodin)
    ZFC+¬SCH
    Z3+(lightface Δ21-determinacy)
  • NBG+(Ord is Woodin)
    ZFC+¬SCH
    Z3+(Δ21-determinacy)
  • ZFC+(there is a Woodin cardinal)
    ZFC+(Δ21-determinacy)
    ZFC+(ODAD)
    ZFC+(NSω1 is ω2-saturated)
  • ZFC+(there are n Woodin cardinals)n
    Z2+(PD)
  • ZFC+(there are ω Woodin cardinals)
    ZF+(AD)
    ZFC+(L()AD)
    ZFC+(OD()AD)
  • ZF+DC+(ω1 is 𝒫(ω1)-strongly compact)
    ZFC+(NSω1 is ω1-dense)
  • ZF+DC+(ω1 is 𝒫()-strongly compact)
    ZF+DC+(AD)
  • ZFC+(there is a superstrong cardinal)
  • ZFC+(there is a subcompact cardinal)
    ZFC+(V=L[E])+κ(¬κ)
  • ZFC+(there is a strongly compact cardinal)
    ZFC+(Proper Forcing Axiom)
  • ZFC+(there is a supercompact cardinal)
    ZFC+(Martin's Maximum)
  • ZFC+n(there is a proper class of C(n)-extendible cardinals)
    ZFC+(Vopěnka's Principle)
  • ZFC+(there is a high-jump cardinal)
  • HUGE=ZFC+( there is a n-huge cardinal )n
  • ZFC+(Wholeness Axiom WAn)
  • ZFC+I3=ZFC+λ(E0(λ))
  • ZFC+I2=ZFC+λ(E1(λ))
  • ZFC+I1=ZFC+λ(Eω(λ))
  • ZFC+I0
  • ZF+DC+λj:Vλ+2ΣωsetVλ+2
  • ZFj+DC+(there is a Reinhardt cardinal )
  • ZF+DC+(there is a Berkeley cardinal)