Обратная математика. Доказательства, вывернутые наизнанку (3000,00 руб.)

Стр.5

Стр.7

Стр.8

Стр.9

Стр.10

УДК 517.9 ББК 22.161.166 С80 С80 Джон Стилуэлл Обратная математика. Доказательства, вывернутые наизнанку / пер. с англ. А. А. Слинкина. – М.: ДМК Пресс, 2021. – 198 с.: ил. ISBN 978-5-97060-888-3 Эта книга – первое изложение обратной математики для аудитории, состоя щей из математиков общего профиля. Обратная математика – новая дисциплина, которая «выворачивает наизнанку» традиционную математическую логику: ее цель – не вывод теорем, а поиск аксиом, которые позволяют доказать известные теоремы. Джон Стилуэлл рассказывает о том, как найти «правильные» аксиомы для доказательства фундаментальных теорем. Придерживаясь исторического взгляда на обратную математику, он описывает два ставших возможными благодаря ей направления развития. Первое – проект арифметизации анализа, предпринятый в XIX веке с целью определить все понятия анализа в терминах натуральных чисел и их множеств. Второе – выполненная в XX веке арифметизация математической логики и понятия вычисления. Таким образом, арифметика в некотором смысле лежит в основе анализа, логики и вычислений. Обратная математика опирается на эту идею, рассматривая анализ как арифметику, дополненную аксиомами существования бесконечных множеств. Книга будет интересна как студентам старших курсов, так и специалистам, интересующимся основаниями математики. УДК 517.9 ББК 22.161.166 Original English language edition published by by Princeton University Press. Copyright © 2018 by John Stillwell. All rights reserved. Russian­language edition copyright © 2021 by DMK Press. All rights reserved. Все права защищены. Любая часть этой книги не может быть воспроизведена в какой бы то ни было форме и какими бы то ни было средствами без письменного разрешения владельцев авторских прав. Материал, изложенный в данной книге, многократно проверен. Но, поскольку вероятность технических ошибок все равно существует, издательство не может гарантировать абсолютную точность и правильность приводимых сведений. В связи с этим издательство не несет ответственности за возможные ошибки, связанные с использованием книги. ISBN 978­0­691­19641­1 (англ.) ISBN 978­5­97060­888­3 (рус.) © John Stillwell, 2018 © Оформление, перевод на русский язык, издание, ДМК Пресс, 2021

Стр.5

Оглавление Предисловие ............................................................................................ 10 Глава 1. Историческое введение ............................................................ 13 1.1. Евклид и аксиома параллельных .........................................................14 Аксиома параллельных ....................................................................................15 Эквиваленты аксиомы параллельных ............................................................16 1.2. Сферическая и неевклидова геометрия ..............................................17 Модели неевклидовой геометрии ...................................................................20 Новые основания геометрии и математики ..................................................22 1.3. Векторная геометрия ............................................................................22 Линейная геометрия Грассмана ......................................................................23 Превращение векторного пространства в неевклидово ...............................25 1.4. Аксиомы Гильберта ...............................................................................26 Алгебраическое содержание аксиом Гильберта.............................................29 1.5. Полная упорядоченность и аксиома выбора ......................................31 Несчетность ......................................................................................................32 Полная упорядоченность .................................................................................33 Теорема о полном упорядочении и аксиомы Цермело .................................34 Математический эквивалент аксиомы выбора .............................................35 1.6. Логика и вычислимость ........................................................................35 Арифметизация ................................................................................................37 Глава 2. Классическая арифметизация ................................................. 38 2.1. От натуральных чисел к рациональным .............................................39 Целые числа ......................................................................................................39 Рациональные числа ........................................................................................40 Алгебраические свойства ................................................................................41 2.2. От рациональных чисел к вещественным ...........................................41 Комплексные числа ..........................................................................................43 2.3. Свойства полноты ℝ .............................................................................44 Последовательности вложенных отрезков .....................................................45 Критерий сходимости Коши ............................................................................46

Стр.7

