В математической логике нестандартная модель арифметики — это модель арифметики Пеано первого порядка , содержащая нестандартные числа. Термин «стандартная модель арифметики» относится к стандартным натуральным числам 0, 1, 2,…. Элементы любой модели арифметики Пеано линейно упорядочены и имеют начальный отрезок , изоморфный стандартным натуральным числам. Нестандартная модель — это модель, имеющая дополнительные элементы за пределами этого начального сегмента. Построение таких моделей принадлежит Торальфу Сколему (1934).
Нестандартные модели арифметики существуют только для формулировок аксиом Пеано первого порядка ; для исходной формулировки второго порядка с точностью до изоморфизма существует только одна модель: сами натуральные числа . [1]
Существует несколько методов, которые можно использовать для доказательства существования нестандартных моделей арифметики.
Существование нестандартных моделей арифметики можно продемонстрировать применением теоремы о компактности . Для этого на языке, включающем язык арифметики Пеано, определяется набор аксиом P* вместе с новым постоянным символом x . Аксиомы состоят из аксиом арифметики Пеано P вместе с другим бесконечным набором аксиом: для каждого числа n включена аксиома x > n . Любому конечному подмножеству этих аксиом удовлетворяет модель, которая представляет собой стандартную модель арифметики плюс константу x , интерпретируемую как некоторое число, большее, чем любое число, упомянутое в конечном подмножестве P*. Таким образом, по теореме о компактности существует модель, удовлетворяющая всем аксиомам Р*. Поскольку любая модель P* является моделью P (поскольку модель набора аксиом, очевидно, также является моделью любого подмножества этого набора аксиом), мы получаем, что наша расширенная модель также является моделью аксиом Пеано. Элемент этой модели, соответствующий x , не может быть стандартным числом, поскольку, как указано, он больше любого стандартного числа.
Используя более сложные методы, можно строить нестандартные модели, обладающие более сложными свойствами. Например, существуют модели арифметики Пеано, в которых теорема Гудштейна не работает. В теории множеств Цермело – Френкеля можно доказать , что теорема Гудштейна справедлива в стандартной модели, поэтому модель, в которой теорема Гудштейна не работает, должна быть нестандартной.
Теоремы Гёделя о неполноте также предполагают существование нестандартных моделей арифметики. Теоремы о неполноте показывают, что конкретное предложение G , предложение Гёделя арифметики Пеано, не является ни доказуемым, ни опровергнутым в арифметике Пеано. По теореме о полноте это означает, что G ложна в некоторой модели арифметики Пеано. Однако G истинно в стандартной модели арифметики, и поэтому любая модель, в которой G ложна, должна быть нестандартной моделью. Таким образом, выполнение ~ G является достаточным условием для того, чтобы модель была нестандартной. Однако это не обязательное условие; для любого гёделева предложения G и любой бесконечной мощности существует модель арифметики с истинным G и этой мощности.
Если предположить, что арифметика непротиворечива, то арифметика с ~ G также непротиворечива. Однако, поскольку ~ G утверждает, что арифметика противоречива, результат не будет ω-согласованным (поскольку ~ G ложно, и это нарушает ω-непротиворечивость).
Другой метод построения нестандартной модели арифметики — через ультрапроизведение . Типичная конструкция использует набор всех последовательностей натуральных чисел . Выберите ультрафильтр на , затем идентифицируйте две последовательности всякий раз, когда они имеют равные значения в позициях, которые образуют член ультрафильтра (для этого требуется, чтобы они согласовывались по бесконечному числу членов, но условие более сильное, чем это, поскольку ультрафильтры напоминают аксиому выбора как максимальные расширения фильтра Фреше). Полученное полукольцо представляет собой нестандартную модель арифметики. Его можно отождествить со сверхнатуральными числами. [2]
Модели ультрапродуктов бесчисленны . Один из способов убедиться в этом — построить инъекцию бесконечного произведения N в ультрапроизведение. Однако по теореме Левенгейма–Скулема должны существовать счетные нестандартные модели арифметики. Один из способов определить такую модель — использовать семантику Хенкина .
Любая счетная нестандартная модель арифметики имеет тип порядка ω + (ω* + ω) ⋅ η , где ω — тип порядка стандартных натуральных чисел, ω* — двойственный порядок (бесконечная убывающая последовательность), а η — тип порядка рациональных чисел . Другими словами, счетная нестандартная модель начинается с бесконечной возрастающей последовательности (стандартных элементов модели). За этим следует набор «блоков», каждый из которых имеет тип порядка ω* + ω , тип порядка целых чисел. Эти блоки, в свою очередь, плотно упорядочены по типу порядка рациональных чисел. Результат получается довольно легко, поскольку легко увидеть, что блоки нестандартных чисел должны быть плотными и линейно упорядоченными без концов, а тип порядка рациональных чисел — единственный счетный плотный линейный порядок без концов . [3] [4] [5]
Итак, известен тип порядка счетных нестандартных моделей. Однако арифметические операции гораздо сложнее.
Легко видеть, что арифметическая структура отличается от ω + (ω* + ω) ⋅ η . Например, если в модели присутствует нестандартный (неконечный) элемент u , то то же самое относится и к m ⋅ u для любого m в начальном сегменте N , однако u 2 больше, чем m ⋅ u для любого стандартного конечного m .
Также можно определить «квадратные корни», такие как наименьшее v такое, что v 2 > 2 ⋅ u . Они не могут находиться в пределах стандартного конечного числа любого рационального кратного u . Методами, аналогичными нестандартному анализу, можно также использовать PA для определения близких приближений к иррациональным кратным нестандартного числа u , например, наименьшему v с v > π ⋅ u (они могут быть определены в PA с использованием нестандартных конечных чисел рациональные аппроксимации π , хотя самого π быть не может). Еще раз: v − ( m / n ) ⋅ ( u / n ) должно быть больше любого стандартного конечного числа для любых стандартных конечных m , n . [ нужна цитата ]
Это показывает, что арифметическая структура счетной нестандартной модели более сложна, чем структура рациональных чисел. Однако это нечто большее: теорема Тенненбаума показывает, что для любой счетной нестандартной модели арифметики Пеано нет способа закодировать элементы модели как (стандартные) натуральные числа, так что либо операция сложения, либо умножение модель вычислима на кодах. Этот результат был впервые получен Стэнли Тенненбаумом в 1959 году.
