Нестандартная модель арифметики

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

Нестандартные модели арифметики существуют только для формулировок аксиом Пеано первого порядка ; для исходной формулировки второго порядка с точностью до изоморфизма существует только одна модель: натуральные числа . сами ^{[ 1 ]}

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

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

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

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

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

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

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

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

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

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

Другой метод построения нестандартной модели арифметики — через ультрапроизведение . Типичная конструкция использует набор всех последовательностей натуральных чисел: $\mathbb {N} ^{\mathbb {N} }$ . Выберите ультрафильтр на $\mathbb {N}$ , затем идентифицируйте две последовательности всякий раз, когда они имеют равные значения в позициях, которые образуют член ультрафильтра (для этого требуется, чтобы они согласовывались по бесконечному числу членов, но условие более сильное, чем это, поскольку ультрафильтры напоминают максимальные расширения типа аксиомы выбора фильтр Фреше). Полученное полукольцо представляет собой нестандартную модель арифметики. Его можно отождествить со сверхнатуральными числами. ^{[ 2 ]}

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

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

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

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

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

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

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

Ссылки

Цитаты

^ Ганс Гермес (1973). Введение в математическую логику . Hochschultext. Лондон: Спрингер. ISBN 3540058192 . ISSN 1431-4657 . Здесь: Ч. VI.3
^ Голдблатт, Роберт (1998), «Сверхмощная конструкция гиперреальности», Лекции по гиперреальности , Нью-Йорк: Springer, стр. 23–33, doi : 10.1007/978-1-4612-0615-6_3
^ Андрей Бовыкин и Ричард Кэй Порядковые типы моделей арифметики Пеано: краткий обзор 14 июня 2001 г.
^ Андрей Бовыкин О порядковых типах моделей арифметики диссертация, представленная в Бирмингемский университет на степень доктора философии. на факультете естественных наук 13 апреля 2000 г.
^ Фред Ландман ЛИНЕЙНЫЕ ПОРЯДКИ, ДИСКРЕТНЫЕ, ПЛОТНЫЕ И НЕПРЕРЫВНЫЕ - включает доказательство того, что Q - единственный счетный плотный линейный порядок.

Источники

Булос, Джордж , и Джеффри, Ричард , 1974. Вычислимость и логика , издательство Кембриджского университета. ISBN 0-521-38923-2 .
Сколем, Торальф (1934). «О нехарактеризуемости числового ряда посредством конечного или счетного числа утверждений с исключительно числовыми переменными» (PDF) . Fundamenta Mathematicae (на немецком языке). 23 (1): 150–161. дои : 10.4064/fm-23-1-150-161 .

См. также

Неевклидова геометрия — о нестандартных моделях в геометрии

[1] Ганс Гермес (1973). Введение в математическую логику . Hochschultext. Лондон: Спрингер. ISBN 3540058192 . ISSN 1431-4657 . Здесь: Ч. VI.3

[2] Голдблатт, Роберт (1998), «Сверхмощная конструкция гиперреальности», Лекции по гиперреальности , Нью-Йорк: Springer, стр. 23–33, doi : 10.1007/978-1-4612-0615-6_3

[3] Андрей Бовыкин и Ричард Кэй Порядковые типы моделей арифметики Пеано: краткий обзор 14 июня 2001 г.

[4] Андрей Бовыкин О порядковых типах моделей арифметики диссертация, представленная в Бирмингемский университет на степень доктора философии. на факультете естественных наук 13 апреля 2000 г.

[5] Фред Ландман ЛИНЕЙНЫЕ ПОРЯДКИ, ДИСКРЕТНЫЕ, ПЛОТНЫЕ И НЕПРЕРЫВНЫЕ - включает доказательство того, что Q - единственный счетный плотный линейный порядок.

[ 1 ]

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]