В математике , дерево Крускала теорема утверждает , что множество конечных деревьев над хорошо квазиупорядоченном набор меток сам хорошо квазиупорядоченное при гомеоморфном вложении. Теорема была предложена Эндрю Вазсони и доказана Джозефом Крускалом ( 1960 ); короткое доказательство было дано Криспином Нэш-Уильямсом ( 1963 ). С тех пор он стал ярким примером в обратной математике как утверждение, которое нельзя доказать в рамках ATR 0 (форма арифметической трансфинитной рекурсии), а конечное применение теоремы дает существование печально известной быстрорастущей функции ДЕРЕВО .
В 2004 году результат был обобщен с деревьев на графы как теорема Робертсона – Сеймура , результат, который также оказался важным в обратной математике и привел к еще более быстрорастущей функции SSCG .
Заявление
Приведем версию, доказанную Нэшем-Вильямсом; Формулировка Крускала несколько сильнее. Все деревья, которые мы рассматриваем, конечны.
Для данного дерева T с корнем и заданных вершин v , w назовем w преемником v, если уникальный путь от корня до w содержит v , и назовем w непосредственным преемником v, если дополнительно путь от v до w содержит другой вершины нет.
Возьмем X, чтобы быть частично упорядоченным множеством . Если T 1 , T 2 - корневые деревья с вершинами, помеченными в X , мы говорим, что T 1 inf-вложимо в T 2, и пишем T 1 ≤ T 2, если существует инъективное отображение F из вершин T 1 в вершины из T 2 такая, что
- Для всех вершин v из T 1 метка v предшествует метке F ( v ) ,
- Если w является любым преемником v в T 1 , то F ( w ) является преемником F ( v ) и
- Если w 1 , w 2 - любые два различных непосредственных последователя v , то путь от F ( w 1 ) к F ( w 2 ) в T 2 содержит F ( v ) .
Теорема Крускала о дереве утверждает:
Если Х является хорошо квазиупорядоченное , то множество корневых деревьев с метками в X хорошо квазиупорядоченное под ИНФ-встраиваемый порядке , определенном выше. (То есть для любой бесконечной последовательности T 1 , T 2 ,… корневых деревьев, помеченных в X , существует некоторое i < j, так что T i ≤ T j .)
Слабая функция дерева
Определите tree ( n ) , функцию слабого дерева, как длину самой длинной последовательности деревьев, помеченных 1 (т. Е. X = {1} ), такую, что:
- Дерево в позиции k в последовательности имеет не более k + n вершин для всех k .
- Никакое дерево не может быть гомеоморфно вложено ни в какое дерево, следующее за ним в последовательности.
Известно, что tree (1) = 1, tree (2) = 5 и tree (3) ≥ 844424930131960, [1] но TREE (3) (см. Ниже ) больше, чем
Работа Фридмана
Для набора счетных этикеток , Теорема Крускала о дереве может быть выражена и доказана с помощью арифметики второго порядка . Однако, подобно теореме Гудстейна или теореме Пэрис – Харрингтона , некоторые частные случаи и варианты теоремы могут быть выражены в подсистемах арифметики второго порядка, намного более слабых, чем подсистемы, в которых они могут быть доказаны. Впервые это заметил Харви Фридман в начале 1980-х годов, став первым успехом зарождающейся тогда области обратной математики. В случае, когда деревья выше считаются немаркированными (то есть в случае, когдаимеет порядок один), Фридман обнаружил, что результат недоказуем в ATR 0 , [2], таким образом дав первый пример предикативного результата с доказуемо импредикативным доказательством. [3] Этот случай теоремы все еще доказуем в Π1
1-CA 0 , но, добавив «условие разрыва» [4] к определению порядка на деревьях выше, он нашел естественный вариант теоремы, недоказуемой в этой системе. [5] [6] Намного позже теорема Робертсона-Сеймура дала бы другую теорему, недоказуемую внутри Π1
1-CA 0 .
Порядковый анализ подтверждает силу теоремы Крускала, при этом теоретико-доказательственный ординал теоремы равен малому ординалу Веблена (иногда путают с меньшим ординалом Аккермана ).
ДЕРЕВО (3)
Предположим, что P ( n ) - это утверждение:
- Существует некоторое m такое, что если T 1 , ..., T m - конечная последовательность немаркированных корневых деревьев, где T k имеет n + k вершин, то T i ≤ T j для некоторого i < j .
Все утверждения P ( n ) верны как следствие теоремы Крускала и леммы Кёнига . Для каждого п , арифметика Пеано можно доказать , что P ( п ) верно, но арифметика Пеано не может доказать утверждение « Р ( п ) верно для всех п ». [7] Более того, длина кратчайшего доказательства P ( n ) в арифметике Пеано растет феноменально быстро как функция от n , намного быстрее, чем любая примитивно рекурсивная функция или, например, функция Аккермана . Наименьшее m, для которого выполняется P ( n ), очень быстро растет с увеличением n .
Включив ярлыки, Фридман определил гораздо более быстрорастущую функцию. [8] Для положительного целого числа n возьмем TREE ( n ) [*] как наибольшее m, чтобы мы получили следующее:
- Существует последовательность T 1 , ..., T m корневых деревьев, помеченная из набора из n меток, где каждое T i имеет не более i вершин, такая что T i ≤ T j не выполняется ни для какого i < j ≤ м .
Последовательность ДЕРЕВО начинается с ДЕРЕВО (1) = 1, ДЕРЕВО (2) = 3, затем внезапно ДЕРЕВО (3) взрывается до значения настолько огромного, что многие другие «большие» комбинаторные константы, такие как n (4) Фридмана , [* *] чрезвычайно малы по сравнению. Фактически, это намного больше, чем n n (5) (5). Нижняя оценка для n (4) и, следовательно, чрезвычайно слабая нижняя оценка для TREE (3), равна A A (187196) (1), [9], где A () - версия функции Аккермана :. Например, число Грэма приблизительно равно A 64 (4), что намного меньше нижней границы A A (187196) (1). Можно показать, что скорость роста функции ДЕРЕВО не менеев быстрорастущей иерархии . A A (187196) (1) приблизительно, где g x - функция Грэма .
Смотрите также
Заметки
- ^ * Фридман первоначально обозначал эту функцию как TR[ n].
- ^ ** n(k) определяется как длина самой длинной возможной последовательности, которая может быть построена с помощью k-буквенного алфавита, так что никакой блок букв x i, ..., x 2i неявляется подпоследовательностью любого последующего блока x j, ..., x 2j. [10].
Рекомендации
- Цитаты
- ^ "Последовательность ДЕРЕВА" . Googology Wiki | Фэндом . Дата обращения 9 июля 2020 .[ нужен лучший источник ]
- ^ Симпсон 1985, теорема 1.8
- Перейти ↑ Friedman 2002, p. 60
- ^ Симпсон 1985, определение 4.1
- ^ Симпсон 1985, теорема 5.14
- ^ Marcone 2001, стр. 8–9
- ^ Смит 1985, стр. 120
- ^ Фридман, Харви (28 марта 2006 г.). «273: Sigma01 / оптимальный / размер» . Математический факультет Университета штата Огайо . Проверено 8 августа 2017 года .
- ^ Фридман, Харви М. (1 июня 2000 г.). «Огромные целые числа в реальной жизни» (PDF) . Государственный университет Огайо . Проверено 8 августа 2017 года .
- ^ Фридман, Харви М. (8 октября 1998 г.). «Длинные конечные последовательности» (PDF) . Математический факультет Университета штата Огайо . С. 5, 48 (Thm.6.8) . Проверено 8 августа 2017 года .
- Библиография
- Фридман, Харви М. (2002), Внутренние конечные вложения деревьев. Размышления об основах математики (Стэнфорд, Калифорния, 1998) , Lect. Протокол заметок, 15 , Урбана, Иллинойс: доц. Символ. Логика, стр. 60–91, MR 1943303
- Gallier, Jean H. (1991), "Что такого особенного в теореме Крускала и ординале Γ 0 ? Обзор некоторых результатов в теории доказательств" (PDF) , Ann. Pure Appl. Логика , 53 (3): 199-260, DOI : 10.1016 / 0168-0072 (91) 90022-Е , МР 1129778
- Крускал, Дж. Б. (май 1960 г.), «Хорошо-квазиупорядочение, теорема о дереве и гипотеза Вазсони» (PDF) , Труды Американского математического общества , Американское математическое общество, 95 (2): 210–225, DOI : 10.2307 / 1993287 , JSTOR 1993287 , MR 0111704
- Марконе, Альберто (2001). «Теория WQO и BQO в подсистемах арифметики второго порядка» (PDF) . Обратная математика . 21 : 303–330.
- Нэш-Уильямс, К. Сент-Джей (1963), "О хорошо квазиупорядоченных конечных деревьях", Proc. Camb. Фил. Soc. , 59 (4): 833-835, DOI : 10,1017 / S0305004100003844 , МР 0153601
- Ратиен, Майкл; Вейерманн, Андреас (1993). "Теоретико-доказательные исследования теоремы Крускала". Летопись чистой и прикладной логики . 60 (1): 49–88. DOI : 10.1016 / 0168-0072 (93) 90192-г .
- Симпсон, Стивен Г. (1985), "Недоказуемость некоторых комбинаторных свойств конечных деревьев", Харрингтон, Лос-Анджелес; Morley, M .; Щедров, А .; и другие. (ред.), Исследования Харви Фридмана по основам математики , Исследования по логике и основам математики, Северная Голландия, стр. 87–117
- Смит, Рик Л. (1985), «Сила совместимости некоторых конечных форм теорем Хигмана и Крускала», в Харрингтоне, Луизиана; Morley, M .; Щедров, А .; и другие. (ред.), Исследования Харви Фридмана по основам математики , Исследования по логике и основам математики, Северная Голландия, стр. 119–136.