Сколемская арифметика

В математической логике арифметика Скулема — это теория первого порядка натуральных чисел с умножением , названная в честь Торальфа Скулема . Сигнатура арифметики Скулема содержит только операцию умножения и равенства, полностью опуская операцию сложения.

Арифметика Скулема слабее арифметики Пеано , которая включает в себя как операции сложения, так и умножения. ^[1] В отличие от арифметики Пеано, арифметика Скулема является разрешимой теорией . Это означает, что для любого предложения на языке арифметики Скулема можно эффективно определить, доказуемо ли это предложение из аксиом арифметики Скулема. Асимптотическая вычислительная сложность времени выполнения этой задачи принятия решений трижды экспоненциальна. ^[2]

Аксиомы

Мы определяем следующие сокращения.

• а | б  := ∃ n .( а n = б )
• Один( е ) := ∀ n .( ne = n )
• Простое число( p ) := ¬Один( p ) ∧ ∀ a .( a | p → (Один( a ) ∨ a = p ))
• PrimePower( p , P ) := Prime( p ) ∧ p | P ∧ ∀ q .(Prime( q ) ∧ ¬( q = p ) → ¬( q | P ))
• InvAdicAbs( p , n , P ) := PrimePower( p , P ) ∧ P | n ∧ ∀Q.((PrimePower( p , Q ) ∧ Q | n ) → Q | P ) [ P — наибольшая степень числа p, делящая n ]
• AdicAbsDiff _n ( p , a , b ) := Prime( p ) ∧ p | ab ∧ ∃ P .∃ Q .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , Q ) ∧ Q = p ⁿ P ) для каждого целого числа n > 0. [Наибольшая степень p, делящая b, равна p ⁿ раз больше наибольшей степени p, делящей a ]

Аксиомы арифметики Скулема таковы: ^[3]

1. ∀ а .∀ б .( аб = ба )
2. ∀ а .∀ б .∀ в .(( аб ) с = а ( бс ))
3. ∃ е .Один( е )
4. ∀ a .∀ b .(Один( ab ) → Один( a ) ∨ Один( b ))
5. ∀ а .∀ б .∀ в .( ac = bc → a = b )
6. ∀ a .∀ b .( a ⁿ = b ⁿ → a = b ) для каждого целого числа n > 0
7. ∀ x .∃ a .∃ r .( x = ar ⁿ ∧ ∀ b .∀ s .( x = bs ⁿ → a | b )) для каждого целого числа n > 0
8. ∀ a .∃ p .(Prime( p ) ∧ ¬( p | a )) [Бесконечность простых чисел]
9. ∀ p .∀ P .∀ Q .((ОсновнаяМощность( p , P ) ∧ ОсновнаяМощность( p , Q )) → ( P | Q ∨ Q | P ))
10. ∀ p .∀ n .(Prime( p ) → ∃ P .InvAdicAbs( p , n , P ))
11. ∀ n .∀ m .( n = m ↔ ∀ p .(Prime( p ) → ∃ P .(InvAdicAbs( p , n , P ) ∧ InvAdicAbs( p , m , P )))) [Уникальная факторизация]
12. ∀ p .∀ n .∀ m .(Prime( p ) → ∃ P .∃ Q .(InvAdicAbs( p , n , P ) ∧ InvAdicAbs( p , m , Q ) ∧ InvAdicAbs( p , nm , PQ ))) [ p -адическое абсолютное значение мультипликативно]
13. ∀ a .∀ b .(∀ p .(Prime( p ) → ∃ P .∃ Q .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , Q ) ∧ P | Q )) → a | b ) [Если p -адическая оценка a меньше, чем оценка b для каждого простого числа p , то a | b ]
14. ∀ a .∀ b .∃ c .∀ p (Prime( p ) → ((( p | a → ∃ P .(InvAdicAbs( p , b , P ) ∧ InvAdicAbs( p , c , P ))) ∧ (( p | b ) → ( p | a )))) [Удаление из разложения на простые множители числа b всех простых чисел, не делящих a ]
15. ∀ a .∃ b .∀ p .(Prime( p ) → (∃ P .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , pP ))) ∧ ( p | b → p | a ))) [Увеличение каждой экспоненты в разложении числа a на простые множители на 1]
16. ∀ a .∀ b .∃ c .∀ p .(Prime( p ) → ((AdicAbsDiff _n ( p , a , b ) → InvAdicAbs( p , c , p )) ∧ ( p | c → AdicAbsDiff _n ( p , a , b ))) для каждого целого числа n > 0 [Произведение тех простых чисел p , для которых наибольшая степень p, делящая b, равна p ⁿ раз наибольшей степени p, делящей a ]

Выразительная сила

Логика первого порядка с равенством и умножением положительных целых чисел может выразить отношение . Используя это отношение и равенство, мы можем определить следующие отношения над положительными целыми числами: ${\displaystyle c=a\cdot b}$

• Делимость: ${\displaystyle b|c\ \Leftrightarrow \ \exists a.c=a\cdot b}$
• Наибольший общий делитель : ${\displaystyle d=\gcd(a,b)\ \Leftrightarrow \ d|a\land d|b\land \forall d'.(d'|a\land d'|b)\Rightarrow d'|d}$
• Наименьшее общее кратное : ${\displaystyle m=\mathrm {lcm} (a,b)\ \Leftrightarrow \ a|m\land b|m\land \forall m'.(a|m'\land b|m')\Rightarrow m|m'}$
• константа : ${\displaystyle 1}$ ${\displaystyle \forall a.1|a}$
• Простое число : ${\displaystyle \mathrm {prime} (p)\ \Leftrightarrow \ p\neq 1\land \forall a.a|p\Rightarrow (a=1\lor a=p)}$
• Число является произведением простых чисел (при фиксированном ): ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle \exists a_{1},...a_{k}.\ \mathrm {prime} (a_{1})\land \ldots \land \mathrm {prime} (a_{k})\land b=a_{1}\cdot \ldots \cdot a_{k}}$
• Число является степенью некоторого простого числа: ${\displaystyle b}$ ${\displaystyle \mathrm {ppower} (b)\ \Leftrightarrow \ \exists p.\mathrm {prime} (p)\land \forall a.(a\neq 1\land a|b)\Rightarrow p|a}$
• Число является произведением именно простых степеней: ${\displaystyle b}$ ${\displaystyle k}$ ${\displaystyle \exists a_{1},...a_{k}.\ \mathrm {ppower} (a_{1})\land \ldots \land \mathrm {ppower} (a_{k})\land b=a_{1}\cdot \ldots \cdot a_{k}}$

