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

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

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

Аксиомы [ править ]

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

а | б := ∃ п .( ан знак равно б )
Один( е ) := ∀ п .( ne знак равно п )
Prime( p ) := ¬One( p ) ∧ ∀ a .( a | p → (One( 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 _п ( п , а , б ) знак равно Prime ( п ) ∧ п | ab ∧ ∃ P .∃ Q .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , Q ) ∧ Q = p ^нP ) для каждого целого числа n > 0. [Наибольшая степень p , делящая b, равна p ^н умножить наибольшую степень p , делящую a ]

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

∀ а .∀ б .( аб знак равно ба )
∀ а .∀ б .∀ c .(( ab ) c знак равно а ( bc ))
∃ е .Один( е )
∀ a .∀ b .(Один( ab ) → Один( a ) ∨ Один( b ))
∀ а .∀ б .∀ c .( ac знак равно bc → а знак равно б )
∀ а .∀ b .∀ n .( а ^н = б ^н → a = b ) для каждого целого числа n > 0
∀ x .∃ a .∃ r .( x = ar ^н ∧ ∀ b .∀ s .( x = bs ^н→ а | б )) для каждого целого числа n > 0
∀ a .∃ p .(Prime( p ) ∧ ¬( p | a )) [Бесконечность простых чисел]
∀ p .∀ P .∀ Q .((PrimePower( p , P ) ∧ PrimePower( p , Q )) → ( P | Q ∨ Q | P ))
∀ p .∀ n .(Prime( p ) → ∃ P . InvAdicAbs( p , n , P ))
∀ n .∀ m .( n = m ↔ ∀ p .(Prime( p ) → ∃ P .(InvAdicAbs( p , n , P ) ∧ InvAdicAbs( p , m , P )))) [Уникальная факторизация]
∀ p .∀ n .∀ m .(Prime( p ) → ∃ P .∃ Q .(InvAdicAbs( p , n , P ) ∧ InvAdicAbs( p , m , Q ) ∧ InvAdicAbs( p , nm , PQ ))) [ p -адическое абсолютное значение мультипликативно]
∀ a .∀ b .(∀ p .(Prime( p ) → ∃ P .∃ Q .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , Q ) ∧ P | Q )) → a | b ) [Если p -адическая оценка a меньше, чем у b для любого простого числа p , то a | б ]
∀ a .∀ b .∃ c .∀ p (Prime( p ) → ((( p | a → ∃ P .(InvAdicAbs( p , b , P ) ∧ InvAdicAbs( p , c , P ))) ∧ (( p | b ) → ( p | a )))) [Удаление из простой факторизации b всех простых чисел, не делящих a ]
∀ a .∃ b .∀ p .(Prime( p ) → (∃ P .(InvAdicAbs( p , a , P ) ∧ InvAdicAbs( p , b , pP ))) ∧ ( p | b → p | a )) ) [Увеличение каждого показателя степени в простой факторизации a на 1]
∀ 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 ]

Выразительная сила [ править ]

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

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

Идея разрешимости [ править ]

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

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

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

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

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

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

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

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

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

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

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

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

Сложность [ править ]

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

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

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

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

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

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

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

Неразрешимые расширения [ править ]

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

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

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

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

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

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

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

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

См. также [ править ]

Ссылки [ править ]

Библиография [ править ]

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

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

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

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

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

Надель, Марк Э. (1981). «Полнота умножения Пеано» . Израильский математический журнал . 39 (3): 225–233. дои : 10.1007/bf02760851 . Проверено 8 сентября 2022 г.

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

[FOOTNOTENadel1981-1] Nadel 1981 .

[FOOTNOTEFerranteRackoff1979135-2] Ферранте и Ракофф 1979 , с. 135.

[FOOTNOTECegielski1981-3] Цегельски 1981 .

[FOOTNOTERobinson1949100-4] Робинсон 1949 , с. 100.

[FOOTNOTEBèsRichard1998-5] Бесс и Ричард 1998 .

[1]

[2]

[3]

[4]

[5]