Функция Веблена
В математике функции Веблена - это иерархия нормальных функций, строго возрастающих от ординала к ординалу, предложенная Освальдом Вебленом в 1908 году. Если φ0 - это какая-либо нормальная функция, тогда для любого ненулевого ординала α, функция φα перечисляет общие неподвижные точки всех φβ для β<α. Все эти функции нормальные.
Иерархия Веблена
В частном случае, когда φ0(α)=ωα это семейство функций называется иерархией Веблена. Например, <math>\varphi_1(\alpha)=\varepsilon_{\alpha}</math>, <math>\varphi_2(\alpha)=\zeta_{\alpha}</math>, <math>\varphi_3(\alpha)=\eta_{\alpha}</math>. В связи с иерархией Веблена применяется вариация нормальной формы Кантора - любой ненулевой ординал α может быть уникально записан как <math>\alpha = \varphi_{\beta_1}(\gamma_1) + \varphi_{\beta_2}(\gamma_2) + \cdots + \varphi_{\beta_k}(\gamma_k)</math>, где k>0 - некое натуральное число, <math>\varphi_{\beta_m}(\gamma_m) \geq \varphi_{\beta_{m+1}}(\gamma_{m+1})</math> и <math>\gamma_m < \varphi_{\beta_m}(\gamma_m)</math>. Таким образом фундаментальная последовательность для любого ненулевого ординала α может быть определена из выражения <math>\alpha [n] = \varphi_{\beta_1}(\gamma_1) + \cdots + \varphi_{\beta_{k-1}}(\gamma_{k-1}) + (\varphi_{\beta_k}(\gamma_k) [n]) </math> с учетом следующих правил
1) если <math>\beta=0</math> тогда <math>\varphi_0(\gamma+1) [n] = \omega^{\gamma} \cdot n</math>
поскольку <math>\varphi_0(0)=1</math> и <math>\varphi_0(\gamma)=\omega^{\gamma}</math>
2) если <math>\gamma=0</math> тогда <math>\varphi_{\beta+1}(0) [0] = 0</math>
и <math>\varphi_{\beta+1}(0) [n+1] = \varphi_{\beta}(\varphi_{\beta+1}(0) [n])</math>
то есть <math>\varphi_{\beta+1}(0)[n]=\varphi_{\beta}^n(0)</math>
3) если <math>\gamma</math> предельный ординал, тогда <math>\varphi_{\beta}(\gamma) [n] = \varphi_{\beta}(\gamma [n])</math>
4) если <math>\beta</math> предельный ординал, тогда <math>\varphi_{\beta}(0) [n] = \varphi_{\beta [n]}(0)</math>
и <math>\varphi_{\beta}(\gamma+1) [n] = \varphi_{\beta [n]}(\varphi_{\beta}(\gamma)+1)</math>
5) иначе <math>\varphi_{\beta+1}(\gamma+1) [0] = \varphi_{\beta+1}(\gamma)+1</math>
и <math>\varphi_{\beta+1}(\gamma+1) [n+1] = \varphi_{\beta} (\varphi_{\beta+1}(\gamma+1) [n]) </math>
то есть <math>\varphi_{\beta+1}(\gamma+1)[n]=\varphi_{\beta}^n(\varphi_{\beta+1}(\gamma)+1)</math>
Примеры
| применение правила 2 | применение правила 5 |
|---|---|
| <math>\varphi_{1}(0)[0]=\varepsilon_{0} [0] = 0</math> | <math>\varphi_{1}(1)[0]=\varphi_{1}(0)+1=\varepsilon_{0}+1=\varepsilon_{1} [0]</math> |
| <math>\varphi_{1}(0)[1]=\varphi_{0}(\varphi_{1}(0)[0])=\varphi_{0}(0)=\omega^0=1</math> | <math>\varphi_{1}(1)[1]=\varphi_{0}(\varphi_{1}(1)[0])=\varepsilon_{1} [1]=\omega^{\varepsilon_{0}+1}</math> |
| <math>\varphi_{1}(0)[2]=\varphi_{0}(\varphi_{1}(0)[1])=\omega^1=\omega</math> | <math>\varphi_{1}(1)[2]=\varphi_{0}(\varphi_{1}(1)[1])=\varepsilon_{1} [2]=\omega^{\omega^{\varepsilon_{0}+1}}</math> |
| <math>\varphi_{1}(0)[3]=\varphi_{0}(\varphi_{1}(0)[2])=\omega^{\omega}</math> | <math>\varphi_{1}(1)[3]=\varphi_{0}(\varphi_{1}(1)[2])=\varepsilon_{1} [3]=\omega^{\omega^{\omega^{\varepsilon_{0}+1}}}</math> |
| <math>\varphi_{1}(0)[4]=\varphi_{0}(\varphi_{1}(0)[3])=\omega^{\omega^{\omega}}</math> | <math>\varphi_{1}(1)[4]=\varphi_{0}(\varphi_{1}(1)[3])=\varepsilon_{1} [4]=\omega^{\omega^{\omega^{\omega^{\varepsilon_{0}+1}}}}</math> |
| <math>\varphi_{2}(0)[4]=\varphi_{1}(\varphi_{1}(\varphi_{1}(\varphi_{1}(0))))=\varepsilon_{\varepsilon_{\varepsilon_{\varepsilon_0}}}=\zeta_0[4]</math> | <math>\varphi_{2}(1)[4]=\varphi_{1}(\varphi_{1}(\varphi_{1}(\varphi_{1}(\varphi_2 (0)+1))))=\varepsilon_{\varepsilon_{\varepsilon_{\varepsilon_{\zeta_0 +1}}}}=\zeta_1[4]</math> |
| <math>\varphi_{3}(0)[4]=\varphi_{2}(\varphi_{2}(\varphi_{2}(\varphi_{2}(0))))=\zeta_{\zeta_{\zeta_{\zeta_0}}}=\eta_0 [4]</math> | <math>\varphi_{3}(1)[4]=\varphi_{2}(\varphi_{2}(\varphi_{2}(\varphi_{2}(\varphi_3 (0)+1))))=\zeta_{\zeta_{\zeta_{\zeta_{\eta_0 +1}}}}=\eta_1[4]</math> |
<math>\varphi_{0}(3)[n]=\omega^2\cdot n </math> (Правило 1)
<math>\varphi_{0}(\varphi_{0}(1))[n]=\varphi_{0}(\varphi_{0}(1)[n])=\omega^{\omega[n]}=\omega^n</math> (Правила 1 и 3)
<math>\varphi_{1}(\omega)[n]=\varphi_{1}(\omega[n])=\varphi_{1}(n)=\varepsilon_n</math> (Правило 3)
<math>\varphi_{1}(\varphi_{1}(0))[n]=\varphi_{1}(\varphi_{1}(0)[n])=\varphi_{1}(\varepsilon_0 [n])=\varepsilon_{\omega \uparrow \uparrow (n-1)}</math> (Правило 3)
<math>\varphi_{\varphi_0 (1)}(0)[n]=\varphi_{\omega}(0)[n]=\varphi_{\omega [n]}(0)=\varphi_{n}(0)</math> (Правила 1 и 4)
<math>\varphi_{\varphi_1 (0)}(0)[3]=\varphi_{\varepsilon_0}(0)[3]=\varphi_{\varepsilon_0[3]}(0)=\varphi_{\omega^{\omega}}(0)</math> (Правило 4)
Соответствующие примеры для быстрорастущей иерархии
<math>f_{\varphi_{1}(0)}(4)=f_{\varphi_{1}(0)[4]}(4)=f_{\omega^{\omega^{\omega}}}(4)</math>
<math>f_{\varphi_{1}(1)}(3)=f_{\varphi_{1}(1)[3]}(3)=f_{\omega^{\omega^{\omega^{\varepsilon_{0}+1}}}}(3)</math>
Г-функция
Функция Γ перечисляет ординалы α, такие что φα(0) = α. Наименьший ординал α, для которого выполняется это условие, называется ординалом Фефермана[en] Γ0. Фундаментальная последовательность для него определяется следующими выражениями
<math>\Gamma_0 [0] = 0 \,</math> и <math>\Gamma_0 [n+1] = \varphi_{\Gamma_0 [n]} (0)</math>.
Для Γβ+1 верно <math>\Gamma_{\beta+1} [0] = \Gamma_{\beta} + 1</math>
и <math>\Gamma_{\beta+1} [n+1] = \varphi_{\Gamma_{\beta+1} [n]} (0)</math>.
Если <math>\beta</math> - предельный ординал и <math>\beta < \Gamma_{\beta}</math>, тогда <math>\Gamma_{\beta} [n] = \Gamma_{\beta [n]}</math>.
Обобщение
Функция Веблена φα(β) также может быть представлена в виде функции φ(α,β) двух аргументов. Веблен показал как обобщить определение для того, что бы получить функцию φ(αn,αn−1,…,α0) для произвольного числа аргументов, а именно:
- φ(α)=ωα для случая одной переменной,
- φ(0,αn−1,…,α0)=φ(αn−1,…,α0), и
- для α>0, γ↦φ(αn,…,αi+1,α,0,…,0,γ) - это функция перечисляющая общие неподвижные точки функций ξ↦φ(αn,…,αi+1,β,ξ,0,…,0) для всех β<α.
Например, φ(1,0,γ) это γ-я неподвижная точка функций ξ↦φ(ξ,0), а именно Γγ.
<math>\varphi(1,0,0)=\Gamma_0</math>- ординал Фефермана.
<math>\varphi(1,0,0,0)</math> - ординал Аккермана.
Предел для <math>\varphi(1,0,\cdots,0,0)</math> - малый ординал Веблена.
Напишите отзыв о статье "Функция Веблена"
Ссылки
- Hilbert Levitz, [www.cs.fsu.edu/~levitz/ords.ps Transfinite Ordinals and Their Notations: For The Uninitiated], expository article (8 pages, in PostScript)
- Pohlers, Wolfram (1989), Proof theory, vol. 1407, Lecture Notes in Mathematics, Berlin: Springer-Verlag, ISBN 3-540-51842-8
- Schütte, Kurt (1977), Proof theory, vol. 225, Grundlehren der Mathematischen Wissenschaften, Berlin-New York: Springer-Verlag, сс. xii+299, ISBN 3-540-07911-4
- Takeuti, Gaisi (1987), Proof theory, vol. 81 (Second ed.), Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland Publishing Co., ISBN 0-444-87943-9
- Smorynski, C. (1982), "[dx.doi.org/10.1007%2FBF03023553 The varieties of arboreal experience]", Math. Intelligencer Т. 4 (4): 182–189, DOI 10.1007/BF03023553 contains an informal description of the Veblen hierarchy.
- Veblen, Oswald (1908), "[dx.doi.org/10.2307%2F1988605 Continuous Increasing Functions of Finite and Transfinite Ordinals]", Transactions of the American Mathematical Society Т. 9 (3): 280–292, DOI 10.2307/1988605
- Miller, Larry W. (1976), "[dx.doi.org/10.2307%2F2272243 Normal Functions and Constructive Ordinal Notations]", The Journal of Symbolic Logic Т. 41 (2): 439–459, DOI 10.2307/2272243
| ||||||||||||||
Отрывок, характеризующий Функция Веблена
Европа действительно скоро составила бы таким образом один и тот же народ, и всякий, путешествуя где бы то ни было, находился бы всегда в общей родине.Я бы выговорил, чтобы все реки были судоходны для всех, чтобы море было общее, чтобы постоянные, большие армии были уменьшены единственно до гвардии государей и т.д.
Возвратясь во Францию, на родину, великую, сильную, великолепную, спокойную, славную, я провозгласил бы границы ее неизменными; всякую будущую войну защитительной; всякое новое распространение – антинациональным; я присоединил бы своего сына к правлению империей; мое диктаторство кончилось бы, в началось бы его конституционное правление…
Париж был бы столицей мира и французы предметом зависти всех наций!..
Потом мои досуги и последние дни были бы посвящены, с помощью императрицы и во время царственного воспитывания моего сына, на то, чтобы мало помалу посещать, как настоящая деревенская чета, на собственных лошадях, все уголки государства, принимая жалобы, устраняя несправедливости, рассевая во все стороны и везде здания и благодеяния.]
Он, предназначенный провидением на печальную, несвободную роль палача народов, уверял себя, что цель его поступков была благо народов и что он мог руководить судьбами миллионов и путем власти делать благодеяния!
«Des 400000 hommes qui passerent la Vistule, – писал он дальше о русской войне, – la moitie etait Autrichiens, Prussiens, Saxons, Polonais, Bavarois, Wurtembergeois, Mecklembourgeois, Espagnols, Italiens, Napolitains. L'armee imperiale, proprement dite, etait pour un tiers composee de Hollandais, Belges, habitants des bords du Rhin, Piemontais, Suisses, Genevois, Toscans, Romains, habitants de la 32 e division militaire, Breme, Hambourg, etc.; elle comptait a peine 140000 hommes parlant francais. L'expedition do Russie couta moins de 50000 hommes a la France actuelle; l'armee russe dans la retraite de Wilna a Moscou, dans les differentes batailles, a perdu quatre fois plus que l'armee francaise; l'incendie de Moscou a coute la vie a 100000 Russes, morts de froid et de misere dans les bois; enfin dans sa marche de Moscou a l'Oder, l'armee russe fut aussi atteinte par, l'intemperie de la saison; elle ne comptait a son arrivee a Wilna que 50000 hommes, et a Kalisch moins de 18000».
[Из 400000 человек, которые перешли Вислу, половина была австрийцы, пруссаки, саксонцы, поляки, баварцы, виртембергцы, мекленбургцы, испанцы, итальянцы и неаполитанцы. Императорская армия, собственно сказать, была на треть составлена из голландцев, бельгийцев, жителей берегов Рейна, пьемонтцев, швейцарцев, женевцев, тосканцев, римлян, жителей 32 й военной дивизии, Бремена, Гамбурга и т.д.; в ней едва ли было 140000 человек, говорящих по французски. Русская экспедиция стоила собственно Франции менее 50000 человек; русская армия в отступлении из Вильны в Москву в различных сражениях потеряла в четыре раза более, чем французская армия; пожар Москвы стоил жизни 100000 русских, умерших от холода и нищеты в лесах; наконец во время своего перехода от Москвы к Одеру русская армия тоже пострадала от суровости времени года; по приходе в Вильну она состояла только из 50000 людей, а в Калише менее 18000.]
Он воображал себе, что по его воле произошла война с Россией, и ужас совершившегося не поражал его душу. Он смело принимал на себя всю ответственность события, и его помраченный ум видел оправдание в том, что в числе сотен тысяч погибших людей было меньше французов, чем гессенцев и баварцев.
Несколько десятков тысяч человек лежало мертвыми в разных положениях и мундирах на полях и лугах, принадлежавших господам Давыдовым и казенным крестьянам, на тех полях и лугах, на которых сотни лет одновременно сбирали урожаи и пасли скот крестьяне деревень Бородина, Горок, Шевардина и Семеновского. На перевязочных пунктах на десятину места трава и земля были пропитаны кровью. Толпы раненых и нераненых разных команд людей, с испуганными лицами, с одной стороны брели назад к Можайску, с другой стороны – назад к Валуеву. Другие толпы, измученные и голодные, ведомые начальниками, шли вперед. Третьи стояли на местах и продолжали стрелять.
Над всем полем, прежде столь весело красивым, с его блестками штыков и дымами в утреннем солнце, стояла теперь мгла сырости и дыма и пахло странной кислотой селитры и крови. Собрались тучки, и стал накрапывать дождик на убитых, на раненых, на испуганных, и на изнуренных, и на сомневающихся людей. Как будто он говорил: «Довольно, довольно, люди. Перестаньте… Опомнитесь. Что вы делаете?»
Измученным, без пищи и без отдыха, людям той и другой стороны начинало одинаково приходить сомнение о том, следует ли им еще истреблять друг друга, и на всех лицах было заметно колебанье, и в каждой душе одинаково поднимался вопрос: «Зачем, для кого мне убивать и быть убитому? Убивайте, кого хотите, делайте, что хотите, а я не хочу больше!» Мысль эта к вечеру одинаково созрела в душе каждого. Всякую минуту могли все эти люди ужаснуться того, что они делали, бросить всо и побежать куда попало.
Но хотя уже к концу сражения люди чувствовали весь ужас своего поступка, хотя они и рады бы были перестать, какая то непонятная, таинственная сила еще продолжала руководить ими, и, запотелые, в порохе и крови, оставшиеся по одному на три, артиллеристы, хотя и спотыкаясь и задыхаясь от усталости, приносили заряды, заряжали, наводили, прикладывали фитили; и ядра так же быстро и жестоко перелетали с обеих сторон и расплюскивали человеческое тело, и продолжало совершаться то страшное дело, которое совершается не по воле людей, а по воле того, кто руководит людьми и мирами.
