| Математические заметки |
|
|
|
|
|
Независимость схемы свертки в арифметике второго порядка от счетного выбора без параметров В. Г. Кановей  , В. А. Любецкий Институт проблем передачи информации им. А. А. Харкевича Российской академии наук, г. Москва
Английская версия:
Mathematical Notes, 2025, Volume 117, Issue 2, Pages DOI: https://doi.org/10.1134/S0001434625010250 
Реферативные базы данных:
   1. ВведениеСтруктура и дедуктивные свойства арифметики Пеано второго порядка $\mathbf{PA}_2$ долгое время остаются одной из центральных тем в логике и основаниях математики. Анализируя эти вопросы, Крайзель указал в [1; § III, с. 366], что выбор подсистем “является центральной проблемой”. Симпсон в монографии [2] изложил современные подходы к подсистемам $\mathbf{PA}_2$, выделенным разными ограничениями на тип формул, участвующих в схемах аксиом, в основном в терминах кванторной сложности формул. Другое возможное ограничение было указано еще Крайзелем [1]: [...] если вы убеждены в значимости чего-либо, например, данной схемы аксиом, то естественным будет изучить детали, такие как эффект от параметров1. В этом контексте параметрами являются свободные переменные в схемах аксиом рассматриваемых теорий. С целью изучения упомянутого “эффекта параметров”, можно ставить вопрос о сравнительной силе той или иной схемы аксиом $S$ по сравнению с ее беспараметрической подсхемой $S^\ast$. Настоящая статья посвящена роли параметров в схеме аксиом свертки $\mathbf{CA}$ в арифметике второго порядка $\mathbf{PA}_2$. Следуя [1]–[3], арифметика второго порядка $\mathbf{PA}_2$ определяется как теория в языке $\mathcal L(\mathbf{PA}_2)$ с двумя сортами переменных – для натуральных чисел (тип 0) и для их множеств (тип 1). Традиционно $j,k,m,n$ используются для переменных по $\omega$, $x,y,z$ для переменных по $\mathscr P(\omega)$. Аксиоматика $\mathbf{PA}_2$ включает следующее:
