Теорема Крускала о дереве - Kruskals tree theorem

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

В 2004 году результат был обобщен с деревьев на графы как Теорема Робертсона – Сеймура, результат, который также оказался важным в обратной математике и приводит к еще более быстрому росту Функция SSCG.

Заявление

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

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

Брать Икс быть частично заказанный набор. Если Т₁, Т₂ корневые деревья с вершинами, помеченными в Иксмы говорим, что Т₁ встраиваемый в Т₂ и писать Т₁ ≤ Т₂ если есть инъективное отображение F из вершин Т₁ в вершины Т₂ такой, что

• Для всех вершин v из Т₁, этикетка v предшествует ярлыку F(v),
• Если ш является преемником v в Т₁, тогда F(ш) является преемником F(v), и
• Если ш₁, ш₂ являются любыми двумя отдельными непосредственными преемниками v, то путь от F(ш₁) к F(ш₂) в Т₂ содержит F(v).

Теорема Крускала о дереве утверждает:

Если Икс является квазиупорядоченный, то набор корневых деревьев с метками в Икс хорошо квазиупорядочен относительно бесконечного вложенного порядка, определенного выше. (То есть для любой бесконечной последовательности Т₁, Т₂, … корневых деревьев, помеченных в Икс, существует некоторое я < j так что Т_я ≤ Т_j.)

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

Определять дерево(п), слабая функция дерева, как длина самой длинной последовательности деревьев с 1 меткой (т. е. Икс = {1}) такой, что:

• Дерево в позиции k в последовательности не более k + п вершины, для всех k.
• Никакое дерево не может быть гомеоморфно вложено в любое дерево, следующее за ним в последовательности.

Известно, что tree (1) = 1, tree (2) = 5 и tree (3) ≥ 844424930131960,^[1] но ДЕРЕВО (3) (см. ниже) больше, чем ${\displaystyle \mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{\mathrm {tree} ^{8}(7)}(7)}(7)}(7)}(7)}$

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

Для набора счетных этикеток ${\displaystyle X}$, Теорему Крускала о дереве можно выразить и доказать с помощью арифметика второго порядка. Однако, как и Теорема Гудштейна или Теорема Пэрис – Харрингтона, некоторые частные случаи и варианты теоремы могут быть выражены в подсистемах арифметики второго порядка, значительно более слабых, чем подсистемы, в которых они могут быть доказаны. Впервые это заметил Харви Фридман в начале 1980-х годов это был ранний успех зарождающейся тогда области обратной математики. В случае, когда деревья выше считаются немаркированными (то есть в случае, когда ${\displaystyle X}$ имеет порядок один), Фридман обнаружил, что результат недоказуем ATR₀,^[2] таким образом давая первый пример предикативный результат с доказуемым доказательством.^[3] Этот случай теоремы все еще доказуем в Π¹
₁-CA₀, но добавив "условие разрыва"^[4] к определению порядка на деревьях выше, он нашел естественный вариант теоремы, недоказуемой в этой системе.^[5][6] Много позже теорема Робертсона-Сеймура дала бы другую теорему, недоказуемую внутри Π¹
₁-CA₀.

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

ДЕРЕВО (3)

Предположим, что п(п) - это утверждение:

Существует некоторое м так что если Т₁,...,Т_м является конечной последовательностью немеченых корневых деревьев, где Т_k имеет п+k вершины, то Т_я ≤ Т_j для некоторых я < j.

Все заявления п(п) истинны как следствие теоремы Крускала и Лемма Кёнига. Для каждого п, Арифметика Пеано может доказать, что п(п) верно, но арифметика Пеано не может доказать утверждение "п(п) верно для всех п".^[7] Кроме того, длина кратчайшего доказательства п(п) в арифметике Пеано растет феноменально быстро как функция п, намного быстрее, чем любой примитивная рекурсивная функция или Функция Аккермана Например. В мере м для которого п(п) также очень быстро растет с п.

Включив ярлыки, Фридман определил гораздо более быстрорастущую функцию.^[8] Для положительного целого числа п, брать ДЕРЕВО(п)^[*] быть самым большим м так что мы имеем следующее:

Есть последовательность Т₁,...,Т_м корневых деревьев, помеченных из набора п этикетки, где каждый Т_я имеет самое большее я вершины, такие что Т_я  ≤  Т_j не выполняется ни для каких я < j  ≤ м.

