Доклады Российской академии наук. Математика, информатика, процессы управления, 2022, T. 505, № 1, стр. 5-10

СПЕКТРЫ КОНСЕРВАТИВНОСТИ И МОДЕЛЬ ЙООСТЕНА–ФЕРНАНДЕСА

Академик РАН Л. Д. Беклемишев^1, *

¹ Математический институт им. В.А. Стеклова Российской академии наук
Москва, Россия

Поступила в редакцию 24.03.2022
После доработки 05.06.2022
Принята к публикации 07.06.2022

EDN: JLTMAB
DOI: 10.31857/S2686954322040038

Аннотация

Рассматривается обобщение понятия спектра консервативности арифметической теории на язык с трансфинитно итерированными определениями истинности. Установлено естественное соответствие между спектрами консервативности и точками специальной модели Крипке, введенной Д. Фернандесом–Дуке и Й. Йоостеном. Для итерированных схем рефлексии над теориями определений истинности установлены результаты о консервативности, аналогичные хорошо известным формулам Шмерля.

Ключевые слова: схема рефлексии, предикат истинности, консервативность

1. ВВЕДЕНИЕ

Данная статья продолжает работу [1], в которой методы логики доказуемости и алгебр рефлексии применены к исследованию теорий предикативной силы. В частности, понятие спектра консервативности арифметической теории обобщается на языки, в которых определимы множества гиперарифметической иерархии и соответствующие определения истинности. Говоря неформально, спектр консервативности теории $S$ есть трансфинитная последовательность ординалов $\beta = {\text{or}}{{{\text{d}}}_{\alpha }}(S)$, где β – максимальный ординал, для которого β-кратная итерация схемы рефлексии для формул класса ${{\Pi }_{{1 + \alpha }}}$ над некоторой фиксированной теорией содержится в $S$. Таким образом, спектр консервативности теории $S$ несет информацию о силе теории $S$ в смысле доказуемости в ней формул каждого класса логической сложности ${{\Pi }_{{1 + \alpha }}}$.

Спектры консервативности, соответствующие уровням арифметической иерархии¹ ¹, были введены Й. Йоостеном [8] под названием разложения Тьюринга–Тейлора арифметических теорий. Он установил каноническое взаимно-однозначное соответствие между $\omega $-спектрами консервативности и точками так называемого фрейма Игнатьева. Позже было показано [4], что фрейм Игнатьева может также рассматриваться как естественная алгебраическая модель исчисления рефлексий RC, расширенного операторами консервативности. Фрейм Игнатьева (в первоначальном его варианте) был введен в работе [7] как универсальная модель Крипке для замкнутого фрагмента логики доказуемости Джапаридзе GLP.

В данной работе мы распространяем результаты [8] на определенное в работе [1] понятие $\lambda $‑спектра консервативности для любых конструктивных ординалов $\lambda $, относящееся к существенно более широкому классу теорий. Д. Фернандес–Дуке и Й. Йоостен [6] ввели расширение фрейма Игнатьева для языка с трансфинитным числом модальностей. Основная теорема нашей работы показывает, что элементы этого фрейма, называемые в работе [6] $\ell $-последовательностями, совпадают с $\lambda $-спектрами консервативности. В силу результатов [6] $\ell $-последовательности имеют простую характеризацию в терминах ординальных функций, связанных с иерархией Веблена. Таким образом, наш результат дает явный ответ на вопрос о том, какие последовательности ординалов реализуются как $\lambda $-спектры консервативности, и подтверждает гипотезу из работы [1].

Данная работа опирается на большой подготовительный материал, обозначения и результаты из работы [1]. Поэтому мы предполагаем знакомство читателя с указанной работой.

2. ОСНОВНЫЕ ПОНЯТИЯ

Здесь мы коротко суммируем основные понятия и результаты, относящиеся к теориям итерированных предикатов истинности и подходу, развитому в работе [1].

2.1. Итерированные предикаты истинности

Пусть ${{\mathcal{L}}_{0}}$ означает язык элементарной арифметики EA. Зафиксируем некоторое элементарно определимое вполне упорядочение $(\Lambda , < )$ и рассмотрим язык

${{\mathcal{L}}_{\Lambda }}: = {{\mathcal{L}}_{0}} \cup \{ {{{\text{T}}}_{\alpha }}\,{\text{|}}\,\alpha < \Lambda \} ,$

где ${{{\text{T}}}_{\alpha }}$ – унарные предикатные символы. Порядок $(\Lambda , < )$ определяет естественную гёделеву нумерацию всех синтаксических объектов языка ${{\mathcal{L}}_{\Lambda }}$. Мы не различаем ординалы и их коды (элементы $\Lambda $).

Для каждого $\alpha \, < \,\Lambda $ мы интерпретируем ${{{\text{T}}}_{\alpha }}$ как предикат истинности для языка ${{\mathcal{L}}_{\alpha }}\, = \,{{\mathcal{L}}_{0}}\, \cup \,\{ {{{\text{T}}}_{\beta }}\,{\text{|}}\,\beta $ < α}. В соответствии с этим мы определяем ${{\mathcal{L}}_{{\alpha + 1}}}$-теорию ${\text{UT}}{{{\text{B}}}_{\alpha }}$, постулируя в качестве аксиом эквивалентности Тарского:

