У математичній логіці арифметика Скулема — це теорія першого порядку натуральних чисел з множенням, названа на честь Туралфа Скулема. Сигнатура арифметики Скулема містить лише операцію множення та рівність, без використання операції додавання.
Арифметика Скулема слабша за арифметику Пеано, яка містить як додавання, так і множення. На відміну від арифметики Пеано, арифметика Скулема є розв'язною теорією. Тобто існує алгоритм, який для будь-якого речення арифметики Скулема визначає, чи виводиться воно з її аксіом. Асимптотична складність обчислень за часом цієї задачі розв'язності є потрійно експоненційною.
Аксіоми
Введемо такі скорочення.
Простіше кажучи: виконується тоді й лише тоді, коли — найбільший цілий степінь , що ділить націло.
виконується тоді й лише тоді, коли p-адичне нормування числа -адичне нормування числа , що позначається , — це показник степеня у розкладі на прості множники. Наприклад, , оскільки , і . перевищує -адичне нормування числа точно на , тобто .
Аксіомами арифметики Скулема є:
Нескінченність множини простих чисел
Однозначність розкладу на множники -адичне абсолютне значення є мультиплікативним Якщо -адичне нормування менше за -адичне нормування для кожного простого , то Видалення з розкладу на прості множники всіх простих чисел, що не ділять Збільшення кожного показника степеня в розкладі на прості множники на Добуток тих простих чисел , для яких найбільший степінь , що ділить , у разів більший за найбільший степінь , що ділить
Виразна здатність
Логіка першого порядку з рівністю та множенням додатних цілих чисел може виразити відношення . Використовуючи це відношення та рівність, можна визначити такі відношення на додатних цілих числах: Подільність: Найбільший спільний дільник: Найменше спільне кратне: Стала : Просте число: Число є добутком простих чисел (для фіксованого ): Число є степенем деякого простого числа: Число є добутком рівно степенів простих чисел:
Ідея розв'язності
Значення істинності формул арифметики Скулема можна звести до значення істинності тверджень про послідовності невід'ємних цілих чисел, що утворюють їх розклад на прості множники, причому множення стає покомпонентним додаванням послідовностей. Розв'язність тоді випливає з теореми Фефермана — Воота, яку можна довести за допомогою елімінації кванторів. Інакше кажучи: теорія першого порядку додатних цілих чисел ізоморфна теорії першого порядку скінченних мультимножин невід'ємних цілих чисел з операцією суми мультимножин, розв'язність якої зводиться до розв'язності теорії елементів.
Детальніше: згідно з основною теоремою арифметики, додатне ціле число можна подати у вигляді добутку степенів простих чисел:
Якщо просте число не входить як множник, ми вважаємо його показник рівним нулю. Таким чином, у нескінченній послідовності ненульовими є лише скінченна кількість показників. Позначимо такі послідовності невід'ємних цілих чисел через .
Тепер розглянемо розклад іншого додатного числа,
Множенню відповідає покомпонентне додавання показників:
Визначимо відповідне покомпонентне додавання на послідовностях так:
Таким чином, маємо ізоморфізм між структурою додатних цілих чисел з множенням та покомпонентним додаванням послідовностей невід'ємних цілих чисел, у яких ненульовими є лише скінченна кількість елементів , .
З теореми Фефермана — Воота для логіки першого порядку значення істинності формули над послідовностями та покомпонентним додаванням на них зводиться алгоритмічним способом до значення істинності формул у теорії елементів послідовності з додаванням, якою в цьому випадку є арифметика Пресбургера. Оскільки арифметика Пресбургера розв'язна, арифметика Скулема також розв'язна.
Складність
за допомогою ігор Еренфойхта — Фраїссе встановлюють метод доведення верхніх меж складності задачі розв'язності слабких прямих степенів теорій. Вони застосовують цей метод, щоб отримати потрійно експоненційну просторову складність для , а отже, і для арифметики Скулема.
доводить, що задача виконуваності для безкванторного фрагмента арифметики Скулема належить до класу складності NP.
Розв'язні розширення
Завдяки наведеному вище зведенню за допомогою теореми Фефермана — Воота можна отримати теорії першого порядку, відкриті формули яких визначають ширшу множину відношень, якщо посилити теорію мультимножин простих множників. Наприклад, розглянемо відношення , яке істинне тоді й лише тоді, коли і мають однакову кількість різних простих множників:
Наприклад, , оскільки обидві частини позначають число, що має два різні прості множники.
Якщо додати відношення до арифметики Скулема, вона залишиться розв'язною. Адже теорія множин індексів залишається розв'язною за наявності оператора рівнопотужності на множинах, як показує теорема Фефермана — Воота.
Нерозв'язні розширення
Розширення арифметики Скулема предикатом наступника може виразити відношення додавання за допомогою тотожності Тарського:
визначаючи відношення на додатних цілих числах як
Оскільки отримана теорія може виразити як множення, так і додавання, вона є нерозв'язною.
Якщо маємо предикат порядку на натуральних числах (менше, ), то можна виразити як
тож розширення з також є нерозв'язним.
Див. також Арифметика Пресбургера Арифметика Робінсона Елімінація кванторів
Примітки
Література