Арифметичен ли ординал Чёрча-Клини?

[nikov]

Существует ли формула в языке арифметики первого порядка с двумя свободными переменными, реализующая порядок на множестве $\mathbb{N}$ изоморфный ординалу Чёрча-Клини $\omega^{\mathrm{CK}}_1$ (наименьшему нерекурсивному ординалу)?

[epros]

Вроде это прямо противоречит определению сего ординала? Это наименьший ординал, формулу которого невозможно построить алгоритмически (ни в каком языке, т.е. в том числе и в языке арифметики первого порядка невозможно).

Или я чего-то не понял в вопросе?

[маткиб]

Ответ на вопрос в названии темы отрицательный. Докажем, что любой арифметичный ординал является вычислимым. Доказательства на идейном уровне.

Будем работать с вычислимыми корневыми деревьями. Такое дерево называется фундированным, если в нём нет бесконечных путей. Ранг фундированного дерева определяется по индукции: если дерево состоит из одной вершины, то ранг равен 1, если нет, то минимальному ординалу, большему, чем ранги всех его поддеревьев.

Лемма 1. Ранг любого вычислимого фундированного дерева вычислим.
Доказательство. Достаточно доказать, что для данного дерева существует вычислимый ординал, который не меньше его ранга. Занумеруем вершины числами. Каждому пути дерева из корня вниз $x_1,\ldots,x_n$ поставим в соответствие последовательность ординалов $x_1,\ldots,x_n,\omega,\omega,\ldots$. Лексикографический порядок таких последовательностей и будет искомым ординалом (доказывается элементарно индукцией по рангу дерева, например).

Предикат $p(x)$ на натуральных числах называется хорошим, если существует поддерево дерева конечных последовательностей натуральных чисел, начинающихся с $1$, являющееся вычислимым, такое, что $p(x)$ истинно тогда и только тогда, когда поддерево, соответствующее сыну корня с номером $x$, не фундировано.

Аналогично определяются хорошие предикаты от нескольких переменных.

Лемма 2. При навешивании квантора существования на хороший предикат получается снова хороший предикат.
Доказательство. Каждой подстановке констант в исходный предикат соответствует дерево. Для каждого фиксированного набора свободных переменных соединим "параллельно" деревья, соответствующие разным значениям подкванторной, потом эти деревья тоже соединим параллельно, получим искомое дерево. Параллельное соединение деревьев - это делание их корней сыновьями одной вершины - нового корня.

Лемма 3. При навешивании квантора всеобщности на хороший предикат получается снова хороший предикат.
Доказательство. Аналогично лемме 2, только вместо "параллельного" на первом шаге используется "последовательное" соединение. Опишем его подробнее. Пусть $T_1, T_2,\ldots$ - деревья, которые нужно соединить (их вершинами пусть для простоты будут натуральные числа). Вершинами нового дерева будут квадратные числовые матрицы. Корень - матрица 0x0. B является сыном A, если:
1) первые n-1 строк и столбцов B образуют A (здесь n - размерность B);
2) для каждого $j$ строка с номером $j$ матрицы $B$ является путём в $T_j$ из корня вниз.
Замечание: чтобы получить окончательное дерево, нужно будет нужным образом переименовать вершины.

Следствие лемм 2 и 3. Любой арифметичный предикат является хорошим.

Теорема. Для любого арифметичного ординала $\alpha$ существует вычислимое фундированное дерево ранга не меньше $\alpha$.
Доказательство. Пусть $p(x,y)$ - хороший предикат, реализующий $\alpha$ (порядок "меньше"), $T_p$ - дерево его "хорошей" реализации. Построим дерево $T$, имеющее нужный ранг. Через $T_{x,y}$ обозначим поддерево $T_p$, соответствующее $(x,y)$ (вершины нумеруем числами). Вершинами дерева $T$ будут векторы вида $(x_1,\ldots,x_n,B)$, где $x_1,\ldots,x_n$ - числа, $B$ - матрица размера n-1 на n. Корень - (пустой вектор, пустая матрица). $(x_1,\ldots,x_n,B)$ является сыном $(x_1,\ldots,x_{n-1},A)$, если:
1) первые $n-2$ строки и $n-1$ столбец $B$ образуют $A$;
2) для каждого $j$, строка с номером $j$ матрицы $B$ является путём из корня вниз в дереве $T_{x_{j+1},x_j}$.

Доказательство, что $T$ имеет ранг не меньше $\alpha$, оставим на совести читателя.

[epros]

Кстати, а как вообще арифметической формулой с двумя свободными переменными можно реализовать порядок, изоморфный некоему ординалу $Ord \gg \omega^2$? Например, я знаю как реализовать порядок, изоморфный $\omega^2$, формулой с тремя свободными переменными: Известной диагональной процедурой. При этом формула определит биекцию: $n \leftrightarrow i \cdot \omega + j$, соответственно, переменными будут $n$, $i$ и $j$.

