Нарезка правды - Slicing the Truth

Срез истины: Теория вычислимости и обратный математический анализ комбинаторных принципов это книга о обратная математика в комбинаторика, изучение аксиомы необходимо для доказательства комбинаторных теорем. Он был написан Денисом Р. Хиршфельдтом на основе курса, прочитанного Хиршфельдтом в Национальном университете Сингапура в 2010 году.[1] и опубликовано в 2014 г. Всемирный научный, как том 28 серии конспектов лекций Института математических наук Национального университета Сингапура.

Темы

Книга начинается с пяти глав, в которых обсуждается обратная математика, целью которого является классификация математических теорем по схемам аксиом, необходимым для их доказательства, большая пятерка подсистем из арифметика второго порядка в который были классифицированы многие теоремы математики.[2][3] В этих главах также рассматриваются некоторые инструменты, необходимые для данного исследования, в том числе теория вычислимости, принуждение, а теорема о низком базисе.[4]

Глава шестая, «Настоящее сердце книги»,[2] применяет этот метод к бесконечный форма Теорема Рамсея: каждый окраска края счетно бесконечного полного графа или полной равномерной гиперграф, использующий конечное число цветов, содержит монохроматическую бесконечную индуцированный подграф. Стандартное доказательство этой теоремы использует аксиома арифметического понимания, попадая в одну из большой пятерки подсистем, ACA0. Однако, как Дэвид Ситапун первоначально доказанная версия теоремы для графов слабее, чем ACA0, и оказывается, что он не эквивалентен какой-либо из подсистем большой пятерки. Версия для равномерных гиперграфов фиксированного порядка больше двух эквивалентна ACA0, а версия теоремы, сформулированная для всех чисел цветов и всех порядков гиперграфов одновременно, сильнее, чем ACA0.[2]

В седьмой главе обсуждаются консервативные расширения теорий, в которых утверждения сильной теории (например, одной из форм арифметики второго порядка), которые одновременно доказуемы в этой теории и выразимы в более слабой теории (например, Арифметика Пеано ) - это только те, которые уже доказуемы в более слабой теории. В восьмой главе представлены результаты в схематической форме. В девятой главе обсуждаются способы ослабить теорему Рамсея.[2] а в последней главе обсуждаются более сильные теоремы комбинаторики, включая Теорема Душника – Миллера о самовложении бесконечных линейных порядков, Теорема Крускала о дереве, Теорема Лавера на заказать встраивание счетного линейные порядки, и теорема Хиндмана о Наборы IP.[3] В приложении содержится доказательство теоремы Цзяи Лю, часть набора результатов, показывающих, что теорема Рамсея о графах не относится к большой пятерке подсистем.[1][3][4]

Аудитория и прием

Это техническая монография, требующая от читателей некоторого знакомства с теорией вычислимости и теорией Рамсея. Предварительные знания обратной математики не требуются.[2] Он написан в несколько неформальном стиле и включает в себя множество упражнений, что позволяет использовать его в качестве учебника для выпускников или для начала работы по обратной математике;[3][4] рецензент Франсуа Дорайс пишет, что это «отличное введение в обратную математику и теорию вычислимости комбинаторных принципов», а также практический пример методов, доступных для доказательства результатов в обратной математике.[3]

Рецензент Уильям Гасарх жалуется на две недостающие темы: работу Джо Милети по обратной математике канонических версий теоремы Рамсея и работу Джеймса Шмерла по обратной математике раскраска графика. Тем не менее он рекомендует эту книгу всем, кто интересуется обратной математикой и теорией Рамсея.[2] И рецензент Бенедикт Истхау называет это «долгожданным дополнением ... дающим свежий и доступный взгляд на центральный аспект современных обратных математических исследований».[4]

Связанное чтение

«Классическим справочником» по обратной математике является книга Подсистемы арифметики второго порядка (2009) Стивен Симпсон;[4] он сосредоточен вокруг большой пятерки подсистем и содержит гораздо больше примеров результатов, эквивалентных по силе одной из этих пяти.[2] Дорайс предлагает использовать две книги вместе в качестве дополнительных томов.[3]

Рецензент Джеффри Херст предлагает Теория вычислимости Ребекки Вебер как хороший источник информации, необходимой для чтения этой книги.[1]

Рекомендации

  1. ^ а б c Херст, Джеффри Л. (сентябрь 2015 г.), "Обзор Нарезка правды", Бюллетень символической логики, 21 (3): 338–339, Дои:10.1017 / bsl.2015.18; см. также более короткий обзор Херста zbMATH, Zbl  1304.03001
  2. ^ а б c d е ж грамм Гасарх, Уильям (Март 2016 г.), "Обзор Нарезка правды" (PDF), Новости ACM SIGACT, 47 (1): 21–24, Дои:10.1145/2902945.2902952
  3. ^ а б c d е ж Дораэ, Франсуа Г., "Обзор Нарезка правды", Математические обзоры, МИСТЕР  3244278
  4. ^ а б c d е Исто, Бенедикт (июль 2017 г.), "Обзор Нарезка правды", Studia Logica, 105 (4): 873–879, Дои:10.1007 / s11225-017-9740-1

внешняя ссылка