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

Размещено на http://www.Allbest.Ru/

Министерство науки и высшего образования Российской Федерации

Федеральное государственное автономное образовательное учреждение высшего образования

«Национальный исследовательский Нижегородский государственный университет им. Н.И. Лобачевского»

Арзамасский филиал

Физико-математический факультет

Кафедра физико-математического образования

Направление подготовки «Педагогическое образование»

Профиль Математика

Курсовая работа

Тема:

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

Выполнила: Спирякова М.Д.,

студентка III курса з/о

Научный руководитель:

Ст. преподаватель Курдин Д.А.

Арзамас - 2021



Содержание

Введение

1. Теория формализации математической теории

1.1 Программа Гильберта формализации математики и теорема Гёделя о неполноте

1.2 Формальные теории числовых систем

2. Формальный математический анализ

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

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

Заключение

Список литературы



Введение

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

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

Любое конечное подмножество этих аксиом классифицируется моделью, которая является стандартной моделью арифметики плюс константа x, интерпретируемая как некоторое число, большее, чем любое число, упомянутое в конечном подмножестве P *.

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

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

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

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

Задачи курсовой работы:

- рассмотреть программу Гильберта формализации математики и теорема Гёделя о неполноте;

- исследовать формальные теории числовых систем;

- проанализировать нестандартную модель формальной арифметики и ее некатегоричность;

- изучить структуру сопоставимых нестандартных моделей.

Структура работы. Работа состоит из введения, двух глав, заключения, списка литературы, приложений.



1. Теория формализации математической теории

1.1 Программа Гильберта формализации математики и теорема Гёделя о неполноте

Язык и аксиомы. Это - логико-математическое исчисление (или прикладное исчисление первого порядка), формализующее элементарную теорию чисел. Наиболее популярная формализация основана на подходе Пеано, предложенном им в 1889 г. и рассмотренном нами в ранее (пример 26.3).

