Баяу өсетін иерархия - Slow-growing hierarchy

Жылы есептеу теориясы, есептеу күрделілігі теориясы және дәлелдеу теориясы, баяу өсетін иерархия - баяу өсетін функциялардың реттік-индекстелген отбасы ж_α: N → N (қайда N жиынтығы натурал сандар, {0, 1, ...}). Бұл тез дамып келе жатқан иерархия.

Анықтама

Μ а болсын үлкен реттік осылай а негізгі дәйектілік әрқайсысына тағайындалады шекті реттік μ-ден аз The баяу өсетін иерархия функциялар ж_α: N → N, α <μ үшін, келесідей анықталады:

• ${ displaystyle g_ {0} (n) = 0}$
• ${ displaystyle g_ {k + 1} (n) = g_ {k} (n) +1}$
• ${ displaystyle g _ { alpha} (n) = g _ { alpha [n]} (n)}$ α реттік реттік үшін.

Мұнда α [n] дегенді білдіреді n^мың α шекарасына берілген іргелі реттіліктің элементі.

Туралы мақала Тез дамып келе жатқан иерархия барлық α <ε үшін негізгі реттіліктің стандартталған таңдауын сипаттайды₀.

Жылдам өсіп келе жатқан иерархиямен байланыс

Баяу өсетін иерархия тез өсетін иерархияға қарағанда әлдеқайда баяу өседі. Тіпті ж_ε0 дегенге ғана тең f₃ және ж_α өсуіне ғана жетеді f_ε0 (бірінші функция Пеано арифметикасы дәлелдей алмайды барлығы иерархияда) α болғанда Бахман –Говард реттік.^[1][2][3]

Алайда, Джирард ақырындап өсетін иерархияның ақыр соңында екенін дәлелдеді қуып жетеді тез өсетінімен.^[1] Нақтырақ айтқанда, барлық бүтін сандар үшін α реттік нөмірі бар n

ж_α(n) < f_α(n) < ж_α(n + 1)

қайда f_α тез өсетін иерархиядағы функциялар болып табылады. Ол бұдан әрі бірінші α теорияның реттік екенін көрсетті Жеке куәлік_<ω индуктивті анықтаманың ерікті ақырлы қайталануы.^[4] Алайда іргелі тізбектерді тағайындау үшін табылған ^[2] бірінші сәйкестік ε деңгейінде болады₀.^[5] Бухгольц стиліндегі ағаш ординалдары үшін бірінші сәйкестіктің тіпті орын алатындығын көрсетуге болады ${ displaystyle omega ^ {2}}$.

Нәтиженің кеңейтілгендігі дәлелденді^[4] едәуір үлкен реттік нөмірлер трансфинитті қайталанатын реттік қатардың астында өте аз реттік екенін көрсетеді ${ displaystyle Pi _ {1} ^ {1}}$- баяу және тез өсетін иерархия сәйкес келетін жерде түсіну.^[6]

Баяу өсетін иерархия негізгі фундаментальды тізбектерді таңдауға өте сезімтал.^[5][7][8]

Мерзімді қайта жазумен байланысты

Цихон баяу өсетін иерархия мен мерзімді қайта жазу үшін туынды ұзындығы арасындағы қызықты байланысты қамтамасыз етті.^[2]

Әдебиеттер тізімі

• Галли, Жан Х. (1991). «Крускалдың теоремасы мен реттік about ерекшелігі неде?₀? Дәлелдеу теориясының кейбір нәтижелерін зерттеу ». Энн. Таза Appl. Логика. 53 (3): 199–260. дои:10.1016 / 0168-0072 (91) 90022-E. МЫРЗА  1129778. PDF файлдары: 1 бөлім 2 3. (Атап айтқанда 3-бөлім, 12-бөлім, 59-64 беттер, «Жылдам және баяу өсетін функциялардың иерархияларына көз жүгірту».)

Ескертулер