葛立恒数二吧 关注:874贴子:67,677
  • 24回复贴,共1

OCF的三大类定义

只看楼主收藏回复

粗略看来,OCF在定义上分为三大类:ψ型、θ型、𝜗型。
从最简单的定义开始。
ψ型定义:
C(α,0) = {0,Ω}
C(α,i+1) = {γ+δ | γ,δ∈C(α,i)} ∪ {ψ(γ) | γ∈C(α,i) ∧ γ<α}
C(α) = ⋃{C(α,i) | i<ω}
ψ(α) = min(Ω\C(α)) = min{β<Ω | β∉C(α)}
θ型定义:
C(α,β,0) = β∪{0,Ω}
C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {θ(γ,δ) | γ,δ∈C(α,β,i) ∧ γ<α}
C(α,β) = ⋃{C(α,β,i) | i<ω}
A(α) = {β | β∉C(α,β)}
θ(α,β) = min{γ∈A(α) | ∀δ<β(θ(α,δ)<γ)} = A(α)中的从小到大第1+β个序数
𝜗型定义:
C(α,β,0) = β∪{0,Ω}
C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {𝜗(γ) | γ∈C(α,β,i) ∧ γ<α}
C(α,β) = ⋃{C(α,β,i) | i<ω}
𝜗(α) = min{β<Ω | C(α,β)∩Ω⊆β ∧ α∈C(α,β)}
仅从这段最简单的定义看,强度上ψ型 < 𝜗型 < θ型。
ψ型的极限:ψ(Ω+Ω+…Ω+Ω) = ε(ω) = 𝜗(Ω+ω) = θ(1,ω)
𝜗型的极限:𝜗(Ω+Ω+…Ω+Ω) = φ(ω,0) = θ(ω,0)
而θ型的极限要高得多。甚至,θ型OCF,即便不使用任何序数,不使用Ω,也就是把定义的第一行弱化成“C(α,β,0) = β∪{0}”,它的极限:θ(θ(…θ(θ(0,0),0)…,0),0) = Γ(0)。【思考:它跟二元φ函数有怎样的联系?】
而用到了Ω的θ型OCF,其极限:θ(θ(θ(…θ(Ω,Ω)…,Ω),Ω),0),超过BHO。
但是,随着大序数的不断加入,OCF变得更强、更复杂,最终的强度会呈现ψ型 ≈ θ型 < 𝜗型的现象。