В ДЕРЕВО последовательность начинается ДЕРЕВО(1) = 1, ДЕРЕВО(2) = 3, то вдруг ДЕРЕВО(3) взрывается до настолько большого значения, что многие другие «большие» комбинаторные константы, такие как Фридмана п(4),^[**] чрезвычайно малы по сравнению. На самом деле он намного больше, чем п^п(5)(5). Нижняя граница для п(4) и, следовательно, очень сильно слабая нижняя оценка для ДЕРЕВО(3), является А^А(187196)(1),^[9] куда А() - это версия Функция Аккермана: ${\displaystyle A(x)=2\uparrow ^{x-1}x}$. Число Грэма, например, примерно А⁶⁴(4), что намного меньше нижней оценки А^А(187196)(1). Можно показать, что скорость роста функции ДЕРЕВО не менее ${\displaystyle f_{\theta (\Omega ^{\omega }\omega )}}$ в быстрорастущая иерархия. А^А(187196)(1) приблизительно ${\displaystyle g_{3\uparrow ^{187196}3}}$, куда грамм_Икс является Функция Грэма.

Смотрите также

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

Примечания

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

^{^ **} п(k) определяется как длина самой длинной возможной последовательности, которая может быть построена с помощью k-буквенный алфавит такой, что не существует блока букв x_я,...,Икс_2i является подпоследовательностью любого более позднего блока x_j,...,Икс_2j.^[10] ${\displaystyle n(1)=3,n(2)=11,\,{\textrm {and}}\,n(3)>2\uparrow ^{7197}158386}$.

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

Цитаты

1. "Последовательность ДЕРЕВА". Googology Wiki | Фэндом. Получено 9 июля 2020.^{[нужен лучший источник ]}
2. Симпсон 1985, теорема 1.8
3. Фридман 2002, стр. 60
4. Симпсон 1985, определение 4.1
5. Симпсон 1985, теорема 5.14
6. Марконе 2001, стр. 8–9
7. Смит 1985, стр. 120
8. Фридман, Харви (28 марта 2006 г.). «273: Sigma01 / оптимальный / размер». Государственный университет Огайо Кафедра математики. Получено 8 августа 2017.
9. Фридман, Харви М. (1 июня 2000 г.). «Огромные целые числа в реальной жизни» (PDF). Государственный университет Огайо. Получено 8 августа 2017.
10. Фридман, Харви М. (8 октября 1998 г.). «Длинные конечные последовательности» (PDF). Департамент математики Университета штата Огайо. стр.5, 48 (Thm.6.8). Получено 8 августа 2017.

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

• Фридман, Харви М. (2002), Внутренние конечные вложения деревьев. Размышления об основах математики (Стэнфорд, Калифорния, 1998), Лект. Журнал заметок., 15, Урбана, Иллинойс: доц. Символ. Логика, стр. 60–91, МИСТЕР  1943303
• Галье, Жан Х. (1991), "Что такого особенного в теореме Крускала и ординале Γ?₀? Обзор некоторых результатов теории доказательств » (PDF), Анна. Pure Appl. Логика, 53 (3): 199–260, Дои:10.1016 / 0168-0072 (91) 90022-Е, МИСТЕР  1129778
• Крускал, Дж. Б. (Май 1960 г.), «Хороший квазиупорядоченность, теорема о дереве и гипотеза Вазсоньи» (PDF), Труды Американского математического общества, Американское математическое общество, 95 (2): 210–225, Дои:10.2307/1993287, JSTOR  1993287, МИСТЕР  0111704
• Марконе, Альберто (2001). «Теория WQO и BQO в подсистемах арифметики второго порядка» (PDF). Обратная математика. 21: 303–330.
• Нэш-Уильямс, К. Сент-Дж. А. (1963), "О хорошо квазиупорядоченных конечных деревьях", Proc. Camb. Фил. Soc., 59 (4): 833–835, Дои:10.1017 / S0305004100003844, МИСТЕР  0153601
• Ратиен, Майкл; Вейерманн, Андреас (1993). "Теоретико-доказательные исследования теоремы Крускала". Анналы чистой и прикладной логики. 60 (1): 49–88. Дои:10.1016 / 0168-0072 (93) 90192-г.
• Симпсон, Стивен Г. (1985), «Недоказуемость некоторых комбинаторных свойств конечных деревьев», в Harrington, L.A .; Morley, M .; Щедров, А .; и другие. (ред.), Исследования Харви Фридмана по основам математики, Исследования по логике и основам математики, Северная Голландия, стр. 87–117.
• Смит, Рик Л. (1985), «Сила совместимости некоторых конечных форм теорем Хигмана и Крускала», в Harrington, L.A .; Morley, M .; Щедров, А .; и другие. (ред.), Исследования Харви Фридмана по основам математики, Исследования по логике и основам математики, Северная Голландия, стр. 119–136.