Нестандартная модель арифметики - Non-standard model of arithmetic

В математической логике , А не-стандартная модель арифметики представляет собой модель (первого порядка) арифметики Пеано , который содержит нестандартные номера. Термин « стандартная модель арифметики» относится к стандартным натуральным числам 0, 1, 2,…. Элементы любой модели арифметики Пеано линейно упорядочены и имеют начальный отрезок, изоморфный стандартным натуральным числам. Нестандартная модель - это модель, в которой есть дополнительные элементы за пределами этого начального сегмента. Создание таких моделей принадлежит Торальфу Сколему (1934).

Существование

Есть несколько методов, которые можно использовать для доказательства существования нестандартных моделей арифметики.

Из теоремы компактности

Существование нестандартных моделей арифметики можно продемонстрировать применением теоремы компактности . Для этого набор аксиом P * определяется на языке, включающем язык арифметики Пеано вместе с новым постоянным символом x . Аксиомы состоят из аксиом арифметики Пеано P вместе с другим бесконечным набором аксиом: для каждого числа n включается аксиома x > n . Любое конечное подмножество этих аксиом удовлетворяется моделью, которая представляет собой стандартную модель арифметики плюс константа x, интерпретируемая как некоторое число, большее, чем любое число, упомянутое в конечном подмножестве P *. Таким образом, по теореме компактности существует модель, удовлетворяющая всем аксиомам P *. Поскольку любая модель P * является моделью P (поскольку модель набора аксиом, очевидно, также является моделью любого подмножества этого набора аксиом), мы имеем, что наша расширенная модель также является моделью аксиом Пеано. Элемент этой модели, соответствующий x, не может быть стандартным числом, потому что, как указано, он больше любого стандартного числа.

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

Из теорем о неполноте

Из теорем Гёделя о неполноте также следует существование нестандартных моделей арифметики. Теоремы о неполноте показывают, что конкретное предложение G , предложение Гёделя арифметики Пеано, не является ни доказуемым, ни опровергаемым в арифметике Пеано. По теореме о полноте это означает, что G ложна в некоторой модели арифметики Пеано. Однако G верен в стандартной модели арифметики, и поэтому любая модель, в которой G неверна, должна быть нестандартной моделью. Таким образом, выполнение ~ G является достаточным условием нестандартности модели. Однако это не является обязательным условием; для любого гёделевского предложения G существуют модели арифметики, в которых G истинна любой мощности.

Арифметическая несостоятельность для моделей с ~ G истинно

Предполагая, что арифметика согласована, арифметика с ~ G также согласована. Однако, поскольку ~ G означает, что арифметика несовместима, результат не будет ω-согласованным (потому что ~ G ложно, и это нарушает ω-согласованность).

Из ультрапродукта

Другой метод построения нестандартной модели арифметики - через сверхпроизведение . Типичная конструкция использует множество всех последовательностей натуральных чисел, . Определите две последовательности, если они почти везде совпадают. Полученное полукольцо представляет собой нестандартную модель арифметики. Его можно идентифицировать по сверхъестественным числам. ${\displaystyle \mathbb {N} ^{\mathbb {N} }}$

Структура счетных нестандартных моделей

Модели сверхпродуктов неисчислимы. Один из способов увидеть это - построить инъекцию бесконечного произведения N в ультрапродукт. Однако по теореме Левенгейма – Сколема должны существовать счетные нестандартные модели арифметики. Один из способов определить такую ​​модель - использовать семантику Хенкина .

Любая счетная нестандартная модель арифметики имеет порядковый тип ω + (ω * + ω) η , где ω - порядковый тип стандартных натуральных чисел, ω * - двойственный порядок (бесконечная убывающая последовательность), а η - тип заказа рациональных чисел. Другими словами, счетная нестандартная модель начинается с бесконечной возрастающей последовательности (стандартных элементов модели). За ним следует набор «блоков», каждый из которых имеет порядковый тип ω * + ω , порядковый тип целых чисел. Эти блоки, в свою очередь, плотно упорядочены по порядку рациональных чисел. Результат следует довольно легко, потому что легко видеть, что блоки нестандартных чисел должны быть плотными и линейно упорядоченными без конечных точек, а тип порядка рациональных чисел - единственный счетный плотный линейный порядок без конечных точек .

Итак, вид заказа счетных нестандартных моделей известен. Однако арифметические операции намного сложнее.

Легко видеть, что арифметическая структура отличается от ω + (ω * + ω) ⋅ η . Например, если нестандартный (не конечный) элемент u находится в модели, то также и m ⋅ u для любых m , n в начальном сегменте N, но u ² больше, чем m ⋅ u для любого стандартного конечного m .

Также можно определить «квадратные корни», такие как наименьшее v, такое, что v ² > 2 ⋅ u . Они не могут быть в пределах стандартного конечного числа любого рационального числа, кратного u . Аналогичными методами нестандартного анализа можно также использовать PA для определения близких приближений к иррациональным кратным нестандартного числа u, например, наименьшему v с v > π ⋅ u (они могут быть определены в PA с использованием нестандартных конечных рациональные приближения числа π, хотя само число π не может быть таким). Еще раз, v - ( m / n ) ⋅ ( u / n ) должно быть больше любого стандартного конечного числа для любых стандартных конечных m , n .

Это показывает, что арифметическая структура счетной нестандартной модели более сложна, чем структура рациональных чисел. Тем не менее, это еще не все: теорема Тенненбаума показывает, что для любой счетной нестандартной модели арифметики Пеано нет способа закодировать элементы модели как (стандартные) натуральные числа, так что операция сложения или умножения Модель вычислима на кодах. Этот результат был впервые получен Стэнли Тенненбаумом в 1959 году.

использованная литература

Цитаты

Источники