IP属地:北京本楼含有高级字体1楼2022-07-31 12:20回复
    稍加解释一下。
    ψ型定义是三大类定义之中最简单的一个。首先,当你看到这个定义的时候(总共有4行),你会觉得好像循环定义了,因为C的定义里有ψ,而ψ的定义里又有C。但其实没有循环定义。它实质上是个归纳的定义。归纳变元在C的第一个参数以及ψ的括号中的α。
    首先,C(0)不依赖任何ψ值。定义好C(0)之后,可以定义ψ(0)。在此之后,定义C(1),然后定义ψ(1)。然后定义C(2),然后ψ(2)。当所有C(n)、ψ(n)都定义好之后,可以定义C(ω),然后ψ(ω)。然后C(ω+1),然后ψ(ω+1),等等。序数上的超限归纳允许我们如此定义,最终使得C与ψ对所有序数都有定义。
    直观上理解,C(α)意味着“从0和Ω出发,用加法和以前定义过的ψ(即你放进ψ里面的序数必须小于α),能在有限步内构造出的所有序数”之集合。ψ(α)则是这种方式不能得到的最小可计算(即小于Ω)序数。
    θ型定义也可以如法炮制。不过它是个二元函数。
    首先,它的归纳变元在于C的第一个参数,A的参数,以及θ的第一个参数。
    直观上理解,C(α,β)意味着“从0、Ω以及小于β的序数出发,用加法和以前定义过的θ(即你放进θ里面的第一参数必须小于α),能在有限步内构造出的所有序数”之集合。A(α)则是“依此法,不能用小于β的序数得到β”的那些序数β组成的序数类。θ(α,β)则是A(α)中的第1+β个序数,即A(α)的计数。
    注意:θ(α,β)中的β可以是Ω甚至更大。例如θ(0,Ω) = Ω·ω,θ(0,Ω+1) = Ω·ω^2,θ(1,Ω) = ε(Ω+1),θ(Ω,Ω) = φ(Ω,1),θ(Ω+1,Ω) = φ(Ω+1,0),等等。
    𝜗型理解起来可能有点复杂。
    首先,它的归纳变元在于C的第一个参数,以及𝜗的括号中的α。
    直观上理解,C(α,β)与θ型的含义几乎相同:它是“从0、Ω以及小于β的序数出发,用加法和以前定义过的𝜗(即你放进𝜗里面的序数必须小于α),能在有限步内构造出的所有序数”之集合。
    𝜗(α)则是满足两个条件的最小β:首先,C(α,β)不含有任何从β到Ω之间的序数(也不能含有β);其次,C(α,β)要含有α。由此可以立即判断出α≠β,于是𝜗(α)≠α。
    如果去掉“α∈C(α,β)”这个条件,那它的数值将与ψ型类似。但如果扩展到很多大序数的情况,它基本上还是𝜗型的。这种OCF参阅https://googology.fandom.com/wiki/User:Hyp_cos/OCF_vs_Array_Notation


    IP属地:北京本楼含有高级字体2楼2022-07-31 12:45
    回复
      如果用“添加新的大序数”的办法强化三大类OCF,那么只需添加ω个大序数,就可以把它们拉到同一水平。
      用Ω(n)表示第n个非递归的admissible序数。Ω(1)就是Ω。
      ψ型定义:
      C(α,β,0) = β ∪ {0} ∪ {Ω(ν) | ν<ω}
      C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {ψ_ν(γ) | γ∈C(α,β,i) ∧ γ<α}
      C(α,β) = ⋃{C(α,β,i) | i<ω}
      ψ_ν(α) = min(Ω(ν+1)\C(α,Ω(ν)))
      这里的ν表示ψ_ν(α)在第几个序数大小区间中取值。ν=0是递归的(可计算的)序数;ν=1与Ω同类,是非递归的,但低于Ω(2);更普遍来看,第ν类,表示这样的ψ_ν(α)与Ω(ν)同类,但低于Ω(ν+1)。
      θ型定义:
      C(α,β,0) = β ∪ {0} ∪ {Ω(ν) | ν<ω}
      C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {θ(γ,δ) | γ,δ∈C(α,β,i) ∧ γ<α}
      C(α,β) = ⋃{C(α,β,i) | i<ω}
      A(α) = {β | β∉C(α,β)}
      θ(α,β) = min{γ∈A(α) | ∀δ<β(θ(α,δ)<γ)}
      θ同样有序数大小区间的概念,但它用“θ的第二参数在哪个序数大小区间中”来表示。比如θ(Ω,θ(Ω(3),θ(1,Ω(2)·2)))以深层“第二参数”中的Ω(2)·2为准,与Ω(2)同类,低于Ω(3)。
      𝜗型定义:
      C(α,β,0) = β ∪ {0} ∪ {Ω(ν) | ν<ω}
      C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {𝜗_ν(γ) | γ∈C(α,β,i) ∧ γ<α}
      C(α,β) = ⋃{C(α,β,i) | i<ω}
      𝜗_ν(α) = min{β<Ω(ν) | C(α,β)∩Ω(ν)⊆β ∧ α∈C(α,β)}
      𝜗也有序数大小区间的概念,而且与ψ型几乎一致。
      以上所有定义都可以扩展到“添加一个Ω(ν)计数函数”的地步。三大类OCF仍然保持同样的强度。
      ψ型定义:
      C(α,β,0) = β ∪ {0}
      C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {Ω(γ) | γ∈C(α,β,i)} ∪ {ψ_ν(γ) | ν,γ∈C(α,β,i) ∧ γ<α}
      C(α,β) = ⋃{C(α,β,i) | i<ω}
      ψ_ν(α) = min(Ω(ν+1)\C(α,Ω(ν)))
      θ型定义:
      C(α,β,0) = β ∪ {0}
      C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {Ω(γ) | γ∈C(α,β,i)} ∪ {θ(γ,δ) | γ,δ∈C(α,β,i) ∧ γ<α}
      C(α,β) = ⋃{C(α,β,i) | i<ω}
      A(α) = {β | β∉C(α,β)}
      θ(α,β) = min{γ∈A(α) | ∀δ<β(θ(α,δ)<γ)}
      𝜗型定义:
      C(α,β,0) = β ∪ {0}
      C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {Ω(γ) | γ∈C(α,β,i)} ∪ {𝜗_ν(γ) | ν,γ∈C(α,β,i) ∧ γ<α}
      C(α,β) = ⋃{C(α,β,i) | i<ω}
      𝜗_ν(α) = min{β<Ω(ν) | C(α,β)∩Ω(ν)⊆β ∧ α,ν∈C(α,β)}


      IP属地:北京本楼含有高级字体3楼2022-07-31 14:02
      收起回复
        “添加一个Ω(ν)计数函数”让三大类OCF都达到了PTO(Π^1_1-TR_0)的强度。但再强化下去,它们就会呈现不一样的道路。
        其中,ψ与θ是较弱的一类,而𝜗则独属较强的一类。
        首先,单考虑Ω(ν)。它是第1+ν个“非递归的admissible序数及其极限”。这个计数函数是个连续增函数,因此可以像φ那样造出一种新的φ函数(新的Veblen层级)。
        用Φ表示。Φ(0,α) = Ω(α)(注意:Ω(0) = 1,Ω(1) = Ω,Ω(ω) = sup{Ω(1), Ω(2), Ω(3), …},Ω(ω+1) = 第ω个admissible序数),然后Φ(1,β)是满足α=Ω(α)的第1+β个序数。在这些二元Φ之上还有Φ(1,0,0), Φ(1,0,0,0,0,0,0,0)等等。最终,我们又需要一个新的OCF,来得出这些Φ(α,β,γ,δ)之流。
        为了让ψ型和θ型OCF表达出它们,我们需要定义一族序数——那就是所有Ω(ν)。可以定义A = 所有大于ω的admissible序数,cl(A)是A的闭包,ec(A)则是A的闭包的计数。这样,只需把函数值限制在cl(A)上,一个简单的OCF就能把这些Φ东西全都表示出来。


        IP属地:北京4楼2022-07-31 14:19
        回复
          而这些OCF用到一个新的、关键的序数——最小的递归不可达序数。这里记作I。
          自然,在I之上,下一个可以用于OCF的序数则是Ω(I+1)。
          在Ω(Ω(…Ω(Ω(I+1))…))之上,则又需要一种新的Φ来计数那些不动点,然后又有下一个递归不可达序数——I_2。
          如此往复,那就令一种新的Φ,它的Φ(0,α) = Ι_α,也就是递归不可达序数的闭包的计数。
          获得这样的Φ,也可以通过OCF来完成,而这个超级OCF所用到的序数,则是最小的2-递归不可达序数——I(2,0)。
          如果一个序数α,它是admissible序数,而且对任何γ<β,α都是γ-递归不可达序数之极限,那么这样的α就是个β-递归不可达序数。
          0-递归不可达序数就是admissible序数。
          1-递归不可达序数就是递归不可达序数。
          这样,以A为基础,就可以构造一系列层次。
          A(0)是所有序数组成的序数类。
          A(1+α)是所有α-递归不可达序数组成的序数类。
          cl(X)表示X的闭包。
          ec(X)是X的闭包的计数。
          接下来才是具体的OCF。
          ψ型定义:
          C(α,β,0) = β ∪ {0}
          C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {ψ(γ) | γ∈C(α,β,i) ∧ γ<α} ∪ {ψ_ν(ξ,γ) | ν,ξ,γ∈C(α,β,i) ∧ γ<α}
          C(α,β) = ⋃{C(α,β,i) | i<ω}
          ψ(α) = min(A(1)\C(α,0))
          ψ_ν(ξ,α) = min(cl(A(ξ))\C(α,ec(A(ξ+1))(ν)))
          由于获取递归序数(小于Ω(1) = min(A(1))的序数)的那个函数无法归类到ψ_ν(ξ,α)之中,所以单拎出来,作为ψ(α)。
          θ型定义:
          C(α,β,0) = β ∪ {0}
          C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {θ(ξ,γ,δ) | ξ,γ,δ∈C(α,β,i) ∧ γ<α}
          C(α,β) = ⋃{C(α,β,i) | i<ω}
          B(ξ,α) = {β∈cl(A(ξ)) | β∉C(α,β)}
          θ(ξ,α,β) = min{γ∈B(ξ,α) | ∀δ<β(θ(α,δ)<γ)}


          IP属地:北京本楼含有高级字体5楼2022-07-31 14:46
          收起回复
            那么,𝜗型OCF,又是如何定义的呢?
            设I(α,β)是α-递归不可达序数之闭包中的第1+β个序数。
            C(α,β,0) = β ∪ {0}
            C(α,β,i+1) = {γ+δ | γ,δ∈C(α,β,i)} ∪ {I(γ,δ) | γ,δ∈C(α,β,i)} ∪ {𝜗_π(γ) | π,γ∈C(α,β,i) ∧ γ<α ∧ π是admissible序数}
            C(α,β) = ⋃{C(α,β,i) | i<ω}
            𝜗_π(α) = min{β<π | C(α,β)∩π⊆β ∧ α,π∈C(α,β)}(其中π是admissible序数)
            主要是把Ω(γ)换成I(γ,δ)。甚至不用添加新的A类。
            考虑函数𝜗_I。对于α<Ι,𝜗_I(α)足以与Φ(1,α)媲美,而𝜗_I(I+α)则对应Φ(2,α)。
            也就是说,虽然我们什么都没加,但是当I作为下标的时候,这个OCF竟然自动地把取值限制在admissible序数之极限上!


            IP属地:北京6楼2022-07-31 14:58
            回复
              如果给𝜗型OCF加类,那它加的就不仅仅是按照“α-递归不可达序数”形成的层级了,而是按照“α-递归Mahlo序数”形成的层级。
              从根本上看,𝜗型OCF可以自然地处理完整的“……,并且Π_1-反射于……”这样的概念。因此只有到了迭代Π_2-反射这样的层级,才需要特意地给𝜗型OCF添加层级。
              但ψ型和θ型OCF做不到。仅仅是α-递归不可达序数,就需要添加层级了。
              然而,它们之间的差别,却也仅仅是“Π_n-反射”跟“Π_(n-1)-反射”的差别而已。如果到了Π_n-反射(任意n<ω)的地步,它们之间的差别将再次抹平。到那时,三大类OCF的区别已经不再重要,重要的(而且是最复杂的)是如何给这些OCF添加层级。
              这个级别下的OCF可以说是群魔乱舞,十分难以理解。


              IP属地:北京7楼2022-07-31 15:05
              收起回复
                厉害,支持


                IP属地:浙江来自Android客户端8楼2022-07-31 20:59
                回复
                  我一般用ψ(α+1)=ψ(α)*ω这样的ocf
                  θ只是在初始强度高于ψ,到了大序数还是会被追平。而且二元函数还不好分析,所以我并不用这类ocf (总有种画蛇添足的感觉)


                  来自Android客户端9楼2022-08-22 07:17
                  回复
                    这贴居然不是2014年的


                    来自iPhone客户端10楼2022-10-03 22:29
                    回复
                      这个vartheta是Weiermann还是Wilken,我忘了。下面均用θ表示(不管Feferman θ)
                      它的问题(好吧也不是问题)在于α<β不代表θ(α)<θ(β)
                      例如θ(ε0)=θ(θ(Ω))>θ(Ω)
                      这个基本上是我在discord里多次提到的一个类似的nonincreasing ψ
                      Rathjen大Ψ也是这个特性,搞得让人Ψ^0_Ω(Ψ^0_Ω(Κ)) > Ψ^0_Ω(Κ)分析起来很头疼


                      来自iPhone客户端11楼2022-10-03 22:34
                      收起回复
                        yes


                        IP属地:上海12楼2023-04-13 17:27
                        回复
                          true


                          IP属地:上海13楼2023-04-13 17:28
                          回复
                            φ和Φ差多远?


                            IP属地:四川来自Android客户端14楼2023-10-17 21:04
                            收起回复
                              不愧是终极大佬,我-1个字都看不懂


                              IP属地:河北来自Android客户端15楼2023-11-13 20:56
                              回复