Нарезка правды
Нарезка истины: теория вычислимости и обратный математический анализ комбинаторных принципов — это книга по обратной математике в комбинаторике , изучению аксиом , необходимых для доказательства комбинаторных теорем. Он был написан Денисом Р. Хиршфельдтом на основе курса, прочитанного Хиршфельдтом в Национальном университете Сингапура в 2010 году. [1] и опубликовано в 2014 году издательством World Scientific в 28-м томе серии лекций Института математических наук Национального университета Сингапура.
Темы
[ редактировать ]Книга начинается с пяти глав, в которых обсуждается область обратной математики , целью которой является классификация математических теорем по схемам аксиом, необходимым для их доказательства, а также пять больших подсистем арифметики второго порядка , на которые были классифицированы многие математические теоремы. . [2] [3] В этих главах также рассматриваются некоторые инструменты, необходимые в этом исследовании, включая теорию вычислимости , форсирование и теорему о низкой базисе . [4]
Глава шестая, «настоящее сердце книги», [2] применяет этот метод к бесконечной форме теоремы Рамсея : каждая раскраска ребер счетно бесконечного полного графа или полного однородного гиперграфа , использующая конечное число цветов, содержит монохроматический бесконечный индуцированный подграф . Стандартное доказательство этой теоремы использует аксиому арифметического понимания , попадающую в одну из больших пяти подсистем, ACA 0 . Однако, как первоначально доказал Дэвид Ситапун , версия теоремы для графов слабее, чем ACA 0 , и оказывается неэквивалентной ни одной из подсистем большой пятерки. Версия для однородных гиперграфов фиксированного порядка больше двух эквивалентна ACA 0 , а версия теоремы, сформулированная для всех чисел цветов и всех порядков гиперграфов одновременно, сильнее, чем ACA 0 . [2]
В седьмой главе обсуждаются консервативные расширения теорий, в которых утверждения мощной теории (например, одной из форм арифметики второго порядка), которые одновременно доказуемы в этой теории и выражаемы в более слабой теории (например, арифметике Пеано ), являются всего лишь те, которые уже доказуемы в более слабой теории. В восьмой главе в схематической форме суммированы полученные на данный момент результаты. В девятой главе обсуждаются способы ослабления теоремы Рамсея. [2] а в последней главе обсуждаются более сильные теоремы комбинаторики, включая теорему Душника-Миллера о самовложении бесконечных линейных порядков, теорему Краскала о дереве , теорему Лейвера о вложении счетных линейных порядков и теорему Хиндмана о множествах IP . [3] В приложении представлено доказательство теоремы Цзяи Лю, входящей в сборник результатов, показывающих, что теорема Рамсея о графе не попадает в большую пятерку подсистем. [1] [3] [4]
Аудитория и прием
[ редактировать ]Это техническая монография, требующая от читателей некоторого знакомства с теорией вычислимости и теорией Рамсея. Предварительные знания обратной математики не требуются. [2] Он написан в несколько неформальном стиле и включает множество упражнений, что позволяет использовать его в качестве учебника для выпускников или для начала работы по обратной математике; [3] [4] рецензент Франсуа Дорэ пишет, что это «отличное введение в обратную математику и теорию вычислимости комбинаторных принципов», а также тематическое исследование доступных методов доказательства результатов в обратной математике. [3]
Рецензент Уильям Гасарч жалуется на две недостающие темы: работу Джо Милети по обратной математике канонических версий теоремы Рэмси и работу Джеймса Шмерла по обратной математике раскраски графов . Тем не менее он рекомендует эту книгу всем, кто интересуется обратной математикой и теорией Рамсея. [2] А рецензент Бенедикт Исто называет это «долгожданным дополнением... обеспечивающим свежий и доступный взгляд на центральный аспект современных обратных математических исследований». [4]
Связанное чтение
[ редактировать ]«Классическим справочником» по обратной математике является книга «Подсистемы арифметики второго порядка» (2009) Стивена Симпсона ; [4] он сосредоточен вокруг большой пятерки подсистем и содержит гораздо больше примеров результатов, эквивалентных по силе одной из этих пяти. [2] Дорэ предлагает использовать обе книги вместе как сопутствующие тома. [3]
Рецензент Джеффри Херст предлагает «Теорию вычислимости» Ребекки Вебер как хороший источник информации, необходимой для чтения этой книги. [1]
Ссылки
[ редактировать ]- ^ Jump up to: Перейти обратно: а б с Херст, Джеффри Л. (сентябрь 2015 г.), «Обзор нарезки истины », Бюллетень символической логики , 21 (3): 338–339, doi : 10.1017/bsl.2015.18 , S2CID 61188908 ; Херста см. также более короткий обзор zbMATH , Збл 1304.03001
- ^ Jump up to: Перейти обратно: а б с д и ж г Гасарч, Уильям (март 2016 г.), «Обзор нарезки истины » (PDF) , ACM SIGACT News , 47 (1): 21–24, doi : 10.1145/2902945.2902952 , S2CID 19457072
- ^ Jump up to: Перейти обратно: а б с д и ж Дорэ, Франсуа Г., «Обзор нарезки истины », Mathematical Reviews , MR 3244278
- ^ Jump up to: Перейти обратно: а б с д и Исто, Бенедикт (июль 2017 г.), «Обзор нарезки истины » , Studia Logica , 105 (4): 873–879, doi : 10.1007/s11225-017-9740-1 , hdl : 1983/1ed76e2d-9bc7-4529- б628-92791f631317 , S2CID 1667765
Внешние ссылки
[ редактировать ]- Нарезая правду , веб-сайт Хиршфельдта, включая препринтную версию книги.