Арифметика Пресбургера
В разделе "Арифметика Пресбургера" мы занимались элиминацией кванторов в теории , которая потребовала добавления бесконечного числа дополнительных предикатов (сравнимость по модулю для всех целых ).
Проанализировав это рассуждение, можно извлечь из него явную аксиоматизацию для теории
(без дополнительных предикатов). Какие свойства порядка и сложения на целых числах мы используем? Нам важно, что целые числа образуют абелеву группу, что порядок согласован со сложением и что есть непосредственно следующий за элемент (достаточно, впрочем, сказать, что непосредственно следует за ). В любой группе можно рассмотреть подгруппу делящихся на элементов (для любой целой константы ) и сравнивать элементы по модулю этой подгруппы. Но этого мало: нам нужно еще иметь возможность делить на с остатком. Это гарантируется такой аксиомой (при каждом — своя аксиома): для любого элемента ровно один из элементов делится на .
Можно проверить, что все шаги элиминации кванторов сохраняют равносильность в такой ситуации. Проверим, например, что сравнения можно умножать на целое положительное число. Почему, скажем, равносильно ? По определению первое означает, что для некоторого , а второе — что для некоторого , и достаточно сослаться на то, что в упорядоченной группе из следует
(поскольку из следует ). Наиболее сложный шаг — доказательство представительности набора. Здесь надо рассмотреть все случаи расположения произвольного относительно правых частей. В каждом из случаев мы заменяли на первый элемент из окрестности правых частей, встречающийся при движении шагами . Эту процедуру можно понимать как деление расстояния (до ближайшей правой части) на с остатком; возможность этого гарантируется нашими аксиомами.
133. Покажите, что теория разрешима.
134. Покажите, что эта теория не категорична в счетной мощности и опишите все ее счетные модели. (Указание: они имеют вид , где — делимая упорядоченная группа.)
135. Покажите, что эта теория не конечно аксиоматизируема. (Указание: рассмотрите интерпретацию , когда в возможно деление на простые числа, меньшие некоторого , но не на .)
