08.12.2022
Используемая в тяжёлой промышленности и иных сферах труба бесшовная называется так потому, что это цельное изделие из металла, на...


08.12.2022
Инженерные строительные коммуникации – это модули и контуры, используемые для подачи или отвода обязательных бытовых ресурсов....


07.12.2022
Реестр Минпромторга - это реестр подтверждающий производство продукции промышленного типа на территории Российской Федерации. Для...


07.12.2022
Формирование и ведение реестра осуществляется Федеральной службой по труду и занятости и ее территориальными органами. За счет...


07.12.2022
В наше время многие люди хотят иметь собственное жилье. Квартиры-студии стали пользоваться большой популярностью в нашей стране...


07.12.2022
В настоящее время многие люди мечтают жить в своем собственном доме, и чтобы еще был огород. Дома из кирпича можно назвать одними...


Медленнорастущая иерархия

19.01.2022

Медленнорастущая иерархия представляет собой семейство функций ( g α : N → N ) α < μ {displaystyle (g_{alpha }:mathbb {N} ightarrow mathbb {N} )_{alpha <mu }} , где μ {displaystyle mu } – это некий большой счетный ординал, такой, что фундаментальные последовательности присвоены всем предельным ординалам, меньшим чем μ {displaystyle mu } .

Медленнорастущая иерархия определяется следующим образом:

  • g 0 ( n ) = 0 {displaystyle g_{0}(n)=0}
  • g α + 1 ( n ) = g α ( n ) + 1 {displaystyle g_{alpha +1}(n)=g_{alpha }(n)+1}
  • g α ( n ) = g α [ n ] ( n ) {displaystyle g_{alpha }(n)=g_{alpha [n]}(n)} , если и только если α {displaystyle alpha } – предельный ординал,

где α [ n ] {displaystyle alpha [n]} обозначает n {displaystyle n} -й элемент фундаментальной последовательности присвоенной предельному ординалу α {displaystyle alpha } .

Каждый ненулевой ординал α < ε 0 = min { β | β = ω β } {displaystyle alpha <varepsilon _{0}=min{eta |eta =omega ^{eta }}} может быть представлен в уникальной нормальной форме Кантора α = ω β 1 + ω β 2 + ⋯ + ω β k − 1 + ω β k , {displaystyle alpha =omega ^{eta _{1}}+omega ^{eta _{2}}+cdots +omega ^{eta _{k-1}}+omega ^{eta _{k}},} где ω {displaystyle omega } – первый трансфинитный ординал, α > β 1 ≥ β 2 ≥ ⋯ ≥ β k − 1 ≥ β k {displaystyle alpha >eta _{1}geq eta _{2}geq cdots geq eta _{k-1}geq eta _{k}} .

Если β k > 0 {displaystyle eta _{k}>0} , тогда α {displaystyle alpha } – предельный ординал и ему может быть присвоена фундаментальная последовательность следующим образом:

α [ n ] = ω β 1 + ω β 2 + ⋯ + ω β k − 1 + { ω γ n , если  β k = γ + 1 ω β k [ n ] , если  β k  - предельный ординал. {displaystyle alpha [n]=omega ^{eta _{1}}+omega ^{eta _{2}}+cdots +omega ^{eta _{k-1}}+left{{egin{array}{lcr}omega ^{gamma }n{ ext{, если }}eta _{k}=gamma +1omega ^{eta _{k}[n]}{ ext{, если }}eta _{k}{ ext{ - предельный ординал.}}end{array}} ight.}

Если α = ε 0 {displaystyle alpha =varepsilon _{0}} , тогда α [ 0 ] = 0 {displaystyle alpha [0]=0} и α [ n + 1 ] = ω α [ n ] {displaystyle alpha [n+1]=omega ^{alpha [n]}} .

Используя эту систему фундаментальных последовательностей можно определить медленнорастущую иерархию до первого числа эпсилон ε 0 {displaystyle varepsilon _{0}} . Для α = ε 0 {displaystyle alpha =varepsilon _{0}} верно равенство g ε 0 ( n ) = n ↑↑ n {displaystyle g_{varepsilon _{0}}(n)=nuparrow uparrow n} согласно стрелочной нотации.

С более мощными системами фундаментальных последовательностей можно ознакомиться на следующих страницах:

  • Функция Веблена
  • Пси-функции Бухгольца

Медленнорастущая иерархия "догоняет" быстрорастущую иерархию при α = ψ 0 ( Ω ω ) {displaystyle alpha =psi _{0}(Omega _{omega })} , используя пси-функции Бухгольца, то есть

g ψ 0 ( Ω ω ) ( n ) < f ψ 0 ( Ω ω ) ( n ) < g ψ 0 ( Ω ω ) ( n + 1 ) {displaystyle g_{psi _{0}(Omega _{omega })}(n)<f_{psi _{0}(Omega _{omega })}(n)<g_{psi _{0}(Omega _{omega })}(n+1)} для всех n > 0 {displaystyle n>0} .



Имя:*
E-Mail:
Комментарий:
Информационный некоммерческий ресурс fccland.ru © 2022
При цитировании информации ссылка на сайт обязательна.
Копирование материалов сайта ЗАПРЕЩЕНО!