Колмогоров А.Н.✫★★Ак, Драгалин А.Г. Математическая логика:
Дополнительные главы. Изд. стереотип.

Оглавление

Предисловие к серии

Уважаемый читатель!

Вы открыли одну из замечательных книг, изданных в серии "Классический университетский учебник", посвященной 250-летию Московского университета. Серия включает свыше 150 учебников и учебных пособий, рекомендованных к изданию учеными советами факультетов, редакционным советом серии и издаваемых к юбилею по решению Ученого совета МГУ.

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

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

Издание серии "Классический университетский учебник" наглядно демонстрирует тот вклад, который вносит Московский университет в классическое университетское образование в нашей стране и, несомненно, служит его развитию.

Решение этой благородной задачи было бы невозможным без активной помощи со стороны издательств, принявших участие в издании книг серии "Классический университетский учебник". Мы расцениваем это как поддержку ими позиции, которую занимает Московский университет в вопросах науки и образования. Это служит также свидетельством того, что 250-летний юбилей Московского университета – выдающееся событие в жизни всей нашей страны, мирового образовательного сообщества.

Предисловие

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

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

[...]

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

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

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

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

Об авторах

Выдающийся советский математик, академик АН СССР. Родился в 1903 году в Тамбове. В 1925 году окончил Московский университет, профессором которого работал с 1931 года. Заведовал различными кафедрами, был деканом механико-математического факультета МГУ. Автор классических работ по теории функций действительного переменного, теории множеств, топологии, конструктивной логике, функциональному анализу, механике, теории алгоритмов, теории информации. Основополагающее значение имеют результаты А.Н.Колмогорова в области теории вероятности. Широко известна его деятельность по разработке методики и организации математического образования. А.Н.Колмогоров был председателем Московского математического общества, почетным доктором зарубежных университетов, иностранным членом многих академий и научных обществ, лауреатом международных премий и кавалером правительственных наград. Умер в Москве в 1987 году.

Альберт Григорьевич Драгалин (1941–1998)

Видный представитель российской школы математического конструктивизма. Родился 10 апреля 1941 года на острове Моржевец Архангельской области. Окончил механико-математический факультет МГУ, где работал с 1966 года. С 1983 года жил в Венгрии, заведовал кафедрой вычислительной математики университета им.Л.Кошута (г.Дебрецен). В 1988 году Венгерской Академией наук ему была присвоена степень доктора наук. Автор фундаментальных трудов по теоретико-модельным и теоретико-доказательственным основаниям интуиционистской логики, конструктивным методам нестандартного анализа. Умер 18 декабря 1998 года в г.Дебрецене.