Идея разрешимости

Истинное значение формул арифметики Скулема может быть сведено к истинному значению последовательностей неотрицательных целых чисел, составляющих их разложение на простые множители, при этом умножение становится поточечным сложением последовательностей. Разрешимость тогда следует из теоремы Фефермана–Воота , которая может быть показана с помощью исключения кванторов . Другой способ утверждения этого состоит в том, что теория первого порядка положительных целых чисел изоморфна теории первого порядка конечных мультимножеств неотрицательных целых чисел с операцией суммы мультимножеств, разрешимость которой сводится к разрешимости теории элементов.

Более подробно, согласно основной теореме арифметики , положительное целое число можно представить в виде произведения степеней простых чисел: ${\displaystyle a>1}$

${\displaystyle a=p_{1}^{a_{1}}p_{2}^{a_{2}}\cdots }$

Если простое число не появляется как множитель, мы определяем его показатель степени как нулевой. Таким образом, только конечное число показателей степени не равны нулю в бесконечной последовательности . Обозначим такие последовательности неотрицательных целых чисел как . ${\displaystyle p_{k}}$ ${\displaystyle a_{k}}$ ${\displaystyle a_{1},a_{2},\ldots }$ ${\displaystyle N^{*}}$

Теперь рассмотрим разложение другого положительного числа,

${\displaystyle b=p_{1}^{b_{1}}p_{2}^{b_{2}}\cdots }$

Умножение соответствует поточечному сложению показателей степеней: ${\displaystyle ab}$

${\displaystyle ab=p_{1}^{a_{1}+b_{1}}p_{2}^{a_{2}+b_{2}}\cdots }$

Определим соответствующее поточечное сложение последовательностей следующим образом:

${\displaystyle (a_{1},a_{2},\ldots ){\bar {+}}(b_{1},b_{2},\ldots )=(a_{1}+b_{1},a_{2}+b_{2},\ldots )}$

Таким образом, мы имеем изоморфизм между структурой положительных целых чисел с умножением и поточечным сложением последовательностей неотрицательных целых чисел, в которых только конечное число элементов не равны нулю . ${\displaystyle (N,\cdot )}$ ${\displaystyle (N^{*},{\bar {+}})}$

Из теоремы Фефермана–Воота для логики первого порядка истинностное значение формулы логики первого порядка над последовательностями и поточечным сложением на них алгоритмическим образом сводится к истинностному значению формул в теории элементов последовательности со сложением, которая в данном случае является арифметикой Пресбургера . Поскольку арифметика Пресбургера разрешима, арифметика Скулема также разрешима.

Сложность

