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

Обновлено: 05.07.2024

В курсовой работе предлагается осветить символический и графический методы решения логических задач. Рекомендуется следующий план работы.

1 Рассмотреть основные понятия алгебры высказываний и логики предикатов (/1/, с.10-35, 122-134).

3 Изучить кванторные операции над предикатами (/1/, с. 134-159).

4 Рассмотреть решение "логических" задач на языке символов (/3/, с.

5 Разобрать графический способ решения задач подобного рода (/2/, с.

Литература, рекомендуемая для изучения темы 1 Игошин В.И. Математическая логика и теория алгоритмов. –

Саратов: Изд-во Сарат. ун-та, 1991.

2 Кэрролл Л. Логическая игра: Пер. с англ. Ю.А. Данилова. – М.: Наука, 1991. (Б-ка “Квант”; Вып. 73).

3 Игошин В.И. Задачник-практикум по математической логике: Учеб. пособие для студентов-заочников физ.-мат. фак-в пед. ин-тов. – М.: Просвещение, 1986.

Тема 35. Неразрешимость логики первого порядка

Одним из принципиально важных результатов математической логики является доказательство неразрешимости в логике первого порядка проблем распознавания как общезначимости, так и выполнимости ее предложений. В курсовой работе необходимо изучить доказательства неразрешимости логики первого порядка. Рекомендуется следующий план работы.

1 Изучить основные понятия логики первого порядка (/1/, с. 130-151).

2 Рассмотреть понятие машины Тьюринга и доказать неразрешимость проблемы остановки (/1/, с. 36-54).

3 Вывести неразрешимость логики первого порядка из неразрешимости проблемы остановки (/1/, с. 152-160).

4 Разобрать доказательство неразрешимости логики первого порядка методом Геделя (/1/, с. 160-166).

Решить задачи 3.6, 3.10 из упражнения на стр. 46-48 и задачи 10.1, 10.3 из упражнения на стр. 164-165 в книге /1/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

Тема 36. Нестандартные модели арифметики

В любой математической теории принципиально важным является вопрос о существовании и единственности модели формализации этой теории. В курсовой работе необходимо проанализировать этот вопрос для элементарной теории арифметики. Рекомендуется следующий план работы.

1 Рассмотреть язык логики узкого исчисления предикатов арифметики

и его стандартную интерпретацию в алгебре натуральных чисел(/1/, с. 131-151; /2/, с. 115-131).

2 Доказать теорему о существовании нестандартных моделей элементарной теории арифметики (/1/, с. 252-260).

3 Изучить метод построения моделей элементарной теории арифметики с помощью принципов нестандартного анализа (/1/, с. 25-32; /3/, с. 57-79).

Разобрать все примеры из указанных выше литературных источников и решить задачи 17.1, 17.2 в /1/, а также задачи 1-3 на стр.131 в книге /2/.

Литература, рекомендуемая для изучения темы

1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

2 Мендельсон Э. Введение в математическую логику. – М.: Наука,

Тема 37. Метод диагонализации в математической логике

В математической логике, теории множеств и других разделах математики широко применяется метод диагонализации, в основе которого лежит возможность построения антидиагонального счетного множества для любой последовательности счетных множеств. В курсовой работе необходимо изучить метод диагонализации и с его помощью построить примеры невычислимых функций. Рекомендуется следующий план работы.

1 Рассмотреть понятие счетного множества и изучить метод диагонализации (/1/, с. 12-30).

2 Рассмотреть понятие машины Тьюринга и методом диагонализации построить пример невычислимой функции (/1/, с. 36-45, 66-74).

3 Рассмотреть проблему остановки машины Тьюринга и с помощью тезиса Черча доказать ее неразрешимость (/1/, с. 47-48, 74-76).

Разобрать решения всех примеров из цитированных разделов /1/ и решить задачи 3.9, 3.10 из упражнения на стр. 45-48 и задачи 5.1-5.4 из упражнения на стр. 76-77 в книге /1/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

Тема 38. Машины Тьюринга и невычислимые функции

Машина Тьюринга и вычислимость являются фундаментальными понятиями математической логики. В курсовой работе необходимо изучить основные свойства машины Тьюринга и с ее помощью построить невычислимую функцию. Рекомендуется следующий план работы.

2 Рассмотреть понятие продуктивности машины Тьюринга и доказать ее основные свойства (/1/, с. 46, 55-60; /2/, с. 12-25).

3 Доказать невычислимость функции продуктивность машины Тьюринга (/1/, с. 60-64).

4 Рассмотреть проблему остановки машины Тьюринга и доказать ее неразрешимость (/1/, с. 47-48, 53-54, 64-65).

Разобрать решения всех примеров из литературных источников /1/,/2/ и решить задачи 3.1-3.10 из упражнения на стр. 45-48 в книге /1/.

Литература, рекомендуемая для изучения темы

1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

2 Мендельсон Э. Введение в математическую логику. – М.: Наука,

Тема 39. Вычислимость на абаке и рекурсивные функции

Рекурсивная функция и вычислимость являются фундаментальными понятиями математической логики. В курсовой работе необходимо изучить вычислимость на абаке, вычислимость машиной Тьюринга и доказать их эквивалентность понятию рекурсивной функции. Рекомендуется следующий план работы.

1 Разобрать такие основополагающие понятия математической логики, как машина Тьюринга, рекурсивная функция и тезис Черча (/1/, с. 36-54).

3 Доказать, что рекурсивные функции вычислимы на абаках (/1/, с. 100-

4 Доказать, что вычислимые функции рекурсивны (/1/, с. 100-122).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 6.1-6.4 из упражнения на стр. 96 в книге /1/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

Тема 40. Представимость рекурсивных функций и отрицательные результаты математической логики

Главными отрицательными результатами математической логики являются теорема Черча о неразрешимости логики, теорема Тарского о неопределимости истинности и первая теорема Геделя о неполноте систем арифметики. В курсовой работе необходимо изучить доказательства этих теорем с помощью представления рекурсивных функций в специальном расширении арифметики. Рекомендуется следующий план работы.

1 Разобрать такие основополагающие понятия математической логики, как язык арифметики и рекурсивная функция (/1/, с. 103-108, 141-145).

2 Рассмотреть понятие представимости функций в теории и доказать представимость рекурсивных функций в специальном непротиворечивом расширении Q арифметики (/1/, с. 212-226).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 14.1-14.2 из упражнения на стр. 226-227 и задачи 15.1-15.4 из упражнения на стр. 240 в книге /1/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

Тема 41. Разрешимость арифметики сложения

Проблема разрешимости теорий имеет принципиальное значение для элементарно аксиоматизируемых математических теорий и, в частности, для арифметики. В курсовой работе необходимо проанализировать эту проблему для арифметики с различными основными операциями. Рекомендуется следующий план работы.

2 Доказать неразрешимость арифметики со сложением и умножением

3 Доказать разрешимость арифметики со сложением, без умножения

Разобрать решения всех примеров из цитированных разделов книг /1/,/2/ и решить задачи 1-3 из упражнения на стр. 152 в книге /2/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

Тема 42. Логика второго порядка и определимость в арифметике

Логика второго порядка существенно отличается от логики первого порядка и позволяет всесторонне исследовать такую фундаментальную проблему математической логики, как определимость арифметической истины. В курсовой работе необходимо изучить основные методы логики второго порядка и с их помощью проанализировать понятие определимости в арифметике. Рекомендуется следующий план работы.

1 Изучить основные понятия логики второго порядка и проанализировать ее главные отличия от логики первого порядка (/1/, с. 261273).

2 Рассмотреть понятие определимого в теории множества и исследовать проблему определимости множеств предложений первого порядка, истинных в стандартной модели арифметики (/1/, с. 273, 274-280).

3 Рассмотреть введенный П. Коэном метод вынуждения и доказать с его помощью теорему Дж. Аддисона о неопределимости в арифметике класса множеств, определимых в арифметике (/1/, с. 281-289).

Разобрать решения всех примеров из цитированных разделов книги /1/ и решить задачи 18.1-18.4 из упражнения на стр. 272-273 и задачи 20.1-20.10 из упражнения на стр. 289 в книге /1/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

Тема 43. Метод ультрапроизведений в теории моделей

Метод ультрапроизведений является одним из основных методов теории моделей – раздела математической логики, изучающего связи между формальным языком и его интерпретациями в алгебраических системах, называемых моделями. Цель курсовой работы – изучить основы метода ультрапроизведений. Рекомендуется следующий план работы.

1 Изучить такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, разобрать примеры теорий (/1/, с. 13-61; /2/, с. 103-118).

2 Рассмотреть понятие фильтра над множеством и доказать основные свойства фильтров (/1/, с. 194-197; /2/, с. 83-87).

3 Рассмотреть понятие фильтрованного произведения алгебраических систем и доказать основную теорему об ультрапроизведениях (/1/, с. 197-203; /2/, с. 119-124).

4 Разобрать такие приложения основной теоремы об ультрапроизведениях, как теорема компактности, характеризация

элементарного класса алгебраических систем и другие (/1/, с. 203-207; /2/, с. 124-125, 172-173).

5 Рассмотреть приложения теоремы Силова и примеры силовских подгрупп (/1/, с. 336-338; /2/, с. 92-96).

Разобрать все примеры из указанных выше литературных источников и решить задачи 1.4.1, 1.4.2, 1.4.9, 1.4.16 на стр.62, 4.1.1-4.1.7, 4.1.12-4.1.14 на стр.207 в /1/, а также задачи 1-4 на стр. 125-126 в /2/.

Литература, рекомендуемая для изучения темы

1 Кейслер Г., Чен Ч.Ч. Теория моделей. – М.: Мир, 1977.

2 Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука,

Тема 44. Теорема Геделя о неполноте формальной арифметики

Теорема Геделя о неполноте формальной арифметики по праву считается одним из наиболее замечательных достижений математической логики, поскольку в своей семантической формулировке устанавливает

невозможность доказательства любого

формальной теории. В курсовой работе

формальной арифметики и разобрать доказательство семантической формулировки теоремы Геделя о ее неполноте. Рекомендуется следующий план работы.

1 Изучить постановку задачи о неполноте формальной арифметики (/1/,

2 Рассмотреть начальные понятия теории алгоритмов и примеры их применения (/1/, с. 12-21).

3 Доказать простейшие критерии неполноты (/1/, с. 21-25).

4 Изучить основы формальной арифметики и доказать семантическую формулировку теоремы Геделя о ее неполноте (/1/, с. 25-42).

Разобрать все примеры и восстановить все пропущенные доказательства

Литература, рекомендуемая для изучения темы 1 Успенский В.А. Теорема Геделя о неполноте. – М.: Наука, 1982.

Тема 45. Разрешимые и неразрешимые аксиоматические теории

Проблема разрешимости теорий имеет принципиальное значение для элементарно аксиоматизируемых математических теорий. В курсовой работе необходимо изучить методы доказательства разрешимости и неразрешимости теорий, проиллюстрировав их применение на известных важных примерах. Рекомендуется следующий план работы.

1 Разобрать такие основополагающие понятия теории моделей, как язык узкого исчисления предикатов (УИП) и его интерпретация в моделях, рассмотреть известные конструкции над алгебраическими системами (/1/, с. 103-118; /2/, с. 12-25).

2 Изучить методы доказательства разрешимости и неразрешимости теорий (/2/, с. 265-275).

3 Рассмотреть известные примеры доказательства разрешимости и неразрешимости аксиоматических теорий (/2/, с. 275-292; /3/).

Разобрать решения всех примеров из литературных источников /1/, /2/.

Литература, рекомендуемая для изучения темы 1 Ершов Ю.Л., Палютин Е.А. Математическая логика. – М.: Наука,

2 Ершов Ю.Л. Проблемы разрешимости и конструктивные модели. –

3 Рабин М.О. Разрешимые теории. В кн.: Справочная книга по математической логике, ч.3. Теория рекурсии. – М.: Наука, 1982. – с. 77-111.

4 Ершов Ю.Л., Лавров И.А., Тайманов А.Д., Тайцлин М.А. Элементарные теории // УМН, 1965, 20, № 4, с. 37-108.

Тема 46. Интерполяционная лемма Крейга и ее приложения

Интерполяционная лемма Крейга дает положительное решение следующей важной задачи логики узкого исчисления предикатов (УИП): если из предложения A следует предложение C, то существует предложение B, которое следует из A, из которого следует C и которое содержит лишь нелогические символы, входящие как в A, так и в C. В курсовой работе необходимо изучить доказательство интерполяционной леммы Крейга и рассмотреть ее приложения к задаче о непротиворечивости объединения теорий и к задаче об определимости понятий теории. Рекомендуется следующий план работы.

1 Разобрать доказательство интерполяционной леммы Крейга (/1/, с.

2 Доказать теорему Робинсона о непротиворечивости объединения теорий (/1/, с. 319-322).

3 Доказать теорему Бета об определимости понятий теории (/1/, с. 25-

Выполнить упражнение на с. 327 в книге /1/.

Литература, рекомендуемая для изучения темы 1 Булос Дж., Джеффри Р. Вычислимость и логика. – М.: Мир, 1994.

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

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

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

Из компактности em

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

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

От нескрупулезности эмов

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

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

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

От ultraproducduct

Другим способом нестандартной модели арифметики является использование ультрапродукта. Типичная конструкция использует множество всех последовательностей натуральных чисел,. Определите две последовательности, если они согласны почти ever . Получающаяся полукровка является нестандартной моделью арифметики. Её можно отождествить с гиперъестественными числами.

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

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

Любая отсчитываемая нестандартная модель арифметики имеет тип порядка, где λ - тип порядка стандартных натуральных чисел, λ * - дуальный порядок (бесконечная декресирующая последовательность) и start- тип порядка относительных чисел. Другими словами, отсчитываемая нестандартная модель начинается с бесконечной возрастающей последовательности (стандартные элементы модели). Далее следует коллекция "блоков", каждый из типов порядка, тип порядка целых чисел. Эти блоки, в свою очередь, плотно упорядочены с типом заказа рационалов. Результат следует довольно легко, потому что легко видеть, что блоки нестандартных чисел должны быть дензе и линейно упорядочены без endpo, и тип порядка rationals является единственным поддающимся отсчету dense линейного порядка без endpo .

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

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

Кроме того, можно определить "квадратные корни", такие как по меньшей мере v, что. Они не могут быть в пределах стандартного конечного числа любого относительного кратного С помощью методов, аналогичных нестандартному анализу, можно также использовать PA для определения близких приближений к иррациональным множествам нестандартного числа u, такого как по меньшей мере v с (они могут быть определены в PA с помощью нестандартных конечных относительных приближений, даже если pi не может быть). Еще раз, должен быть больше, чем любое стандартное конечное число для любого стандартного конечного m, n.

Это показывает, что арифметическая структура отсчитываемой нестандартной модели более сложна, чем структура рационалов. Но в этом есть нечто большее, чем это.

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

Вот философию-то развели. Я вовсе не хочу поддержать anikа, однако в вопросе про бесконечность множества натуральных чисел действительно есть двойное дно (именно в математическом смысле). Дело в том, что понятие "конечности" множества однозначно выразимо только на языке логики второго порядка, в то время как арифметика и теория множеств обычно формализуются в логике первого порядка. Отсюда и возникают неоднозначности в интерпретациях.

Например, если мы хотим сказать, что некий алгоритм завершается за конечное количество шагов, то на языке арифметики первого порядка это запишется примерно так: "Существует такое натуральное число n, которое является номером шага, на котором алгоритм останавливается". Всё просто? Отнюдь. Вопрос в том, что такое "натуральное число". Если это - объект, который определяет арифметика первого порядка, то мы можем вспомнить, что сия теория некатегорична, т.е. у неё есть "нестандартные модели". А это значит, что номером шага, на котором останавливается алгоритм, может оказаться "нестандартное число", что равносильно утверждению о том, что у последнего шага стандартного-то номера как раз и нет, т.е. в стандартном смысле алгоритм не останавливается никогда.

Может быть в некой формализованной теории множеств первого порядка этот казус удастся разрешить? На первый взгляд кажется, что это так. Например, в ZFC стандартное натуральное число можно определить как элемент минимального индуктивного множества. Однако при более детальном копании выясняется, что у самой ZFC есть нестандартные модели, в которых то, что ZFC трактует как "стандартное натуральное число" на самом деле может оказаться нестандартным.

Увы, в логике первого порядка эти проблемы неразрешимы из-за принципиальных ограничений языка. В логике второго порядка они, казалось бы, разрешимы. Но оказывается, что там - свои тараканы: логика второго порядка оччень странная штука. (вроде бы Willard Van Orman Quine
где-то даже сказал, что есть основания трактовать логику второго порядка как нечто, в строгом смысле слова "логикой" не являющееся).

Вот это вообще один из лучших постов, что я вычитал в последнее время на dxdy, может для кого-то банальность, но в нём полностью сформулирован тот момент, который мне не даёт покоя во всём этом предприятии с классической логикой, теоремами Гёделя, нестандартными моделями, Левенгеймом Сколемом и т.д. я в нескольких топиках обещал это наисать, кажется, вот epros написал вместо меня лучше гораздо.

Правда я никакой ставки, в отличии от epros , на конструктивизм не делаю, может из-за того что его плохо продумывал, конечно

Мне кажется, нестандартные модели ZFC — это немного другое дело. Если мы всё нужное себе выразили в ZFC, то как на нас скажется их существование?

Ну вот тем и мешает: ZFC ведь просто дедуктивная система, пользуясь ей мы можем сформулировать и доказать некоторое утверждение вида (n)$" />
, гарантирует ли это, что есть конечная строка вида которая будет номером шага, на котором алгоритм остановится? Нет, не гарантирует.

В самой , скорее всего, не получится (если получится - то это будет означать, что у нет стандартной модели). А так - добавим к акиому \bot$" />
(ну или для любого другого алгоритма , вопрос остановки которого не разрешим в , добавим аксиому " останавливается").

Последний раз редактировалось Z1X 24.05.2017, 09:28, всего редактировалось 1 раз.

Дело в том, что понятие "конечности" множества однозначно выразимо только на языке логики второго порядка, в то время как арифметика и теория множеств обычно формализуются в логике первого порядка.

Что за глупости? Понятие конечности можно выразить в теории множеств первого порядка. Если делать это без арифметики, то множество конечно тогда, когда не существует биекции между этим множеством и каким-либо собственным его подмножеством. Очевидно например, что пустое множество конечно.

Например, в ZFC стандартное натуральное число можно определить как элемент минимального индуктивного множества. Однако при более детальном копании выясняется, что у самой ZFC есть нестандартные модели, в которых то, что ZFC трактует как "стандартное натуральное число" на самом деле может оказаться нестандартным.

Это уже какая-то полная чушь. Первое, что важно: что такое стандартная модель ZFC? Что это? Какие требования стандартности? И как понять: на самом деле может оказаться нестандартным? На самом деле — это как? Во-вторых, стандартная модель и вообще все модели задаются до изоморфизма. Модели разные, если они неизоморфны. Поэтому внутренняя структура каждого числа, арифметических операций и всей арифметики в целом не играет никакой роли. Множество конечно, если биекция отображает его на отрезок стандартного натурального ряда. Строение элементов этого отрезка нам безразлично. Отрезок задается простыми неравенствами.

В самой , скорее всего, не получится (если получится - то это будет означать, что у нет стандартной модели).

Последний раз редактировалось Someone 24.05.2017, 22:23, всего редактировалось 2 раз(а).

Но Вы просто не поняли, о чём идёт речь. В метаматематике есть теорема, касающаяся теорий первого порядка: если у нас есть набор аксиом, который имеет конечные модели из сколь угодно большого числа элементов, то этот набор имеет и бесконечную модель.

Так вот, представьте себе, что мы сочинили некий набор аксиом, которому, по нашему мнению, должны удовлетворять только конечные множества, но среди них есть сколь угодно большие. Из упомянутой теоремы следует, что существуют и бесконечные множества, удовлетворяющие всем нашим аксиомам. Это и есть "понятие конечности нельзя выразить в теории первого порядка".

множество конечно тогда, когда не существует биекции между этим множеством и каким-либо собственным его подмножеством

Ну да, это определение Дедекинда, насколько я помню. Беда в том, что оно не равносильно обычному (множество конечно, если оно равномощно натуральному числу; причём, имеются в виду не "натуральные числа вообще" (это непонятно, что такое), а конкретная модель натурального ряда, определяемая в теории множеств). Если в качестве теории множеств взять ZF (без аксиомы выбора), то возможны странные множества, в которых можно найти сколь угодно длинную конечную последовательность попарно различных элементов, но нельзя указать бесконечную последовательность. Они конечны по Дедекинду, но бесконечны в смысле обычного определения.

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

В метаматематике есть такая теорема: если у нас есть некое множество аксиом, в котором каждый конечный набор аксиом имеет модель, то и всё наше множество имеет модель.

Вот возьмём арифметику Пеано, присоединим к её алфавиту новую константу и добавим бесконечную последовательность аксиом , , , , … (штрих означает "следующее натуральное число", то есть, , , …). Очевидно, если мы добавим только конечное число этих новых аксиом, то модель есть: новый символ можно отождествить с натуральным числом, которое не упоминается в добавленных аксиомах. По упомянутой теореме, модель существует и для всех указанных аксиом. Но в ней есть натуральное число, не совпадающее ни с одним из натуральных чисел в первоначальной модели. Эта новая модель и будет нестандартной.

Поскольку модель арифметики Пеано вкладывается в ZFC как наименьшее индуктивное множество, мы теперь можем повторить эту конструкцию для ZFC.

Последний раз редактировалось Anton_Peplov 24.05.2017, 11:07, всего редактировалось 1 раз.

Последний раз редактировалось Z1X 24.05.2017, 11:11, всего редактировалось 2 раз(а).

В метаматематике есть теорема, касающаяся теорий первого порядка: если у нас есть набор аксиом, который имеет конечные модели из сколь угодно большого числа элементов, то этот набор имеет и бесконечную модель.

Если понятие нельзя выразить в теории первого порядка, то нельзя будет и для второго порядка. Ведь порядок всегда можно понизить, если задействовать теоретико-множественный синтаксис. Например, вы можете написать , а можете . Это одно и то же. Таким образом у вас конечность вообще не выразима.

Ну, под стандартной моделью арифметики или теории подразумевается некая гипотетическая модель, которая обладает всеми свойствами, которые мы интуитивно ожидаем от натуральных чисел или множеств. Но выразить эти свои смутные желания аксиоматически не можем.

Это чушь. Если утверждение нельзя формализовать, оно не научно. Модель арифметики первого порядка в некоторой метатеории называется стандартной, если в этой же метатеории существует модель арифметики второго порядка, и две модели изоморфны. Вернее, надо взять от модели второго порядка лишь числовую часть, и доказать изоморфность с первой, но это не важно. Это научно, и все это можно при необходимости аксиоматизировать. Если же стандартную модель ZFC нельзя определить так же строго, то все утверждения о ней заведомо бессмысленны.

Вы можете поделиться своими знаниями, улучшив их ( как? ) Согласно рекомендациям соответствующих проектов .

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

Резюме

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

Существование нестандартных моделей арифметики можно показать, применив теорему компактности . Для этого мы определяем теорию с языком арифметики Пеано, к которому мы добавляем новый символ x . Набор аксиом новой теории содержит аксиомы арифметики Пеано, к которым мы добавляем бесконечный набор аксиом, а именно аксиом x > n , для каждого естественного стандарта n . Каждое конечное подмножество этих аксиом справедливо в стандартной модели арифметики, и поэтому по теореме компактности существует модель, удовлетворяющая всем этим аксиомам, но элемент этой модели, соответствующий x, не может быть стандартным естественным целым.

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

Счетные модели

Мы действительно можем определить отношение эквивалентности для нестандартных целых чисел с помощью эквивалента b тогда и только тогда, когда a и b отличаются от стандартного целого числа. Мы легко проверяем, что это отношение эквивалентности, что классы эквивалентности изоморфны как упорядоченные множества (по аналогии с гиперреальными числами , эти классы по-прежнему называются галактиками ) и что отношение порядка целых чисел модели переходит в фактор . Затем мы показываем, что фактормножество является упорядоченным множеством, не содержащим ни большего, ни меньшего элемента, чей порядок плотный , и, поскольку он счетный, он изоморфен . Z > Q >

Ниже приведена коллекция сомнений, на некоторые из которых есть конкретные ответы, а на другие, возможно, нет. Любая помощь будет приветствоваться.

Читая книгу Питера Смита "Gödel Without (Too Many) Tears", особенно там, где он приводит нестандартную модель Q, я начал задаваться вопросом, имеет ли причина существования нестандартных моделей арифметики какое-либо отношение к теоремам неполноты.

Я не знаю, подразумевает ли категоричность полноту (в смысле, что каждое предложение может быть решено доказательством), но в любом случае, кажется разумным, когда формализуешь данную (неформальную) теорию, попытаться "заставить"- каким-то образом формальную теорию говорить "почти исключительно" о предполагаемой интерпретации. Поэтому я начал думать, нельзя ли добавить в PA какую-нибудь аксиому (или схему аксиом), чтобы запретить ее наиболее очевидные нестандартные модели.

Первая идея в этом направлении была такой: хорошо, у нас есть наш класс терминов 0, S0, SS0 и т.д. Итак, если бы мы нашли способ сказать, что для каждого x существует некоторый термин, которому он равен, мы бы закончили.

Но потом я понял, что наши термины определяются индуктивно и что мы неявно делаем предположение: "и ничто другое не является термином", очень похожее на желаемое "и ничто другое не является числом", которое мы хотели бы добавить в PA. Эта мысль несколько обеспокоила меня: каждое метатеоретическое понятие (термины, формулы и даже доказательства!) основано на подобных предположениях! (Я до сих пор не нашел способа избавиться от этих опасений).

Оставим это в стороне. Что если мы перейдем к более сильной теории (с другими аксиомами, но с расширением по определениям, которое доказывает каждую аксиому PA), например, ZFC? Натуральные числа становятся тогда 0 (пустым множеством) плюс ординалы фон Неймана (полученные с помощью пар и союзов), которые не содержат предельного ординала. Множество натуральных чисел получается из Бесконечности, просто выбирая их с помощью Постижения. Кунен на странице 23 своего "Основания математики" говорит, что кругооборот в неформальном определении натурального числа нарушается "путем формализации свойств отношения порядка на омеге". Могут ли нестандартные модели пережить такую формализацию?

Ну, мне кажется, я где-то читал, что омега абсолютна, так что форсирование не будет способом получения таких нестандартных моделей. Кроме того, я не уверен, является ли (расширение определениями из) теории множеств ZFC консервативным расширением PA, но тогда оно не смогло бы доказать ничего о натуральных числах (выражаемых на языке арифметики), чего не может доказать только PA. Так что, похоже, что нестандартные модели должны выжить! Возможно, из-за того, что понятие подмножества данного множества не является особенно ясным (хотя похоже, что это не должно быть проблематичным для наследственно конечных множеств).

Читайте также: