Примитивные рекурсивные предикаты возведения в степень и умножения
У меня есть следующие неофициально сформулированные и слабо обоснованные убеждения, некоторые из которых кажутся мне несовместимыми после дальнейшего размышления. Мне интересно, где может быть источник ошибки (ошибок) в моем мышлении; вполне возможны ошибки в основных определениях.
Невозможно выполнить исключение квантора в теории первого порядка целых чисел со сложением и умножением. (Насколько я могу судить, это немного более сильная версия первой теоремы о неполноте.)
В теории первого порядка целых чисел со сложением и умножением можно определить примитивный рекурсивный предикат возведения в степень. (Под предикатом возведения в степень я просто подразумеваю то, что ведет себя как "$Fabc\text{ just when }a^b = c.$")
Это является возможным сделать кванторное устранение в теории первого порядка целых чисел с двумя операциями$a \oplus b = \min(a, b)$ и $a \otimes b = a + b$(т.е. обычное сложение целых чисел). Я знаю, что нам также нужны предикаты делимости и операторы умножения для простых чисел, чтобы на самом деле выполнить исключение кванторов.
В теории чисел первого порядка с операциями $\oplus$ и $\otimes$, можно определить примитивный рекурсивный предикат для умножения (почти точно так же, как предикат для возведения в степень выше).
Грубо говоря, похоже, что есть разрыв в аналогии между «обычной операционной башней». $(+, \times, \hat{\phantom{n}}, \cdots)$ и «тропическая башня операций» $(\min, +, \times, \cdots)$.
Более конкретно, если (4) и (3) верны, я не понимаю, почему нельзя просто свободно использовать предикат умножения, а затем иметь ситуацию, когда мы оба можем выполнить исключение квантора (через (3)), а не сделать исключение квантора (через (1)). Меня бы очень удивило, если бы (2) было истинным, а (4) - нет, и меня бы еще больше удивило, если бы (2) было ложным.
Я подозреваю, что не совсем понимаю, что подразумевается под предикатом возведения в степень (т. Е. Мое неформальное определение $Fabc$ неверно, или есть еще некоторые подробности относительно "свободного использования предиката умножения", о которых я не знаю.
Ответы
Ваши претензии $(1), (2)$, и $(3)$каждый правильный. Запрос$(4)$, однако, неверно ; действительно, если бы умножение было определимо над$(\mathbb{N};\max,+)$ тогда теория $Th(\mathbb{N};\max,+)$ было бы так же сложно, как $Th(\mathbb{N};+,\times)$. Но первое рекурсивно, а второе даже арифметически не определимо.
Проблема в том, что «очевидное» определение умножения в терминах сложения на самом деле не относится к первому порядку : рекурсивные определения не являются априори чем-то, что может делать логика первого порядка. В достаточно богатых структурах мы можем найти способы выполнять рекурсивные определения в первом порядке, и действительно, это богатство$Th(\mathbb{N};+,\times)$в этом смысле, что делает возможной теорему Гёделя, но одного лишь дополнения недостаточно, чтобы заставить эту работу работать. Ключ в том, что если у нас есть и сложение, и умножение, мы можем «закодировать» конечные последовательности натуральных чисел отдельными натуральными числами (например, через$\beta$function ) и поэтому говорим о рекурсивных конструкциях, говоря о последовательностях, кодирующих их «пошаговое поведение», но с одним лишь сложением мы не можем даже кодировать пары чисел отдельными числами .
Проработка последнего предложения и возвращение к вашему требованию $(2)$, вот схема того, как определить возведение в степень с помощью сложения и умножения в первом порядке:
У нас есть $a^b=c$ если есть какое-то число, которое при интерпретации как последовательность имеет длину $b$, первый срок $a$, последний семестр $c$, и $i+1$-й член равен $a$ раз $i$-й семестр.
Обратите внимание, что это определение «все сразу», а не определение «рекурсивным процессом»: по модулю деталей кодирования конечных последовательностей числами, оно просто включает в себя количественную оценку отдельных чисел и проверку основных свойств, что и есть в первую очередь. логика заказа может. Без возможности кодировать конечные последовательности как отдельные числа способом первого порядка, что$(\mathbb{N};\max,+)$ недостатков - мы бы застряли на обычном определении не первого порядка.
- В стороне, важно, чтобы это было «проверяемое определение»: в теории $\mathsf{Q}$, который является крошечным фрагментом полной теории $Th(\mathbb{N};+,\times)$, у нас есть это для каждого $a,b,c$ предложение сокращено $$\underline{a}^{\underline{b}}=\underline{c}$$ (где $\underline{k}$ это цифра, обозначающая натуральное число $k$) доказуемо в $\mathsf{Q}$ если $a^b=c$ и опровергается в $\mathsf{Q}$ если $a^b\not=c$. Это называется представимостью и является одной из ключевых идей доказательства Гёделя; фактически, любая рекурсивная функция представима .