Но как реализовать тот же порядок арифметической формулой с двумя переменными?

-- Вт дек 13, 2011 11:53:42 --

А, кажись, я понял о чём речь...

[epros]

Тогда есть вопрос вдогонку. Есть ли бинарная арифметическая формула $a < b$, реализующая на $\mathbb{N}$ порядок, изоморфный ординалу $\varepsilon_0$?

Дело в том, что используя многоступенчатую факторизацию, можно каждому натуральному числу поставить в соответствие ординал, меньший $\varepsilon_0$.

Факторизация в арифметике вроде бы реализуема. Однако ж, записав эту формулу для $a < b$, вроде бы можно будет в рамках арифметики применять трансфинитную индукцию до $\varepsilon_0$. А это, кажется, нельзя?

[nikov]

epros в сообщении #515045 писал(а):

Тогда есть вопрос вдогонку. Есть ли бинарная арифметическая формула $a < b$, реализующая на $\mathbb{N}$ порядок, изоморфный ординалу $\varepsilon_0$? Однако ж, записав эту формулу для $a < b$, вроде бы можно будет в рамках арифметики применять трансфинитную индукцию до $\varepsilon_0$. А это, кажется, нельзя?

Формулу такую написать можно, но не получится доказать из аксиом арифметики Пеано, что она действительно вполне упорядочивает натуральные числа.

[маткиб]

nikov в сообщении #515249 писал(а):

Формулу такую написать можно, но не получится доказать из аксиом арифметики Пеано, что она действительно вполне упорядочивает натуральные числа.

Даже сформулировать...

[epros]

маткиб в сообщении #516475 писал(а):

Даже сформулировать...

Не получится сформулировать аксиомы полного порядка? А в какой части возникнут затруднения? Наверное, в части существования минимального элемента любого множества? А разве нельзя ограничиться схемой, что для каждой формулы $\varphi$ существует минимальное число $a$, удовлетворяющее $\varphi(a)$?

[маткиб]

epros в сообщении #517206 писал(а):

Наверное, в части существования минимального элемента любого множества?

Да.

epros в сообщении #517206 писал(а):

А разве нельзя ограничиться схемой, что для каждой формулы $\varphi$ существует минимальное число $a$, удовлетворяющее $\varphi(a)$?

Естественно, нельзя, ибо существует куча примеров, когда есть бесконечная убывающая цепочка, но нет ни одной такой, которая бы была представима какой-то там формулой.

[epros]

маткиб в сообщении #517217 писал(а):

Естественно, нельзя, ибо существует куча примеров, когда есть бесконечная убывающая цепочка, но нет ни одной такой, которая бы была представима какой-то там формулой.

Если я правильно понял, последнее означает, что утверждение о существовании такой бесконечно убывающей цепочки также невыразимо в арифметике первого порядка?

А раз так, то почему бы факт существования таких "нестандартных" цепочек не проигнорировать и не записать указанную схему аксиом?

[маткиб]

epros в сообщении #517236 писал(а):

Если я правильно понял, последнее означает, что утверждение о существовании такой бесконечно убывающей цепочки также невыразимо в арифметике первого порядка?

Всё правильно.

epros в сообщении #517236 писал(а):

А раз так, то почему бы факт существования таких "нестандартных" цепочек не проигнорировать и не записать указанную схему аксиом?

Ну это из разряда: эта задача плохая, давай лучше другую порешаем.

[epros]

маткиб в сообщении #517252 писал(а):

Ну это из разряда: эта задача плохая, давай лучше другую порешаем.

Раз мы не можем в арифметике первого порядка даже сформулировать эту задачу, то что ещё остаётся? Ну, невыразимо в ней общее понятие "множества", но ведь "свойство, выраженное формулой" является каким-то более слабым, но всё же аналогом оного? С аксиомой индукции второго порядка ведь так и поступили - заменили её более слабой схемой индукции первого порядка.

Это я к чему ... В этой "более слабой" формулировке утверждение о том, что данная формула определяет отношение полного порядка, всё ещё остаётся недоказуемым? Точнее, интересно даже не это, а вот что:
Можно ли доказать формулу трансфинитной индукции для некой произвольной формулы $\varphi$?

[маткиб]

epros в сообщении #517555 писал(а):

В этой "более слабой" формулировке утверждение о том, что данная формула определяет отношение полного порядка, всё ещё остаётся недоказуемым?

Кажется, остаётся недоказуемым, ибо теорема Гудстейна через такое утверждение легко доказывается (взять множество ординалов, соответствующих числам, для которых последовательность не сходится, взять у них минимум и т.д.).

[Профессор Снэйп]

+1 к маткиб Любой арифметический ординал вычислим!!!