Ферранте и Ракофф (1979, Глава 5) устанавливают, используя игры Эренфойхта–Фрайсса , метод доказательства верхних границ сложности задач принятия решений слабых прямых степеней теорий. Они применяют этот метод для получения трижды экспоненциальной пространственной сложности для , и, таким образом, арифметики Сколема. ${\displaystyle (N^{*},{\bar {+}})}$

Грэдель (1989, раздел 5) доказывает, что проблема выполнимости для бескванторного фрагмента арифметики Скулема принадлежит классу сложности NP .

Разрешимые расширения

Благодаря приведенной выше редукции с использованием теоремы Фефермана–Воота мы можем получить теории первого порядка, открытые формулы которых определяют более широкий набор отношений, если мы усилим теорию мультимножеств простых множителей. Например, рассмотрим отношение, которое истинно тогда и только тогда, когда и имеют одинаковое количество различных простых множителей: ${\displaystyle a\sim b}$ ${\displaystyle a}$ ${\displaystyle b}$

${\displaystyle |\{p\mid \mathrm {prime} (p)\land (p|a)\}|\ =\ |\{p\mid \mathrm {prime} (p)\land (p|b)\}|}$

Например, потому что обе стороны обозначают число, имеющее два различных простых множителя. ${\displaystyle 2^{10}\cdot 3^{100}\sim 5^{8}\cdot 19^{9}}$

Если мы добавим отношение к арифметике Скулема, оно останется разрешимым. Это потому, что теория множеств индексов останется разрешимой при наличии оператора равночисленности на множествах, как показывает теорема Фефермана–Воота . ${\displaystyle \sim }$

Неразрешимые расширения

Расширение арифметики Скулема с предикатом преемника может определить отношение сложения, используя тождество Тарского: ^{[4] [5]} ${\displaystyle succ(n)=n+1}$

${\displaystyle (c=0\lor c=a+b)\Leftrightarrow (ac+1)(bc+1)=c^{2}(ab+1)+1}$

и определение отношения положительных целых чисел ${\displaystyle c=a+b}$

${\displaystyle \mathrm {succ} (ac)\,\mathrm {succ} (bc)=\mathrm {succ} (c^{2}\mathrm {succ} (ab))}$

Поскольку она может выражать как умножение, так и сложение, полученная теория неразрешима.

Если у нас есть предикат упорядочения натуральных чисел (меньше, ), мы можем выразить это как ${\displaystyle <}$ ${\displaystyle \mathrm {succ} }$

${\displaystyle \mathrm {succ} (a)=b\ \ \Leftrightarrow \ \ a<b\land \forall c.{\big (}a<c\Rightarrow (b=c\lor b<c){\big )}}$

поэтому расширение с также неразрешимо. ${\displaystyle <}$

Смотрите также

• арифметика Пресбургера
• арифметика Робинсона
• Устранение квантификатора

Ссылки

1. Надель 1981.
2. Ферранте и Ракофф 1979, стр. 135.
3. Цегельски 1981.
4. Робинсон 1949, стр. 100.
5. Бес и Ричард 1998.

Библиография

• Бес, Алексис (2001). «Обзор арифметической определимости» (PDF) . В Краббе, Марсель; Пойнт, Франсуаза; Мишо, Кристиан (ред.). Посвящение Морису Боффе . Брюссель: Бельгийское математическое общество. стр. 1–54.

• Бес, Алексис; Ричард, Денис (1998). «Неразрешимые расширения арифметики Сколема». Журнал символической логики . 63 (2): 379–401. CiteSeerX  10.1.1.2.1139 . doi :10.2307/2586837. JSTOR  2586837. S2CID  14566619.

• Цегельски, Патрик (1981), «Элементарная теория умножения всех природных явлений», в Берлине, Шанталь; Макалун, Кеннет; Рессейр, Жан-Пьер (ред.), Теория моделей и арифметика , Берлин: Springer, стр. 44–89.

• Ферранте, Жанна; Ракофф, Чарльз В. (1979). Вычислительная сложность логических теорий. Берлин Гейдельберг Нью-Йорк: Springer-Verlag. doi :10.1007/BFb0062837. ISBN 3-540-09501-2.

• Грэдель, Эрих (июнь 1989). «Домино и сложность подклассов логических теорий». Annals of Pure and Applied Logic . 43 (1): 1–30. doi : 10.1016/0168-0072(89)90023-7 .

• Надель, Марк Э. (1981). «Полнота умножения Пеано». Israel Journal of Mathematics . 39 (3): 225–233. doi : 10.1007/bf02760851 . Получено 08.09.2022 .

• Робинсон, Джулия Холл Боумен (1949). «Проблемы определимости и принятия решений в арифметике» (PDF) . Журнал символической логики . 14 (2): 98–114. doi :10.2307/2266510. JSTOR  2266510. S2CID  40861592 . Получено 05.09.2022 .