Теорема Краскала о дереве

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

История

Теорема была доказана выдвинута Эндрю Вассони и ; Джозефом Крускалом ( 1960 ) короткое доказательство было дано Криспином Нэш-Уильямсом ( 1963 ). С тех пор оно стало ярким примером в обратной математике как утверждение, которое невозможно доказать в ATR ₀ ( арифметическая теория второго порядка с формой арифметической трансфинитной рекурсии ).

В 2004 году результат был обобщен с деревьев на графы как теорема Робертсона-Сеймура , результат, который также оказался важным в обратной математике и приводит к еще более быстро растущей функции SSCG , которая затмевает ${\text{TREE}}(3)$. Финитарное функции применение теоремы приводит к существованию быстрорастущей TREE .

Заявление

Представленная здесь версия доказана Нэш-Вильямсом; Формулировка Краскала несколько более сильная. Все деревья, которые мы рассматриваем, конечны.

Учитывая дерево T с корнем и вершины v , w , назовите преемником v , w если уникальный путь от корня до w содержит v , и назовите w непосредственным преемником v, если дополнительно путь от v до w содержит никакой другой вершины.

Возьмем X множеством частично упорядоченным . Если T1 _T1 , T2 _— корневые деревья с вершинами, помеченными в , мы говорим, что инф _X - вложимо в T2 _, и пишем $T_{1}\leq T_{2}$ если существует инъективное отображение F вершин T ₁ в вершины T ₂ такое, что:

• Для всех вершин v из T ₁ метка v предшествует метке вершины. $F(v)$;
• Если w — любой преемник v в T ₁ , то $F(w)$ является преемником $F(v)$; и
• Если w1 _, v w2 _— любые два различных непосредственных наследника , то путь от $F(w_{1})$ к $F(w_{2})$ в Т ₂ содержится $F(v)$.

Теорема Краскала о дереве гласит:

Если X , хорошо квазиупорядочено то множество корневых деревьев с метками в X хорошо квазиупорядочено в соответствии с inf-вложимым порядком, определенным выше. (То есть, для любой бесконечной последовательности T ₁ , T ₂ , … корневых деревьев, помеченных в X , существует некоторая $i<j$ так что $T_{i}\leq T_{j}$.)

Работа Фридмана

Для счетного множества меток X теорема Крускала о дереве может быть выражена и доказана с использованием арифметики второго порядка . Однако, как и теорема Гудштейна или теорема Пэрис-Харрингтона , некоторые частные случаи и варианты теоремы могут быть выражены в подсистемах арифметики второго порядка, гораздо более слабых, чем подсистемы, где они могут быть доказаны. Впервые это заметил Харви Фридман в начале 1980-х годов, что стало первым успехом зарождавшейся тогда области обратной математики. В случае, когда деревья выше считаются непомеченными (то есть в случае, когда X имеет размер один), Фридман обнаружил, что результат недоказуем в ATR ₀ , таким образом давая первый пример предикативного результата с доказуемо непредикативным доказательством. Этот случай теоремы все еще доказывается П. ¹
₁ -CA ₀ , но добавив «условие разрыва» к определению порядка на деревьях, приведенному выше, он нашел естественный вариант теоремы, недоказуемой в этой системе. Намного позже теорема Робертсона-Сеймура дала еще одну теорему, недоказуемую П. ¹
₁ -СА ₀ .

Порядковый анализ подтверждает силу теоремы Крускала, при этом теоретико-доказательный ординал теоремы равен малому ординалу Веблена (иногда его путают с меньшим ординалом Аккермана ).

Слабая древовидная функция

Предположим, что $P(n)$ это заявление:

Существует некоторое m такое, что если T ₁ , ..., T _m — конечная последовательность немеченых корневых деревьев, где T _i имеет $i+n$ вершины, то $T_{i}\leq T_{j}$ для некоторых $i<j$.

Все заявления $P(n)$ верны как следствие теоремы Краскала и леммы Кенига . Для каждого n что арифметика Пеано может доказать, $P(n)$ верно, но арифметика Пеано не может доказать утверждение» $P(n)$ верно для всех n ". При этом длина доказательства кратчайшего $P(n)$ в арифметике Пеано растет феноменально быстро как функция n , намного быстрее, чем любая примитивно-рекурсивная функция или функция Аккермана . , например, Наименьшее m, для которого $P(n)$ Так же очень быстро растет с n .

Определять ${\text{tree}}(n)$, слабая древесная функция, как наибольшее m , так что мы имеем следующее:

Существует последовательность T ₁ , ..., T _m немаркированных корневых деревьев, где каждое имеет _Ti не более $i+n$ вершины, такие что $T_{i}\leq T_{j}$ не выполняется ни для какого $i<j\leq m$.

Известно, что ${\text{tree}}(1)=2$, ${\text{tree}}(2)=5$, ${\text{tree}}(3)\geq 844,424,930,131,960$ (около 844 трлн), ${\text{tree}}(4)\gg g_{64}$ (где $g_{64}$ — число Грэма ), и ${\text{TREE}}(3)$ (где аргумент указывает количество меток ; см. ниже ) больше, чем $\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7).$