Оглавление 7 2.4. Функции и множества .................................................................................. 47 Функции пересчета пар ...................................................................................47 Кодирование последовательностей и некоторых других функций ..............49 2.5. Непрерывные функции ................................................................................ 49 Кодирование непрерывных функций рациональными интервалами .........50 2.6. Аксиомы Пеано .............................................................................................. 52 Аксиомы следования .......................................................................................52 Аксиомы суммы и произведения....................................................................52 Индукция ..........................................................................................................53 Примеры доказательств по индукции ............................................................54 2.7. Язык PA ............................................................................................................. 55 Упрощение связок ............................................................................................57 Предваренная форма .......................................................................................57 2.8. Арифметически определимые множества .............................................. 57 ∑0 1­свойства........................................................................................................58 2.9. Пределы арифметизации ............................................................................ 60 Диагональный метод Кантора ........................................................................61 Определимость и вычислимость .....................................................................61 Глава 3. Классический анализ ................................................................ 63 3.1. Пределы ........................................................................................................... 63 Пределы последовательностей .......................................................................63 Пределы функций ............................................................................................64 Предельные точки множества .........................................................................65 3.2. Алгебраические свойства пределов .......................................................... 65 3.3. Непрерывность и промежуточные значения ......................................... 67 Основная теорема алгебры ..............................................................................68 3.4. Теорема Больцано–Вейерштрасса ............................................................. 69 3.5. Лемма Гейне–Бореля .................................................................................... 70 3.6. Теорема о достижении экстремальных значений ................................. 72 3.7. Равномерная непрерывность ..................................................................... 73 Интегрируемость по Риману ...........................................................................75 3.8. Канторово множество .................................................................................. 76 3.9. Деревья в анализе .......................................................................................... 77 Арифметизация деревьев ................................................................................79 Глава 4. Вычислимость ........................................................................... 81 4.1. Вычислимость и тезис Чёрча ...................................................................... 82 4.2. Проблема остановки ..................................................................................... 84 4.3. Эффективно перечислимые множества................................................... 85 4.4. Вычислимые последовательности в анализе ......................................... 88

Стр.8

8 Оглавление 4.5. Вычислимое дерево, не имеющее вычислимых путей ........................ 90 4.6. Вычислимость и неполнота ........................................................................ 92 4.7. Вычислимость и анализ................................................................................ 93 Конструктивные подходы к анализу ...............................................................94 Глава 5. Арифметизация вычисления ................................................... 97 5.1. Формальные системы ................................................................................... 98 5.2. Элементарные формальные системы Смаллиана ................................. 99 Примеры систем аксиом ................................................................................100 5.3. Нотация для положительных целых чисел............................................101 Универсальные элементарные формальные системы ................................102 5.4. Анализ вычисления, предпринятый Тьюрингом ................................103 От машин Тьюринга к элементарным формальным системам ..................104 5.5. Операции над ЭФС­порожденными множествами ............................105 5.6. Порождение ∑0 5.7. ЭФС для ∑0 1­множеств .........................................................................107 1­отношений ..............................................................................110 Булевы комбинации равенств .......................................................................110 Ограниченные кванторы ...............................................................................111 5.8. Арифметизация элементарных формальных систем ........................112 Слова и числа ..................................................................................................112 Конечные последовательности .....................................................................113 ЭФС­порожденные множества – то же, что ∑0 1 .............................................115 5.9. Арифметизация эффективного перечисления ....................................115 Арифметизация рекурсии .............................................................................115 Эффективное перечисление ..........................................................................116 5.10. Арифметизация вычислимого анализа ...........................................118 Пример доказательства в RCA0 ......................................................................119 Минимальная модель RCA0 ............................................................................120 Глава 6. Арифметическое выделение .................................................. 121 6.1. Система аксиом ACA0 ..................................................................................122 Минимальная модель ACA0 ............................................................................122 6.2. ∑0 ∑0 1­выделение и арифметическое выделение .......................................123 1 ..............................................125 ­выделение и область значений функций ................................................124 Индукция и системы более слабые, чем ACA0 6.3. Свойства полноты в ACA0 ..........................................................................125 6.4. Арифметизация деревьев ..........................................................................129 6.5. Лемма Кёнига о бесконечном пути .........................................................130 6.6. Теория Рамсея ..............................................................................................134 6.7. Некоторые результаты из математической логики ............................136

Стр.9

Оглавление 9 6.8. Арифметика Пеано в ACA0 .........................................................................140 Относительная непротиворечивость ACA0 ............................................................ 141 Глава 7. Рекурсивное выделение .......................................................... 143 7.1. Система аксиом RCA0 ..................................................................................144 7.2. Вещественные числа и непрерывные функции ...................................145 7.3. Теорема о промежуточном значении .....................................................147 7.4. И снова о канторовом множестве ............................................................149 7.5. От леммы Гейне–Бореля к слабой лемме Кёнига ................................150 7.6. От слабой леммы Кёнига к лемме Гейне–Бореля ................................153 7.7. Равномерная непрерывность ....................................................................155 7.8. От слабой леммы Кёнига к экстремальным значениям .....................157 7.9. Теоремы WKL0 ...............................................................................................160 Другие топологические теоремы ..................................................................162 7.10. WKL0 «Большая пятерка» систем ............................................................................164 Теоремы Краскала и Робертсона–Сеймура ..................................................165 , ACA0 и далее .....................................................................................163 Глава 8. Более широкая картина .......................................................... 168 8.1. Конструктивная математика ....................................................................169 8.2. Логика предикатов ......................................................................................170 8.3. Виды неполноты ..........................................................................................173 8.4. Вычислимость ..............................................................................................176 Степени неразрешимости .............................................................................176 И арифметически определимые множества ................................................177 Низкие степени ..............................................................................................177 8.5. Теория множеств .........................................................................................178 АВ в элементарном анализе ..........................................................................179 8.6. Понятия «глубины» .....................................................................................180 Список литературы ............................................................................... 182 Предметный указатель ......................................................................... 189

Стр.10