Следующая схема нередко рассматривается в связи с $\mathbf{PA}_2$. Мы используем $\mathbf{AC}_\omega$ вместо более обычной аббревиатуры $\mathbf{AC}$ в контексте $\mathbf{PA}_2$, поскольку $\mathbf{AC}$ резервируется здесь для обозначения полной аксиомы выбора в теории множеств. Схема (счетного) выбора $\mathbf{AC}_\omega$ – это
$$
\begin{equation*}
\forall\, k\,\exists\, x\ \Phi(k,x)\Longrightarrow \exists\, x\,\forall\, k\ \Phi(k,(x)_k))
\end{equation*}
\notag
$$
для любой формулы $\Phi$ с разрешенными параметрами, где $(x)_k=\{j\colon 2^k(2j+1)-1\in x\}$. Через $\mathbf{CA}(\mathbf\Sigma^1_2)$ обозначается схема $\mathbf{CA}$, ограниченная требованием, чтобы $\Phi$ была $\mathbf\Sigma^1_2$ формулой (параметры разрешены). Напомним, что $\mathbf\Sigma^1_2$-формулами называются $\mathcal L(\mathbf{PA}_2)$-формулы вида $\exists\, x\,\forall\, y\,\Psi$, где $\Psi$ – арифметическая формула, т.е. не содержащая кванторов по переменным по $\mathscr P(\omega)$. Через $\mathbf{CA}^\ast$ обозначается беспараметрическая часть $\mathbf{CA}$ (т.е. $\Phi(k)$ в формулировке не содержит свободных переменных кроме $k$). Aналогично понимается $\mathbf{AC}_\omega^\ast$. Наконец, $\mathbf{PA}_2^\ast$ будет обозначать подтеорию $(1)+(2)+(3)+\mathbf{CA}^\ast$ теории $\mathbf{PA}_2$. Теперь формулируется главный результат этой статьи. Теорема 1.1. Cуществует генерическое расширение $\mathbf L[G]$ класса $\mathbf L$ конструктивных множеств и множество $X\in\mathbf L[G]$, для которого $\mathscr P(\omega)\cap\mathbf L\subseteq X\subseteq\mathscr P(\omega)$ и $\langle\omega;X\rangle$ – модель теории $\mathbf{PA}_2^\ast + \mathbf{CA}(\mathbf\Sigma^1_2)+\mathbf{AC}_\omega^\ast$, в которой не выполнен некоторый конкретный пример $\mathbf{CA}$ c параметрами. Таким образом, схема $\mathbf{CA}$ недоказуема в $\mathbf{PA}_2^\ast + \mathbf{CA}(\mathbf\Sigma^1_2)+\mathbf{AC}_\omega^\ast$. Замечание 1.2. В формулировке теоремы мы не делаем различия между параметрами типа 0 и типа 1. Однако представленная модель является $\omega$-моделью в теоретико-множественном универсуме, где параметры типа 0 интерпретируются как обычные натуральные числа и потому тривиально элиминируются. Поэтому теорема 1.1 остается верной в предположении, что в схемах $\mathbf{PA}_2^\ast$ и $\mathbf{AC}_\omega^\ast$ запрещены только параметры типа 1 (но разрешены параметры типа 0). 2. КомментарииИсследования роли параметров в схемах аксиом начались еще в ранние годы современной теории множеств. В частности, Гузицки [4] установил, используя модели $\mathbf{ZF}$ с генерической сверткой кардиналов по Леви–Соловею [5], [6], что счетная схема выбора $\mathbf{AC}_\omega$, в языке $\mathbf{PA}_2$, не следует из своей беспараметрической подсхемы $\mathbf{AC}_\omega^\ast$. Этот же результат о разделении $\mathbf{AC}_\omega$ и $\mathbf{AC}_\omega^\ast$, но при помощи моделей с сохранением кардиналов, содержится в нашей недавней работе [7]. Из этого результата, кстати, следует, что $\mathbf{AC}_\omega^\ast$ нельзя заменить на $\mathbf{AC}_\omega$ (c разрешенными параметрами) в теореме 1.1 по той причине, что $\mathbf{AC}_\omega$ влечет полную $\mathbf{CA}$ (c параметрами), так что такое усиление теоремы невозможно. О некоторых результатах о беспараметрических подсхемах выделения и подстановки в теории множеств Цермело–Френкеля $\mathbf{ZF}$ см. в работах [8]–[10]. Отождествляя теории с их дедуктивными замыканиями, мы заключаем из теоремы 1.1 (даже в ослабленной форме без $\mathbf{AC}_\omega^\ast$), что
$$
\begin{equation*}
\bigl(\mathbf{PA}_2^\ast + \mathbf{CA}(\mathbf\Sigma^1_2)\bigr)\subsetneqq\mathbf{PA}_2.
\end{equation*}
\notag
$$
Работы по подсистемам теории $\mathbf{PA}_2$ дали немало случаев, когда строгое включение $S\subsetneqq S'$ выполнено для какой-то пары подсистем $S,S'$, см. к примеру [2]. В ряде случаев такие результаты получаются посредством вывода в $S'$ формальной непротиворечивости $S$. Однако для результата выше это оказывается не так, поскольку
$$
\begin{equation*}
\text{теории }\mathbf{PA}_2^\ast,\ \mathbf{PA}_2^\ast + \mathbf{CA}(\mathbf\Sigma^1_2) \text{ и полная }\mathbf{PA}_2\text{ равнонепротиворечивы}
\end{equation*}
\notag
$$
согласно одной из теорем в [11], которая также упомянута в cтатье [12]. Эта равнонепротиворечивость также следует из более сильного результата в [13; 1.5]. (Авторы благодарны Али Энаяту за ссылки на работы [11]–[13] в отношении этого результата о равнонепротиворечивости.) Что касается самого результата теоремы 1.1, то он является усилением нашего предшествующего результата в этом направлении из статьи [14], где установлена невыводимость $\mathbf{CA}$ в $\mathbf{PA}_2^\ast + \mathbf{CA}(\mathbf\Sigma^1_2)$ (т.е. без $\mathbf{AC}_\omega^\ast$). Этот более слабый результат с наброском доказательства также опубликован в нашей статье [7]. Усиление в теореме 1.1 состоит в том, что схема $\mathbf{AC}_\omega^\ast$ (т.е. некоторый ее конкретный пример) не выводится в $\mathbf{PA}_2^\ast + \mathbf{CA}(\mathbf\Sigma^1_2)$ (и даже в полной $\mathbf{PA}_2$), как установлено в [4], [5]. И несколько слов о роли $\mathbf{CA}(\mathbf\Sigma^1_2)$ в утверждении теоремы 1.1. Модель для $\mathbf{PA}_2^\ast$ (без $\mathbf{CA}(\mathbf\Sigma^1_2)$), в которой не выполненa полная схема $\mathbf{CA}$, строится гораздо более простыми средствами, чем доказательство теоремы 1.1. Именно, берем генерическую по Коэну над $\mathbf L$ последовательность $\langle x_i\rangle_{i<\omega}$ множеств $x_i\subseteq\omega$ и образуем множество $X=(\mathscr P(\omega)\cap\mathbf L)\cup \{x_i\colon i<\omega\}$. Тогда $\langle\omega;X\rangle$ – модель $\mathbf{PA}_2^\ast$, где полная $\mathbf{CA}$ не выполнена поскольку $X$ не содержит дополнений $\omega\smallsetminus x_i$ множеств $x_i$. Таким образом, теория $\mathbf{PA}_2^\ast$ с беспараметрической сверткой недостаточно сильна, чтобы доказать $\mathbf{CA}$ даже в той элементарной форме, что каждое множество имеет дополнение. Теории с таким свойством вряд ли интересны, и именно поэтому некоторую часть $\mathbf{CA}$ с параметрами приходится добавить. Как показывает наша теорема, добавление $\mathbf{CA}(\mathbf\Sigma^1_2)$ сохраняет в силе главный результат. В целом, изучение подсистем арифметики второго порядка продолжает оставаться предметом интереса в современных работах, см. к примеру [15], и эта наша статья принадлежит данному направлению. 3. Обобщенный итерированный форсинг по СаксуДоказательство теоремы 1.1 использует сложную итерацию форсинга Сакса, разработанную в [16] на основе более ранних работ [17], [18] и др. Также будет использована кодировка при помощи степеней конструктивности, в духе метода, изложенного в связи с теоремой T3106 в статье [19; с. 143]. Книга Кюнена [20] дается как главный источник по методу форсинга. Мы в особенности ссылаемся на раздел IV.6 в книге в отношении подхода названного там “forcing over the universe” (форсинг над универсумом всех множеств). Конструктивный универсум $\mathbf L$ используется как исходная модель. Далее в этом пункте все рассуждения проводятся в универсуме $\mathbf L$. Напомним, что $2^{<\omega}=$ все кортежи чисел $0,1$. Мы определяем в $\mathbf L$ множество
$$
\begin{equation}
\boldsymbol I=(\omega_1\times2^{<\omega})\cup\omega_1, \qquad \boldsymbol I\in\mathbf L,
\end{equation}
\tag{1}
$$
частично упорядоченное так, что $\langle\gamma,s\rangle\preccurlyeq\langle\beta,t\rangle$, когда $\gamma=\beta$ и $s\subseteq t$ в $2^{<\omega}$; при этом каждый ординал $\gamma<\omega_1$ (вторая часть $\boldsymbol I$) остается $\preccurlyeq$-несравнимым в $\boldsymbol I$ ни с каким иным элементом. Заметим, что если $\gamma<\omega_1$, то $\gamma$ принадлежит $\boldsymbol I$ как элемент множества $\omega_1$, и пара $\langle\gamma,\Lambda\rangle$ (где $\Lambda\in2^{<\omega}$ – пустой кортеж) также принадлежит $\boldsymbol I$ как элемент множества $\omega_1\times2^{<\omega}$, причем мы не отождествляем $\gamma$ и $\langle\gamma,\Lambda\rangle$, это разные (и $\preccurlyeq$-несравнимые) элементы $\boldsymbol I$, причем оба $\preccurlyeq$-минимальны в $\boldsymbol I$. Буквы $\boldsymbol i,\boldsymbol j$ используются для обозначения элементов $\boldsymbol I$. Если $\boldsymbol i=\gamma$ или $\boldsymbol i=\langle\gamma,s\rangle$ принадлежит $\boldsymbol I$, то обозначим $\gamma=|\boldsymbol i|$. Положим $\mathbf\Xi=\{\text{все не более чем счетные начальные сегменты }\zeta\subseteq\boldsymbol I\}$. Буквы $\xi,\eta,\zeta,\vartheta$ будут обозначать начальные сегменты из $\mathbf\Xi$. Если $\boldsymbol i\in\zeta\in\mathbf\Xi$, то рассматриваются начальные сегменты $[\prec\boldsymbol i]=\{\boldsymbol j\in\boldsymbol I\colon \boldsymbol j\prec\boldsymbol i\}$ и $\zeta[\not\succcurlyeq\boldsymbol i]=\{\boldsymbol j\in\zeta\colon\boldsymbol j\not\succcurlyeq\boldsymbol i\}$ и аналогично определенные $[\preccurlyeq\boldsymbol i]$, $\zeta[\not\succ\boldsymbol i]$. Далее, рассматривается канторов дисконтинуум $\mathscr D=2^\omega$. Если $\xi$ счетно, то $\mathscr D^\xi$ есть произведение $\xi$ копий пространства $\mathscr D$ с топологией произведения. Пусть $\eta\subseteq\xi\in\mathbf\Xi$. Если $x\in\mathscr D^\xi$, то через $x\upharpoonright\eta\in\mathscr D^\eta$ обозначим обычное ограничение. Если $X\subseteq\mathscr D^\xi$, то положим $X\upharpoonright \eta=\{x\upharpoonright\eta\colon x\in X\}$. Для краткости будем писать $x\upharpoonright_{\prec\boldsymbol i}$ вместо $x\upharpoonright[\prec\boldsymbol i]$, $X\upharpoonright_{\not\succcurlyeq\boldsymbol i}$ – вместо $X\upharpoonright\xi[\not\succcurlyeq\boldsymbol i]$, и т.п. Если же $Y\subseteq\mathscr D^\eta$, то положим $Y\upharpoonright^{-1} \xi=\{x\in\mathscr D^\xi\colon x\upharpoonright\eta\in Y\}$. Определение 3.1 [16]. Если $\zeta\in\mathbf\Xi$, то $\mathbf{Perf}_\zeta$ состоит из всех множеств $X\subseteq\mathscr D^\zeta$, для которых имеется гомеоморфизм $H\colon \mathscr D^\zeta\overset{\text{на}}{\longrightarrow} X$, удовлетворяющий для всех $x_0,x_1\in\operatorname{dom} H$ и $\xi\in\mathbf\Xi$, $\xi\subseteq\zeta$. Гомеоморфизмы $H$, удовлетворяющие этому условию, называются сохраняющими проекцию. Другими словами, множества из $\mathbf{Perf}_\zeta$ – это образы $\mathscr D^\zeta$ при сохраняющих проекцию гомеоморфизмах. Замечание 3.2. Пустое множество $\varnothing$ формально принадлежит $\mathbf\Xi$, и тогда $\mathscr D^\varnothing=\{\varnothing\}$, и очевидно, что $\mathbb I=\{\varnothing\}$ – единственное множество в $\mathbf{Perf}_\varnothing$. Для удобства читателя мы приведем с соответствующей ссылкой одну лемму о множествах из $\mathbf{Perf}_\zeta$, которая доказана в [16]. Лемма 3.3 (см. [16; лемма 8]). Если $\zeta\in\mathbf\Xi$, $X\in\mathbf{Perf}_\zeta$, $X'\subseteq X$ открыто в $X$, и $x_0\in X'$, то имеется множество $X''\in\mathbf{Perf}_\zeta$, $X''\subseteq X'$, открыто-замкнутое в $X$ и содержащее $x_0$. 4. Форсинг и базовое расширениеЗдесь вводится форсинг для доказательства теоремы 1.1 и рассматривается соответствующее генерическое расширение. Мы продолжаем рассуждать в $\mathbf L$. Напомним, что частично упорядоченное множество $\boldsymbol I\in \mathbf L$ определено через (1) в п. 3, а $\mathbf\Xi\in\mathbf L$ – множество всех не более чем счетных начальных сегментов $\xi\subseteq\boldsymbol I$ в $\mathbf L$. Если $\zeta\in\mathbf\Xi$, то пусть $\mathbb P_\zeta=(\mathbf{Perf}_\zeta)^{\mathbf L}$. Множество $\mathbb P=\mathbb P_{\boldsymbol I}=\bigcup_{\zeta\in\mathbf\Xi}\mathbb P_\zeta\in \mathbf L$ и есть наш форсинг. Его элементы $X\in \mathbb P$ будут называться “условиями”. Для определения порядка мы положим $\|X\|=\zeta$ для всех $X\in\mathbb P_\zeta$. Теперь определяем $X\leqslant Y$ (т.е. $X$ сильнее, чем $Y$), когда $\zeta=\|Y\|\subseteq \|X\|$ и $X\upharpoonright\zeta\subseteq Y$. Замечание 4.1. Множество $\mathbb I=\{\varnothing\}$, как и в замечании 3.2, принадлежит $\mathbb P$ и является $\leqslant$-наибольшим (т.е. самым слабым) “условием” в $\mathbb P$. Замечание 4.2. Пусть множество $G\subseteq\mathbb P$ является $\mathbb P$-генерическим над $\mathbf L$. Если $X\in\mathbb P_\zeta$ в $\mathbf L$ то $X$ на самом деле не является замкнутым множеством в $\mathscr D^\zeta$ в $\mathbf L[G]$. Однако его можно преобразовать в замкнутое множество в $\mathbf L[G]$ операцией замыкания. При этом топологическое замыкание $X^{\#}$ такого $X$ в $\mathscr D^\zeta$, определенное в $\mathbf L[G]$, принадлежит $\mathbf{Perf}_\zeta$ уже в смысле расширения $\mathbf L[G]$. Согласно лемме 3.3 в ситуации замечания 4.2 существует (единственный) массив $\mathbf{a}[G]=\langle\mathbf{a}_{\boldsymbol i}[G]\rangle_{\boldsymbol i\in\boldsymbol I}$ точек $\mathbf{a}_{\boldsymbol i}[G]\in2^\omega$, для которого мы имеем $\mathbf{a}[G]\upharpoonright\xi\in X^\#$ всякий раз, когда $X\in G$ и $\|X\|=\xi$. Тогда $\mathbf L[G]=\mathbf L[\langle\mathbf{a}_{\boldsymbol i}[G]\rangle_{\boldsymbol i\in\boldsymbol I}]=\mathbf L[\mathbf{a}[G]]$ есть $\mathbb P$-генерическое расширение $\mathbf L$. Такие массивы $\mathbf{a}=\mathbf{a}[G]$ также будут называться $\mathbb P$-генерическими. Теорема 4.3 (см. [16; теоремы 24, 31]). Все кардиналы в $\mathbf L$ остаются кардиналами в $\mathbf L[G]$. Каждая точка $\mathbf{a}_{\boldsymbol i}[G]$ является генерической по Саксу над $\mathbf L[\mathbf{a}[G]\upharpoonright_{\prec\boldsymbol i}]$. Следующие четыре результата получены в [16]. В каждой из лемм, множество $G\subseteq \mathbb P $ является $\mathbb P$-генерическим над $\mathbf L$. Лемма 4.4 (см. [16; лемма 22]). Если конечные или счетные множества $\eta,\xi\subseteq\boldsymbol I$ в $\mathbf L$ удовлетворяют $\forall\,\boldsymbol j\in\eta\ \exists\, \boldsymbol i\in\xi\ (\boldsymbol j\preccurlyeq\boldsymbol i)$, то $\mathbf{a}[G]\upharpoonright\eta\in\mathbf L[\mathbf{a}[G]\upharpoonright\xi]$. Лемма 4.5 (см. [16; лемма 26]). Если $\boldsymbol K\in\mathbf L$ – начальный сегмент в $\boldsymbol I$, и $\boldsymbol i\in\boldsymbol I\smallsetminus\boldsymbol K$, то $\mathbf{a}_{\boldsymbol i}[G]\not\in\mathbf L[\mathbf{a}[G]\upharpoonright\boldsymbol K]$. Лемма 4.6 (см. [16; следствие 27]). Если $\boldsymbol i\not=\boldsymbol j$ в $\boldsymbol I$, то $\mathbf{a}_{\boldsymbol i}[G]\not=\mathbf{a}_{\boldsymbol j}[G]$, и даже $\mathbf L[\mathbf{a}_{\boldsymbol i}[G]]\not=\mathbf L[\mathbf{a}_{\boldsymbol j}[G]]$. Лемма 4.7 (см. [16; лемма 29]). Если $\boldsymbol K\in\mathbf L$ – начальный сегмент в $\boldsymbol I$ и $r\in2^\omega\cap\mathbf L[G]$, то либо $r\in\mathbf L[\mathbf{a}\upharpoonright\boldsymbol K]$ либо имеется $\boldsymbol i\not\in\boldsymbol K$, для которого $\mathbf{a}_{\boldsymbol i}[G]\in\mathbf L[r]$. Мы применим эти леммы в доказательстве следующей теоремы. Через $\leqslant_{\mathbf L}$ обозначим порядок относительной конструктивности на $2^\omega$, так что $x\leqslant_{\mathbf L} y$ равносильно $x\in\mathbf L[y]$. Через $x<_{\mathbf L} y$ обозначим строгое отношение: $x\leqslant_{\mathbf L} y$ но $y\not\leqslant_{\mathbf L} x$, а эквивалентность $x\equiv_{\mathbf L} y$ означает, что $x\leqslant_{\mathbf L} y$ и $y\leqslant_{\mathbf L} x$. Теорема 4.8. Пусть $\boldsymbol i\in\boldsymbol I$ и $r\in\mathbf L[G]\cap2^\omega$. Тогда Доказательство. (i) Используем лемму 4.4 при $\eta=\{\boldsymbol j\}$ и $\xi=\{\boldsymbol i\}$.
(ii) Используем лемму 4.5 для $\boldsymbol K=[\preccurlyeq\boldsymbol i]$. (iii) Если существует $\boldsymbol j\in\mathcal I$, $\boldsymbol j\preccurlyeq\boldsymbol i$, для которого $\mathbf{a}_{\boldsymbol j}[G]\in\mathbf L[r]$, то пусть $\boldsymbol j$ обозначает наибольшее из них, и пусть $\xi=[\preccurlyeq\boldsymbol j]$ (конечный начальный сегмент в $\boldsymbol I$). Согласно лемме 4.7 либо $r\in\mathbf L[\mathbf{a}[G]\upharpoonright\xi]$, либо имеется $\boldsymbol i'\not\in\xi$ с $\mathbf{a}_{\boldsymbol i'}[G]\in\mathbf L[r]$. В первом случае $r\in\mathbf L[\mathbf{a}_{\boldsymbol j}[G]]$ по (i), так что $\mathbf L[r]=\mathbf L[\mathbf{a}_{\boldsymbol j}[G]]$ по выбору $\boldsymbol j$. Во втором же случае мы имеем $\mathbf{a}_{\boldsymbol i'}[G]\in\mathbf L[a_{\boldsymbol i}[G]]$, так что $\boldsymbol i'\preccurlyeq\boldsymbol i$ по (ii). Но это противоречит выбору $\boldsymbol j$ и $\boldsymbol i'$. Наконец, если нет $\boldsymbol j\in\mathcal I$, $\boldsymbol j\preccurlyeq\boldsymbol i$, для которого $\mathbf{a}_{\boldsymbol j}[G]\in\mathbf L[r]$, то аналогичное рассуждение с $\xi=\varnothing$ дает $r\in\mathbf L$. (iv) Соотношение $\mathbf{a}_{\boldsymbol j}[G]<_{\mathbf L}\mathbf{a}_{\boldsymbol i^\smallfrown e}[G]$ вытекает из лемм 4.4 и 4.5. Если теперь $y<_{\mathbf L}\mathbf{a}_{\boldsymbol i^\smallfrown e}[G]$, то $y\in\mathbf L$ или же $y\equiv_{\mathbf L} \mathbf{a}_{\boldsymbol j}[G]$ для какого-то $\boldsymbol j\preccurlyeq\boldsymbol i^\smallfrown e$ согласно (iii), причем во втором случае $\boldsymbol j\prec\boldsymbol i^\smallfrown e$, откуда $\boldsymbol j\preccurlyeq\boldsymbol i$, и, наконец, $y\leqslant_{\mathbf L}\mathbf{a}_{\boldsymbol i}[G]$. (v) Согласно (iv) достаточно доказать, что $x\leqslant_{\mathbf L}\mathbf{a}_{\boldsymbol i^\smallfrown 0}[G]$ или $x\leqslant_{\mathbf L}\mathbf{a}_{\boldsymbol i^\smallfrown 1}[G]$. Допустим, что $x\not\leqslant_{\mathbf L}\mathbf{a}_{\boldsymbol i^\smallfrown 0}[G]$. Тогда по лемме 4.7 имеется такое $\boldsymbol j\in\boldsymbol I$ что $\boldsymbol j\not\preccurlyeq\boldsymbol i^\smallfrown0$ и $\mathbf{a}_{\boldsymbol i_0}[G]\leqslant_{\mathbf L} x$. Если $\mathbf{a}_{\boldsymbol j}[G]<_{\mathbf L} x$ строго, то $\mathbf{a}_{\boldsymbol j}[G]\leqslant_{\mathbf L}\mathbf{a}_{\boldsymbol i}[G]$ по свойству правильного наследника, а значит, $\boldsymbol i_0\preccurlyeq\boldsymbol i$, что противоречит $\boldsymbol i_0\not\preccurlyeq\boldsymbol i^\smallfrown0$, как и выше. Поэтому на самом деле $\mathbf{a}_{\boldsymbol i_0}[G]\equiv_{\mathbf L} x$. Тогда мы имеем $\boldsymbol i_0=\boldsymbol i^\smallfrown0$ или $\boldsymbol i_0=\boldsymbol i^\smallfrown1$, так как $x$ – правильный наследник. Но тогда $\boldsymbol i_0=\boldsymbol i^\smallfrown1$, поскольку предполагается $x\not\leqslant_{\mathbf L}\mathbf{a}_{\boldsymbol i^\smallfrown 0}[G]$, что и требовалось. 5. МодельПусть множество $G$ является $\mathbb P$-генерическим над $\mathbf L$ и $\mathbf{a}=\mathbf{a}[G]=\langle\mathbf{a}_{\boldsymbol i}\rangle_{\boldsymbol i\in\boldsymbol I}\in \mathscr D^{\boldsymbol I}$. Рассмотрим множество $\boldsymbol J[G]=\boldsymbol J[\mathbf{a}]\in\mathbf L[G]=\mathbf L[\mathbf{a}]$ всех $\boldsymbol i\in\boldsymbol I$, для которых выполнено одно из следующих утверждений: либо $\boldsymbol i=\langle\gamma,0^m\rangle$, гдe $\gamma<\omega_1$, $m<\omega$, $0^m=\langle0,0,\dots,0\rangle$ ($m$ членов равных $0$); либо $\boldsymbol i=\langle\gamma,{0^{m}}^\smallfrown1\rangle$, гдe $\gamma<\omega_1$ и $m<\omega$, $\mathbf{a}_\gamma[G](m)=1$. Таким образом, если $\gamma<\omega_1$, то значение $\mathbf{a}_\gamma[G](m)=1\text{ или }0$ для любого данного числа $m<\omega$ кодируется посредством наличия (для значения 1) или соответственно отсутствия (для 0) развилки из кортежей $\langle\gamma,{0^m}^\smallfrown0\rangle=\langle\gamma,0^{m+1}\rangle$ и $\langle\gamma,{0^m}^\smallfrown1\rangle$ над кортежем $\langle\gamma,0^m\rangle$ в $\boldsymbol J[G]$. При этом сами ординалы $\gamma<\omega_1$ (вторая часть определения $\boldsymbol I$ согласно (1) в п. 3) множеству $\boldsymbol J[G]=\boldsymbol J[\mathbf{a}]$ не принадлежат. На этом и будет построен контрпример к $\mathbf{CA}$ в определенной через $\boldsymbol J[\mathbf{a}]$ модели $W[\mathbf{a}]$ из (2). Именно, для любого $\gamma<\omega_1$ множество $\{m<\omega\colon \mathbf{a}_\gamma[G](m)=1\}$ не будет принадлежать $W[\mathbf{a}]$, поскольку $\gamma\notin\boldsymbol J[\mathbf{a}]$, но будет определимо в $W[\mathbf{a}]$ подходящей формулой языка $\mathbf{PA}_2$ c параметром $\mathbf{a}_{\langle\gamma,\Lambda\rangle}[G]$ через указанное свойство развилок. Итак, мы определяем $\mathcal L(E)=\bigcup_{x\in E}{\mathbf L[x]}$ для любого множества $E$. Понятно, что $\mathcal L(E)\subseteq\mathbf L[E]$, но в принципе $\mathcal L(E)$ может и не быть моделью $\mathbf{ZF}$. Наконец, полагаем
$$
\begin{equation}
E[\mathbf{a}]=\{\mathbf{a}\upharpoonright\xi\colon \xi\in\mathbf\Xi\land\xi\subseteq\boldsymbol J[\mathbf{a}]\} \quad\text{и}\quad W[\mathbf{a}]=\mathscr P(\omega)\cap\mathcal L(E[\mathbf{a}]).
\end{equation}
\tag{2}
$$
Лемма 5.1. Если $\boldsymbol i\notin\boldsymbol J[\mathbf{a}]$, то $\mathbf{a}_{\boldsymbol i}\notin W[\mathbf{a}]$. Доказательство. Мы не можем сразу сослаться на лемму 4.5, так как $\boldsymbol J[\mathbf{a}]\notin\mathbf L$. Однако множество $\boldsymbol K=\{\boldsymbol j\in\boldsymbol I\colon \boldsymbol i\not\preccurlyeq\boldsymbol j\}$ принадлежит $\mathbf L$ и удовлетворяет $\boldsymbol J[\mathbf{a}]\subseteq\boldsymbol K\subseteq \boldsymbol I$. Мы имеем $\boldsymbol i\notin\boldsymbol K$, следовательно, $\mathbf{a}_{\boldsymbol i}\notin\mathbf L[\mathbf{a}\upharpoonright\boldsymbol K]$ по лемме 4.5. С другой стороны, выполнено $W[\mathbf{a}]\subseteq \mathbf L[\mathbf{a}\upharpoonright\boldsymbol K]$, откуда и следует результат. Имея в виду теорему 1.1, мы докажем, что $\langle\omega;W[\mathbf{a}]\rangle$ выполняет $\mathbf{PA}_2^\ast+\mathbf{CA}(\mathbf\Sigma^1_2)+\mathbf{AC}_\omega^\ast$, но полная свертка $\mathbf{CA}$ неверна в $\langle\omega;W[\mathbf{a}]\rangle$. Это утверждение разбито на две теоремы. Теорема 5.2. Если множество $G$ является $\mathbb P$-генерическим над $\mathbf L$ и $\mathbf{a}=\mathbf{a}[G]$, то $\langle\omega;W[\mathbf{a}]\rangle\models\mathbf{PA}_2^\ast +\mathbf{CA}(\mathbf\Sigma^1_2)+\neg\mathbf{CA}$. Доказательство. То, что $\langle\omega;W[\mathbf{a}]\rangle$ выполняет все аксиомы $\mathbf{PA}_2$, кроме $\mathbf{CA}$, тривиально. Истинность свертки $\mathbf{CA}(\mathbf\Sigma^1_2)$ (с параметрами) в $\langle\omega;W[\mathbf{a}]\rangle$ следует из теоремы абсолютности Шенфилда.
Докажем, что полная $\mathbf{CA}$ без ограничения на формулы ложна в $\langle\omega;W[\mathbf{a}]\rangle$. Пусть $\gamma<\omega_1^{\mathbf L}$, так что $\gamma$ и каждая пара $\langle\gamma,s\rangle$, $s\in2^{<\omega}$, принадлежат $\boldsymbol I$ по определению (1) в п. 3. В частности, $\boldsymbol i_0=\langle\gamma,\Lambda\rangle\in\boldsymbol I$, где $\Lambda$ – пустой кортеж. К тому же $\gamma$ (как элемент $\boldsymbol I$) не принадлежит $\boldsymbol J[\mathbf{a}]$. Мы собираемся доказать, что точка $\mathbf{a}_\gamma$ не принадлежит $W[\mathbf{a}]$, но определима в $\langle\omega;W[\mathbf{a}]\rangle$. Шаг 1. Имеем $\mathbf{a}_\gamma\notin W[\mathbf{a}]$ по лемме 5.1, так как $\gamma\notin\boldsymbol J[G]$. Шаг 2. Мы утверждаем, что точка $\mathbf{a}_\gamma$ определима в $\langle\omega;W[\mathbf{a}]\rangle$ с параметром $\mathbf{a}_{\boldsymbol i_0}$, гдe $\boldsymbol i_0=\langle\gamma,\Lambda\rangle\in\boldsymbol J[\mathbf{a}]$. Более точно, утверждается, что при любом $m<\omega$:
$$
\begin{equation}
\mathbf{a}_\gamma(m)=1 \quad\Longleftrightarrow\quad
\begin{array}{l} \text{существует набор точек}\\[-.5mm]
b_0,b_1,\dots,b_m,b_{m+1} \text{ и } b'_{m+1} \text{ в } 2^\omega,\\[-.5mm]
\text{для которого выполнено следующее:}\\[-.5mm]
b_0= \mathbf{a}_{\boldsymbol i_0}, \text{ каждая } b_{k+1} \text{ есть правильный наследник } b_k\ (k\leqslant m),\\[-.5mm]
b'_{m+1} \text{ есть правильный наследник } b_m, \text{ и } b'_{m+1}\not\equiv_{\mathbf L} b_{m+1}. \end{array}
\end{equation}
\tag{3}
$$
Формула в правой части эквивалентности (3) основана на геделевой канонической $\varSigma^1_2$-формуле для $\leqslant_{\mathbf L}$, которая абсолютна для $W[\mathbf{a}]$ по определению $W[\mathbf{a}]$. Следовательно, (3) означает, что $\mathbf{a}_\gamma[G]$ в самом деле определима в $\langle\omega;W[\mathbf{a}]\rangle$ с параметром $\mathbf{a}_{\boldsymbol i_0}[G]$. Итак, остается доказать (3). Импликация $\Longrightarrow$. Пусть $\mathbf{a}_\gamma(m)=1$. Тогда $\boldsymbol J[\mathbf{a}]$ содержит элементы $\boldsymbol i_k=\langle\gamma,0^k\rangle$, $k\leqslant m+1$, а также содержит $\boldsymbol i'_{m+1}=\langle\gamma,{0^m}^\smallfrown 1\rangle$. Поэтому точки $b_k=\mathbf{a}_{\boldsymbol i_k}$, $k\leqslant m+1$, и $b'_{m+1}=\mathbf{a}_{\boldsymbol i'_{m+1}}[G]$ принадлежат $W[\mathbf{a}]$. Теперь теорема 4.8, (iv), (ii) влечет то, что точки $b_k$ и $b'_{m+1}$ удовлетворяют правой части (3), что и требовалось. Импликация $\Longleftarrow$. Допустим, что точки $b_k$, $k\leqslant m+1$, и $b'_{m+1}$ удовлетворяют правой части (3). По теореме 4.8, (v) имеется массив чисел $e_1,\dots,e_m,e_{m+1},e'_{m+1}=0,1$, удовлетворяющих $b_k=\mathbf{a}_{\boldsymbol i_k}$ для всех $k\leqslant m+1$, а также $b'_{m+1}=\mathbf{a}_{\boldsymbol i'_{m+1}}$, где $\boldsymbol i_k=\langle\gamma,\langle e_1,\dots,e_k\rangle\rangle$ и $\boldsymbol i'_{m+1}=\langle\gamma,\langle e_1,\dots,e_m,e'_{m+1}\rangle\rangle$. Однако по лемме 5.1 $\boldsymbol i_k\in\boldsymbol J[\mathbf{a}]$ для всех $k\leqslant m+1$, и $\boldsymbol i'_{m+1}\in\boldsymbol J[\mathbf{a}]$, поскольку точки $b_k$ и $b'_{m+1}$ принадлежат $W[\mathbf{a}]$. Тогда очевидно $e_1=\dots=e_m=0$, а также $e_{m+1}=0$ и $e'_{m+1}=1$, либо наоборот, $e_{m+1}=1$ и $e'_{m+1}=0$. Другими словами, пары $\langle\gamma,0^{m+1}\rangle$ и $\langle\gamma,{0^{m}}^\smallfrown1\rangle$ принадлежат $\boldsymbol J[\mathbf{a}]$. Отсюда и следует $\mathbf{a}_\gamma[G](m)=1$, завершая доказательство теоремы 5.2. Теорема 5.3. Если множество $G$ является $\mathbb P$-генерическим над $\mathbf L$ и $\mathbf{a}=\mathbf{a}[G]$, то $\langle\omega;W[\mathbf{a}]\rangle\models\mathbf{AC}_\omega^\ast$ (беспараметрическая). Доказательство этой теоремы основано на технике пермутаций для форсинга $\mathbb P$, излагаемой в следующем пункте. Само доказательство последует в п. 7. 6. ПермутацииРассуждая в $\mathbf L$, рассмотрим группу $\mathbf\Pi\in\mathbf L$ всех таких биекций $\pi\colon \omega_1\overset{\text{на}}{\longrightarrow}\omega_1$, что область нетривиальности $|\pi|=\{\alpha\colon \pi(\alpha)\ne\alpha\}$ ограничена в $\omega_1$, с суперпозицией $\circ$ в роли групповой операции; такие $\pi$ называем пермутациями. Определение 6.1. Любая пермутация $\pi\in\mathbf\Pi$ действует: Лемма 6.2. Если $\xi\in\mathbf\Xi$, $\mathbf{a}\in\mathscr D^{\boldsymbol I}$ и $\pi,\sigma\in\mathbf\Pi$, то $\pi^\smallfrown\mathbf{a}=\mathbf{a}\circ\pi^{-1}$, а также $\pi^\smallfrown(\sigma^\smallfrown \mathbf{a})=(\pi\circ\sigma)^\smallfrown \mathbf{a}$, и $\pi^\smallfrown (\mathbf{a}\upharpoonright\xi)= (\pi^\smallfrown\mathbf{a})\upharpoonright(\pi^\smallfrown\xi)\in\mathscr D^{\pi^\smallfrown\xi}$. Доказательство. К примеру, по определению мы имеем Остальные утверждения также проверяются непосредственно. Для изучения генерических структур вида $\langle\omega;W[\mathbf{a}]\rangle$, рассматривается язык форсинга, т.е. в данном случае обычный $\in$-язык, обогащенный именами вида
$$
\begin{equation}
\left. \begin{array}{rcl} \text{имя }\overset{\bullet}x &- &\text{для любого }x\in\mathbf L, \textit{ отождествляетcя с } x \\ \text{имя }\underline{\sigma\mathbf{a}} &-&\text{для любого }\sigma\in\mathbf\Pi \\ \text{в том числе имя }\underline{\varepsilon\mathbf{a}}=\underline{\mathbf{a}} &-& \text{для тождественной пермутации }\varepsilon\in\mathbf\Pi \\ {\underline {\mathbf\Omega}}&-&\text{одно специальное имя} \end{array}\right\}
\end{equation}
\tag{4}
$$
Действие пермутаций $\pi\in\mathbf\Pi$ продолжается на имена $t$ так:
$$
\begin{equation}
\left. \begin{array}{rcl} \pi^\smallfrown\overset{\bullet} x&=& \overset{\bullet} x \\ \pi^\smallfrown(\underline{\sigma\mathbf{a}}) &=&\underline{(\sigma\circ\pi^{-1})\mathbf{a}} \\ \text{в частности, }\pi^\smallfrown\underline{\mathbf{a}} &=&\underline{(\pi^{-1})\mathbf{a}}\text{ (при }\sigma=\varepsilon) \\ \pi^\smallfrown \underline {\mathbf\Omega} &=&\underline {\mathbf\Omega} \end{array}\right\}
\end{equation}
\tag{5}
$$
Далее, если $\mathbf{a}\in\mathscr D^{\boldsymbol I}$, то интерпретация $t[\mathbf{a}]$ любого имени $t$ определяется так:
$$
\begin{equation}
\left. \begin{array}{rcl} \overset{\bullet} x[\mathbf{a}]&= & x\quad\text{(независимо от }\mathbf{a}) \\ \underline{\sigma\mathbf{a}}[\mathbf{a}]&= &\sigma^\smallfrown\mathbf{a} =\mathbf{a}\circ\sigma^{-1}\quad (\text{принадлежит }\mathscr D^{\boldsymbol I}) \\ \underline {\mathbf\Omega}[\mathbf{a}] &=&\{\sigma^\smallfrown(\mathbf{a}\upharpoonright\xi)\colon \sigma\in\mathbf\Pi\land\xi\in\mathbf\Xi\land\xi\subseteq\boldsymbol J[\mathbf{a}]\} \\ \text{и также } W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]] &=&\mathscr P(\omega)\cap\mathcal L(\underline {\mathbf\Omega}[\mathbf{a}]) =\mathscr P(\omega)\cap\bigcup_{u\in\underline {\mathbf\Omega}[\mathbf{a}]}\mathbf L[u] \quad\text{(ср. с (2))} \end{array}\right\}
\end{equation}
\tag{6}
$$
Лемма 6.3. В условиях теоремы 5.3, если $\pi\in\mathbf\Pi$, то массив $\mathbf{b}=\pi^\smallfrown\mathbf{a}\in\mathscr D^{\boldsymbol I}$ – $\mathbb P$-генерический над $\mathbf L$, $\boldsymbol J[\mathbf{b}]=\pi^\smallfrown(\boldsymbol J[\mathbf{a}])$, и $t[\mathbf{a}]=(\pi^\smallfrown t)[\mathbf{b}]$ для любого имени $t$. Доказательство. Отображение $\boldsymbol i\mapsto\pi^\smallfrown\boldsymbol i$ является порядковым автоморфизмом $\boldsymbol I$, поэтому генеричность $\mathbf{b}$ следует из генеричности $\mathbf{a}$ по общим теоремам о форсинге. Для проверки равенства $\boldsymbol J[\mathbf{b}]=\pi^\smallfrown(\boldsymbol J[\mathbf{a}])$ достаточно заметить, что если $\delta=\pi(\gamma)$, то по определению $\pi^\smallfrown\gamma=\delta$ и $\pi^\smallfrown\langle\gamma,s\rangle=\langle\delta,s\rangle$. (Здесь $\boldsymbol i=\gamma$ и $\boldsymbol i=\langle\gamma,s\rangle$ – элементы множества $\boldsymbol I$.) C другой стороны, мы имеем $\mathbf{b}_\delta=\mathbf{a}_\gamma$ также в силу того, что $\mathbf{b}=\pi^\smallfrown\mathbf{a}$. Из этих фактов нетрудно вывести $\boldsymbol J[\mathbf{b}]=\pi^\smallfrown(\boldsymbol J[\mathbf{a}])$.
Рассмотрим имя $t=\underline{\sigma\mathbf{a}}$, как в (4), где $\sigma\in\mathbf\Pi$. Используя равенствo $\pi^\smallfrown(\sigma^\smallfrown \mathbf{a})=(\pi\circ\sigma)^\smallfrown \mathbf{a}$ леммы 6.2, мы непосредственно вычисляем
$$
\begin{equation*}
(\pi^\smallfrown (\underline{\sigma\mathbf{a}}))[\pi^\smallfrown\mathbf{a}]= (\underline{(\sigma\circ\pi^{-1})\mathbf{a}})[\pi^\smallfrown\mathbf{a}]= (\sigma\circ\pi^{-1})^\smallfrown(\pi^\smallfrown\mathbf{a})= (\sigma\circ\pi^{-1}\circ\pi)^\smallfrown\mathbf{a} = \sigma^\smallfrown \mathbf{a},
\end{equation*}
\notag
$$
по формулам (5) и (6), что и требовалось.
Наконец, рассмотрим имя $t=\underline {\mathbf\Omega}$, как в (4). Требуется доказать $\underline {\mathbf\Omega}[\mathbf{b}] =\underline {\mathbf\Omega}[\mathbf{a}]$. Рассмотрим произвольное $x=\sigma^\smallfrown(\mathbf{a}\upharpoonright\xi)\in\underline {\mathbf\Omega}[\mathbf{a}]$, где $\sigma\in\mathbf\Pi$, $\xi\in\mathbf\Xi$, $\xi\subseteq\boldsymbol J[\mathbf{a}]$. Положим $\xi_1=\pi^\smallfrown\xi\in\mathbf\Xi$ и $\sigma_1=\sigma\circ\pi^{-1}\in\mathbf\Pi$. Используя лемму 6.2, вычисляем
$$
\begin{equation*}
\begin{aligned} \, \sigma^\smallfrown(\mathbf{a}\upharpoonright\xi) &=(\sigma^\smallfrown\mathbf{a})\upharpoonright(\sigma^\smallfrown\xi) =\bigl((\sigma_1\circ\pi)^\smallfrown\mathbf{a}\bigr)\upharpoonright \bigl((\sigma_1\circ\pi)^\smallfrown\xi\bigr) =\bigl(\sigma_1^\smallfrown(\pi^\smallfrown\mathbf{a})\bigr) \upharpoonright\bigl(\sigma_1^\smallfrown(\pi^\smallfrown\xi)\bigr) \\ &=\sigma_1^\smallfrown\bigl((\pi^\smallfrown\mathbf{a})\upharpoonright(\pi^\smallfrown\xi)\bigr) =\sigma_1^\smallfrown(\mathbf{b}\upharpoonright\xi_1). \end{aligned}
\end{equation*}
\notag
$$
Однако из равенства $\boldsymbol J[\mathbf{b}]=\pi^\smallfrown(\boldsymbol J[\mathbf{a}])$ следует $\xi_1\subseteq\boldsymbol J[\mathbf{b}]$, и поэтому $x=\sigma^\smallfrown(\mathbf{a}\upharpoonright\xi) =\sigma_1^\smallfrown(\mathbf{b}\upharpoonright\xi_1)\in\underline {\mathbf\Omega}[\mathbf{b}]$. Лемма 6.3 доказана. Eсли $\Phi$ является $\in$-формулой с именами вида (4) в роли параметров, то $\pi^\smallfrown\Phi$ будет обозначать результат замены каждого участвующего имени $t$ на $\pi^\smallfrown t$. Если, кроме того, $\mathbf{a}\in\mathscr D^{\boldsymbol I}$, то $\Phi[\mathbf{a}]$ будет обозначать результат замены каждого участвующего имени $t$ на интерпретацию $t[\mathbf{a}]$ по формулам (6). Через $\mathrel{{\|}\hspace{-0.5ex}{-}}$ обозначается отношение $\mathbb P$-вынуждения над $\mathbf L$ как базовой моделью, cогласованное с определением интерпретаций по (6). Следующая теорема является ключевым результатом теории форсинга для $\mathrel{{\|}\hspace{-0.5ex}{-}}$. Теорема 6.4. Пусть $X\in\mathbb P$, $\xi=\|X\|$, a $\Phi$ – замкнутая $\in$-формула с именами (4) в роли параметров. Тогда $X\mathrel{{\|}\hspace{-0.5ex}{-}}\Phi$ равносильно тому, что $\mathbf L[\mathbf{a}]\models\Phi[\mathbf{a}]$ для любого $\mathbf{a}\in\mathscr D^{\boldsymbol I}$, $\mathbb P$-генерического над $\mathbf L$ и такого, что $\mathbf{a}\upharpoonright\xi\in X^{\#}$. Рутинное доказательство следующего результата 6.5 об инвариантности отношения $\mathrel{{\|}\hspace{-0.5ex}{-}}$ относительно пермутаций, основанное на лемме 6.3, опускается. Следствие 6.5. Пусть $\Phi$ является замкнутой $\in$-формулой с именами (4) в роли параметров, $\pi\in\mathbf\Pi$ и $X\in\mathbb P$. Tогда $X\mathrel{{\|}\hspace{-0.5ex}{-}}\Phi$ равносильно $\pi^\smallfrown X\mathrel{{\|}\hspace{-0.5ex}{-}}\pi^\smallfrown\Phi$. Следствие 6.6. Пусть $\Phi$ – замкнутая $\in$-формула с именами только вида $\overset{\bullet} x$ и $\underline {\mathbf\Omega}$ из (4), и $X\in\mathbb P$. Tогда $X\mathrel{{\|}\hspace{-0.5ex}{-}}\Phi$ влечет $\mathbb I\mathrel{{\|}\hspace{-0.5ex}{-}}\Phi$. Напомним, что $\mathbb I$ является слабейшим “условием” в $\mathbb P$, см. замечание 4.1. Доказательство следствия 6.6. В противном случае выполнено $Y\mathrel{{\|}\hspace{-0.5ex}{-}}\neg\,\Phi$ для какого-то “условия” $Y\in\mathbb P$. Множества $\xi=\|X\|$ и $\eta=\|Y\|$ (см. начало п. 4) принадлежат $\Xi$, в частности, они счетны в $\mathbf L$. Поэтому найдется такая пермутация $\pi\in\mathbf\Pi$, что множества $\xi$ и $\eta'=\pi^\smallfrown\eta$ дизъюнктны. Отсюда следует, что “условия” $X$ и $Y'=\pi^\smallfrown Y$ (последнее удовлетворяет $\|Y'\|=\eta'$) совместны в $\mathbb P$.
С другой стороны, формула $\Phi$ по условию удовлетворяет $\pi^\smallfrown\Phi=\Phi$. Отсюда по следствию 6.5 и выбору $Y$ следует $Y'\mathrel{{\|}\hspace{-0.5ex}{-}}\neg\,\Phi$. Но это противоречит выбору $X$ и совместности $X$ и $Y'$. Противоречие доказывает доказывает следствие 6.6. 7. Беспараметрический выбор и доказательство основной теоремыЗдесь мы доказываем теорему 5.3 как решающий шаг в доказательстве нашей основной теоремы. Доказательство теоремы 5.3. Мы фиксируем $\mathbb P$-генерическое над $\mathbf L$ множество $G\subseteq\mathbb P$ и полагаем $\mathbf{a}=\mathbf{a}[G]$. Нашей целью является вывод $\mathbf{AC}_\omega^\ast$ в структуре $\langle\omega;W[\mathbf{a}]\rangle\in\mathbf L[\mathbf{a}]=\mathbf L[G]$. Поэтому фиксируем беспараметрическую формулу $\varphi(k,x)$ языка $\mathcal L(\mathbf{PA}_2)$. Требуется доказать, что
Прервемся на следующую простую лемму. Лемма 7.1. Имеет место равенство $W[\mathbf{a}] =W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]]$ (см. (2) и (6)). Доказательство. Если $\sigma\in\mathbf\Pi$ то $\mathbf L[\mathbf{a}\upharpoonright\xi]=\mathbf L[\sigma^\smallfrown(\mathbf{a}\upharpoonright\xi)]$ (поскольку $\mathbf\Pi\in\mathbf L$). Отсюда следует $\mathcal L(E[\mathbf{a}])=\mathcal L(\underline {\mathbf\Omega}[\mathbf{a}])$, и лемма доказана. Доказанная лемма разрешает переписать (7) в следующем эквивалентном виде:
$$
\begin{equation}
\langle\omega;W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]]\rangle \models\bigl(\forall\, k\,\exists\, x\ \varphi(k,x)\Longrightarrow \exists\, y\,\forall\, k\ \varphi(k,(y)_k)\bigr).
\end{equation}
\tag{8}
$$
что мы и будем доказывать. Начиная вывод (8), предполагаем противное, т.е. $\neg$(8). По теореме 6.4 это вынуждается некоторым “условием” $X\in G$. Однако вынуждаемое предложение здесь содержит только имя $\underline {\mathbf\Omega}$ cогласно (6). Поэтому согласно следствию 6.6 мы имеем
$$
\begin{equation}
\mathbb I\mathrel{{\|}\hspace{-0.5ex}{-}}\neg\, (8), \quad\text{т.е. } \ \mathbb I\,\mathrel{{\|}\hspace{-0.5ex}{-}}\, \bigl[ \langle\omega;W^\ast[\underline {\mathbf\Omega}]\rangle \models \bigl(\forall\, k\,\exists\, x\ \varphi(k,x)\land \neg\,\exists\, y\,\forall\, k\ \varphi(k,(y)_k\bigr)\bigr].
\end{equation}
\tag{9}
$$
В частности, для каждого $k<\omega$ выполнено
$$
\begin{equation*}
\mathbb I\,\mathrel{{\|}\hspace{-0.5ex}{-}}\, \bigl(\langle\omega;W^\ast[\underline {\mathbf\Omega}]\rangle \models\,\exists\, x\ \varphi(k,x)\bigr).
\end{equation*}
\notag
$$
По определению (6) для каждого $k$ имеются такие $\xi_k\in\mathbf\Xi$, $\mu_k<\omega_1$, $X_k\in\mathbb P$, что
$$
\begin{equation}
X_k\mathrel{{\|}\hspace{-0.5ex}{-}} {\xi_k}\subseteq \boldsymbol J[\underline{\mathbf{a}}] \:\land\: \exists\, x\ \bigl(\Psi(\underline{\mathbf{a}}\upharpoonright\xi_k,\mu_k,x)\land \langle\omega;W^\ast[\underline {\mathbf\Omega}]\rangle \models\varphi(k,x) \bigr),
\end{equation}
\tag{10}
$$
где $\in$-формула $\Psi(\underline{\mathbf{a}}\upharpoonright\xi_k,\mu_k,x)$ говорит, что $x$ есть $\mu_k$-й в смысле канонического геделева порядка на $\mathbf L[\underline{\mathbf{a}}\upharpoonright\xi_k]$ элемент множества $\mathscr P(\omega)\cap\mathbf L[\underline{\mathbf{a}}\upharpoonright\xi_k]$. Замечание 7.2. Квантор $\exists\, x\in\mathbf L[\sigma^\smallfrown(\underline{\mathbf{a}}\upharpoonright\xi_k)]\cap\mathscr P(\omega)$ в (10), ожидавшийся по определению (6), сначала заменен более простым $\exists\, x\in\mathbf L[\underline{\mathbf{a}}\upharpoonright\xi_k]\cap\mathscr P(\omega)$, на основании того, что $\mathbf L[\mathbf{a}\upharpoonright\xi]=\mathbf L[\sigma^\smallfrown(\mathbf{a}\upharpoonright\xi)]$ (следует из $\sigma\in\mathbf\Pi\in\mathbf L$), а затем и просто на $\exists\, x$, поскольку $\Psi(\underline{\mathbf{a}}\upharpoonright\xi_k,\mu_k,x)$ формально влечет $x\in\mathbf L[\underline{\mathbf{a}}\upharpoonright\xi_k]\cap\mathscr P(\omega)$. И при этом отображение $k\mapsto\langle\xi_k,\mu_k,X_k\rangle$ принадлежит $\mathbf L$. Отображение $k\mapsto\eta_k=\|X_k\|\in\mathbf\Xi$ тогда также принадлежит $\mathbf L$. Cледовательно, рассуждая в $\mathbf L$, можно построить систему $\langle\pi_k\rangle_{k<\omega}\in\mathbf L$ пермутаций $\pi_k\in\mathbf\Pi$, для которых множества $\eta'_k=\pi_k^\smallfrown\eta_k\in\mathbf\Xi$ попарно дизъюнктны. Тогда “условия” $Y_k=\pi_k^\smallfrown X_k\in\mathbb P$ удовлетворяют $\|Y_k\|=\eta'_k$, откуда и из попарной дизъюнктности следует, что множество $Y=\bigcup_k(Y_k\upharpoonright^{-1}\eta)$ принадлежит $\mathbb P$ и $\|Y\|=\eta$, где $\eta=\bigcup_k\eta'_k\in\mathbf\Xi$. Пусть теперь $\xi'_k=\pi_k^\smallfrown\xi_k$ $\forall\, k$. Поскольку $Y\leqslant Y_k$ в $\mathbb P$, мы имеем из (10)
$$
\begin{equation}
Y\mathrel{{\|}\hspace{-0.5ex}{-}} {\xi_k}\subseteq \boldsymbol J[\underline{\pi_k\mathbf{a}}] \,\land\, \exists\, x\, \bigl(\Psi((\underline{\pi_k\mathbf{a}})\upharpoonright\xi_k,\mu_k,x)\land \langle\omega;W^\ast[\underline {\mathbf\Omega}]\rangle \models\varphi(k,x) \bigr) \quad \forall\, k.
\end{equation}
\tag{11}
$$
Рассмотрим теперь любой массив $\mathbf{a}\in\mathscr D^{\boldsymbol I}$, $\mathbb P$-генерический над $\mathbf L$ и такой, что $\mathbf{a}\upharpoonright\eta\in Y^{\#}$. По теореме 6.4 (11) влечет в $\mathbf L[\mathbf{a}]$ следующее:
$$
\begin{equation}
{\xi_k}\subseteq \boldsymbol J[\pi_k^\smallfrown\mathbf{a}] \,\land\, \exists\, x\, \bigl(\Psi((\pi_k^\smallfrown \mathbf{a})\upharpoonright\xi_k,\mu_k,x)\land \langle\omega;W^\ast[\underline {\mathbf\Omega}[\mathbf a]]\rangle \models\varphi(k,x) \bigr) \quad \forall\, k.
\end{equation}
\tag{12}
$$
Однако равенство $\boldsymbol J[\mathbf{b}]=\pi^\smallfrown(\boldsymbol J[\mathbf{a}])$ леммы 6.3 позволяет заменить соотношение ${\xi_k}\subseteq \boldsymbol J[\pi_k^\smallfrown\mathbf{a}]$ на эквивалентное ${\xi'_k}\subseteq \boldsymbol J[\mathbf{a}]$, а последнее равенство леммы 6.2 позволяет заменить $(\pi_k^\smallfrown\mathbf{a})\upharpoonright\xi_k$ на эквивалентное $\pi_k^\smallfrown(\mathbf{a}\upharpoonright\xi'_k)$. Тем самым, в $\mathbf L[\mathbf{a}]$ выполнено
$$
\begin{equation}
{\xi'_k}\subseteq \boldsymbol J[\mathbf{a}] \,\land\, \exists\, x\, \bigl(\Psi(\pi_k^\smallfrown(\mathbf{a}\upharpoonright\xi'_k),\mu_k,x)\land \langle\omega;W^\ast[\underline {\mathbf\Omega}[\mathbf a]]\rangle \models\varphi(k,x) \bigr) \quad \forall\, k.
\end{equation}
\tag{13}
$$
Далее, коль скоро отображения $k\mapsto \xi_k,\pi_k$ принадлежат $\mathbf L$, отображения $k\mapsto \xi'_k$ также принадлежат $\mathbf L$, а потому множество $\xi'=\bigcup_k\xi'_k$ принадлежат $\mathbf L$, и $\xi'\in\mathbf\Xi$, $\xi'\subseteq \boldsymbol J[\mathbf{a}]$ cогласно (13). Тогда $\mathbf{a}\upharpoonright\xi'\in\underline {\mathbf\Omega}[\mathbf{a}]$ и $\mathbf L[\mathbf{a}\upharpoonright\xi']\cap\mathscr P(\omega)\subseteq W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]]$ по определению (6). Теперь, рассуждая в $\mathbf L[\mathbf{a}\upharpoonright\xi']$, для каждого $k<\omega$ мы, через $x_k$, обозначим $\mu_k$-й в смысле канонического геделева порядка на $\mathbf L[\pi_k^\smallfrown(\mathbf{a}\upharpoonright\xi'_k)]$ элемент множества $\mathscr P(\omega)\cap\mathbf L[\pi_k^\smallfrown(\mathbf{a}\upharpoonright\xi'_k)]$, а затем определяем $y\in\mathscr P(\omega)\cap\mathbf L[\mathbf{a}\upharpoonright\xi']$ равенствами $(y)_k=x_k$ для всех $k$. Имеем
$$
\begin{equation*}
\langle\omega;W^\ast[\underline {\mathbf\Omega}[\mathbf a]]\rangle \models\varphi(k,x_k) \quad \forall\, k
\end{equation*}
\notag
$$
cогласно (13), и в то же время
$$
\begin{equation*}
y\in\mathscr P(\omega)\cap\mathbf L[\mathbf{a}\upharpoonright\xi']\subseteq W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]]
\end{equation*}
\notag
$$
по построению. Таким образом, $\langle\omega;W^\ast[\underline {\mathbf\Omega}[\mathbf a]]\rangle \models\exists\, y\,\forall\, k\,\varphi(k,(y)_k)$. Но это противоречит (13), поскольку $\mathbb I\in\mathbb P$ – слабейшее “условие”, а $\mathbf{a}$ – генерический массив. Противоречие завершает вывод теоремы 5.3. Доказательство теоремы 1.1. Берем произвольное $\mathbb P$-генерическoe над $\mathbf L$ множество $G\subseteq\mathbb P$. Пусть $\mathbf{a}=\mathbf{a}[G]$ и $X=W[\mathbf{a}] =W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]]$ (cм. лемму 7.1). Имеем $\langle\omega;W[\mathbf{a}]\rangle\models\mathbf{PA}_2^\ast +\mathbf{CA}(\mathbf\Sigma^1_2)+\neg\,\mathbf{CA}$. по теореме 5.2 и $\langle\omega;W[\mathbf{a}]\rangle\models\mathbf{AC}_\omega^\ast$ (беспараметрическая) по теореме 5.3.
8. ОбсуждениеМы закончим несколькими вопросами и замечаниями в связи с теоремой 1.1. Проблема 1. Остается неясным, до какого проективного уровня схема свертки $\mathbf{CA}$ верна в построенной модели $W[\mathbf{a}] =W^\ast[\underline {\mathbf\Omega}[\mathbf{a}]]$ для доказательства теоремы 1.1. Из теоремы 5.2 следует, что $\mathbf{CA}(\mathbf\Sigma^1_2)$ верна в этой модели, а внимательный анализ примера для $\neg\,\mathbf{CA}$ из доказательства теоремы 5.2 показывает, что $\mathbf{CA}(\mathbf\Sigma^1_4)$ не выполнена. Остается открытым вопрос, верна ли там $\mathbf{CA}(\mathbf\Sigma^1_3)$. Наша гипотеза состоит в том, что $\mathbf{CA}(\mathbf\Sigma^1_3)$, т.е. $\mathbf{CA}(\mathbf\Sigma^1_3)+ \neg\,\mathbf{CA}(\mathbf\Sigma^1_4)$ выполнена в $W[\mathbf{a}]$, а предполагаемый метод доказательства состоит в использовании внутренних автоморфизмов форсинга Сакса дополнительно к пермутациям из $\mathbf\Pi$. Проблема 2. Построить модель для теории $\mathbf{AC}_\omega^\ast + \mathbf{CA}(\mathbf\Sigma^1_2)+ \neg\,\mathbf{CA}(\mathbf\Sigma^1_3)$. Решение этой проблемы следует ожидать на основе итераций и произведений форсинга Йенсена из [21], [22]. Дело в том, что релятивная “йенсеновость” является $\varPi^1_2$-отношением, в отличие от отношения “правильного наследника” из доказательства теоремы 4.8, которое оценивается как заведомо более сложное чем $\varPi^1_2$. Проблема 3. Как обобщение предыдущего, было бы интересно доказать, что при любом $n\geqslant2$, $\mathbf{PA}_2^\ast + \mathbf{AC}_\omega^\ast + \mathbf{CA}(\mathbf\Sigma^1_n)$ (с параметрами) не влечет $\mathbf{CA}(\mathbf\Sigma^1_{n+1})$. (Ср. с проблемой 9 в [3; § 11].) Отсюда следовало бы, что полная схема свертки $\mathbf{CA}$ не является конечно аксиоматизируемой над $\mathbf{PA}_2^\ast+ \mathbf{AC}_\omega^\ast$. Мы ожидаем, что методы индуктивного построения форсингов в $\mathbf L$, подобных итерированному форсингу Йенсена из [22], но имеющих скрытые автоморфизмы, из наших недавних работ [23], [24], [25] и др., могут привести к решению этой проблемы. Проблема 4 (сообщена Али Энаятом). Возможны ли результаты, подобные нашей теореме 1.1, для теории классов Келли–Морса как теории второго порядка над $\mathbf{ZFC}$? Решение этой задачи может потребовать развития техники форсинга Сакса для несчетных кардиналов, как у Канамори [26], или как сделано в недавней еще неопубликованной работе Фридмана и Гитман [27] для форсинга Йенсена. Замечание 8.1. Это исследование может быть полезно при создании алгоритмов или счетных алгоритмических моделей, которые представляют эволюцию клеточных типов и связаны с хранением и обработкой геномной информации. Авторы благодарят Али Энайята, Гюнтера Фукса и Викторию Гитман за дискуссию и замечания, которые привели к успешному завершению этой работы. Авторы признательны анонимным рецензентам за ценные исправления, позволившие существенно дополнить и улучшить изложение.
Цитирование в формате AMSBIB
\RBibitem{KanLyu25} |
|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Обратная связь: |
Пользовательское соглашение
|
Регистрация посетителей портала |
Логотипы |
|