U1: $\forall \vec {x}\left( {\varphi (\vec {x}) \leftrightarrow {{{\text{T}}}_{\alpha }}( \ulcorner \varphi (\underline {\vec {x}} ) \urcorner )} \right)$ для всех ${{\mathcal{L}}_{\alpha }}$-формул $\varphi (\vec {x})$ с указанными свободными переменными $\vec {x} = {{x}_{1}}, \ldots ,{{x}_{k}}$;

U2: $\neg {{{\text{T}}}_{\alpha }}(\underline n )$, для всех n таких, что n не есть гёделев номер никакого ${{\mathcal{L}}_{\alpha }}$-предложения.

Здесь $\underline n $ означает нумерал для натурального числа n и $ \ulcorner \varphi (\underline {\vec {x}} ) \urcorner $ – элементарно определимый терм, представляющий функцию, сопоставляющую набору $\vec {n} = {{n}_{1}}, \ldots ,{{n}_{k}}$ гёделев номер предложения $\varphi ({{\underline n }_{1}}$, ..., ${{\underline n }_{k}})$. Также мы положим ${\text{UT}}{{{\text{B}}}_{{ < \alpha }}}\,: = \,\bigcup\limits_{\beta < \alpha } {{\text{UT}}{{{\text{B}}}_{\beta }}} $.

2.2. Гиперарифметическая иерархия формул

Пусть $\mathcal{L}$ – язык, расширяющий ${{\mathcal{L}}_{0}}$ новыми предикатными символами. $\Delta _{0}^{\mathcal{L}}$ означает класс всех формул, получаемых из атомарных $\mathcal{L}$-формул с помощью булевых связок и ограниченных кванторов. Классы $\Pi _{n}^{\mathcal{L}}$ и $\Sigma _{n}^{\mathcal{L}}$ получаются из $\Delta _{0}^{\mathcal{L}}$ обычным образом: $\Pi _{0}^{\mathcal{L}}\, = \,\Sigma _{0}^{\mathcal{L}}\, = \,\Delta _{0}^{\mathcal{L}}$, $\Pi _{{n + 1}}^{\mathcal{L}}\, = \,\{ \forall \vec {x}\varphi (\vec {x}):\varphi \, \in \,\Sigma _{n}^{\mathcal{L}}\} $, и $\Sigma _{{n + 1}}^{\mathcal{L}} = \{ \exists \vec {x}\varphi (\vec {x}):\varphi \in \Pi _{n}^{\mathcal{L}}\} $.

Поскольку предикат истинности соответствует ω-кратному применению операции скачка в гиперарифметической иерархии, систему ординальных обозначений $(\Lambda , < )$ необходимо расширить на несколько больший сегмент ординалов до $\omega (1 + \Lambda )$. Например, мы можем закодировать ординалы вида $\omega \alpha + n$ парами $\left\langle {\alpha ,n} \right\rangle $. Классы формул, соответствующие уровням гиперарифметической иерархии вплоть до $\omega (1 + \Lambda )$, определены следующим образом:

• ${{\Pi }_{n}}: = \Pi _{n}^{{{{\mathcal{L}}_{0}}}}$ если $n < \omega $; ${{\Pi }_{{\omega (1 + \alpha ) + n}}}: = \Pi _{{n + 1}}^{{{{\mathcal{L}}_{{\alpha + 1}}}}}$ если $n < \omega $;

• ${{\Pi }_{{ < \alpha }}}: = \bigcup\limits_{\beta < \alpha }^{} {{{\Pi }_{\beta }}} $.

Заметим, что формулы класса ${{\Pi }_{{1 + \alpha }}}$ определяют ${{\Pi }_{1}}({{{\mathbf{0}}}^{{(\alpha )}}})$-множества в стандартной модели.

2.3. Схемы рефлексии

Пусть S – перечислимое расширение теории ${\text{EA}} + {\text{UT}}{{{\text{B}}}_{{ < \Lambda }}}$ вместе с фиксированной элементарной формулой, определяющей множество гёделевых номеров ее аксиом в стандартной модели арифметики. Через ${{\square }_{S}}$ обозначаем гёделевскую формулу доказуемости в теории S (как она определена, например, в работе [5]).

Пусть $\Gamma $ – некоторое множество формул языка S. Через $\Gamma {\text{ - RFN}}(S)$ мы обозначаем равномерную схему рефлексии для $\Gamma $-формул, т.е. схему

$\Gamma {\text{ - RFN}}(S):\quad \forall x({{\square }_{S}}( \ulcorner \varphi (\underline x ) \urcorner ) \to \varphi (x)),\quad \varphi \in \Gamma .$

Мы будем рассматривать следующие схемы рефлексии для введенных выше классов для всех $\alpha < \omega (1 + \Lambda )$:

${{{\text{R}}}_{\alpha }}(S): = {{\Pi }_{{1 + \alpha }}}{\text{ - RFN}}(S),$

${{{\text{R}}}_{{ < \alpha }}}(S): = {{\Pi }_{{{\text{ < }}\alpha }}}{\text{ - RFN(S)}}{\text{.}}$

Теории, аксиоматизированные трансфинитными итерациями операторов рефлексии вдоль заданной системы ординальных обозначений $(\Omega , \prec )$, определяются формализацией следующего уравнения на неподвижную точку в S:

(1)