Язык этого исчисления кроме логических связок и равенства содержит нелогическую константу 0, двухместные функциональные символы +, одноместный функциональный символ `. Термы строятся из константы 0 и переменных с помощью функциональных символов; в частности, натуральные числа изображаются термами вида 0”…'. [11]

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

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

Средства формальной арифметики оказываются достаточными для вывода теорем, устанавливаемых в стандартных курсах элементарной теории чисел. Более того, формальная арифметика оказывается эквивалентной аксиоматической теории множеств ZF Цермело-Френкеля без аксиомы бесконечности (ZF7): в каждой из этих систем может быть построена модель другой.[7]

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

Одним из путей выхода из кризиса в основаниях математики в начале XX в., обусловленного обнаружением парадоксов (антиномий) в теории множеств, должен был стать гильбертовский путь формализации математики и логики. [2]

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

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

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

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

1) всякая естественная непротиворечивая формализация S арифметики или любой другой математической теории, содержащей арифметику (например, теории множеств), неполна и непо-полнима. Неполнота означает, что в S имеется содержательно истинная, но неразрешимая формула, т.е. такая формула A, что ни A, ни ее отрицание -А не выводимы в S. Непополнимость S означает, что каким бы конечным множеством дополнительных аксиом (например, неразрешимыми S в формулами) ни расширить систему S, в новой формальной системе неизбежно появятся свои неразрешимые формулы;

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

Эта теорема, как и первая, распространяется на всякую непротиворечивую формальную систему, содержащую формальную арифметику.

Доказательство первой теоремы проводится разработанным Гёделем методом арифметизации синтаксиса языка формальной теории, который стал одним из основных методов теории доказательств (метаматематики). Этим методом строится формально неразрешимая формула. Фиксируется нумерация основных формальных объектов (формул, конечных последовательностей формул и т.д.) натуральными числами, такая, что основные свойства этих объектов (быть аксиомой, быть выводом по правилам системы и т.д.) оказываются распознаваемыми по их номерам с помощью весьма простых алгоритмов.

Столь же просто вычисляются по номерам исходных данных номера результатов комбинаторных преобразований (например, подстановки терма в формулу вместо переменной). При этом оказывается возможным написать арифметическую формулу В(а, Ь), имеющую вид f (а, Ь) = 0 (где f - примитивно рекурсивная функция) и выражающую условие: b есть номер формулы, которая получается из формулы с номером а путем подстановки натурального числа а вместо переменной х.

Если р - номер формулы , то формулаЪ)) выражает свою собственную невыводимость. Она и оказывается формально неразрешимой. Отсюда и следует, что в любой непротиворечивой системе с минимальными выразительными арифметическими возможностями имеется истинное, но невыводимое суждение указанного вида. Достаточно подробно доказательство этой теоремы будет изложено позднее после того, как будут изучены основы теории алгоритмов и рекурсивных функций.[8]

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

Из первой теоремы Гёделя о неполноте арифметики видно, что (семантическое) понятие истинности в арифметике, а следовательно, и во всей математике нельзя исчерпывающим образом формализовать посредством (синтаксического) понятия доказуемости в какой-либо одной формально-логической системе.

Вторая теорема Гёделя о неполноте арифметики показывает, что и основная цель первоначальной программы Гильберта по формализации математики оказывается недостижимой. Эта цель состояла в том, чтобы доказать формальную непротиворечивость арифметики, пользуясь при этом так называемыми "финитными" методами, т.е. лишь такими методами доказательств, которые применяются в самой арифметике. Но всякое разумное уточнение понятия финитного доказательства, по-видимому, формализуемо в формальной арифметике и потому, согласно второй теореме Гёделя, невозможно.[2]

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

Упомянем также еще об одной важной теореме метаматематики, доказанной в 1936 г. американским логиком А.Чёрчем. В ней утверждается, что не существует эффективной процедуры для решения вопроса относительно произвольной формулы формальной теории, содержащей арифметику натуральных чисел, является ли такая формула теоремой теории, т.е. всякая такая формальная теория неразрешима. Из этой теоремы вытекает, в частности, и теорема Гёделя о неполноте. Впоследствии была доказана неразрешимость большого числа формальных теорий, в частности элементарной теории групп, элементарной теории полей.[3]

Таким образом, после этих результатов Гёделя стало ясно, что для решения одного из основных вопросов математики - проблемы непротиворечивости, по-видимому, не обойтись без других, отличных от финитистских, средств и идей. Непротиворечивость формальной системы может быть обоснована только средствами более сильными, чем те, которые формализованы в данной системе. Здесь оказались возможными разные подходы, не для всех математиков в равной степени приемлемые или убедительные, в частности, ввиду существования различных точек зрения на допустимость тех или иных логических средств. В 1936 г. Г. Генцен получил доказательство непротиворечивости формальной арифметики, использующее средство, отсутствующее в арифметике, - так называемую трансфинитную (бесконечную) индукцию до некоторого счетного трансфинитного числа.

1.2 Формальные теории числовых систем

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

Во второй половине XIX в. в связи с необходимостью обоснования математического анализа и приведения в систему огромного количества результатов, полученных в этой области математики, числа снова оказались в центре внимания математиков. [1]

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

Приведем еще одну теорему - теорему А. Тарского об истинности, показывающую, что формальным системам присуща ограниченность еще одного типа. Содержательное понятие истинности, которым мы постоянно пользуемся, также поддается формализации. Понятие истинности в формальной системе Т определяется относительно другой формальной системы Т' Эта система Т' должна быть в определенным смысле сильнее системы Т В 1956 г. Тарский доказал, что понятие истинности (множество всех истинных предложений, множество истинности предиката) в непротиворечивой формальной теории, включающей формальную арифметику, неопределимо в этой теории.[8]

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

Перефразируя образное изречение Куайна, можно сказать, что формальные системы попытались проглотить больший кусок онтологии, чем они в состоянии переварить.

Опишем кратко формальные теории других систем чисел - целых, рациональных, действительных.

Систему целых чисел можно охарактеризовать с помощью следующих условий. Кольцо целых чисел - это есть кольцо с единицей е, не содержащее отличного от него подкольца с единицей и обладающее тем свойством, что пе ? 0 для любого натурального числа п. В самом деле, нетрудно показать, что множество всех элементов вида пе изоморфно системе < N; + > натуральных чисел. Следовательно, данное кольцо содержит подкольцо Z₀, изоморфное кольцу Z целых чисел, поскольку кольцо Z - минимальное из таких колец. Но так как Z₀ содержит единицу е, то, по условию, Z₀ должно совпасть с данным кольцом, которое, следовательно, будет кольцом целых чисел.[10]

Систему рациональных чисел можно охарактеризовать с помощью следующих условий. Поле рациональных чисел - это простое поле характеристики нуль. (Поле называется простым, если оно не имеет подполей, отличных от него самого. Говорят, что поле имеет характеристику нуль, если ае ? 0 для любого его элемента а ? 0 и любого целого числа n ? 0).

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

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

Гильберт охарактеризовал множество вещественных чисел как максимальное архимедово упорядоченное поле (т. е. любое поле, являющееся его расширением, уже не архимедово).[15]

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

С этой характеристикой системы действительных чисел связана одна из знаменитейших проблем XX в. - проблема М.Я. Суслина. Эта проблема состоит в том, что требуется узнать, сохранится ли указанная характеристика системы действительных чисел, если в ней последнее условие сепарабельности заменить более слабым требованием, называемым условием Суслина: любая система из попарно не пересекающихся непустых интервалов не более чем счётна. Другими словами, будет ли изоморфно системе действительных чисел линейно упорядоченное множество, удовлетворяющее перечисленным выше условиям, кроме, сепарабельности, и условию Суслина. нестандартный формальный арифметика гильберт гёдель

Судьба этой проблемы, оказалась поистине исторической, и на ее решение потребовалось более 40 лет. Предположение о ее положительном решении получила название гипотезы Суслина.

Контрпример к гипотезе (хотя пока и не существующий), т.е. упорядоченное множество, удовлетворяющее всем условиям проблемы! М. Я. Суслина, но не изоморфное действительной прямой, получил названий континуум Суслина. Эта проблема встала в один ряд с континуум-проблемой Кантора, и полное решение их обеих было получено лишь в начале 1960-х гг., когда американский математик П. Коэн открыл принципиально новый метод доказательства, получивший название метода форсинга (вынуждений). (За это открытие он был удостоен в 1966 г. на Международном математическом конгрессе в Москве высшей международной награды, которой удостаиваются ученые-математики, - Филдсовской премии.)

Проблему Суслина, как и континуум-проблему Кантора, вообще невозможно решить в обычном смысле слов - решить проблему, т.е. дать определенный ответ "да" или "нет" на поставленный вопрос. Гипотеза Суслина, как и континуум-гипотеза Кантора, оказалась не зависящей от остальных аксиом теории множеств. Другими словами, возможна теория множеств, в которой гипотеза Суслина справедлива, и возможна теория множеств, в которой эта гипотеза не выполняется. Кроме того, была также установлена взаимная независимость и самих двух гипотез - гипотезы Суслина и континуум-гипотезы Кантора.

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

Аксиоматическая теория натуральных чисел, построенная на базе системы аксиом Пеано, категорична, т.е. имеет единственную с точностью до изоморфизма модель. С использованием теоремы Гёделя о неполноте формальной арифметики можно доказать существование неизоморфных моделей формальной арифметики. [20]

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

В аксиоме индукции из системы Пеано участвует множество М, на которое не накладывается никаких ограничений и которое может рассматриваться как множество истинности произвольного предиката _: т.е. множество натуральных чисел, удовлетворяющих любому мыслимому свойству F натуральных чисел.

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

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

Ясно, что моделью формальной арифметики является обычное множество натуральных чисел N, в котором и +,. - обычные операции сложения и умножения натуральных чисел.

Пользуясь локальной теоремой Гёделя-Мальцева, установим наличие у формальной арифметики одной необычной модели. Она называется нестандартная модель арифметики. Рассмотрим следующую бесконечную совокупность формул формальной арифметики:

(в данной формуле в правой части равенства п слагаемых). Первая из этих формул утверждает, что число х делится на 2, вторая - что х делится на 3 и т.д., (п -1)-я - что х делится на п и т.д. [11]

Поэтому обозначим эти формулы соответственно:

Рассмотрим далее следующую бесконечную совокупность формул:

Наконец, обозначив через совокупность из девяти аксиом формальной арифметики, рассмотрим следующее множество формул формальной арифметики . [12]

Таким образом, применив к ₁ локальную теорему Гёделя-Мальцева. Ясно, что каждое конечное подмножество формул из ₁ содержит лишь конечное число формул из 0 и потому имеет модель: его моделью будет обычная система натуральных чисел. Тогда по упомянутой теореме все множество ₁ имеет модель. Ее особенностью будет то свойство, что в этой модели будет существовать (натуральное) число, делящееся на все натуральные числа.

2. Формальный математический анализ

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

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

Суть их состоит в том, что все эти теории все же еще не до конца формализованы. Дело в том, что приведенные выше характеризации, например системы действительных чисел, сформулированы в терминах не только основных, элементарных понятий, таких, как +, *, ? и т.п., но и в терминах, относящихся к понятиям более высокого типа, таких, как "ограниченное сверху множество", "счетное всюду плотное подмножество" и т.п.

Другими словами, эти характеристики выражены не на языке первой ступени, а на языке более высокой ступени, в котором понятие множества выступает как самостоятельный индивид. На первый взгляд может показаться, что для углубления формализации понятия действительного числа далее следует приступить к формализации концепции множества. Но теория множеств таит в себе немало проблем и подводных камней (таких, как, например, континуум-гипотеза), которые могут не иметь никакого отношения к предмету изучения. [13]

На практике множества, нужные в такой области, как теория чисел, - это лишь такие, которые могут быть описаны с помощью совсем специальных свойств. Поэтому возможен другой подход к формализации теорий числовых систем - изгнать из аксиоматик упоминания о множествах и заменить их соответствующими свойствами. Так, содержательная аксиома индукции Пеано "Любое множество натуральных чисел, которое содержит 0 и вместе с любым своим элементом х содержит также следующий элемент х', - это множество всех натуральных чисел" при таком подходе превращается в схему формальных аксиом

где F(x) - произвольная формула с одной свободной предметной переменной х. Таких формул бесконечно много, и соответствующая формальная аксиома формулируется для каждой из них. Можно показать, что такая схема аксиом не может исчерпать всей силы содержательной аксиомы индукции в том смысле, что нельзя посредством такой схемы (наряду с другими формальными аксиомами формальной арифметики) обеспечить, чтобы единственной с точностью до изоморфизма моделью такой системы аксиом было множество натуральных чисел (что, напомним, обеспечивала содержательная система аксиом Пеано). Тем не менее, для многих целей вполне достаточно употреблять эту форму аксиомы индукции. [17]

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

Словесно эту запись можно прочитать так: если существует число, обладающее свойством F, и всякое число, обладающее этим свойством, меньше некоторого числа, то существует наименьшее такое число, что все числа, обладающие свойством F. меньше его. В связи с такой формализацией возникает естественный вопрос, до какой степени она отражает "полное содержание" исходной аксиомы полноты в ее содержательной теоретико-множественной формулировке. [10]

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

Например, чтобы сказать, что множество вещественных чисел х, обладающих свойством F(x), не пусто, мы пишем просто; существование верхней грани выражается формулой и т.д. Это и дает приведенную выше формальную запись аксиомы полноты. Вопрос о том, насколько мы при этом отдалились от первичной теоретико-множественной аксиомы полноты, - это по существу, вопрос о том, каков класс множеств, определимых свойствами F(x).[9]

Таким образом, формальная (элементарная) теория вещественных чисел может быть построена на базе системы следующих аксиом:

аксиомы поля;

аксиомы порядка: x ? x

аксиома полноты (схема аксиом).

Это означает, что система действительных чисел есть полное линейно упорядоченное поле.[8]

Иногда аксиому полноты формулируют в более ограниченном виде - не для произвольного свойства F(x) действительных чисел x, а для конкретного свойства:



- быть корнем алгебраического многочлена. В этом случае аксиома полноты формулируется так:

где .

Или же в этом случае аксиома полноты распадается на две части:

1) (из каждого вещественного числа или противоположного ему числа можно извлечь квадратный корень);

2) (каждый алгебраический многочлен нечетной степени имеет хотя бы один вещественный корень).

Аксиомы поля и аксиомы порядка (т.е. аксиомы линейно упорядоченного поля) и аксиома полноты в одной из двух последних формулировок образуют систему аксиом элементарной теории, так называемых вещественно-замкнутых полей.[6]

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

В 1930-е гг. А. Тарский доказал, что для любого данного суждения о действительных числах, которое может быть выражено на формальном языке элементарной теории вещественно-замкнутых полей, либо само это суждение, либо его отрицание доказуемо в этой теории, те. выводимо из ее аксиом. Это означает, что элементарная теория вещественно-замкнутых полей абсолютно полна, а соответствующая система аксиом по существу определяет алгебраические свойства действительных чисел. При этом разрешающая процедура (алгоритм) основана на так называемом методе элиминации (ликвидации) кванторов, который впервые применили Ленгфорд и Пресбургер в 1920-е гг. [4]

Этот метод оказался чрезвычайно эффективным и впоследствии нашел многочисленные применения для решения проблемы разрешимости в самых разных разделах математики.

Идея метода элиминации кванторов состоит в следующем. Вначале доказывается, что для любой формулы А (рассматриваемой теории первого порядка) вида где - атомарная формула или отрицание атомарной формулы, найдется такая бескванторная формула В, что в данной теории доказуема (выводима) эквивалентность А - В. Основываясь на этом утверждении, к каждой замкнутой формуле (предложению) S данной теории может быть применена процедура элиминации кванторов, которая состоит в следующем:

• превратить самые внутренние кванторы этого предложения в кванторы существования, если они не таковы (пользоваться при этом законами де Моргана);

• привести область действия каждого из этих кванторов к дизъюнктивной нормальной форме;

• распределить кванторы существования по дизъюнктивным членам:

• заменить все ?-формулы А эквивалентными им бескванторными формулами В на основании предыдущего утверждения;

• если полученная формула все еще не является бескванторной, то повторить описанные шаги, начиная с п. 1; в противном случае рассматриваемое предложение S превратилось бы либо в истину, либо в ложь.[3]

Таким образом, метод элиминации кванторов сводит логический вопрос о (раз) решении к математическому вопросу о критериях существования решения совершенно определенной задачи. Что касается теории вещественно-замкнутых полей, то решение обсуждаемой проблемы в ней основывается на классической теореме Штурма (доказанной еще в 1829 г.) и доставляющей средство определения числа (вещественных) корней алгебраического многочлена с целыми коэффициентами между двумя заданными границами, а также общего числа корней такого многочлена.

Теорема утверждает, что число корней между b и с (b < с) многочлена р(х) равно (без учета кратности) числу перемен знака в так называемом ряду Штурма этого многочлена. В удобной для элиминации кванторов форме эта теорема может быть сформулирована следующим образом: для каждого многочлена р (a, а_1,..., а_п) с целыми коэффициентами имеется такая бескванторная формула B(a₁,..., а_п b, с), что эквивалентность

выводима из аксиом элементарной теории вещественно-замкнутых полей.

Заслуга А.Тарского состоит в том, что он доказал эту теорему в следующем обобщенном виде: для любой бескванторной формулы А(x) найдется такая бескванторная формула В(b, с), что эквивалентность

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

В самом деле, пусть А(x) - бескванторная формула с единственной свободной переменной x и мы хотим элиминировать (удалить) квантор ?x из формулы .

Очевидно, что в любом линейно упорядоченном поле справедливо утверждение (эквивалентность):

Но ведь из этой формулы можно удалить кванторы на основании обобщенной теоремы Штурма. [14]

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

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

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

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

Поскольку в качестве системы расстояний в евклидовой геометрии принимается поле R вещественных чисел, геометрию проще всего понимать, например, по Вейлю - как точечное пространство E над соответствующим векторным пространством V над полем R.

Теперь программу формализации (аксиоматизиции) можно сформулировать следующим образом. Выбрав конечное число первичных геометрических понятий (элементов) и отношений между ними, найти такую систему аксиом для этих элементов и отношений, для которой из того, что некоторая элементарная теорема верна для принятого в E определения основных понятий, вытекает, что она выводима из принятых аксиом, и, обратно, выводимость влечет истинность. (Здесь, как и обычно, мы называем высказывание элементарным, если оно выразимо в языке первой ступени с рассматриваемыми отношениями на рассматриваемых элементах.) Эта программа аксиоматизации реализуется посредством так называемой координатизации исходного геометрического пространства E.[18]

Задача формализации аксиоматической геометрии, построенной, например, на базе системы аксиом Гильберта, снова ставит нас перед проблемой, уже возникавшей при формализации теорий числовых систем: как адекватно выразить содержание аксиомы полноты (непрерывности), в формулировке которой участвуют множества M и N, в нашем формальном языке первой ступени, как понимать участвующие там множества? Здесь мы снова выбираем тот же выход, что и при формализации теорий числовых систем: мы заменяем множества определяющими их предикатами (свойствами) в языке первого порядка для элементарной геометрии с исходными понятиями по системе Гильберта. Получаемая таким образом в элементарной форме аксиома полноты (а точнее, схема аксиом, называемая схемой Тарского) может быть сформулирована следующим образом: для любых формул P(.) и Q(.)имеем

Из этой схемы Тарского непосредственно следует, что построенное на прямой g упорядоченное поле удовлетворяет (элементарной) аксиоме полноты из теории вещественных чисел, т.е. в конечном итоге является вещественно-замкнутым полем. [19]

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

Таким образом, элементарная теория евклидовой геометрии на плоскости, построенная на основе планиметрических аксиом системы Гильберта, полна, т.е. для любого предложения F в языке элементарной геометрии одно из предложений F выводимо из этих аксиом; более того, вопрос о выводимости данного предложения эффективно разрешим. Это связано с тем, что всякую формулу в языке элементарной геометрии можно в силу осуществленной координатизации воспринимать (или перевести) в языке линейной алгебры, основывающейся на полной и разрешимой теории вещественно-замкнутых полей.

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



Заключение

Насколько универсален и насколько всемогущ аксиоматический метод и его наивысшее математическое выражение - формализация? Прежде всего, границы методу формализации были поставлены двумя выдающимися теоремами К. Гёделя, доказанными им в 1931 г. Первая из них утверждает, что для всякой непротиворечивой формальной системы, содержащей аксиомы формальной арифметики, можно дать явное описание замкнутой формулы F, такой, что ни сама эта формула, ни ее отрицание -F не выводимы в этой формальной системе.

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

Эти теоремы Гёделя фактически означали, что истинное утверждение не всегда может быть доказано. Эти логические теоремы по существу разрушали восходящее к Лейбницу и Декарту мнение, будто всякое истинное утверждение подвластно обоснованию методами математического доказательства. Но оставалась надежда, что выводимость ненамного меньше истинности, что недоказуемыми являются лишь экзотические формулы гёделевского типа, в которых зашифрованы утверждения, относящиеся к самим этим формулам. Однако результаты, полученные А.Тарским в 1936 г., окончательно разрушили и эту последнюю надежду (см. более подробно об этом в Заключении).

Конечно, эти результаты, показывающие, что расстояние от доказуемости (выводимости) до истинности столь велико, могут служить солидным основанием для значительной доли пессимизма в оценке роли логики (и в частности, математической логики) в процессе познания окружающего мира и истины.

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

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

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

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



Список литературы

1. Аляев, Ю.А. Дискретная математика и математическая логика: учеб. для вузов / Ю.А. Аляев, С.Ф. Тюрин. - М.: Финансы и статистика, 2016. - 368 с.

2. Ерусалимский Я.М. Дискретная математика: теория, задачи, приложения. - М.: Вузовская книга, 2020. - 280 с.

3. Ершов, Ю.Л. Математическая логика: учеб. пособие для вузов / Ю.Л. Ершов, Е.А. Палютин. - СПб.: Лань, 2015. - 336 с.

4. Игошин В.И. Математическая логика и теория алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Академия», 2018. - 448 с.

5. Игошин В.И. Задачи и упражнения по математической логике и теории алгоритмов: учеб. пособие для студ. высш. учеб. заведений / В.И. Игошин. - М.: Издательский центр «Акадения», 2017. - 307 с.

6. Клини, С.К. Математическая логика: пер. с англ. / С.К. Клини; под ред. Г.Е. Минца. - М.: УРСС, 2015. - 480 с.

7. Колмогоров А.Н., Драгалин А.Г. Математическая логика. - М.: КомКнига, 2016. - 240 с.

8. Куртова, Л.Н. Основы математической логики: Учебное пособие / Л.Н. Куртова.- Белгород: Изд-во НИУ «БелГУ», 2018. с. 85.

9. Назиев А.Х. Математическая логика: задачник-практикум / А.Х. Назиев, С.А. Моисеев. -Рязань: Ряз. Гос. Ун-т им. С.А. Есенина, 2011. - 80 с.

10. Лихтарников Л.М., Сукачева Т.Г. Математическая логика. курс лекций. Задачник-практикум и решения. - СПб.: Издательство «Лань», 1999. - 288 с.

11. Математическая логика: учебно-методический комплекс (для студентовзаочников, обучающихся по специальности 050202 «Информатика»). - ГорноАлтайск.: РИО ГАГУ, 2010. - 87 с.

12. Лавров И.А. Математическая логика: учеб. пособие для студ. высш. учеб. заведений. - М.: Издательский центр «Академия», 2016. - 240 с.

13. Лавров, И.А. Задачи по теории множеств, математической логике и теории алгоритмов / И.А. Лавров, Л.Л. Максимова. - М.: Физматлит, 2014. - 256 с.

14. Лихтарников, Л.М. Математическая логика: курс лекций, задачник практикум и решения: учеб. пособие / Л.М. Лихтарников, Т.Г. Сукачева. - СПб.: Лань, 2018. - 288 с.

15. Мендельсон, Э. Введение в математическую логику: пер. с англ. / Э. Мендельсон. - М.: Наука, 1984. - 320 с.

16. Новиков, П.С. Элементы математической логики. М.: Наука, 1973. 400 с.

17. Романович, В.А. Лекции по математической логике. - Т.: Издательство ТГУ, 2015. - 408 с. 85

18. Глухов М.М., Шишков А.Б. Математическая логика. Дискретные функции. Теория алгоритмов. - М.: Изд-во «Лань», 2012. - 416 с.

19. Скорубский, В.И. Математическая логика: учебник и практикум для академического бакалавриата / В.И. Скорубский, В.И. Поляков, А.Г. Зыков. - М.: Издательство Юрайт, 2018. - 211 с.

20. Шапорев С.Д. Математическая логика. Курс лекций и практических занятий. - СПб.: БХВ-Петербург, 2015. - 416 с.

Размещено на allbest.ru

...