1611678200-36438fb4f1ee6f855c93dc4a315ea8eb (826633), страница 2
Текст из файла (страница 2)
И. Каргаполова, Н. В. Белякина,И. А. Лаврова, Л. Л. Максимовой и многих других. Этим коллегам итоварищам мы выражаем свою искреннюю признательность и благодарность.При работе над данной книгой были использованы записи курсовлекций А. И. Мальцева и Ю. Л.
Ершова, книги: Ершов Ю. Л., Палютин Е.А., Тайцлин М.А. Математическая логика.Изд-во НГУ,жеств.-1973;М.: Мир,Новосибирск:-Куратовский К., Мостовский А.1970;Теория мноМальцев А. И. Алгебраические системы.Изд-во АНСССР,М.: Наука,1975,1970; Марков А. А. Теория алгорифмов. - М.:1954; Шенфилд Дж.
Математическая логика. --М.: Наука,а также другие монографии и научные статьи.НовосибирскАкадемгородокЮ.Л. ЕршовЕ. А. Палютин1)Последнее издание - М.: ФИЗМАТЛИТ, 2009. (Прим. ред.)ВведениеМатематическая логика как самостоятельный раздел современнойматематики сформировалась сравнительно недавновятнадцатого-на рубеже дедвадцатого веков. Возникновение и быстрое развитие-математической логики в начале двадцатого века было связано с такназываемым кризисом в основаниях математики.
Поговорим об этомчуть подробнее.При любой попытке систематического изложения математики (как,впрочем, и любой другой науки) возникает проблема выбора начальных(исходных) понятий и принципов, которые будут положены в основувсего изложения. Проблема выбора и обоснование этого выбора исходных данных лежит, как правило, вне самой научной дисциплиныи относится к философии и методологии научного познания. Систематизация математики в конце девятнадцатого века выявила, что весьмаперспективнымявляетсяиспользованиепонятиямножествавкачестве единственного исходного понятия для всей математики.
РаботамиБ. Больцано, Р. Дедекинда и Г. Кантора была создана новая областьматематики-теория множеств, которая красотой и силой своих построений и перспективами использования ее в основаниях математикипривлекла внимание многих ведущих математиков того времени. Былапроделана большая работа по теоретико-множественному осмыслениюматематических и даже логических понятий.
В этой связи большойинтерес представляют исследования Г. Фреге и Б. Рассела. Однако высокая степень абстрактности и <<универсальносты понятия множестване могли не привести в конце концов к трудностям, хорошо и давно известным в философии при работе с <<универсалиями>>. Проявилось этов появлении так называемых теоретико-множественных парадоксов.Приведем один из наиболее типичных теоретико-множественныхпарадоксов-парадокс Рассела. Для произвольного множества является вполне осмысленным вопрос, <<будет ли это множество своимэлементом,>.
Примером множества, которое содержит само себя в качестве элемента, могло бы служить, например, множество всех множеств.Рассмотрим множество Мо всех множеств, для которых ответ на этотвопрос отрицателен. Спросим теперь, является ли это множество своимэлементом? К своему (наивному) удивлению обнаружим, что если ответположительный, то имеем Мо ,/с Мо, т. е. ответ должен быть отрицательным. Если же ответ отрицателен, то в силу определения множестваМо ответ должен быть положительным. Этот парадокс показывает,что если мыне хотимприходить к противоречиям, то необходимоотказаться от приятной мысли, что любое осмысленное условие наВведение9элементы определяет некоторое множество. К счастью, такого рода парадоксы можно получить лишь с <<большимю> или <<неестественными,>множествами, без которых в математике можно вполне обойтись 1).Появление таких парадоксов в теории множеств было воспринятомногими математиками очень болезненно и поэтому привлекло к вопросам оснований математики пристальное внимание практически всехведущих математиков того времени (назовем, к примеру, Д.
Гильберта,А. Пуанкаре, Г. Вейля). Было предложено несколько программ <<спасения,>математикиот<<ужаса»парадоксов,входитьвдеталикоторыхмы не будем. Укажем вкратце только две наиболее действенные программы, различные модификации которых обсуждаются и в настоящеевремя. Отметим, что многообразие подходов к основаниям математикиостается и поныне. Однако прошедшие годы и безусловные достиженияматематической логики, речь о которых еще впереди, сняли остротуэтой проблемы настолько, что большинство математиков, работающихв других разделах математики, не уделяют особого внимания тем дискуссиям, которые ведут ныне специалисты по основаниям математики.Одной из наиболее разработанных программ по основаниям математики является предложенная Д.
Гильбертом программа финитарногообоснования математики.Суть этой программысостоит в попыткепостроения такой формализации математики, что средствами этой системы можно доказать свою собственную непротиворечивость. Другимпринципиальным требованием к такой формализации является условие, чтобы все простейшие, проверяемые непосредственно утвержденияо натуральных числах были истинными в этой формализации. Работанад этой программой как самого Гильберта, так и его учеников и последователей оказалась весьма плодотворной для математической логики,в частности, в разработке современного аксиоматического метода. Хотяпрограмма <<финитизма» в своей исходной постановке оказалась невыполнимой, как показал в своих знаменитых работах К.
Гёдель, однаковозможные модификации этой программы подвергаются полезному обсуждению и до настоящего времени.Другой подход к основаниям математики был связан с критикойряда положений, которые использовались в математике без должногообоснования. Это относится, в частности, к неограниченному использованию закона исключенного третьего и аксиомы выбора.
Программапостроения математикиэтихпринциповприполучилажесткихназваниеограничениях наинтуиционизма;использованиееесозданиеиразвитие связано в первую очередь с именем Л. Э. Я. Брауэра. Развитый1)Упоминаемые ниже формализации теории множеств -теории множеств,-аксиоматическиесохраняя все полезное, не допускают прямого проведениявсех известных <<парадоксальных,> рассуждений.Введение10в Советском Союзе А.
А. Марковым и его последователями конструктивистский подход к основаниям математики также связан с критическимподходомкдопустимымстематическииспользуетлогическимпонятиесредствамалгоритмапривматематикеисиконструктивистскомвоспроизведении математических результатов.Хотя основания математики традиционно относятся к математической логике, в настоящем учебнике не место вдаваться в большиеподробности этого раздела, находящегося на стыке математики и философии. Поэтому ограничим обсуждение оснований математики приведеннымивышезамечаниями,служащимискорееиллюстративнымцелям.Основным итогом деятельности в области оснований математикиможно считать становление математической логики как самостоятельного раздела математики, а принципиальным достижением математической логики-разработку современного аксиоматического метода,который может быть охарактеризован следующими тремя чертами:1.Явная формулировка исходных положений (аксиом) той или инойтеории.2.Явная формулировка логических средств (правил вывода), которые допускаются для последовательного построения (развертывания) этой теории.3.Использование искусственно построенных формальных языковдля изложения всех положений (теорем) рассматриваемой теории.Первая черта характеризует классический аксиоматический метод.Две следующие являются дальнейшими шагами в достижении максимальной точности и ясности в изложении теорий.
Введение и использование подходящих обозначений было на протяжении всей историиматематики весьма важной и продуктивной процедурой. Но математические символы были только элементами формальных языков. В математической же логике впервые в истории были созданы такие богатыеформальные языки, которые позволяют формулировать практически всеосновные положения современной математики. Богатые формальныеязыки математической логики и успешный опыт работы с ними создали одну из объективных предпосылок для создания универсальныхвычислительных машин, пользующихся в настоящее время весьма раз)нообразным спектром формальных языков программирования.Основным объектом изучения в математической логике являютсяразличные исчисления. В понятие исчисления входят такие основные компоненты, как: а) язык (формальный) исчисления; б) аксиомыисчисления; в) правила вывода.
Понятие исчисления позволяет датьстрогоематематическое определениепонятиядоказательстваиполучить точные утверждения о невозможности доказательства тех илиВведение11иных предложений теории. Еще одним замечательным достижениемматематической логики является нахождение математического определения понятия алгоритма, т. е. эффективной процедуры для решениязадач из того или иного (бесконечного) класса задач. Интуитивно понятие алгоритма использовалось очень давно. Выдающийся мыслительXVII-XVIIIвв.
Г. Лейбниц даже мечтал о нахождении универсальногоалгоритма для решения всех математических проблем. Точное определение понятия алгоритма позволило довольно быстро разрушить этукрасивую утопию: А. Чёрч в1936г. показал, что невозможен алгоритм,который по произвольному утверждению, записанному на формальномязыке элементарной арифметики, отвечал бы на вопрос: будет ли этоутверждение истинно на натуральных числах? Далее оказалось, чтодаже в системе, описывающей «чистую логику,> (исчисление предикатов), проблема доказуемости алгоритмически неразрешима. В последующие годы было обнаружено большое многообразие алгоритмически неразрешимых проблем в многих разделах математики.
Большойвклад в разработку теории алгоритмов и решение алгоритмическихпроблем внесли Э. Пост, А. Тьюринг, С. Клини и советские математикиА. И. Мальцев, П. С. Новиков и А. А. Марков.Изучение исчислений составляет синтаксическую часть математической логики. Наиболее глубокое изучение (синтаксического) понятиядоказательства в тех или иных исчислениях составляет самостоятельный раздел математической логики, который носит название теориидоказательств. Наряду с синтаксическим изучением исчислений проводится также семантическое изучение формальных языков математической логики.Основнымпонятием семантики являетсяпонятиеистинности для выражений (формул, секвенций и т. п.) формальногоязыка.
Семантические понятия также получили точные математическиеопределения, что дало возможность систематического и строгого изучения различных понятий истинности. Классическая семантика языка исчисления предикатов составила весьма богатый раздел математическойлогики-теорию моделей, которая активно развивается, а ее методыи результаты успешно применяются и в других областях математики(алгебре, анализе). Основателями теории моделей являются А.
Тарскийи А. И. Мальцев.Исчисления позволяют формализовать многие разделы математикии других наук. Исчисление высказываний и упоминавшееся выше исчисление предикатов являются формализациями логики, древнейшейнауки о законах правильного мышления. Создание и изучение этихформализаций явилось важным этапом в развитии логики как науки.Первые попытки формализации логики связаны с именами Аристотеля и Дж. Буля, но действительная (и действенная) формализациялогики была осуществлена только с созданием математической логики.Введение12Итальянский математик Дж. Пеана м·ного сделал для разработки и популяризации формальных языков логики.Дляматематики особенно важнойоказаласьвозможность формализации теории множеств.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