$\forall \beta \in \Omega ({{\bar {R}}}_{\alpha }^{\beta }(S) \equiv S + \cup \{ {{{\text{R}}}_{\alpha }}({{\bar {R}}}_{\alpha }^{\gamma }(S)):\gamma \prec \beta \} ).$

Теории ${{\bar {R}}}_{\alpha }^{\beta }(S)$, удовлетворяющие (1), единственны по модулю доказуемой эквивалентности в S [4]. Аналогично можно определить теории ${{\bar {R}}}_{{ < \alpha }}^{\beta }(S)$ с помощью трансфинитной итерации операторов ${{{{\bar {R}}}}_{{ < \alpha }}}:U \mapsto S + {{{\text{R}}}_{{ < \alpha }}}(U)$, действующих на полурешетке перечислимых расширений теории S.

Обозначим через EA⁺ расширение теории EA аксиомой, утверждающей тотальность итерированной экспоненциальной функции. Для основных результатов работы [1], как и в настоящей рботе, мы выбираем в качестве базовой теории S теорию ${\text{IB}}: = {\text{E}}{{{\text{A}}}^{ + }} + {\text{UT}}{{{\text{B}}}_{{ < \Lambda }}}$. Теории ${{\bar {R}}}_{\alpha }^{\beta }({\text{IB}})$ и ${{\bar {R}}}_{{ < \alpha }}^{\beta }({\text{IB}})$ обозначаем сокращенно ${{\bar {R}}}_{\alpha }^{\beta }$ и ${{\bar {R}}}_{{ < \alpha }}^{\beta }$ соответственно.

3. ФОРМУЛЫ ШМЕРЛЯ

Один из основных результатов работы [1] – результат о консервативности, соотносящий смешанные схемы рефлексии с трансфинитно итерированными схемами рефлексии сложности ${{\Pi }_{{1 + \alpha }}}$. Мы выведем из этого результата соотношения между иерархиями итерированных схем рефлексии известными как формулы Шмерля. Подобные соотношения впервые возникли в работах Ульфа Шмерля [9, 10] и были впоследствии обобщены в [2].

Для любых ординалов $\alpha \leqslant \beta $ обозначим через $ - \alpha \, + \,\beta $ единственный ординал γ такой, что $\alpha \, + \,\gamma $ = β. Мы будем рассматривать небольшой вариант известной функции Веблена $\varphi $:

