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

Модель арифметики Пеано (первого порядка), которая содержит нестандартные числа

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Ссылки

Цитаты

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

Источники

Булос, Джордж и Джеффри, Ричард 1974. Вычислимость и логика , Cambridge University Press. ISBN 0-521-38923-2 .
Сколем, Торальф (1934). «Über die Nicht-charakterisierbarkeit der Zahlenreihe mittels endlich oder abzählbar unendlich vieler Aussagen mit ausschließlich Zahlenvariablen» (PDF) . Fundamenta Mathematicae (на немецком языке). 23 (1): 150–161 . doi :10.4064/fm-23-1-150-161.

Смотрите также

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

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

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

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

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

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