Чтобы различать эти две функции, «TREE» (со всеми заглавными буквами) — это большая функция TREE, а «tree» (со всеми буквами в нижнем регистре) — это слабая функция дерева.

ДЕРЕВО функция

Последовательность корневых деревьев, помеченных набором из трех меток (синий <красный <зеленый). n - е дерево в последовательности содержит не более n вершин, и ни одно дерево не является inf-встраиваемым в какое-либо более позднее дерево последовательности. TREE(3) определяется как максимально возможная длина такой последовательности.

Включив ярлыки, Фридман определил гораздо более быстрорастущую функцию. В качестве натурального числа n возьмем ${\text{TREE}}(n)$^[а] быть наибольшим m, чтобы мы имели следующее:

Существует последовательность T ₁ , ..., T _m корневых деревьев, помеченных набором из n меток, где каждое T _i имеет не более i вершин, такая, что $T_{i}\leq T_{j}$ не выполняется ни для какого $i<j\leq m$.

Последовательность ДЕРЕВА начинается ${\text{TREE}}(1)=1$, ${\text{TREE}}(2)=3$, а потом вдруг, ${\text{TREE}}(3)$ взрывается до значения, которое настолько велико, что многие другие «большие» комбинаторные константы, такие как константа Фридмана $n(4)$, $n^{n(5)}(5)$, и число Грэма , ^[б] по сравнению с ними чрезвычайно малы. граница Нижняя для $n(4)$и, следовательно, крайне слабая нижняя оценка для ${\text{TREE}}(3)$, является $A^{A(187196)}(1)$. ^[с] Например, число Грэма намного меньше нижней границы. $A^{A(187196)}(1)$, что примерно $g_{3\uparrow ^{187196}3}$, где $g_{x}$ есть функция Грэма .

См. также

• Теорема Пэрис – Харрингтона
• Теорема Канамори – Макалуна
• Теорема Робертсона – Сеймура

Примечания

^{^ а} Первоначально Фридман обозначил эту функцию TR [ n ].

^{^ б} n ( k ) определяется как длина самой длинной возможной последовательности, которую можно составить с помощью k -буквенного алфавита, так что ни один блок букв x _i ,...,x _{2 i} не является подпоследовательностью любого последующего блока x _j , ...,x _{2 j} . $n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386$.

^{^ с} A ( x ), принимающая один аргумент, определяется как A ( x , x ), где A ( k , n ), принимающая два аргумента, представляет собой конкретную версию функции Аккермана , определенную как: A (1, n ) = 2 n , А ( к +1, 1) = А ( к , 1), А ( к +1, п +1) = А ( к , А ( к +1, п )).

Ссылки

Цитаты

Библиография

• Фридман, Харви М. (2002), Внутренние вложения конечных деревьев. Размышления об основах математики (Стэнфорд, Калифорния, 1998) , Lect. Журнал примечаний, вып. 15, Урбана, Иллинойс: доц. Символ. Логика, стр. 60–91, МР   1943303.
• Галье, Жан Х. (1991), «Что такого особенного в теореме Краскала и ординале Γ ₀ ? Обзор некоторых результатов теории доказательств» (PDF) , Ann. Чистое приложение. Логика , 53 (3): 199–260, doi : 10.1016/0168-0072(91)90022-E , MR   1129778
• Крускал, Дж. Б. (май 1960 г.), «Хороший квазиупорядочение, теорема о дереве и гипотеза Вассони» (PDF) , Transactions of the American Mathematical Society , 95 (2), American Mathematical Society: 210–225, doi : 10.2307 /1993287 , JSTOR   1993287 , MR   0111704
• Марконе, Альберто (2001), «Теория Wqo и bqo в подсистемах арифметики второго порядка» (PDF) , Reverse Mathematics , 21 : 303–330
• Нэш-Вильямс, К. Ст.Дж.А. (1963), «О хорошо квазиупорядоченных конечных деревьях», Proc. Кэмб. Фил. Соц. , 59 (4): 833–835, Bibcode : 1963PCPS...59..833N , doi : 10.1017/S0305004100003844 , MR   0153601 , S2CID   251095188
• Ратьен, Майкл; Вейерманн, Андреас (1993), «Теоретико-доказательные исследования теоремы Краскала» (PDF) , Annals of Pure and Applied Logic , 60 (1): 49–88, doi : 10.1016/0168-0072(93)90192-G , МР   1212407
• Симпсон, Стивен Г. (1985), «Недоказуемость некоторых комбинаторных свойств конечных деревьев», в Харрингтоне, Луизиана; Морли, М.; Щедров А.; и др. (ред.), Исследования Харви Фридмана по основам математики , Исследования по логике и основам математики, Северная Голландия, стр. 87–117.
• Смит, Рик Л. (1985), «Сила непротиворечивости некоторых конечных форм теорем Хигмана и Краскала», в Харрингтоне, Луизиана; Морли, М.; Щедров А.; и др. (ред.), Исследования Харви Фридмана по основам математики , Исследования по логике и основам математики, Северная Голландия, стр. 119–136.