${{\bar {\varphi }}_{\alpha }}(\beta ): = \left( {\begin{array}{*{20}{l}} {0,\quad {\text{если}}\;\;\beta = 0,} \\ {{{\omega }^{\beta }},\quad {\text{если}}\;\;\alpha = 0,\beta \ne 0,} \\ {{{\varphi }_{\alpha }}( - 1 + \beta ),\quad {\text{иначе}}.} \end{array}} \right.$

Обозначим через Cr_α класс всех значений функции ${{\bar {\varphi }}_{\alpha }}$. Нетрудно видеть, что ${\text{C}}{{{\text{r}}}_{{\alpha + 1}}}$ есть класс всех неподвижных точек функции ${{\bar {\varphi }}_{\alpha }}$ и для предельных ординалов $\lambda $ ${\text{C}}{{{\text{r}}}_{\lambda }} = \bigcup\limits_{\alpha < \lambda } {{\text{C}}{{{\text{r}}}_{\alpha }}} $. Функции ${{\bar {\varphi }}_{\alpha }}$ монотонно возрастают и непрерывны, и классы Cr_α замкнуты и неограниченны. Эти условия однозначно определяют функции ${{\bar {\varphi }}_{\alpha }}$ как только фиксирована функция ${{\bar {\varphi }}_{0}}$. Отметим, что в терминах иерархии “гиперэкспоненциальных функций”, введенной в работе [6], можно выразить ${{\bar {\varphi }}_{\alpha }}(\beta )$ как ${{e}^{{{{\omega }^{\alpha }}}}}(\beta )$.

Ниже мы будем использовать специальные системы ординальных обозначений ${{\mathbb{W}}^{\Lambda }}$ (и $\mathbb{W}_{\alpha }^{\Lambda }$), определяемые на основе исчисления рефлексий ${\text{R}}{{{\text{C}}}_{\Lambda }}$ (см. [1, раздел 6.2]). Эти системы дают обозначения для ординалов из начального сегмента, содержащего $\Lambda $ и замкнутого относительно ординальных функций + и ${{\bar {\varphi }}_{\alpha }}$ для всех $\alpha < \Lambda $. Ординал, соответствующий слову $A \in \mathbb{W}_{\alpha }^{\Lambda }$, обозначается ${{o}_{\alpha }}(A)$.

Обозначим через $U{{ \equiv }_{\alpha }}V$ взаимную консервативность теорий U и V относительно ${{\Pi }_{{1 + \alpha }}}$-предложений.

Теорема 3.1.

(i) ${{\bar {R}}}_{{\alpha + {{\omega }^{\beta }}}}^{\gamma }{{ \equiv }_{\alpha }}\overline {\text{R}} _{\alpha }^{{{{{\bar {\varphi }}}_{\beta }}(\gamma )}}$;

(ii) $\overline {\text{R}} _{{\alpha + {{\omega }^{\beta }}}}^{{{{\gamma }_{1}}}} \cup \overline {\text{R}} _{\alpha }^{{{{\gamma }_{2}} + 1}}{{ \equiv }_{\alpha }}\overline {\text{R}} _{\alpha }^{{{{\gamma }_{2}} + 1 + {{{\bar {\varphi }}}_{\beta }}({{\gamma }_{1}})}}$.

Доказательство. (i) Мы предполагаем $\Lambda $ настолько большим, что $\alpha + {{\omega }^{\beta }} < \Lambda $ и $\gamma $ имеет обозначение в системе $\mathbb{W}_{{\alpha + {{\omega }^{\beta }}}}^{\Lambda }$. (Для любых конструктивных ординалов $\alpha ,\beta ,\gamma $ можно всегда выбрать подходящий $\Lambda $, и мы также можем считать ординал $\Lambda $ аддитивно неразложимым.) Это означает, что существует слово $C \in \mathbb{W}_{{\alpha + {{\omega }^{\beta }}}}^{\Lambda }$ такое, что ${{o}_{{\alpha + {{\omega }^{\beta }}}}}(C) = \gamma $. По теореме 8 работы [1] мы имеем

$C{\kern 1pt} *{{ \equiv }_{{\alpha + {{\omega }^{\beta }}}}}\overline {\text{R}} _{{\alpha + {{\omega }^{\beta }}}}^{\gamma }.$

Поскольку $C \in \mathbb{W}_{\alpha }^{\Lambda }$, тот же результат дает

$C{\kern 1pt} *{{ \equiv }_{\alpha }}\overline {\text{R}} _{\alpha }^{{{{o}_{\alpha }}(C)}}.$

Значит, $\overline {\text{R}} _{{\alpha + {{\omega }^{\beta }}}}^{\gamma }{{ \equiv }_{\alpha }}\overline {\text{R}} _{\alpha }^{{{{o}_{\alpha }}(C)}}$ и нам достаточно вычислить ${{o}_{\alpha }}(C)$.

Обозначим через $\nu \uparrow A$ результат замены каждой буквы x в слове A на $\nu + x$. Аналогично, $\nu \downarrow A$ означает результат замены каждой буквы $x$ в A на $ - \nu + x$. В силу трансляционной симметриии ${\text{R}}{{{\text{C}}}_{\Lambda }}$, которая имеет место для аддитивно неразложимых ординалов $\Lambda $, эти отображения представляют собой изоморфизмы между системами обозначений $(\mathbb{W}_{\nu }^{\Lambda }{{, < }_{\nu }})$ и $(\mathbb{W}_{0}^{\Lambda }{{, < }_{0}})$.

Положим $D\,: = \,(\alpha \, + \,{{\omega }^{\beta }}) \downarrow C\, = \,{{\omega }^{\beta }} \downarrow (\alpha \downarrow C)$. Мы имеем

$o(D) = {{o}_{{\alpha + {{\omega }^{\beta }}}}}(C) = \gamma .$

Отсюда получаем

${{o}_{\alpha }}(C) = o(\alpha \downarrow C) = o({{\omega }^{\beta }} \uparrow D) = {{\bar {\varphi }}_{\beta }}(o(D)) = {{\bar {\varphi }}_{\beta }}(\gamma ),$

по [3, Lemma 17] (см. также [1, Section 6.2)].

(ii) Рассуждая аналогичным образом, рассмотрим ${{C}_{1}} \in \mathbb{W}_{{\alpha + {{\omega }^{\beta }}}}^{\Lambda }$ и ${{C}_{2}} \in \mathbb{W}_{\alpha }^{\Lambda }$ такие, что ${{o}_{{\alpha + {{\omega }^{\beta }}}}}({{C}_{1}}) = {{\gamma }_{1}}$ and ${{o}_{\alpha }}({{C}_{2}}) = {{\gamma }_{2}}$. Тогда

$\overline {\text{R}} _{{\alpha + {{\omega }^{\beta }}}}^{{{{\gamma }_{1}}}}{{ \equiv }_{{\alpha + {{\omega }^{\beta }}}}}C_{1}^{*}\quad {\text{и}}\quad \overline {\text{R}} _{\alpha }^{{{{\gamma }_{2}}}}{{ \equiv }_{\alpha }}C_{2}^{*}.$

Вторая эквивалентность дает

${{{{\bar {R}}}}_{\alpha }}({{\bar {R}}}_{\alpha }^{{{{\gamma }_{2}}}}) \equiv {{{{\bar {R}}}}_{\alpha }}(C_{2}^{*}).$

Поскольку R_α имеет сложность ${{\Pi }_{{1 + \alpha }}}$, первая эквивалентность влечет

${{\bar {R}}}_{{\alpha + {{\omega }^{\beta }}}}^{{{{\gamma }_{1}}}} \cup {{{{\bar {R}}}}_{\alpha }}({{\bar {R}}}_{\alpha }^{{{{\gamma }_{2}}}}){{ \equiv }_{{\alpha + {{\omega }^{\beta }}}}}({{C}_{1}} \wedge \alpha {{C}_{2}}){\kern 1pt} *.$

Мы имеем ${{C}_{1}}\, \wedge \,\alpha {{C}_{2}}\,{{ = }_{{{\text{R}}{{{\text{C}}}_{\Lambda }}}}}\,{{C}_{1}}\alpha {{C}_{2}}$, поскольку ${{C}_{1}}\, \in \,\mathbb{W}_{{\alpha + 1}}^{\Lambda }$. Более того,

${{o}_{\alpha }}({{C}_{1}}\alpha {{C}_{2}}) = {{o}_{\alpha }}({{C}_{2}}) + 1 + {{\omega }^{{{{o}_{{\alpha + 1}}}({{C}_{1}})}}} = {{\gamma }_{2}} + 1 + {{\bar {\varphi }}_{\beta }}({{\gamma }_{1}}).$

Тогда по [1, теорема 8] мы получаем

$({{C}_{1}} \wedge \alpha {{C}_{2}}){\kern 1pt} *{{ \equiv }_{\alpha }}{{\bar {R}}}_{\alpha }^{{{{\gamma }_{2}} + 1 + {{{\bar {\varphi }}}_{\beta }}({{\gamma }_{1}})}},$

что и требовалось. $ \dashv $

Заметим, что формула (ii) может быть также выведена из формулы (i) с помощью рефлексивной индукции как в [4, лемма 7.3].

4. СПЕКТРЫ КОНСЕРВАТИВНОСТИ

Как и ранее, мы рассматриваем ординалы, представимые в системе обозначений ${{\mathbb{W}}^{\Lambda }}$ для достаточно больших ординалов $\Lambda $. Определяем спектр консервативности теории S (длины $\lambda $) как $\lambda $-последовательность ординалов ${\text{or}}{{{\text{d}}}_{\alpha }}(S)$, для всех $\alpha < \lambda $, где

${\text{or}}{{{\text{d}}}_{\alpha }}(S): = \sup \{ \gamma \in {{\mathbb{W}}^{\Lambda }}:S \vdash {{\bar {R}}}_{\alpha }^{\gamma }\} .$

Спектр консервативности называем собственным, если значение ${\text{or}}{{{\text{d}}}_{\alpha }}(S)$ лежит в ${{\mathbb{W}}^{\Lambda }}$ для каждого $\alpha < \lambda $. Мы будем неявно предполагать все рассматриваемые спектры собственными.

Очевидно, последовательность ${\text{or}}{{{\text{d}}}_{\alpha }}(S)$ является невозрастающей по $\alpha $. Следующая теорема дает более сильное необходимое условие того, чтобы данная $\lambda $-последовательность ординалов представляла спектр консервативности некоторой теории S. Нам понадобится известная функция ординального логарифма $\ell $, определяемая условиями: $\ell (0) = 0$ и $\ell (\alpha + {{\omega }^{\beta }}) = \beta $ для любых ординалов $\alpha $ и $\beta $. Заметим, что в силу теоремы о канторовской нормальной форме эти условия однозначно определяют значение $\ell (\alpha )$ для любого $\alpha $.

Теорема 4.1. Пусть f – спектр консервативности теории S длины $\lambda $. Тогда для любых α, β таких, что $\alpha + {{\omega }^{\beta }} < \lambda $,

(i) $\ell (f(\alpha )) \geqslant f(\alpha + 1)$;

(ii) $\ell (f(\alpha )) \geqslant {{\bar {\varphi }}_{\beta }}(f(\alpha + {{\omega }^{\beta }}))$, если $\beta > 0$.

Доказательство. (i) Обозначим γ := := $f(\alpha + 1)$ и допустим, от противного, что $\gamma > \ell f(\alpha )$. В этом случае $f(\alpha ) \geqslant f(\alpha + 1) = \gamma > 0$ и мы можем представить $f(\alpha )$ в виде ${{\alpha }_{0}} + {{\omega }^{{\ell f(\alpha )}}}$ для некоторого α₀.

По определению спектра

$S \vdash {{\bar {R}}}_{{\alpha + 1}}^{\gamma } \cup {{\bar {R}}}_{\alpha }^{{{{\alpha }_{0}} + 1}}.$

По теореме 3.1 (ii) отсюда следует, что $S \vdash {{\bar {R}}}_{\alpha }^{{{{\alpha }_{0}} + 1 + {{\omega }^{\gamma }}}}$. Следовательно, ord_α(S) ≥ α₀ + ${{\omega }^{\gamma }} > {{\alpha }_{0}} + {{\omega }^{{\ell f(\alpha )}}}$ = = f(α), противоречие.

(ii) Обозначим $\gamma : = f(\alpha + {{\omega }^{\beta }})$ для некоторого β > 0, и допустим, от противного, что $\ell f(\alpha )\, < \,{{\bar {\varphi }}_{\beta }}(\gamma )$. Поскольку β > 0, мы также получаем ${{\bar {\varphi }}_{\beta }}(\gamma )$ = = ${{\omega }^{{{{{\bar {\varphi }}}_{\beta }}(\gamma )}}}\, > \,{{\omega }^{{\ell f(\alpha )}}}$.

По определению спектра

$S \vdash {{\bar {R}}}_{{\alpha + {{\omega }^{\beta }}}}^{\gamma } \cup {{\bar {R}}}_{\alpha }^{{{{\alpha }_{0}} + 1}}.$

По теореме 3.1 (ii) отсюда следует, что $S\, \vdash \,{{\bar {R}}}_{\alpha }^{{{{\alpha }_{0}} + 1 + {{{\bar {\varphi }}}_{\beta }}(\gamma )}}$. Значит, ord_α(S) ≥ α₀ + ${{\bar {\varphi }}_{\beta }}(\gamma )$ > α₀ + + ${{\omega }^{{\ell f(\alpha )}}}$ = f(α), противоречие.

Д. Фернандес-Дуке и Й. Йоостен [6, предложение 5.2] определяют понятие $\ell $-последовательности как ординальной последовательности длины $\lambda $ такой, что для всех $\xi < \zeta < \lambda $

$\ell f(\xi ) \geqslant \ell {{e}^{{{{\omega }^{{\ell \zeta }}}}}}f(\zeta ).$

Напомним, что функция e такова, что ${{e}^{{{{\omega }^{\alpha }}}}}(\beta )$ = = ${{\bar {\varphi }}_{\alpha }}(\beta )$. Поэтому их условие эквивалентно требованию $\ell f(\xi ) \geqslant f(\zeta )$, если $\zeta = \xi + 1$, и

$\ell f(\xi ) \geqslant {{\bar {\varphi }}_{\beta }}(f(\zeta )),$

если $\zeta = \xi + {{\omega }^{\beta }}$ для некоторого $\beta > 0$. (Если $\beta > 0$, то ${{\bar {\varphi }}_{\beta }}(f(\zeta ))$ есть неподвижная точка $\ell $, поэтому применение $\ell $ перед $\bar {\varphi }$ может быть опущено.) Отсюда следует, что необходимое условие в теореме 4.1 эквивалентно тому, что f является $\ell $-последовательностью.

Следствие 4.2. $\lambda $-спектр консервативности любой теории S является $\ell $-последовательностью.

Для доказательства того, что всякая $\ell $-последовательность является спектром консервативности некоторой теории, отметим несколько свойств $\ell $-последовательностей.

Пусть f – $\ell $-последовательность длины λ и $\alpha \, < \,\lambda $. Обозначим ${{\gamma }_{1}}: = f(\alpha )$ и γ₂ := $\min \{ f(\gamma ):\gamma $ < α}.

Лемма 4.3. ${{\bar {R}}}_{\alpha }^{{{{\gamma }_{1}}}} \cup {{\bar {R}}}_{{ < \alpha }}^{{{{\gamma }_{2}}}}{{ \equiv }_{{ < \alpha }}}{{\bar {R}}}_{{ < \alpha }}^{{{{\gamma }_{2}}}}.$

Доказательство. Если $\alpha = {{\alpha }_{0}} + 1$ для некоторого α₀, то ${{\gamma }_{2}} = f({{\alpha }_{0}})$, $l({{\gamma }_{2}}) \geqslant {{\gamma }_{1}}$ и требуется показать

$\overline {\text{R}} _{{{{\alpha }_{0}} + 1}}^{{{{\gamma }_{1}}}} \cup \overline {\text{R}} _{{{{\alpha }_{0}}}}^{{{{\gamma }_{2}}}}{{ \equiv }_{{{{\alpha }_{0}}}}}\overline {\text{R}} _{{{{\alpha }_{0}}}}^{{{{\gamma }_{2}}}}.$

Мы также можем считать ${{\gamma }_{1}}\, > \,0$ (в противном случае утверждение тривиально), отсюда ${{\gamma }_{2}}\, \in \,{\text{Lim}}$.

Рассмотрим любой ординал-последователь δ < ${{\gamma }_{2}}$. По формуле Шмерля

$\overline {\text{R}} _{{{{\alpha }_{0}} + 1}}^{{{{\gamma }_{1}}}} \cup \overline {\text{R}} _{{{{\alpha }_{0}}}}^{\delta }{{ \equiv }_{{{{\alpha }_{0}}}}}\overline {\text{R}} _{{{{\alpha }_{0}}}}^{{\delta + {{\omega }^{{{{\gamma }_{1}}}}}}}.$

Заметим теперь, что $\delta + {{\omega }^{{{{\gamma }_{1}}}}} \leqslant \delta + {{\omega }^{{\ell {{\gamma }_{2}}}}} \leqslant {{\gamma }_{2}}$. Значит, для любого $\delta < {{\gamma }_{2}}$ теория ${{\bar {R}}}_{{{{\alpha }_{0}} + 1}}^{{{{\gamma }_{1}}}} \cup {{\bar {R}}}_{{{{\alpha }_{0}}}}^{\delta }$ ${{\Pi }_{{1 + {{\alpha }_{0}}}}}$-консервативна над $\overline {\text{R}} _{{{{\alpha }_{0}}}}^{{{{\gamma }_{2}}}},$ откуда следует требуемое.

Допустим, что $\alpha = {{\alpha }_{0}} + {{\omega }^{\beta }}$, где $\beta > 0$. Выберем $\alpha {\kern 1pt} '\, < \,\alpha $ такое, что $\alpha {\kern 1pt} ' \geqslant {{\alpha }_{0}}$ и $f(\alpha {\kern 1pt} ') = {{\gamma }_{2}}$. Тогда $\alpha {\kern 1pt} '\, + {{\omega }^{\beta }}$ = = α и $\ell ({{\gamma }_{2}}) \geqslant {{\bar {\varphi }}_{\beta }}({{\gamma }_{1}})$.

Рассмотрим любой ординал-последователь $\delta < {{\gamma }_{2}}$. По формуле Шмерля

$\overline {\text{R}} _{\alpha }^{{{{\gamma }_{1}}}} \cup \overline {\text{R}} _{{\alpha {\kern 1pt} '}}^{\delta }{{ \equiv }_{{\alpha {\kern 1pt} '}}}\overline {\text{R}} _{{\alpha {\kern 1pt} '}}^{{\delta + {{{\bar {\varphi }}}_{\beta }}({{\gamma }_{1}})}}.$

Поскольку $\ell {{\gamma }_{2}} \geqslant {{\bar {\varphi }}_{\beta }}({{\gamma }_{1}})$, имеем $\delta + {{\bar {\varphi }}_{\beta }}({{\gamma }_{1}}) \leqslant {{\gamma }_{2}}$. Так как это верно для всех достаточно больших ординалов $\alpha {\kern 1pt} ' < \alpha $ и $\delta < {{\gamma }_{2}}$, получаем требуемое утверждение.

Теорема 4.4. Любая $\ell $-последовательность длины $\lambda $ есть спектр консервативности некоторой теории S.

Доказательство. Заметим, что любая $\ell $-последовательнрость f не возрастает и поэтому принимает не более конечного числа различных значений, скажем ${{\gamma }_{1}},{{\gamma }_{2}}, \ldots ,{{\gamma }_{n}}$ в порядке убывания. Положим

${{\alpha }_{i}} = \min \{ \alpha :f(\alpha ) = {{\gamma }_{{i + 1}}}\} .$

Тогда значение f есть константа ${{\gamma }_{{i + 1}}}$ на каждом интервале $[{{\alpha }_{i}},{{\alpha }_{{i + 1}}})$, где ${{\alpha }_{0}} = 0$ и ${{\alpha }_{n}}: = \lambda $. Положим

${{S}_{n}}: = {{\bar {R}}}_{{ < {{\alpha }_{n}}}}^{{{{\gamma }_{n}}}} \cup {{\bar {R}}}_{{ < {{\alpha }_{{n - 1}}}}}^{{{{\gamma }_{{n - 1}}}}} \cup \cdots \cup {{\bar {R}}}_{{ < {{\alpha }_{1}}}}^{{{{\gamma }_{1}}}}.$

Мы утверждаем, что спектр консервативности теории S_n совпадает с f. Для доказательства нам понадобятся две дополнительные леммы.

Лемма 4.5. Допустим ${{\alpha }_{{i - 1}}} \leqslant \alpha < {{\alpha }_{i}}$. Тогда $\overline {\text{R}} _{{{{\alpha }_{i}}}}^{{{{\gamma }_{i}}}}{{ \equiv }_{\alpha }}\overline {\text{R}} _{\alpha }^{{{{\gamma }_{i}}}}.$

Доказательство. Мы можем представить ${{\alpha }_{i}}$ в виде ${{\alpha }_{i}}\,: = \,\alpha \, + \,{{\omega }^{{{{\beta }_{1}}}}}\, + \, \cdots \, + \,{{\omega }^{{{{\beta }_{k}}}}}$. Положим ${{\bar {\alpha }}_{j}}$ := := $\alpha + {{\omega }^{{{{\beta }_{1}}}}} + \cdots + {{\omega }^{{{{\beta }_{j}}}}}$, где ${{\bar {\alpha }}_{0}}: = \alpha $. Поскольку f есть $\ell $-последовательность и $f({{\bar {\alpha }}_{j}}) = {{\gamma }_{i}}$, мы имеем ${{\gamma }_{i}} \geqslant \ell ({{\gamma }_{i}}) \geqslant {{\bar {\varphi }}_{{{{\beta }_{j}}}}}({{\gamma }_{i}})$. Следовательно, ${{\gamma }_{i}}$ есть неподвижная точка функции ${{\varphi }_{{{{\beta }_{j}}}}}$ для каждого j. Тогда индукцией по $j = k, \ldots ,0$ из теоремы 3.1 (i) мы получаем

${{\bar {R}}}_{{{{\alpha }_{i}}}}^{{{{\gamma }_{i}}}}{{ \equiv }_{{{{{\bar {\alpha }}}_{j}}}}}{{\bar {R}}}_{{{{{\bar {\alpha }}}_{j}}}}^{{{{\gamma }_{i}}}}.$

Утверждение леммы получается для $j = 0$. $ \dashv $

Лемма 4.6. Для любого $i < n$, ${{S}_{{i + 1}}}{{ \equiv }_{{ < {{\alpha }_{i}}}}}{{S}_{i}}$.

Доказательство. Во-первых, по лемме 4.5,

${{\bar {R}}}_{{ < {{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}{{ \equiv }_{{ < {{\alpha }_{{i + 1}}}}}}{{\bar {R}}}_{{{{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}{{ \equiv }_{{{{\alpha }_{i}}}}}{{\bar {R}}}_{{{{\alpha }_{i}}}}^{{{{\gamma }_{{i + 1}}}}}.$

Поскольку S_i есть множество формул сложности ${{\Pi }_{{ < {{\alpha }_{i}}}}}$, отсюда следует, что

$\begin{gathered} {{S}_{{i + 1}}} \equiv {{S}_{i}} \cup \overline {\text{R}} _{{ < {{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}{{ \equiv }_{{{{\alpha }_{i}}}}}{{S}_{i}} \cup \overline {\text{R}} _{{{{\alpha }_{i}}}}^{{{{\gamma }_{{i + 1}}}}} \equiv \\ \, \equiv {{S}_{{i - 1}}} \cup \overline {\text{R}} _{{ < {{\alpha }_{i}}}}^{{{{\gamma }_{i}}}} \cup \overline {\text{R}} _{{{{\alpha }_{i}}}}^{{{{\gamma }_{{i + 1}}}}}. \\ \end{gathered} $

Поскольку ${{S}_{{i - 1}}}$ имеет сложность ${{\Pi }_{{ < {{\alpha }_{{i - 1}}}}}}$, по лемме 4.3 получаем

${{S}_{{i - 1}}} \cup {{\bar {R}}}_{{ < {{\alpha }_{i}}}}^{{{{\gamma }_{i}}}} \cup {{\bar {R}}}_{{{{\alpha }_{i}}}}^{{{{\gamma }_{{i + 1}}}}}{{ \equiv }_{{ < {{\alpha }_{i}}}}}{{S}_{{i - 1}}} \cup {{\bar {R}}}_{{ < {{\alpha }_{i}}}}^{{{{\gamma }_{i}}}} \equiv {{S}_{i}}.$

Теперь индукцией по $i = 0, \ldots ,n$ мы покажем, что ${{\alpha }_{i}}$-спектр консервативности теории ${{S}_{i}}$ совпадает с ${\text{`}}f|{{\alpha }_{i}}$. Теорема 4.4 получается отсюда при $i = n$. Для $i = 0$ утверждение тривиально.

Допустим, что утверждение имеет место для i и докажем его для i + 1. По лемме 4.6 ${\text{or}}{{{\text{d}}}_{\alpha }}({{S}_{{i + 1}}})$ = ord_α(S_i) для всех $\alpha < {{\alpha }_{i}}$. Поэтому мы можем считать, что ${{\alpha }_{i}} \leqslant \alpha < {{\alpha }_{{i + 1}}}$. В этом случае, поскольку сложность теории ${{S}_{i}}$ есть ${{\Pi }_{{ < {{\alpha }_{i}}}}}$ и ${{S}_{i}}$ корректна,

${\text{or}}{{{\text{d}}}_{\alpha }}({{S}_{{i + 1}}}) = {\text{or}}{{{\text{d}}}_{\alpha }}({{S}_{i}} \cup {{\bar {R}}}_{{ < {{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}) = {\text{or}}{{{\text{d}}}_{\alpha }}({{\bar {R}}}_{{ < {{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}).$

Наконец, по лемме 4.5

${{\bar {R}}}_{{ < {{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}{{ \equiv }_{\alpha }}{{\bar {R}}}_{\alpha }^{{{{\gamma }_{{i + 1}}}}}.$

Значит, ${\text{or}}{{{\text{d}}}_{\alpha }}({{\bar {R}}}_{{ < {{\alpha }_{{i + 1}}}}}^{{{{\gamma }_{{i + 1}}}}}) = {{\gamma }_{{i + 1}}} = f(\alpha )$. Теорема 4.4 доказана.

Список литературы

Beklemishev L., Pakhomov F. Reflection algebras and conservation results for theories of iterated truth. Annals of Pure and Applied Logic, 2022. https://doi.org/10.1016/j.apal.2022.103093
Beklemishev L.D. Proof-theoretic analysis by iterated reflection. Archive for Mathematical Logic. 2003. V. 42. P. 515–552.
Beklemishev L.D. Veblen hierarchy in the context of provability algebras. In P. Hájek, L. Valdés-Villanueva, and D. Westerståhl, editors, Logic, Methodology and Philosophy of Science, Proceedings of the Twelfth International Congress (Kings College Publications, London, 2005), p. 65–78.
Beklemishev L.D. Reflection calculus and conservativity spectra. Russian Math. Surveys. 2018. V. 73. № 4. P. 569–613. Russian original: Uspekhi Matematicheskikh Nauk. 2018. V. 73. № 4 (442). P. 3–52.
Feferman S. Arithmetization of metamathematics in a general setting. Fundamenta Mathematicae. 1960. V. 49. P. 35–92.
Fernández-Duque D., Joosten J. Models of transfinite provability logic. J. Symbolic Logic. 2013. V. 78. № 2. P. 543–561.
Ignatiev K.N. On strong provability predicates and the associated modal logics. The Journal of Symbolic Logic. 1993. V. 58. P. 249–290.
Joosten J.J. Turing–Taylor expansions of arithmetical theories. Studia Logica. 2015. V. 104. P. 1225–1243. https://doi.org/10.1007/s11225-016-9674-z
Schmerl U.R. A fine structure generated by reflection formulas over Primitive Recursive Arithmetic. In M. Boffa, D. van Dalen, and K. McAloon, editors, Logic Colloquium'78. North Holland, Amsterdam, 1979, p. 335–350.
Schmerl U.R. A proof-theoretical _ne structure in systems of ramified analysis. Archive for Mathematical Logic. 1982. V. 22. P. 167–186.

Дополнительные материалы отсутствуют.

Инструменты

следующая статья выпуска содержание выпуска

Доклады Российской академии наук. Математика, информатика, процессы управления

Архивы выпусков Информация о журнале Отправить рукопись в журнал